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 occured, 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 occured, 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, const 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, const 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