← Back to branch summary

~ubuntu-branches/ubuntu/utopic/glib2.0/utopic

« back to all changes in this revision

Viewing changes to glib/glist.c

Tags: upstream-2.12.12
Import upstream version 2.12.12

Show diffs side-by-side

added added

removed removed

Lines of Context:
glib/glist.c
 
1
/* GLIB - Library of useful routines for C programming
 
2
 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
 
3
 *
 
4
 * This library is free software; you can redistribute it and/or
 
5
 * modify it under the terms of the GNU Lesser General Public
 
6
 * License as published by the Free Software Foundation; either
 
7
 * version 2 of the License, or (at your option) any later version.
 
8
 *
 
9
 * This library is distributed in the hope that it will be useful,
 
10
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
11
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
12
 * Lesser General Public License for more details.
 
13
 *
 
14
 * You should have received a copy of the GNU Lesser General Public
 
15
 * License along with this library; if not, write to the
 
16
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 
17
 * Boston, MA 02111-1307, USA.
 
18
 */
 
19
 
 
20
/*
 
21
 * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
 
22
 * file for a list of people on the GLib Team.  See the ChangeLog
 
23
 * files for a list of changes.  These files are distributed with
 
24
 * GLib at ftp://ftp.gtk.org/pub/gtk/. 
 
25
 */
 
26
 
 
27
/* 
 
28
 * MT safe
 
29
 */
 
30
 
 
31
#include "config.h"
 
32
 
 
33
#include "glib.h"
 
34
#include "galias.h"
 
35
 
 
36
 
 
37
void g_list_push_allocator (gpointer dummy) { /* present for binary compat only */ }
 
38
void g_list_pop_allocator  (void)           { /* present for binary compat only */ }
 
39
 
 
40
#define _g_list_alloc()         g_slice_new (GList)
 
41
#define _g_list_alloc0()        g_slice_new0 (GList)
 
42
#define _g_list_free1(list)     g_slice_free (GList, list)
 
43
 
 
44
GList*
 
45
g_list_alloc (void)
 
46
{
 
47
  return _g_list_alloc0 ();
 
48
}
 
49
 
 
50
void
 
51
g_list_free (GList *list)
 
52
{
 
53
  g_slice_free_chain (GList, list, next);
 
54
}
 
55
 
 
56
void
 
57
g_list_free_1 (GList *list)
 
58
{
 
59
  _g_list_free1 (list);
 
60
}
 
61
 
 
62
GList*
 
63
g_list_append (GList    *list,
 
64
               gpointer  data)
 
65
{
 
66
  GList *new_list;
 
67
  GList *last;
 
68
  
 
69
  new_list = _g_list_alloc ();
 
70
  new_list->data = data;
 
71
  new_list->next = NULL;
 
72
  
 
73
  if (list)
 
74
    {
 
75
      last = g_list_last (list);
 
76
      /* g_assert (last != NULL); */
 
77
      last->next = new_list;
 
78
      new_list->prev = last;
 
79
 
 
80
      return list;
 
81
    }
 
82
  else
 
83
    {
 
84
      new_list->prev = NULL;
 
85
      return new_list;
 
86
    }
 
87
}
 
88
 
 
89
GList*
 
90
g_list_prepend (GList    *list,
 
91
                gpointer  data)
 
92
{
 
93
  GList *new_list;
 
94
  
 
95
  new_list = _g_list_alloc ();
 
96
  new_list->data = data;
 
97
  new_list->next = list;
 
98
  
 
99
  if (list)
 
100
    {
 
101
      new_list->prev = list->prev;
 
102
      if (list->prev)
 
103
        list->prev->next = new_list;
 
104
      list->prev = new_list;
 
105
    }
 
106
  else
 
107
    new_list->prev = NULL;
 
108
  
 
109
  return new_list;
 
110
}
 
111
 
 
112
GList*
 
113
g_list_insert (GList    *list,
 
114
               gpointer  data,
 
115
               gint      position)
 
116
{
 
117
  GList *new_list;
 
118
  GList *tmp_list;
 
119
  
 
120
  if (position < 0)
 
121
    return g_list_append (list, data);
 
122
  else if (position == 0)
 
123
    return g_list_prepend (list, data);
 
124
  
 
125
  tmp_list = g_list_nth (list, position);
 
126
  if (!tmp_list)
 
127
    return g_list_append (list, data);
 
128
  
 
129
  new_list = _g_list_alloc ();
 
130
  new_list->data = data;
 
131
  new_list->prev = tmp_list->prev;
 
132
  if (tmp_list->prev)
 
133
    tmp_list->prev->next = new_list;
 
134
  new_list->next = tmp_list;
 
135
  tmp_list->prev = new_list;
 
136
  
 
137
  if (tmp_list == list)
 
138
    return new_list;
 
139
  else
 
140
    return list;
 
141
}
 
