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 * MERCHANTIBILITY 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/list.h>
25#include <libxml/globals.h>
26
27/*
28 * Type definition are kept internal
29 */
30
31struct _xmlLink
32{
33 struct _xmlLink *next;
34 struct _xmlLink *prev;
35 void *data;
36};
37
38struct _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 */
58static void
59xmlLinkDeallocator(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 */
78static int
79xmlLinkCompare(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 */
97static xmlLinkPtr
98xmlListLowerSearch(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 */
117static xmlLinkPtr
118xmlListHigherSearch(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 */
137static xmlLinkPtr
138xmlListLinkSearch(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 */
162static xmlLinkPtr
163xmlListLinkReverseSearch(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 */
187xmlListPtr
188xmlListCreate(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 */
230void *
231xmlListSearch(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 */
251void *
252xmlListReverseSearch(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 */
272int
273xmlListInsert(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 */
305int 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 */
333void 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 */
352int
353xmlListRemoveFirst(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 */
377int
378xmlListRemoveLast(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 */
402int
403xmlListRemoveAll(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 */
421void
422xmlListClear(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 */
445int
446xmlListEmpty(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 */
461xmlLinkPtr
462xmlListFront(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 */
477xmlLinkPtr
478xmlListEnd(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 */
493int
494xmlListSize(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 */
512void
513xmlListPopFront(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 */
525void
526xmlListPopBack(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 */
541int
542xmlListPushFront(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 */
573int
574xmlListPushBack(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 */
603void *
604xmlLinkGetData(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 */
617void
618xmlListReverse(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 */
642void
643xmlListSort(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 */
675void
676xmlListWalk(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 */
696void
697xmlListReverseWalk(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 */
716void
717xmlListMerge(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 */
731xmlListPtr
732xmlListDup(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 */
760int
761xmlListCopy(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 */
778#define bottom_list
779#include "elfgcchack.h"
780