1 /* libxml2 - Library for parsing XML documents
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 /*
11 * Copyright (C) 2000 Gary Pennington and Daniel Veillard.
12 *
13 * Permission to use, copy, modify, and distribute this software for any
14 * purpose with or without fee is hereby granted, provided that the above
15 * copyright notice and this permission notice appear in all copies.
16 *
17 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
18 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
19 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
20 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
21 *
22 * Author: Gary.Pennington@uk.sun.com
23 */
24
25 /*
26 * list.c: lists handling implementation
27 */
28
29 #define IN_LIBXML
30 #include "libxml.h"
31
32 #include <stdlib.h>
33 #include <string.h>
34 #include <libxml/xmlmemory.h>
35 #include <libxml/list.h>
36 #include <libxml/globals.h>
37
38 /*
39 * Type definition are kept internal
40 */
41
42 struct _xmlLink
43 {
44 struct _xmlLink *next;
45 struct _xmlLink *prev;
46 void *data;
47 };
48
49 struct _xmlList
50 {
51 xmlLinkPtr sentinel;
52 void (*linkDeallocator)(xmlLinkPtr );
53 int (*linkCompare)(const void *, const void*);
54 };
55
56 /************************************************************************
57 * *
58 * Interfaces *
59 * *
60 ************************************************************************/
61
62 /**
63 * xmlLinkDeallocator:
64 * @l: a list
65 * @lk: a link
66 *
67 * Unlink and deallocate @lk from list @l
68 */
69 static void
70 xmlLinkDeallocator(xmlListPtr l, xmlLinkPtr lk)
71 {
72 (lk->prev)->next = lk->next;
73 (lk->next)->prev = lk->prev;
74 if(l->linkDeallocator)
75 l->linkDeallocator(lk);
76 xmlFree(lk);
77 }
78
79 /**
80 * xmlLinkCompare:
81 * @data0: first data
82 * @data1: second data
83 *
84 * Compares two arbitrary data
85 *
86 * Returns -1, 0 or 1 depending on whether data1 is greater equal or smaller
87 * than data0
88 */
89 static int
90 xmlLinkCompare(const void *data0, const void *data1)
91 {
92 if (data0 < data1)
93 return (-1);
94 else if (data0 == data1)
95 return (0);
96 return (1);
97 }
98
99 /**
100 * xmlListLowerSearch:
101 * @l: a list
102 * @data: a data
103 *
104 * Search data in the ordered list walking from the beginning
105 *
106 * Returns the link containing the data or NULL
107 */
108 static xmlLinkPtr
109 xmlListLowerSearch(xmlListPtr l, void *data)
110 {
111 xmlLinkPtr lk;
112
113 if (l == NULL)
114 return(NULL);
115 for(lk = l->sentinel->next;lk != l->sentinel && l->linkCompare(lk->data, data) <0 ;lk = lk->next);
116 return lk;
117 }
118
119 /**
120 * xmlListHigherSearch:
121 * @l: a list
122 * @data: a data
123 *
124 * Search data in the ordered list walking backward from the end
125 *
126 * Returns the link containing the data or NULL
127 */
128 static xmlLinkPtr
129 xmlListHigherSearch(xmlListPtr l, void *data)
130 {
131 xmlLinkPtr lk;
132
133 if (l == NULL)
134 return(NULL);
135 for(lk = l->sentinel->prev;lk != l->sentinel && l->linkCompare(lk->data, data) >0 ;lk = lk->prev);
136 return lk;
137 }
138
139 /**
140 * xmlListSearch:
141 * @l: a list
142 * @data: a data
143 *
144 * Search data in the list
145 *
146 * Returns the link containing the data or NULL
147 */
148 static xmlLinkPtr
149 xmlListLinkSearch(xmlListPtr l, void *data)
150 {
151 xmlLinkPtr lk;
152 if (l == NULL)
153 return(NULL);
154 lk = xmlListLowerSearch(l, data);
155 if (lk == l->sentinel)
156 return NULL;
157 else {
158 if (l->linkCompare(lk->data, data) ==0)
159 return lk;
160 return NULL;
161 }
162 }
163
164 /**
165 * xmlListLinkReverseSearch:
166 * @l: a list
167 * @data: a data
168 *
169 * Search data in the list processing backward
170 *
171 * Returns the link containing the data or NULL
172 */
173 static xmlLinkPtr
174 xmlListLinkReverseSearch(xmlListPtr l, void *data)
175 {
176 xmlLinkPtr lk;
177 if (l == NULL)
178 return(NULL);
179 lk = xmlListHigherSearch(l, data);
180 if (lk == l->sentinel)
181 return NULL;
182 else {
183 if (l->linkCompare(lk->data, data) ==0)
184 return lk;
185 return NULL;
186 }
187 }
188
189 /**
190 * xmlListCreate:
191 * @deallocator: an optional deallocator function
192 * @compare: an optional comparison function
193 *
194 * Create a new list
195 *
196 * Returns the new list or NULL in case of error
197 */
198 xmlListPtr
199 xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)
200 {
201 xmlListPtr l;
202 if (NULL == (l = (xmlListPtr )xmlMalloc( sizeof(xmlList)))) {
203 xmlGenericError(xmlGenericErrorContext,
204 "Cannot initialize memory for list");
205 return (NULL);
206 }
207 /* Initialize the list to NULL */
208 memset(l, 0, sizeof(xmlList));
209
210 /* Add the sentinel */
211 if (NULL ==(l->sentinel = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
212 xmlGenericError(xmlGenericErrorContext,
213 "Cannot initialize memory for sentinel");
214 xmlFree(l);
215 return (NULL);
216 }
217 l->sentinel->next = l->sentinel;
218 l->sentinel->prev = l->sentinel;
219 l->sentinel->data = NULL;
220
221 /* If there is a link deallocator, use it */
222 if (deallocator != NULL)
223 l->linkDeallocator = deallocator;
224 /* If there is a link comparator, use it */
225 if (compare != NULL)
226 l->linkCompare = compare;
227 else /* Use our own */
228 l->linkCompare = xmlLinkCompare;
229 return l;
230 }
231
232 /**
233 * xmlListSearch:
234 * @l: a list
235 * @data: a search value
236 *
237 * Search the list for an existing value of @data
238 *
239 * Returns the value associated to @data or NULL in case of error
240 */
241 void *
242 xmlListSearch(xmlListPtr l, void *data)
243 {
244 xmlLinkPtr lk;
245 if (l == NULL)
246 return(NULL);
247 lk = xmlListLinkSearch(l, data);
248 if (lk)
249 return (lk->data);
250 return NULL;
251 }
252
253 /**
254 * xmlListReverseSearch:
255 * @l: a list
256 * @data: a search value
257 *
258 * Search the list in reverse order for an existing value of @data
259 *
260 * Returns the value associated to @data or NULL in case of error
261 */
262 void *
263 xmlListReverseSearch(xmlListPtr l, void *data)
264 {
265 xmlLinkPtr lk;
266 if (l == NULL)
267 return(NULL);
268 lk = xmlListLinkReverseSearch(l, data);
269 if (lk)
270 return (lk->data);
271 return NULL;
272 }
273
274 /**
275 * xmlListInsert:
276 * @l: a list
277 * @data: the data
278 *
279 * Insert data in the ordered list at the beginning for this value
280 *
281 * Returns 0 in case of success, 1 in case of failure
282 */
283 int
284 xmlListInsert(xmlListPtr l, void *data)
285 {
286 xmlLinkPtr lkPlace, lkNew;
287
288 if (l == NULL)
289 return(1);
290 lkPlace = xmlListLowerSearch(l, data);
291 /* Add the new link */
292 lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
293 if (lkNew == NULL) {
294 xmlGenericError(xmlGenericErrorContext,
295 "Cannot initialize memory for new link");
296 return (1);
297 }
298 lkNew->data = data;
299 lkPlace = lkPlace->prev;
300 lkNew->next = lkPlace->next;
301 (lkPlace->next)->prev = lkNew;
302 lkPlace->next = lkNew;
303 lkNew->prev = lkPlace;
304 return 0;
305 }
306
307 /**
308 * xmlListAppend:
309 * @l: a list
310 * @data: the data
311 *
312 * Insert data in the ordered list at the end for this value
313 *
314 * Returns 0 in case of success, 1 in case of failure
315 */
316 int xmlListAppend(xmlListPtr l, void *data)
317 {
318 xmlLinkPtr lkPlace, lkNew;
319
320 if (l == NULL)
321 return(1);
322 lkPlace = xmlListHigherSearch(l, data);
323 /* Add the new link */
324 lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
325 if (lkNew == NULL) {
326 xmlGenericError(xmlGenericErrorContext,
327 "Cannot initialize memory for new link");
328 return (1);
329 }
330 lkNew->data = data;
331 lkNew->next = lkPlace->next;
332 (lkPlace->next)->prev = lkNew;
333 lkPlace->next = lkNew;
334 lkNew->prev = lkPlace;
335 return 0;
336 }
337
338 /**
339 * xmlListDelete:
340 * @l: a list
341 *
342 * Deletes the list and its associated data
343 */
344 void xmlListDelete(xmlListPtr l)
345 {
346 if (l == NULL)
347 return;
348
349 xmlListClear(l);
350 xmlFree(l->sentinel);
351 xmlFree(l);
352 }
353
354 /**
355 * xmlListRemoveFirst:
356 * @l: a list
357 * @data: list data
358 *
359 * Remove the first instance associated to data in the list
360 *
361 * Returns 1 if a deallocation occurred, or 0 if not found
362 */
363 int
364 xmlListRemoveFirst(xmlListPtr l, void *data)
365 {
366 xmlLinkPtr lk;
367
368 if (l == NULL)
369 return(0);
370 /*Find the first instance of this data */
371 lk = xmlListLinkSearch(l, data);
372 if (lk != NULL) {
373 xmlLinkDeallocator(l, lk);
374 return 1;
375 }
376 return 0;
377 }
378
379 /**
380 * xmlListRemoveLast:
381 * @l: a list
382 * @data: list data
383 *
384 * Remove the last instance associated to data in the list
385 *
386 * Returns 1 if a deallocation occurred, or 0 if not found
387 */
388 int
389 xmlListRemoveLast(xmlListPtr l, void *data)
390 {
391 xmlLinkPtr lk;
392
393 if (l == NULL)
394 return(0);
395 /*Find the last instance of this data */
396 lk = xmlListLinkReverseSearch(l, data);
397 if (lk != NULL) {
398 xmlLinkDeallocator(l, lk);
399 return 1;
400 }
401 return 0;
402 }
403
404 /**
405 * xmlListRemoveAll:
406 * @l: a list
407 * @data: list data
408 *
409 * Remove the all instance associated to data in the list
410 *
411 * Returns the number of deallocation, or 0 if not found
412 */
413 int
414 xmlListRemoveAll(xmlListPtr l, void *data)
415 {
416 int count=0;
417
418 if (l == NULL)
419 return(0);
420
421 while(xmlListRemoveFirst(l, data))
422 count++;
423 return count;
424 }
425
426 /**
427 * xmlListClear:
428 * @l: a list
429 *
430 * Remove the all data in the list
431 */
432 void
433 xmlListClear(xmlListPtr l)
434 {
435 xmlLinkPtr lk;
436
437 if (l == NULL)
438 return;
439 lk = l->sentinel->next;
440 while(lk != l->sentinel) {
441 xmlLinkPtr next = lk->next;
442
443 xmlLinkDeallocator(l, lk);
444 lk = next;
445 }
446 }
447
448 /**
449 * xmlListEmpty:
450 * @l: a list
451 *
452 * Is the list empty ?
453 *
454 * Returns 1 if the list is empty, 0 if not empty and -1 in case of error
455 */
456 int
457 xmlListEmpty(xmlListPtr l)
458 {
459 if (l == NULL)
460 return(-1);
461 return (l->sentinel->next == l->sentinel);
462 }
463
464 /**
465 * xmlListFront:
466 * @l: a list
467 *
468 * Get the first element in the list
469 *
470 * Returns the first element in the list, or NULL
471 */
472 xmlLinkPtr
473 xmlListFront(xmlListPtr l)
474 {
475 if (l == NULL)
476 return(NULL);
477 return (l->sentinel->next);
478 }
479
480 /**
481 * xmlListEnd:
482 * @l: a list
483 *
484 * Get the last element in the list
485 *
486 * Returns the last element in the list, or NULL
487 */
488 xmlLinkPtr
489 xmlListEnd(xmlListPtr l)
490 {
491 if (l == NULL)
492 return(NULL);
493 return (l->sentinel->prev);
494 }
495
496 /**
497 * xmlListSize:
498 * @l: a list
499 *
500 * Get the number of elements in the list
501 *
502 * Returns the number of elements in the list or -1 in case of error
503 */
504 int
505 xmlListSize(xmlListPtr l)
506 {
507 xmlLinkPtr lk;
508 int count=0;
509
510 if (l == NULL)
511 return(-1);
512 /* TODO: keep a counter in xmlList instead */
513 for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next, count++);
514 return count;
515 }
516
517 /**
518 * xmlListPopFront:
519 * @l: a list
520 *
521 * Removes the first element in the list
522 */
523 void
524 xmlListPopFront(xmlListPtr l)
525 {
526 if(!xmlListEmpty(l))
527 xmlLinkDeallocator(l, l->sentinel->next);
528 }
529
530 /**
531 * xmlListPopBack:
532 * @l: a list
533 *
534 * Removes the last element in the list
535 */
536 void
537 xmlListPopBack(xmlListPtr l)
538 {
539 if(!xmlListEmpty(l))
540 xmlLinkDeallocator(l, l->sentinel->prev);
541 }
542
543 /**
544 * xmlListPushFront:
545 * @l: a list
546 * @data: new data
547 *
548 * add the new data at the beginning of the list
549 *
550 * Returns 1 if successful, 0 otherwise
551 */
552 int
553 xmlListPushFront(xmlListPtr l, void *data)
554 {
555 xmlLinkPtr lkPlace, lkNew;
556
557 if (l == NULL)
558 return(0);
559 lkPlace = l->sentinel;
560 /* Add the new link */
561 lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
562 if (lkNew == NULL) {
563 xmlGenericError(xmlGenericErrorContext,
564 "Cannot initialize memory for new link");
565 return (0);
566 }
567 lkNew->data = data;
568 lkNew->next = lkPlace->next;
569 (lkPlace->next)->prev = lkNew;
570 lkPlace->next = lkNew;
571 lkNew->prev = lkPlace;
572 return 1;
573 }
574
575 /**
576 * xmlListPushBack:
577 * @l: a list
578 * @data: new data
579 *
580 * add the new data at the end of the list
581 *
582 * Returns 1 if successful, 0 otherwise
583 */
584 int
585 xmlListPushBack(xmlListPtr l, void *data)
586 {
587 xmlLinkPtr lkPlace, lkNew;
588
589 if (l == NULL)
590 return(0);
591 lkPlace = l->sentinel->prev;
592 /* Add the new link */
593 if (NULL ==(lkNew = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
594 xmlGenericError(xmlGenericErrorContext,
595 "Cannot initialize memory for new link");
596 return (0);
597 }
598 lkNew->data = data;
599 lkNew->next = lkPlace->next;
600 (lkPlace->next)->prev = lkNew;
601 lkPlace->next = lkNew;
602 lkNew->prev = lkPlace;
603 return 1;
604 }
605
606 /**
607 * xmlLinkGetData:
608 * @lk: a link
609 *
610 * See Returns.
611 *
612 * Returns a pointer to the data referenced from this link
613 */
614 void *
615 xmlLinkGetData(xmlLinkPtr lk)
616 {
617 if (lk == NULL)
618 return(NULL);
619 return lk->data;
620 }
621
622 /**
623 * xmlListReverse:
624 * @l: a list
625 *
626 * Reverse the order of the elements in the list
627 */
628 void
629 xmlListReverse(xmlListPtr l)
630 {
631 xmlLinkPtr lk;
632 xmlLinkPtr lkPrev;
633
634 if (l == NULL)
635 return;
636 lkPrev = l->sentinel;
637 for (lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
638 lkPrev->next = lkPrev->prev;
639 lkPrev->prev = lk;
640 lkPrev = lk;
641 }
642 /* Fix up the last node */
643 lkPrev->next = lkPrev->prev;
644 lkPrev->prev = lk;
645 }
646
647 /**
648 * xmlListSort:
649 * @l: a list
650 *
651 * Sort all the elements in the list
652 */
653 void
654 xmlListSort(xmlListPtr l)
655 {
656 xmlListPtr lTemp;
657
658 if (l == NULL)
659 return;
660 if(xmlListEmpty(l))
661 return;
662
663 /* I think that the real answer is to implement quicksort, the
664 * alternative is to implement some list copying procedure which
665 * would be based on a list copy followed by a clear followed by
666 * an insert. This is slow...
667 */
668
669 if (NULL ==(lTemp = xmlListDup(l)))
670 return;
671 xmlListClear(l);
672 xmlListMerge(l, lTemp);
673 xmlListDelete(lTemp);
674 return;
675 }
676
677 /**
678 * xmlListWalk:
679 * @l: a list
680 * @walker: a processing function
681 * @user: a user parameter passed to the walker function
682 *
683 * Walk all the element of the first from first to last and
684 * apply the walker function to it
685 */
686 void
687 xmlListWalk(xmlListPtr l, xmlListWalker walker, void *user) {
688 xmlLinkPtr lk;
689
690 if ((l == NULL) || (walker == NULL))
691 return;
692 for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
693 if((walker(lk->data, user)) == 0)
694 break;
695 }
696 }
697
698 /**
699 * xmlListReverseWalk:
700 * @l: a list
701 * @walker: a processing function
702 * @user: a user parameter passed to the walker function
703 *
704 * Walk all the element of the list in reverse order and
705 * apply the walker function to it
706 */
707 void
708 xmlListReverseWalk(xmlListPtr l, xmlListWalker walker, void *user) {
709 xmlLinkPtr lk;
710
711 if ((l == NULL) || (walker == NULL))
712 return;
713 for(lk = l->sentinel->prev; lk != l->sentinel; lk = lk->prev) {
714 if((walker(lk->data, user)) == 0)
715 break;
716 }
717 }
718
719 /**
720 * xmlListMerge:
721 * @l1: the original list
722 * @l2: the new list
723 *
724 * include all the elements of the second list in the first one and
725 * clear the second list
726 */
727 void
728 xmlListMerge(xmlListPtr l1, xmlListPtr l2)
729 {
730 xmlListCopy(l1, l2);
731 xmlListClear(l2);
732 }
733
734 /**
735 * xmlListDup:
736 * @old: the list
737 *
738 * Duplicate the list
739 *
740 * Returns a new copy of the list or NULL in case of error
741 */
742 xmlListPtr
743 xmlListDup(const xmlListPtr old)
744 {
745 xmlListPtr cur;
746
747 if (old == NULL)
748 return(NULL);
749 /* Hmmm, how to best deal with allocation issues when copying
750 * lists. If there is a de-allocator, should responsibility lie with
751 * the new list or the old list. Surely not both. I'll arbitrarily
752 * set it to be the old list for the time being whilst I work out
753 * the answer
754 */
755 if (NULL ==(cur = xmlListCreate(NULL, old->linkCompare)))
756 return (NULL);
757 if (0 != xmlListCopy(cur, old))
758 return NULL;
759 return cur;
760 }
761
762 /**
763 * xmlListCopy:
764 * @cur: the new list
765 * @old: the old list
766 *
767 * Move all the element from the old list in the new list
768 *
769 * Returns 0 in case of success 1 in case of error
770 */
771 int
772 xmlListCopy(xmlListPtr cur, const xmlListPtr old)
773 {
774 /* Walk the old tree and insert the data into the new one */
775 xmlLinkPtr lk;
776
777 if ((old == NULL) || (cur == NULL))
778 return(1);
779 for(lk = old->sentinel->next; lk != old->sentinel; lk = lk->next) {
780 if (0 !=xmlListInsert(cur, lk->data)) {
781 xmlListDelete(cur);
782 return (1);
783 }
784 }
785 return (0);
786 }
787 /* xmlListUnique() */
788 /* xmlListSwap */
789 #define bottom_list
790 #include "elfgcchack.h"