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