142
 
 
143
GList*
 
144
g_list_insert_before (GList   *list,
 
145
                      GList   *sibling,
 
146
                      gpointer data)
 
147
{
 
148
  if (!list)
 
149
    {
 
150
      list = g_list_alloc ();
 
151
      list->data = data;
 
152
      g_return_val_if_fail (sibling == NULL, list);
 
153
      return list;
 
154
    }
 
155
  else if (sibling)
 
156
    {
 
157
      GList *node;
 
158
 
 
159
      node = _g_list_alloc ();
 
160
      node->data = data;
 
161
      node->prev = sibling->prev;
 
162
      node->next = sibling;
 
163
      sibling->prev = node;
 
164
      if (node->prev)
 
165
        {
 
166
          node->prev->next = node;
 
167
          return list;
 
168
        }
 
169
      else
 
170
        {
 
171
          g_return_val_if_fail (sibling == list, node);
 
172
          return node;
 
173
        }
 
174
    }
 
175
  else
 
176
    {
 
177
      GList *last;
 
178
 
 
179
      last = list;
 
180
      while (last->next)
 
181
        last = last->next;
 
182
 
 
183
      last->next = _g_list_alloc ();
 
184
      last->next->data = data;
 
185
      last->next->prev = last;
 
186
      last->next->next = NULL;
 
187
 
 
188
      return list;
 
189
    }
 
190
}
 
191
 
 
192
GList *
 
193
g_list_concat (GList *list1, GList *list2)
 
194
{
 
195
  GList *tmp_list;
 
196
  
 
197
  if (list2)
 
198
    {
 
199
      tmp_list = g_list_last (list1);
 
200
      if (tmp_list)
 
201
        tmp_list->next = list2;
 
202
      else
 
203
        list1 = list2;
 
204
      list2->prev = tmp_list;
 
205
    }
 
206
  
 
207
  return list1;
 
208
}
 
209
 
 
210
GList*
 
211
g_list_remove (GList         *list,
 
212
               gconstpointer  data)
 
213
{
 
214
  GList *tmp;
 
215
  
 
216
  tmp = list;
 
217
  while (tmp)
 
218
    {
 
219
      if (tmp->data != data)
 
220
        tmp = tmp->next;
 
221
      else
 
222
        {
 
223
          if (tmp->prev)
 
224
            tmp->prev->next = tmp->next;
 
225
          if (tmp->next)
 
226
            tmp->next->prev = tmp->prev;
 
227
          
 
228
          if (list == tmp)
 
229
            list = list->next;
 
230
          
 
231
          _g_list_free1 (tmp);
 
232
          
 
233
          break;
 
234
        }
 
235
    }
 
236
  return list;
 
237
}
 
238
 
 
239
GList*
 
240
g_list_remove_all (GList        *list,
 
241
                   gconstpointer data)
 
242
{
 
243
  GList *tmp = list;
 
244
 
 
245
  while (tmp)
 
246
    {
 
247
      if (tmp->data != data)
 
248
        tmp = tmp->next;
 
249
      else
 
250
        {
 
251
          GList *next = tmp->next;
 
252
 
 
253
          if (tmp->prev)
 
254
            tmp->prev->next = next;
 
255
          else
 
256
            list = next;
 
257
          if (next)
 
258
            next->prev = tmp->prev;
 
259
 
 
260
          _g_list_free1 (tmp);
 
261
          tmp = next;
 
262
        }
 
263
    }
 
264
  return list;
 
265
}
 
266
 
 
267
static inline GList*
 
268
_g_list_remove_link (GList *list,
 
269
                     GList *link)
 
270
{
 
271
  if (link)
 
272
    {
 
273
      if (link->prev)
 
274
        link->prev->next = link->next;
 
275
      if (link->next)
 
276
        link->next->prev = link->prev;
 
277
      
 
278
      if (link == list)
 
279
        list = list->next;
 
280
      
 
281
      link->next = NULL;
 
282
      link->prev = NULL;
 
283
    }
 
284
  
 
285
  return list;
 
286
}
 
287
 
 
288
GList*
 
289
g_list_remove_link (GList *list,
 
290
                    GList *link)
 
291
{
 
292
  return _g_list_remove_link (list, link);
 
293
}
 
294
 
 
295
GList*
 
296
g_list_delete_link (GList *list,
 
297
                    GList *link)
 
298
{
 
299
  list = _g_list_remove_link (list, link);
 
300
  _g_list_free1 (link);
 
301
 
 
302
  return list;
 
303
}
 
304
 
 
305
GList*
 
306
g_list_copy (GList *list)
 
