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 l = (xmlListPtr)xmlMalloc(sizeof(xmlList));
192 if (l == NULL)
193 return (NULL);
194 /* Initialize the list to NULL */
195 memset(l, 0, sizeof(xmlList));
196
197 /* Add the sentinel */
198 l->sentinel = (xmlLinkPtr)xmlMalloc(sizeof(xmlLink));
199 if (l->sentinel == NULL) {
200 xmlFree(l);
201 return (NULL);
202 }
203 l->sentinel->next = l->sentinel;
204 l->sentinel->prev = l->sentinel;
205 l->sentinel->data = NULL;
206
207 /* If there is a link deallocator, use it */
208 if (deallocator != NULL)
209 l->linkDeallocator = deallocator;
210 /* If there is a link comparator, use it */
211 if (compare != NULL)
212 l->linkCompare = compare;
213 else /* Use our own */
214 l->linkCompare = xmlLinkCompare;
215 return l;
216 }
217
218 /**
219 * xmlListSearch:
220 * @l: a list
221 * @data: a search value
222 *
223 * Search the list for an existing value of @data
224 *
225 * Returns the value associated to @data or NULL in case of error
226 */
227 void *
xmlListSearch(xmlListPtr l,void * data)228 xmlListSearch(xmlListPtr l, void *data)
229 {
230 xmlLinkPtr lk;
231 if (l == NULL)
232 return(NULL);
233 lk = xmlListLinkSearch(l, data);
234 if (lk)
235 return (lk->data);
236 return NULL;
237 }
238
239 /**
240 * xmlListReverseSearch:
241 * @l: a list
242 * @data: a search value
243 *
244 * Search the list in reverse order for an existing value of @data
245 *
246 * Returns the value associated to @data or NULL in case of error
247 */
248 void *
xmlListReverseSearch(xmlListPtr l,void * data)249 xmlListReverseSearch(xmlListPtr l, void *data)
250 {
251 xmlLinkPtr lk;
252 if (l == NULL)
253 return(NULL);
254 lk = xmlListLinkReverseSearch(l, data);
255 if (lk)
256 return (lk->data);
257 return NULL;
258 }
259
260 /**
261 * xmlListInsert:
262 * @l: a list
263 * @data: the data
264 *
265 * Insert data in the ordered list at the beginning for this value
266 *
267 * Returns 0 in case of success, 1 in case of failure
268 */
269 int
xmlListInsert(xmlListPtr l,void * data)270 xmlListInsert(xmlListPtr l, void *data)
271 {
272 xmlLinkPtr lkPlace, lkNew;
273
274 if (l == NULL)
275 return(1);
276 lkPlace = xmlListLowerSearch(l, data);
277 /* Add the new link */
278 lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
279 if (lkNew == NULL)
280 return (1);
281 lkNew->data = data;
282 lkPlace = lkPlace->prev;
283 lkNew->next = lkPlace->next;
284 (lkPlace->next)->prev = lkNew;
285 lkPlace->next = lkNew;
286 lkNew->prev = lkPlace;
287 return 0;
288 }
289
290 /**
291 * xmlListAppend:
292 * @l: a list
293 * @data: the data
294 *
295 * Insert data in the ordered list at the end for this value
296 *
297 * Returns 0 in case of success, 1 in case of failure
298 */
xmlListAppend(xmlListPtr l,void * data)299 int xmlListAppend(xmlListPtr l, void *data)
300 {
301 xmlLinkPtr lkPlace, lkNew;
302
303 if (l == NULL)
304 return(1);
305 lkPlace = xmlListHigherSearch(l, data);
306 /* Add the new link */
307 lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
308 if (lkNew == NULL)
309 return (1);
310 lkNew->data = data;
311 lkNew->next = lkPlace->next;
312 (lkPlace->next)->prev = lkNew;
313 lkPlace->next = lkNew;
314 lkNew->prev = lkPlace;
315 return 0;
316 }
317
318 /**
319 * xmlListDelete:
320 * @l: a list
321 *
322 * Deletes the list and its associated data
323 */
xmlListDelete(xmlListPtr l)324 void xmlListDelete(xmlListPtr l)
325 {
326 if (l == NULL)
327 return;
328
329 xmlListClear(l);
330 xmlFree(l->sentinel);
331 xmlFree(l);
332 }
333
334 /**
335 * xmlListRemoveFirst:
336 * @l: a list
337 * @data: list data
338 *
339 * Remove the first instance associated to data in the list
340 *
341 * Returns 1 if a deallocation occurred, or 0 if not found
342 */
343 int
xmlListRemoveFirst(xmlListPtr l,void * data)344 xmlListRemoveFirst(xmlListPtr l, void *data)
345 {
346 xmlLinkPtr lk;
347
348 if (l == NULL)
349 return(0);
350 /*Find the first instance of this data */
351 lk = xmlListLinkSearch(l, data);
352 if (lk != NULL) {
353 xmlLinkDeallocator(l, lk);
354 return 1;
355 }
356 return 0;
357 }
358
359 /**
360 * xmlListRemoveLast:
361 * @l: a list
362 * @data: list data
363 *
364 * Remove the last instance associated to data in the list
365 *
366 * Returns 1 if a deallocation occurred, or 0 if not found
367 */
368 int
xmlListRemoveLast(xmlListPtr l,void * data)369 xmlListRemoveLast(xmlListPtr l, void *data)
370 {
371 xmlLinkPtr lk;
372
373 if (l == NULL)
374 return(0);
375 /*Find the last instance of this data */
376 lk = xmlListLinkReverseSearch(l, data);
377 if (lk != NULL) {
378 xmlLinkDeallocator(l, lk);
379 return 1;
380 }
381 return 0;
382 }
383
384 /**
385 * xmlListRemoveAll:
386 * @l: a list
387 * @data: list data
388 *
389 * Remove the all instance associated to data in the list
390 *
391 * Returns the number of deallocation, or 0 if not found
392 */
393 int
xmlListRemoveAll(xmlListPtr l,void * data)394 xmlListRemoveAll(xmlListPtr l, void *data)
395 {
396 int count=0;
397
398 if (l == NULL)
399 return(0);
400
401 while(xmlListRemoveFirst(l, data))
402 count++;
403 return count;
404 }
405
406 /**
407 * xmlListClear:
408 * @l: a list
409 *
410 * Remove the all data in the list
411 */
412 void
xmlListClear(xmlListPtr l)413 xmlListClear(xmlListPtr l)
414 {
415 xmlLinkPtr lk;
416
417 if (l == NULL)
418 return;
419 lk = l->sentinel->next;
420 while(lk != l->sentinel) {
421 xmlLinkPtr next = lk->next;
422
423 xmlLinkDeallocator(l, lk);
424 lk = next;
425 }
426 }
427
428 /**
429 * xmlListEmpty:
430 * @l: a list
431 *
432 * Is the list empty ?
433 *
434 * Returns 1 if the list is empty, 0 if not empty and -1 in case of error
435 */
436 int
xmlListEmpty(xmlListPtr l)437 xmlListEmpty(xmlListPtr l)
438 {
439 if (l == NULL)
440 return(-1);
441 return (l->sentinel->next == l->sentinel);
442 }
443
444 /**
445 * xmlListFront:
446 * @l: a list
447 *
448 * Get the first element in the list
449 *
450 * Returns the first element in the list, or NULL
451 */
452 xmlLinkPtr
xmlListFront(xmlListPtr l)453 xmlListFront(xmlListPtr l)
454 {
455 if (l == NULL)
456 return(NULL);
457 return (l->sentinel->next);
458 }
459
460 /**
461 * xmlListEnd:
462 * @l: a list
463 *
464 * Get the last element in the list
465 *
466 * Returns the last element in the list, or NULL
467 */
468 xmlLinkPtr
xmlListEnd(xmlListPtr l)469 xmlListEnd(xmlListPtr l)
470 {
471 if (l == NULL)
472 return(NULL);
473 return (l->sentinel->prev);
474 }
475
476 /**
477 * xmlListSize:
478 * @l: a list
479 *
480 * Get the number of elements in the list
481 *
482 * Returns the number of elements in the list or -1 in case of error
483 */
484 int
xmlListSize(xmlListPtr l)485 xmlListSize(xmlListPtr l)
486 {
487 xmlLinkPtr lk;
488 int count=0;
489
490 if (l == NULL)
491 return(-1);
492 /* TODO: keep a counter in xmlList instead */
493 for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next, count++);
494 return count;
495 }
496
497 /**
498 * xmlListPopFront:
499 * @l: a list
500 *
501 * Removes the first element in the list
502 */
503 void
xmlListPopFront(xmlListPtr l)504 xmlListPopFront(xmlListPtr l)
505 {
506 if(!xmlListEmpty(l))
507 xmlLinkDeallocator(l, l->sentinel->next);
508 }
509
510 /**
511 * xmlListPopBack:
512 * @l: a list
513 *
514 * Removes the last element in the list
515 */
516 void
xmlListPopBack(xmlListPtr l)517 xmlListPopBack(xmlListPtr l)
518 {
519 if(!xmlListEmpty(l))
520 xmlLinkDeallocator(l, l->sentinel->prev);
521 }
522
523 /**
524 * xmlListPushFront:
525 * @l: a list
526 * @data: new data
527 *
528 * add the new data at the beginning of the list
529 *
530 * Returns 1 if successful, 0 otherwise
531 */
532 int
xmlListPushFront(xmlListPtr l,void * data)533 xmlListPushFront(xmlListPtr l, void *data)
534 {
535 xmlLinkPtr lkPlace, lkNew;
536
537 if (l == NULL)
538 return(0);
539 lkPlace = l->sentinel;
540 /* Add the new link */
541 lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
542 if (lkNew == NULL)
543 return (0);
544 lkNew->data = data;
545 lkNew->next = lkPlace->next;
546 (lkPlace->next)->prev = lkNew;
547 lkPlace->next = lkNew;
548 lkNew->prev = lkPlace;
549 return 1;
550 }
551
552 /**
553 * xmlListPushBack:
554 * @l: a list
555 * @data: new data
556 *
557 * add the new data at the end of the list
558 *
559 * Returns 1 if successful, 0 otherwise
560 */
561 int
xmlListPushBack(xmlListPtr l,void * data)562 xmlListPushBack(xmlListPtr l, void *data)
563 {
564 xmlLinkPtr lkPlace, lkNew;
565
566 if (l == NULL)
567 return(0);
568 lkPlace = l->sentinel->prev;
569 /* Add the new link */
570 lkNew = (xmlLinkPtr)xmlMalloc(sizeof(xmlLink));
571 if (lkNew == NULL)
572 return (0);
573 lkNew->data = data;
574 lkNew->next = lkPlace->next;
575 (lkPlace->next)->prev = lkNew;
576 lkPlace->next = lkNew;
577 lkNew->prev = lkPlace;
578 return 1;
579 }
580
581 /**
582 * xmlLinkGetData:
583 * @lk: a link
584 *
585 * See Returns.
586 *
587 * Returns a pointer to the data referenced from this link
588 */
589 void *
xmlLinkGetData(xmlLinkPtr lk)590 xmlLinkGetData(xmlLinkPtr lk)
591 {
592 if (lk == NULL)
593 return(NULL);
594 return lk->data;
595 }
596
597 /**
598 * xmlListReverse:
599 * @l: a list
600 *
601 * Reverse the order of the elements in the list
602 */
603 void
xmlListReverse(xmlListPtr l)604 xmlListReverse(xmlListPtr l)
605 {
606 xmlLinkPtr lk;
607 xmlLinkPtr lkPrev;
608
609 if (l == NULL)
610 return;
611 lkPrev = l->sentinel;
612 for (lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
613 lkPrev->next = lkPrev->prev;
614 lkPrev->prev = lk;
615 lkPrev = lk;
616 }
617 /* Fix up the last node */
618 lkPrev->next = lkPrev->prev;
619 lkPrev->prev = lk;
620 }
621
622 /**
623 * xmlListSort:
624 * @l: a list
625 *
626 * Sort all the elements in the list
627 */
628 void
xmlListSort(xmlListPtr l)629 xmlListSort(xmlListPtr l)
630 {
631 xmlListPtr lTemp;
632
633 if (l == NULL)
634 return;
635 if(xmlListEmpty(l))
636 return;
637
638 /* I think that the real answer is to implement quicksort, the
639 * alternative is to implement some list copying procedure which
640 * would be based on a list copy followed by a clear followed by
641 * an insert. This is slow...
642 */
643
644 lTemp = xmlListDup(l);
645 if (lTemp == NULL)
646 return;
647 xmlListClear(l);
648 xmlListMerge(l, lTemp);
649 xmlListDelete(lTemp);
650 }
651
652 /**
653 * xmlListWalk:
654 * @l: a list
655 * @walker: a processing function
656 * @user: a user parameter passed to the walker function
657 *
658 * Walk all the element of the first from first to last and
659 * apply the walker function to it
660 */
661 void
xmlListWalk(xmlListPtr l,xmlListWalker walker,void * user)662 xmlListWalk(xmlListPtr l, xmlListWalker walker, void *user) {
663 xmlLinkPtr lk;
664
665 if ((l == NULL) || (walker == NULL))
666 return;
667 for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
668 if((walker(lk->data, user)) == 0)
669 break;
670 }
671 }
672
673 /**
674 * xmlListReverseWalk:
675 * @l: a list
676 * @walker: a processing function
677 * @user: a user parameter passed to the walker function
678 *
679 * Walk all the element of the list in reverse order and
680 * apply the walker function to it
681 */
682 void
xmlListReverseWalk(xmlListPtr l,xmlListWalker walker,void * user)683 xmlListReverseWalk(xmlListPtr l, xmlListWalker walker, void *user) {
684 xmlLinkPtr lk;
685
686 if ((l == NULL) || (walker == NULL))
687 return;
688 for(lk = l->sentinel->prev; lk != l->sentinel; lk = lk->prev) {
689 if((walker(lk->data, user)) == 0)
690 break;
691 }
692 }
693
694 /**
695 * xmlListMerge:
696 * @l1: the original list
697 * @l2: the new list
698 *
699 * include all the elements of the second list in the first one and
700 * clear the second list
701 */
702 void
xmlListMerge(xmlListPtr l1,xmlListPtr l2)703 xmlListMerge(xmlListPtr l1, xmlListPtr l2)
704 {
705 xmlListCopy(l1, l2);
706 xmlListClear(l2);
707 }
708
709 /**
710 * xmlListDup:
711 * @old: the list
712 *
713 * Duplicate the list
714 *
715 * Returns a new copy of the list or NULL in case of error
716 */
717 xmlListPtr
xmlListDup(xmlListPtr old)718 xmlListDup(xmlListPtr old)
719 {
720 xmlListPtr cur;
721
722 if (old == NULL)
723 return(NULL);
724 /* Hmmm, how to best deal with allocation issues when copying
725 * lists. If there is a de-allocator, should responsibility lie with
726 * the new list or the old list. Surely not both. I'll arbitrarily
727 * set it to be the old list for the time being whilst I work out
728 * the answer
729 */
730 cur = xmlListCreate(NULL, old->linkCompare);
731 if (cur == NULL)
732 return (NULL);
733 if (0 != xmlListCopy(cur, old))
734 return NULL;
735 return cur;
736 }
737
738 /**
739 * xmlListCopy:
740 * @cur: the new list
741 * @old: the old list
742 *
743 * Move all the element from the old list in the new list
744 *
745 * Returns 0 in case of success 1 in case of error
746 */
747 int
xmlListCopy(xmlListPtr cur,xmlListPtr old)748 xmlListCopy(xmlListPtr cur, xmlListPtr old)
749 {
750 /* Walk the old tree and insert the data into the new one */
751 xmlLinkPtr lk;
752
753 if ((old == NULL) || (cur == NULL))
754 return(1);
755 for(lk = old->sentinel->next; lk != old->sentinel; lk = lk->next) {
756 if (0 !=xmlListInsert(cur, lk->data)) {
757 xmlListDelete(cur);
758 return (1);
759 }
760 }
761 return (0);
762 }
763 /* xmlListUnique() */
764 /* xmlListSwap */
765