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