307
{
 
308
  GList *new_list = NULL;
 
309
 
 
310
  if (list)
 
311
    {
 
312
      GList *last;
 
313
 
 
314
      new_list = _g_list_alloc ();
 
315
      new_list->data = list->data;
 
316
      new_list->prev = NULL;
 
317
      last = new_list;
 
318
      list = list->next;
 
319
      while (list)
 
320
        {
 
321
          last->next = _g_list_alloc ();
 
322
          last->next->prev = last;
 
323
          last = last->next;
 
324
          last->data = list->data;
 
325
          list = list->next;
 
326
        }
 
327
      last->next = NULL;
 
328
    }
 
329
 
 
330
  return new_list;
 
331
}
 
332
 
 
333
GList*
 
334
g_list_reverse (GList *list)
 
335
{
 
336
  GList *last;
 
337
  
 
338
  last = NULL;
 
339
  while (list)
 
340
    {
 
341
      last = list;
 
342
      list = last->next;
 
343
      last->next = last->prev;
 
344
      last->prev = list;
 
345
    }
 
346
  
 
347
  return last;
 
348
}
 
349
 
 
350
GList*
 
351
g_list_nth (GList *list,
 
352
            guint  n)
 
353
{
 
354
  while ((n-- > 0) && list)
 
355
    list = list->next;
 
356
  
 
357
  return list;
 
358
}
 
359
 
 
360
GList*
 
361
g_list_nth_prev (GList *list,
 
362
                 guint  n)
 
363
{
 
364
  while ((n-- > 0) && list)
 
365
    list = list->prev;
 
366
  
 
367
  return list;
 
368
}
 
369
 
 
370
gpointer
 
371
g_list_nth_data (GList     *list,
 
372
                 guint      n)
 
373
{
 
374
  while ((n-- > 0) && list)
 
375
    list = list->next;
 
376
  
 
377
  return list ? list->data : NULL;
 
378
}
 
379
 
 
380
GList*
 
381
g_list_find (GList         *list,
 
382
             gconstpointer  data)
 
383
{
 
384
  while (list)
 
385
    {
 
386
      if (list->data == data)
 
387
        break;
 
388
      list = list->next;
 
389
    }
 
390
  
 
391
  return list;
 
392
}
 
393
 
 
394
GList*
 
395
g_list_find_custom (GList         *list,
 
396
                    gconstpointer  data,
 
397
                    GCompareFunc   func)
 
398
{
 
399
  g_return_val_if_fail (func != NULL, list);
 
400
 
 
401
  while (list)
 
402
    {
 
403
      if (! func (list->data, data))
 
404
        return list;
 
405
      list = list->next;
 
406
    }
 
407
 
 
408
  return NULL;
 
409
}
 
410
 
 
411
 
 
412
gint
 
413
g_list_position (GList *list,
 
414
                 GList *link)
 
415
{
 
416
  gint i;
 
417
 
 
418
  i = 0;
 
419
  while (list)
 
420
    {
 
421
      if (list == link)
 
422
        return i;
 
423
      i++;
 
424
      list = list->next;
 
425
    }
 
426
 
 
427
  return -1;
 
428
}
 
429
 
 
430
gint
 
431
g_list_index (GList         *list,
 
432
              gconstpointer  data)
 
433
{
 
434
  gint i;
 
435
 
 
436
  i = 0;
 
437
  while (list)
 
438
    {
 
439
      if (list->data == data)
 
440
        return i;
 
441
      i++;
 
442
      list = list->next;
 
443
    }
 
444
 
 
445
  return -1;
 
446
}
 
447
 
 
448
GList*
 
449
g_list_last (GList *list)
 
450
{
 
451
  if (list)
 
452
    {
 
453
      while (list->next)
 
454
        list = list->next;
 
455
    }
 
456
  
 
457
  return list;
 
458
}
 
459
 
 
460
GList*
 
461
g_list_first (GList *list)
 
462
{
 
463
  if (list)
 
464
    {
 
465
      while (list->prev)
 
466
        list = list->prev;
 
467
    }
 
468
  
 
469
  return list;
 
470
}
 
471
 
 
472
guint
 
473
g_list_length (GList *list)
 
474
{
 
475
  guint length;
 
476
  
 
477
  length = 0;
 
478
  while (list)
 
479
    {
 
480
      length++;
 
481
      list = list->next;
 
482
    }
 
483
  
 
484
  return length;
 
485
}
 
486
 
 
487
void
 
488
g_list_foreach (GList    *list,
 
489
                GFunc     func,
 
490
                gpointer  user_data)
 
491
{
 
492
  while (list)
 
493
    {
 
494
      GList *next = list->next;
 
495
      (*func) (list->data, user_data);
 
496
      list = next;
 
497
    }
 
498
}
 
499
 
 
500
static GList*
 
501
g_list_insert_sorted_real (GList    *list,
 
502
                           gpointer  data,
 
503
                           GFunc     func,
 
504
                           gpointer  user_data)
 
