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