2 * list.c: lists handling implementation
4 * Copyright (C) 2000 Gary Pennington and Daniel Veillard.
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.
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.
15 * Author: Gary.Pennington@uk.sun.com
23 #include <libxml/xmlmemory.h>
24 #include <libxml/list.h>
25 #include <libxml/globals.h>
28 * Type definition are kept internal
33 struct _xmlLink *next;
34 struct _xmlLink *prev;
41 void (*linkDeallocator)(xmlLinkPtr );
42 int (*linkCompare)(const void *, const void*);
45 /************************************************************************
49 ************************************************************************/
56 * Unlink and deallocate @lk from list @l
59 xmlLinkDeallocator(xmlListPtr l, xmlLinkPtr lk)
61 (lk->prev)->next = lk->next;
62 (lk->next)->prev = lk->prev;
63 if(l->linkDeallocator)
64 l->linkDeallocator(lk);
73 * Compares two arbitrary data
75 * Returns -1, 0 or 1 depending on whether data1 is greater equal or smaller
79 xmlLinkCompare(const void *data0, const void *data1)
83 else if (data0 == data1)
93 * Search data in the ordered list walking from the beginning
95 * Returns the link containing the data or NULL
98 xmlListLowerSearch(xmlListPtr l, void *data)
104 for(lk = l->sentinel->next;lk != l->sentinel && l->linkCompare(lk->data, data) <0 ;lk = lk->next);
109 * xmlListHigherSearch:
113 * Search data in the ordered list walking backward from the end
115 * Returns the link containing the data or NULL
118 xmlListHigherSearch(xmlListPtr l, void *data)
124 for(lk = l->sentinel->prev;lk != l->sentinel && l->linkCompare(lk->data, data) >0 ;lk = lk->prev);
133 * Search data in the list
135 * Returns the link containing the data or NULL
138 xmlListLinkSearch(xmlListPtr l, void *data)
143 lk = xmlListLowerSearch(l, data);
144 if (lk == l->sentinel)
147 if (l->linkCompare(lk->data, data) ==0)
154 * xmlListLinkReverseSearch:
158 * Search data in the list processing backward
160 * Returns the link containing the data or NULL
163 xmlListLinkReverseSearch(xmlListPtr l, void *data)
168 lk = xmlListHigherSearch(l, data);
169 if (lk == l->sentinel)
172 if (l->linkCompare(lk->data, data) ==0)
180 * @deallocator: an optional deallocator function
181 * @compare: an optional comparison function
185 * Returns the new list or NULL in case of error
188 xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)
191 if (NULL == (l = (xmlListPtr )xmlMalloc( sizeof(xmlList)))) {
192 xmlGenericError(xmlGenericErrorContext,
193 "Cannot initialize memory for list");
196 /* Initialize the list to NULL */
197 memset(l, 0, sizeof(xmlList));
199 /* Add the sentinel */
200 if (NULL ==(l->sentinel = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
201 xmlGenericError(xmlGenericErrorContext,
202 "Cannot initialize memory for sentinel");
206 l->sentinel->next = l->sentinel;
207 l->sentinel->prev = l->sentinel;
208 l->sentinel->data = NULL;
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 */
215 l->linkCompare = compare;
216 else /* Use our own */
217 l->linkCompare = xmlLinkCompare;
224 * @data: a search value
226 * Search the list for an existing value of @data
228 * Returns the value associated to @data or NULL in case of error
231 xmlListSearch(xmlListPtr l, void *data)
236 lk = xmlListLinkSearch(l, data);
243 * xmlListReverseSearch:
245 * @data: a search value
247 * Search the list in reverse order for an existing value of @data
249 * Returns the value associated to @data or NULL in case of error
252 xmlListReverseSearch(xmlListPtr l, void *data)
257 lk = xmlListLinkReverseSearch(l, data);
268 * Insert data in the ordered list at the beginning for this value
270 * Returns 0 in case of success, 1 in case of failure
273 xmlListInsert(xmlListPtr l, void *data)
275 xmlLinkPtr lkPlace, lkNew;
279 lkPlace = xmlListLowerSearch(l, data);
280 /* Add the new link */
281 lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
283 xmlGenericError(xmlGenericErrorContext,
284 "Cannot initialize memory for new link");
288 lkPlace = lkPlace->prev;
289 lkNew->next = lkPlace->next;
290 (lkPlace->next)->prev = lkNew;
291 lkPlace->next = lkNew;
292 lkNew->prev = lkPlace;
301 * Insert data in the ordered list at the end for this value
303 * Returns 0 in case of success, 1 in case of failure
305 int xmlListAppend(xmlListPtr l, void *data)
307 xmlLinkPtr lkPlace, lkNew;
311 lkPlace = xmlListHigherSearch(l, data);
312 /* Add the new link */
313 lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
315 xmlGenericError(xmlGenericErrorContext,
316 "Cannot initialize memory for new link");
320 lkNew->next = lkPlace->next;
321 (lkPlace->next)->prev = lkNew;
322 lkPlace->next = lkNew;
323 lkNew->prev = lkPlace;
331 * Deletes the list and its associated data
333 void xmlListDelete(xmlListPtr l)
339 xmlFree(l->sentinel);
344 * xmlListRemoveFirst:
348 * Remove the first instance associated to data in the list
350 * Returns 1 if a deallocation occured, or 0 if not found
353 xmlListRemoveFirst(xmlListPtr l, void *data)
359 /*Find the first instance of this data */
360 lk = xmlListLinkSearch(l, data);
362 xmlLinkDeallocator(l, lk);
373 * Remove the last instance associated to data in the list
375 * Returns 1 if a deallocation occured, or 0 if not found
378 xmlListRemoveLast(xmlListPtr l, void *data)
384 /*Find the last instance of this data */
385 lk = xmlListLinkReverseSearch(l, data);
387 xmlLinkDeallocator(l, lk);
398 * Remove the all instance associated to data in the list
400 * Returns the number of deallocation, or 0 if not found
403 xmlListRemoveAll(xmlListPtr l, void *data)
410 while(xmlListRemoveFirst(l, data))
419 * Remove the all data in the list
422 xmlListClear(xmlListPtr l)
428 lk = l->sentinel->next;
429 while(lk != l->sentinel) {
430 xmlLinkPtr next = lk->next;
432 xmlLinkDeallocator(l, lk);
441 * Is the list empty ?
443 * Returns 1 if the list is empty, 0 if not empty and -1 in case of error
446 xmlListEmpty(xmlListPtr l)
450 return (l->sentinel->next == l->sentinel);
457 * Get the first element in the list
459 * Returns the first element in the list, or NULL
462 xmlListFront(xmlListPtr l)
466 return (l->sentinel->next);
473 * Get the last element in the list
475 * Returns the last element in the list, or NULL
478 xmlListEnd(xmlListPtr l)
482 return (l->sentinel->prev);
489 * Get the number of elements in the list
491 * Returns the number of elements in the list or -1 in case of error
494 xmlListSize(xmlListPtr l)
501 /* TODO: keep a counter in xmlList instead */
502 for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next, count++);
510 * Removes the first element in the list
513 xmlListPopFront(xmlListPtr l)
516 xmlLinkDeallocator(l, l->sentinel->next);
523 * Removes the last element in the list
526 xmlListPopBack(xmlListPtr l)
529 xmlLinkDeallocator(l, l->sentinel->prev);
537 * add the new data at the beginning of the list
539 * Returns 1 if successful, 0 otherwise
542 xmlListPushFront(xmlListPtr l, void *data)
544 xmlLinkPtr lkPlace, lkNew;
548 lkPlace = l->sentinel;
549 /* Add the new link */
550 lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
552 xmlGenericError(xmlGenericErrorContext,
553 "Cannot initialize memory for new link");
557 lkNew->next = lkPlace->next;
558 (lkPlace->next)->prev = lkNew;
559 lkPlace->next = lkNew;
560 lkNew->prev = lkPlace;
569 * add the new data at the end of the list
571 * Returns 1 if successful, 0 otherwise
574 xmlListPushBack(xmlListPtr l, void *data)
576 xmlLinkPtr lkPlace, lkNew;
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");
588 lkNew->next = lkPlace->next;
589 (lkPlace->next)->prev = lkNew;
590 lkPlace->next = lkNew;
591 lkNew->prev = lkPlace;
601 * Returns a pointer to the data referenced from this link
604 xmlLinkGetData(xmlLinkPtr lk)
615 * Reverse the order of the elements in the list
618 xmlListReverse(xmlListPtr l)
625 lkPrev = l->sentinel;
626 for (lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
627 lkPrev->next = lkPrev->prev;
631 /* Fix up the last node */
632 lkPrev->next = lkPrev->prev;
640 * Sort all the elements in the list
643 xmlListSort(xmlListPtr l)
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...
658 if (NULL ==(lTemp = xmlListDup(l)))
661 xmlListMerge(l, lTemp);
662 xmlListDelete(lTemp);
669 * @walker: a processing function
670 * @user: a user parameter passed to the walker function
672 * Walk all the element of the first from first to last and
673 * apply the walker function to it
676 xmlListWalk(xmlListPtr l, xmlListWalker walker, const void *user) {
679 if ((l == NULL) || (walker == NULL))
681 for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
682 if((walker(lk->data, user)) == 0)
688 * xmlListReverseWalk:
690 * @walker: a processing function
691 * @user: a user parameter passed to the walker function
693 * Walk all the element of the list in reverse order and
694 * apply the walker function to it
697 xmlListReverseWalk(xmlListPtr l, xmlListWalker walker, const void *user) {
700 if ((l == NULL) || (walker == NULL))
702 for(lk = l->sentinel->prev; lk != l->sentinel; lk = lk->prev) {
703 if((walker(lk->data, user)) == 0)
710 * @l1: the original list
713 * include all the elements of the second list in the first one and
714 * clear the second list
717 xmlListMerge(xmlListPtr l1, xmlListPtr l2)
729 * Returns a new copy of the list or NULL in case of error
732 xmlListDup(const xmlListPtr old)
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
744 if (NULL ==(cur = xmlListCreate(NULL, old->linkCompare)))
746 if (0 != xmlListCopy(cur, old))
756 * Move all the element from the old list in the new list
758 * Returns 0 in case of success 1 in case of error
761 xmlListCopy(xmlListPtr cur, const xmlListPtr old)
763 /* Walk the old tree and insert the data into the new one */
766 if ((old == NULL) || (cur == NULL))
768 for(lk = old->sentinel->next; lk != old->sentinel; lk = lk->next) {
769 if (0 !=xmlListInsert(cur, lk->data)) {
776 /* xmlListUnique() */
779 #include "elfgcchack.h"