505
{
 
506
  GList *tmp_list = list;
 
507
  GList *new_list;
 
508
  gint cmp;
 
509
 
 
510
  g_return_val_if_fail (func != NULL, list);
 
511
  
 
512
  if (!list) 
 
513
    {
 
514
      new_list = _g_list_alloc0 ();
 
515
      new_list->data = data;
 
516
      return new_list;
 
517
    }
 
518
  
 
519
  cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
 
520
 
 
521
  while ((tmp_list->next) && (cmp > 0))
 
522
    {
 
523
      tmp_list = tmp_list->next;
 
524
 
 
525
      cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
 
526
    }
 
527
 
 
528
  new_list = _g_list_alloc0 ();
 
529
  new_list->data = data;
 
530
 
 
531
  if ((!tmp_list->next) && (cmp > 0))
 
532
    {
 
533
      tmp_list->next = new_list;
 
534
      new_list->prev = tmp_list;
 
535
      return list;
 
536
    }
 
537
   
 
538
  if (tmp_list->prev)
 
539
    {
 
540
      tmp_list->prev->next = new_list;
 
541
      new_list->prev = tmp_list->prev;
 
542
    }
 
543
  new_list->next = tmp_list;
 
544
  tmp_list->prev = new_list;
 
545
 
 
546
  if (tmp_list == list)
 
547
    return new_list;
 
548
  else
 
549
    return list;
 
550
}
 
551
 
 
552
GList*
 
553
g_list_insert_sorted (GList        *list,
 
554
                      gpointer      data,
 
555
                      GCompareFunc  func)
 
556
{
 
557
  return g_list_insert_sorted_real (list, data, (GFunc) func, NULL);
 
558
}
 
559
 
 
560
GList*
 
561
g_list_insert_sorted_with_data (GList            *list,
 
562
                                gpointer          data,
 
563
                                GCompareDataFunc  func,
 
564
                                gpointer          user_data)
 
565
{
 
566
  return g_list_insert_sorted_real (list, data, (GFunc) func, user_data);
 
567
}
 
568
 
 
569
static GList *
 
570
g_list_sort_merge (GList     *l1, 
 
571
                   GList     *l2,
 
572
                   GFunc     compare_func,
 
573
                   gpointer  user_data)
 
574
{
 
575
  GList list, *l, *lprev;
 
576
  gint cmp;
 
577
 
 
578
  l = &list; 
 
579
  lprev = NULL;
 
580
 
 
581
  while (l1 && l2)
 
582
    {
 
583
      cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
 
584
 
 
585
      if (cmp <= 0)
 
586
        {
 
587
          l->next = l1;
 
588
          l1 = l1->next;
 
589
        } 
 
590
      else 
 
591
        {
 
592
          l->next = l2;
 
593
          l2 = l2->next;
 
594
        }
 
595
      l = l->next;
 
596
      l->prev = lprev; 
 
597
      lprev = l;
 
598
    }
 
599
  l->next = l1 ? l1 : l2;
 
600
  l->next->prev = l;
 
601
 
 
602
  return list.next;
 
603
}
 
604
 
 
605
static GList* 
 
606
g_list_sort_real (GList    *list,
 
607
                  GFunc     compare_func,
 
608
                  gpointer  user_data)
 
609
{
 
610
  GList *l1, *l2;
 
611
  
 
612
  if (!list) 
 
613
    return NULL;
 
614
  if (!list->next) 
 
615
    return list;
 
616
  
 
617
  l1 = list; 
 
618
  l2 = list->next;
 
619
 
 
620
  while ((l2 = l2->next) != NULL)
 
621
    {
 
622
      if ((l2 = l2->next) == NULL) 
 
623
        break;
 
624
      l1 = l1->next;
 
625
    }
 
626
  l2 = l1->next; 
 
627
  l1->next = NULL; 
 
628
 
 
629
  return g_list_sort_merge (g_list_sort_real (list, compare_func, user_data),
 
630
                            g_list_sort_real (l2, compare_func, user_data),
 
631
                            compare_func,
 
632
                            user_data);
 
633
}
 
634
 
 
635
GList *
 
636
g_list_sort (GList        *list,
 
637
             GCompareFunc  compare_func)
 
638
{
 
639
  return g_list_sort_real (list, (GFunc) compare_func, NULL);
 
640
                            
 
641
}
 
642
 
 
643
GList *
 
644
g_list_sort_with_data (GList            *list,
 
645
                       GCompareDataFunc  compare_func,
 
646
                       gpointer          user_data)
 
647
{
 
648
  return g_list_sort_real (list, (GFunc) compare_func, user_data);
 
649
}
 
650
 
 
651
#define __G_LIST_C__
 
652
#include "galiasdef.c"