/src/libxml2/list.c

Source (jump to first uncovered line)
/*
 * list.c: lists handling implementation
 *
 * Copyright (C) 2000 Gary Pennington and Daniel Veillard.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
 *
 * Author: Gary Pennington
 */

#define IN_LIBXML
#include "libxml.h"

#include <stdlib.h>
#include <string.h>
#include <libxml/xmlmemory.h>
#include <libxml/xmlerror.h>
#include <libxml/list.h>

/*
 * Type definition are kept internal
 */

struct _xmlLink
{
    struct _xmlLink *next;
    struct _xmlLink *prev;
    void *data;
};

struct _xmlList
{
    xmlLinkPtr sentinel;
    void (*linkDeallocator)(xmlLinkPtr );
    int (*linkCompare)(const void *, const void*);
};

/************************************************************************
 *                                    *
 *                Interfaces                *
 *                                    *
 ************************************************************************/

/**
 * Unlink and deallocate `lk` from list `l`
 *
 * @param l  a list
 * @param lk  a link
 */
static void
xmlLinkDeallocator(xmlListPtr l, xmlLinkPtr lk)
{
    (lk->prev)->next = lk->next;
    (lk->next)->prev = lk->prev;
    if(l->linkDeallocator)
        l->linkDeallocator(lk);
    xmlFree(lk);
}

/**
 * Compares two arbitrary data
 *
 * @param data0  first data
 * @param data1  second data
 * @returns -1, 0 or 1 depending on whether data1 is greater equal or smaller
 *          than data0
 */
static int
xmlLinkCompare(const void *data0, const void *data1)
{
    if (data0 < data1)
        return (-1);
    else if (data0 == data1)
  return (0);
    return (1);
}

/**
 * Search data in the ordered list walking from the beginning
 *
 * @param l  a list
 * @param data  a data
 * @returns the link containing the data or NULL
 */
static xmlLinkPtr
xmlListLowerSearch(xmlListPtr l, void *data)
{
    xmlLinkPtr lk;

    if (l == NULL)
        return(NULL);
    for(lk = l->sentinel->next;lk != l->sentinel && l->linkCompare(lk->data, data) <0 ;lk = lk->next);
    return lk;
}

/**
 * Search data in the ordered list walking backward from the end
 *
 * @param l  a list
 * @param data  a data
 * @returns the link containing the data or NULL
 */
static xmlLinkPtr
xmlListHigherSearch(xmlListPtr l, void *data)
{
    xmlLinkPtr lk;

    if (l == NULL)
        return(NULL);
    for(lk = l->sentinel->prev;lk != l->sentinel && l->linkCompare(lk->data, data) >0 ;lk = lk->prev);
    return lk;
}

/**
 * Search data in the list
 *
 * @param l  a list
 * @param data  a data
 * @returns the link containing the data or NULL
 */
static xmlLinkPtr
xmlListLinkSearch(xmlListPtr l, void *data)
{
    xmlLinkPtr lk;
    if (l == NULL)
        return(NULL);
    lk = xmlListLowerSearch(l, data);
    if (lk == l->sentinel)
        return NULL;
    else {
        if (l->linkCompare(lk->data, data) ==0)
            return lk;
        return NULL;
    }
}

/**
 * Search data in the list processing backward
 *
 * @param l  a list
 * @param data  a data
 * @returns the link containing the data or NULL
 */
static xmlLinkPtr
xmlListLinkReverseSearch(xmlListPtr l, void *data)
{
    xmlLinkPtr lk;
    if (l == NULL)
        return(NULL);
    lk = xmlListHigherSearch(l, data);
    if (lk == l->sentinel)
        return NULL;
    else {
        if (l->linkCompare(lk->data, data) ==0)
            return lk;
        return NULL;
    }
}

/**
 * Create a new list
 *
 * @param deallocator  an optional deallocator function
 * @param compare  an optional comparison function
 * @returns the new list or NULL in case of error
 */
xmlList *
xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)
{
    xmlListPtr l;
    l = (xmlListPtr)xmlMalloc(sizeof(xmlList));
    if (l == NULL)
        return (NULL);
    /* Initialize the list to NULL */
    memset(l, 0, sizeof(xmlList));

    /* Add the sentinel */
    l->sentinel = (xmlLinkPtr)xmlMalloc(sizeof(xmlLink));
    if (l->sentinel == NULL) {
  xmlFree(l);
        return (NULL);
    }
    l->sentinel->next = l->sentinel;
    l->sentinel->prev = l->sentinel;
    l->sentinel->data = NULL;

    /* If there is a link deallocator, use it */
    if (deallocator != NULL)
        l->linkDeallocator = deallocator;
    /* If there is a link comparator, use it */
    if (compare != NULL)
        l->linkCompare = compare;
    else /* Use our own */
        l->linkCompare = xmlLinkCompare;
    return l;
}

/**
 * Search the list for an existing value of `data`
 *
 * @param l  a list
 * @param data  a search value
 * @returns the value associated to `data` or NULL in case of error
 */
void *
xmlListSearch(xmlList *l, void *data)
{
    xmlLinkPtr lk;
    if (l == NULL)
        return(NULL);
    lk = xmlListLinkSearch(l, data);
    if (lk)
        return (lk->data);
    return NULL;
}

/**
 * Search the list in reverse order for an existing value of `data`
 *
 * @param l  a list
 * @param data  a search value
 * @returns the value associated to `data` or NULL in case of error
 */
void *
xmlListReverseSearch(xmlList *l, void *data)
{
    xmlLinkPtr lk;
    if (l == NULL)
        return(NULL);
    lk = xmlListLinkReverseSearch(l, data);
    if (lk)
        return (lk->data);
    return NULL;
}

/**
 * Insert data in the ordered list at the beginning for this value
 *
 * @param l  a list
 * @param data  the data
 * @returns 0 in case of success, 1 in case of failure
 */
int
xmlListInsert(xmlList *l, void *data)
{
    xmlLinkPtr lkPlace, lkNew;

    if (l == NULL)
        return(1);
    lkPlace = xmlListLowerSearch(l, data);
    /* Add the new link */
    lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
    if (lkNew == NULL)
        return (1);
    lkNew->data = data;
    lkPlace = lkPlace->prev;
    lkNew->next = lkPlace->next;
    (lkPlace->next)->prev = lkNew;
    lkPlace->next = lkNew;
    lkNew->prev = lkPlace;
    return 0;
}

/**
 * Insert data in the ordered list at the end for this value
 *
 * @param l  a list
 * @param data  the data
 * @returns 0 in case of success, 1 in case of failure
 */
int xmlListAppend(xmlList *l, void *data)
{
    xmlLinkPtr lkPlace, lkNew;

    if (l == NULL)
        return(1);
    lkPlace = xmlListHigherSearch(l, data);
    /* Add the new link */
    lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
    if (lkNew == NULL)
        return (1);
    lkNew->data = data;
    lkNew->next = lkPlace->next;
    (lkPlace->next)->prev = lkNew;
    lkPlace->next = lkNew;
    lkNew->prev = lkPlace;
    return 0;
}

/**
 * Deletes the list and its associated data
 *
 * @param l  a list
 */
void xmlListDelete(xmlList *l)
{
    if (l == NULL)
        return;

    xmlListClear(l);
    xmlFree(l->sentinel);
    xmlFree(l);
}

/**
 * Remove the first instance associated to data in the list
 *
 * @param l  a list
 * @param data  list data
 * @returns 1 if a deallocation occurred, or 0 if not found
 */
int
xmlListRemoveFirst(xmlList *l, void *data)
{
    xmlLinkPtr lk;

    if (l == NULL)
        return(0);
    /*Find the first instance of this data */
    lk = xmlListLinkSearch(l, data);
    if (lk != NULL) {
        xmlLinkDeallocator(l, lk);
        return 1;
    }
    return 0;
}

/**
 * Remove the last instance associated to data in the list
 *
 * @param l  a list
 * @param data  list data
 * @returns 1 if a deallocation occurred, or 0 if not found
 */
int
xmlListRemoveLast(xmlList *l, void *data)
{
    xmlLinkPtr lk;

    if (l == NULL)
        return(0);
    /*Find the last instance of this data */
    lk = xmlListLinkReverseSearch(l, data);
    if (lk != NULL) {
  xmlLinkDeallocator(l, lk);
        return 1;
    }
    return 0;
}

/**
 * Remove the all instance associated to data in the list
 *
 * @param l  a list
 * @param data  list data
 * @returns the number of deallocation, or 0 if not found
 */
int
xmlListRemoveAll(xmlList *l, void *data)
{
    int count=0;

    if (l == NULL)
        return(0);

    while(xmlListRemoveFirst(l, data))
        count++;
    return count;
}

/**
 * Remove the all data in the list
 *
 * @param l  a list
 */
void
xmlListClear(xmlList *l)
{
    xmlLinkPtr  lk;

    if (l == NULL)
        return;
    lk = l->sentinel->next;
    while(lk != l->sentinel) {
        xmlLinkPtr next = lk->next;

        xmlLinkDeallocator(l, lk);
        lk = next;
    }
}

/**
 * Is the list empty ?
 *
 * @param l  a list
 * @returns 1 if the list is empty, 0 if not empty and -1 in case of error
 */
int
xmlListEmpty(xmlList *l)
{
    if (l == NULL)
        return(-1);
    return (l->sentinel->next == l->sentinel);
}

/**
 * Get the first element in the list
 *
 * @param l  a list
 * @returns the first element in the list, or NULL
 */
xmlLink *
xmlListFront(xmlList *l)
{
    if (l == NULL)
        return(NULL);
    return (l->sentinel->next);
}

/**
 * Get the last element in the list
 *
 * @param l  a list
 * @returns the last element in the list, or NULL
 */
xmlLink *
xmlListEnd(xmlList *l)
{
    if (l == NULL)
        return(NULL);
    return (l->sentinel->prev);
}

/**
 * Get the number of elements in the list
 *
 * @param l  a list
 * @returns the number of elements in the list or -1 in case of error
 */
int
xmlListSize(xmlList *l)
{
    xmlLinkPtr lk;
    int count=0;

    if (l == NULL)
        return(-1);
    /* TODO: keep a counter in xmlList instead */
    for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next, count++);
    return count;
}

/**
 * Removes the first element in the list
 *
 * @param l  a list
 */
void
xmlListPopFront(xmlList *l)
{
    if(!xmlListEmpty(l))
        xmlLinkDeallocator(l, l->sentinel->next);
}

/**
 * Removes the last element in the list
 *
 * @param l  a list
 */
void
xmlListPopBack(xmlList *l)
{
    if(!xmlListEmpty(l))
        xmlLinkDeallocator(l, l->sentinel->prev);
}

/**
 * add the new data at the beginning of the list
 *
 * @param l  a list
 * @param data  new data
 * @returns 1 if successful, 0 otherwise
 */
int
xmlListPushFront(xmlList *l, void *data)
{
    xmlLinkPtr lkPlace, lkNew;

    if (l == NULL)
        return(0);
    lkPlace = l->sentinel;
    /* Add the new link */
    lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
    if (lkNew == NULL)
        return (0);
    lkNew->data = data;
    lkNew->next = lkPlace->next;
    (lkPlace->next)->prev = lkNew;
    lkPlace->next = lkNew;
    lkNew->prev = lkPlace;
    return 1;
}

/**
 * add the new data at the end of the list
 *
 * @param l  a list
 * @param data  new data
 * @returns 1 if successful, 0 otherwise
 */
int
xmlListPushBack(xmlList *l, void *data)
{
    xmlLinkPtr lkPlace, lkNew;

    if (l == NULL)
        return(0);
    lkPlace = l->sentinel->prev;
    /* Add the new link */
    lkNew = (xmlLinkPtr)xmlMalloc(sizeof(xmlLink));
    if (lkNew == NULL)
        return (0);
    lkNew->data = data;
    lkNew->next = lkPlace->next;
    (lkPlace->next)->prev = lkNew;
    lkPlace->next = lkNew;
    lkNew->prev = lkPlace;
    return 1;
}

/**
 * See Returns.
 *
 * @param lk  a link
 * @returns a pointer to the data referenced from this link
 */
void *
xmlLinkGetData(xmlLink *lk)
{
    if (lk == NULL)
        return(NULL);
    return lk->data;
}

/**
 * Reverse the order of the elements in the list
 *
 * @param l  a list
 */
void
xmlListReverse(xmlList *l)
{
    xmlLinkPtr lk;
    xmlLinkPtr lkPrev;

    if (l == NULL)
        return;
    lkPrev = l->sentinel;
    for (lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
        lkPrev->next = lkPrev->prev;
        lkPrev->prev = lk;
        lkPrev = lk;
    }
    /* Fix up the last node */
    lkPrev->next = lkPrev->prev;
    lkPrev->prev = lk;
}

/**
 * Sort all the elements in the list
 *
 * @param l  a list
 */
void
xmlListSort(xmlList *l)
{
    xmlListPtr lTemp;

    if (l == NULL)
        return;
    if(xmlListEmpty(l))
        return;

    /* I think that the real answer is to implement quicksort, the
     * alternative is to implement some list copying procedure which
     * would be based on a list copy followed by a clear followed by
     * an insert. This is slow...
     */

    lTemp = xmlListDup(l);
    if (lTemp == NULL)
        return;
    xmlListClear(l);
    xmlListMerge(l, lTemp);
    xmlListDelete(lTemp);
}

/**
 * Walk all the element of the first from first to last and
 * apply the walker function to it
 *
 * @param l  a list
 * @param walker  a processing function
 * @param user  a user parameter passed to the walker function
 */
void
xmlListWalk(xmlList *l, xmlListWalker walker, void *user) {
    xmlLinkPtr lk;

    if ((l == NULL) || (walker == NULL))
        return;
    for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
        if((walker(lk->data, user)) == 0)
                break;
    }
}

/**
 * Walk all the element of the list in reverse order and
 * apply the walker function to it
 *
 * @param l  a list
 * @param walker  a processing function
 * @param user  a user parameter passed to the walker function
 */
void
xmlListReverseWalk(xmlList *l, xmlListWalker walker, void *user) {
    xmlLinkPtr lk;

    if ((l == NULL) || (walker == NULL))
        return;
    for(lk = l->sentinel->prev; lk != l->sentinel; lk = lk->prev) {
        if((walker(lk->data, user)) == 0)
                break;
    }
}

/**
 * include all the elements of the second list in the first one and
 * clear the second list
 *
 * @param l1  the original list
 * @param l2  the new list
 */
void
xmlListMerge(xmlList *l1, xmlList *l2)
{
    xmlListCopy(l1, l2);
    xmlListClear(l2);
}

/**
 * Duplicate the list
 *
 * @param old  the list
 * @returns a new copy of the list or NULL in case of error
 */
xmlList *
xmlListDup(xmlList *old)
{
    xmlListPtr cur;

    if (old == NULL)
        return(NULL);
    /* Hmmm, how to best deal with allocation issues when copying
     * lists. If there is a de-allocator, should responsibility lie with
     * the new list or the old list. Surely not both. I'll arbitrarily
     * set it to be the old list for the time being whilst I work out
     * the answer
     */
    cur = xmlListCreate(NULL, old->linkCompare);
    if (cur == NULL)
        return (NULL);
    if (0 != xmlListCopy(cur, old))
        return NULL;
    return cur;
}

/**
 * Move all the element from the old list in the new list
 *
 * @param cur  the new list
 * @param old  the old list
 * @returns 0 in case of success 1 in case of error
 */
int
xmlListCopy(xmlList *cur, xmlList *old)
{
    /* Walk the old tree and insert the data into the new one */
    xmlLinkPtr lk;

    if ((old == NULL) || (cur == NULL))
        return(1);
    for(lk = old->sentinel->next; lk != old->sentinel; lk = lk->next) {
        if (0 !=xmlListInsert(cur, lk->data)) {
            xmlListDelete(cur);
            return (1);
        }
    }
    return (0);
}
/* xmlListUnique() */
/* xmlListSwap */

Coverage Report

Created: 2025-07-01 06:27

Line	Count	Source (jump to first uncovered line)
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
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		* Unlink and deallocate `lk` from list `l`
53		*
54		* @param l a list
55		* @param lk a link
56		*/
57		static void
58		xmlLinkDeallocator(xmlListPtr l, xmlLinkPtr lk)
59	0	{
60	0	(lk->prev)->next = lk->next;
61	0	(lk->next)->prev = lk->prev;
62	0	if(l->linkDeallocator)
63	0	l->linkDeallocator(lk);
64	0	xmlFree(lk);
65	0	}
66
67		/**
68		* Compares two arbitrary data
69		*
70		* @param data0 first data
71		* @param data1 second data
72		* @returns -1, 0 or 1 depending on whether data1 is greater equal or smaller
73		* than data0
74		*/
75		static int
76		xmlLinkCompare(const void data0, const void data1)
77	0	{
78	0	if (data0 < data1)
79	0	return (-1);
80	0	else if (data0 == data1)
81	0	return (0);
82	0	return (1);
83	0	}
84
85		/**
86		* Search data in the ordered list walking from the beginning
87		*
88		* @param l a list
89		* @param data a data
90		* @returns the link containing the data or NULL
91		*/
92		static xmlLinkPtr
93		xmlListLowerSearch(xmlListPtr l, void *data)
94	0	{
95	0	xmlLinkPtr lk;
96
97	0	if (l == NULL)
98	0	return(NULL);
99	0	for(lk = l->sentinel->next;lk != l->sentinel && l->linkCompare(lk->data, data) <0 ;lk = lk->next);
100	0	return lk;
101	0	}
102
103		/**
104		* Search data in the ordered list walking backward from the end
105		*
106		* @param l a list
107		* @param data a data
108		* @returns the link containing the data or NULL
109		*/
110		static xmlLinkPtr
111		xmlListHigherSearch(xmlListPtr l, void *data)
112	0	{
113	0	xmlLinkPtr lk;
114
115	0	if (l == NULL)
116	0	return(NULL);
117	0	for(lk = l->sentinel->prev;lk != l->sentinel && l->linkCompare(lk->data, data) >0 ;lk = lk->prev);
118	0	return lk;
119	0	}
120
121		/**
122		* Search data in the list
123		*
124		* @param l a list
125		* @param data a data
126		* @returns the link containing the data or NULL
127		*/
128		static xmlLinkPtr
129		xmlListLinkSearch(xmlListPtr l, void *data)
130	0	{
131	0	xmlLinkPtr lk;
132	0	if (l == NULL)
133	0	return(NULL);
134	0	lk = xmlListLowerSearch(l, data);
135	0	if (lk == l->sentinel)
136	0	return NULL;
137	0	else {
138	0	if (l->linkCompare(lk->data, data) ==0)
139	0	return lk;
140	0	return NULL;
141	0	}
142	0	}
143
144		/**
145		* Search data in the list processing backward
146		*
147		* @param l a list
148		* @param data a data
149		* @returns the link containing the data or NULL
150		*/
151		static xmlLinkPtr
152		xmlListLinkReverseSearch(xmlListPtr l, void *data)
153	0	{
154	0	xmlLinkPtr lk;
155	0	if (l == NULL)
156	0	return(NULL);
157	0	lk = xmlListHigherSearch(l, data);
158	0	if (lk == l->sentinel)
159	0	return NULL;
160	0	else {
161	0	if (l->linkCompare(lk->data, data) ==0)
162	0	return lk;
163	0	return NULL;
164	0	}
165	0	}
166
167		/**
168		* Create a new list
169		*
170		* @param deallocator an optional deallocator function
171		* @param compare an optional comparison function
172		* @returns the new list or NULL in case of error
173		*/
174		xmlList *
175		xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)
176	0	{
177	0	xmlListPtr l;
178	0	l = (xmlListPtr)xmlMalloc(sizeof(xmlList));
179	0	if (l == NULL)
180	0	return (NULL);
181		/* Initialize the list to NULL */
182	0	memset(l, 0, sizeof(xmlList));
183
184		/* Add the sentinel */
185	0	l->sentinel = (xmlLinkPtr)xmlMalloc(sizeof(xmlLink));
186	0	if (l->sentinel == NULL) {
187	0	xmlFree(l);
188	0	return (NULL);
189	0	}
190	0	l->sentinel->next = l->sentinel;
191	0	l->sentinel->prev = l->sentinel;
192	0	l->sentinel->data = NULL;
193
194		/* If there is a link deallocator, use it */
195	0	if (deallocator != NULL)
196	0	l->linkDeallocator = deallocator;
197		/* If there is a link comparator, use it */
198	0	if (compare != NULL)
199	0	l->linkCompare = compare;
200	0	else /* Use our own */
201	0	l->linkCompare = xmlLinkCompare;
202	0	return l;
203	0	}
204
205		/**
206		* Search the list for an existing value of `data`
207		*
208		* @param l a list
209		* @param data a search value
210		* @returns the value associated to `data` or NULL in case of error
211		*/
212		void *
213		xmlListSearch(xmlList l, void data)
214	0	{
215	0	xmlLinkPtr lk;
216	0	if (l == NULL)
217	0	return(NULL);
218	0	lk = xmlListLinkSearch(l, data);
219	0	if (lk)
220	0	return (lk->data);
221	0	return NULL;
222	0	}
223
224		/**
225		* Search the list in reverse order for an existing value of `data`
226		*
227		* @param l a list
228		* @param data a search value
229		* @returns the value associated to `data` or NULL in case of error
230		*/
231		void *
232		xmlListReverseSearch(xmlList l, void data)
233	0	{
234	0	xmlLinkPtr lk;
235	0	if (l == NULL)
236	0	return(NULL);
237	0	lk = xmlListLinkReverseSearch(l, data);
238	0	if (lk)
239	0	return (lk->data);
240	0	return NULL;
241	0	}
242
243		/**
244		* Insert data in the ordered list at the beginning for this value
245		*
246		* @param l a list
247		* @param data the data
248		* @returns 0 in case of success, 1 in case of failure
249		*/
250		int
251		xmlListInsert(xmlList l, void data)
252	0	{
253	0	xmlLinkPtr lkPlace, lkNew;
254
255	0	if (l == NULL)
256	0	return(1);
257	0	lkPlace = xmlListLowerSearch(l, data);
258		/* Add the new link */
259	0	lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
260	0	if (lkNew == NULL)
261	0	return (1);
262	0	lkNew->data = data;
263	0	lkPlace = lkPlace->prev;
264	0	lkNew->next = lkPlace->next;
265	0	(lkPlace->next)->prev = lkNew;
266	0	lkPlace->next = lkNew;
267	0	lkNew->prev = lkPlace;
268	0	return 0;
269	0	}
270
271		/**
272		* Insert data in the ordered list at the end for this value
273		*
274		* @param l a list
275		* @param data the data
276		* @returns 0 in case of success, 1 in case of failure
277		*/
278		int xmlListAppend(xmlList l, void data)
279	0	{
280	0	xmlLinkPtr lkPlace, lkNew;
281
282	0	if (l == NULL)
283	0	return(1);
284	0	lkPlace = xmlListHigherSearch(l, data);
285		/* Add the new link */
286	0	lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
287	0	if (lkNew == NULL)
288	0	return (1);
289	0	lkNew->data = data;
290	0	lkNew->next = lkPlace->next;
291	0	(lkPlace->next)->prev = lkNew;
292	0	lkPlace->next = lkNew;
293	0	lkNew->prev = lkPlace;
294	0	return 0;
295	0	}
296
297		/**
298		* Deletes the list and its associated data
299		*
300		* @param l a list
301		*/
302		void xmlListDelete(xmlList *l)
303	0	{
304	0	if (l == NULL)
305	0	return;
306
307	0	xmlListClear(l);
308	0	xmlFree(l->sentinel);
309	0	xmlFree(l);
310	0	}
311
312		/**
313		* Remove the first instance associated to data in the list
314		*
315		* @param l a list
316		* @param data list data
317		* @returns 1 if a deallocation occurred, or 0 if not found
318		*/
319		int
320		xmlListRemoveFirst(xmlList l, void data)
321	0	{
322	0	xmlLinkPtr lk;
323
324	0	if (l == NULL)
325	0	return(0);
326		/Find the first instance of this data /
327	0	lk = xmlListLinkSearch(l, data);
328	0	if (lk != NULL) {
329	0	xmlLinkDeallocator(l, lk);
330	0	return 1;
331	0	}
332	0	return 0;
333	0	}
334
335		/**
336		* Remove the last instance associated to data in the list
337		*
338		* @param l a list
339		* @param data list data
340		* @returns 1 if a deallocation occurred, or 0 if not found
341		*/
342		int
343		xmlListRemoveLast(xmlList l, void data)
344	0	{
345	0	xmlLinkPtr lk;
346
347	0	if (l == NULL)
348	0	return(0);
349		/Find the last instance of this data /
350	0	lk = xmlListLinkReverseSearch(l, data);
351	0	if (lk != NULL) {
352	0	xmlLinkDeallocator(l, lk);
353	0	return 1;
354	0	}
355	0	return 0;
356	0	}
357
358		/**
359		* Remove the all instance associated to data in the list
360		*
361		* @param l a list
362		* @param data list data
363		* @returns the number of deallocation, or 0 if not found
364		*/
365		int
366		xmlListRemoveAll(xmlList l, void data)
367	0	{
368	0	int count=0;
369
370	0	if (l == NULL)
371	0	return(0);
372
373	0	while(xmlListRemoveFirst(l, data))
374	0	count++;
375	0	return count;
376	0	}
377
378		/**
379		* Remove the all data in the list
380		*
381		* @param l a list
382		*/
383		void
384		xmlListClear(xmlList *l)
385	0	{
386	0	xmlLinkPtr lk;
387
388	0	if (l == NULL)
389	0	return;
390	0	lk = l->sentinel->next;
391	0	while(lk != l->sentinel) {
392	0	xmlLinkPtr next = lk->next;
393
394	0	xmlLinkDeallocator(l, lk);
395	0	lk = next;
396	0	}
397	0	}
398
399		/**
400		* Is the list empty ?
401		*
402		* @param l a list
403		* @returns 1 if the list is empty, 0 if not empty and -1 in case of error
404		*/
405		int
406		xmlListEmpty(xmlList *l)
407	0	{
408	0	if (l == NULL)
409	0	return(-1);
410	0	return (l->sentinel->next == l->sentinel);
411	0	}
412
413		/**
414		* Get the first element in the list
415		*
416		* @param l a list
417		* @returns the first element in the list, or NULL
418		*/
419		xmlLink *
420		xmlListFront(xmlList *l)
421	0	{
422	0	if (l == NULL)
423	0	return(NULL);
424	0	return (l->sentinel->next);
425	0	}
426
427		/**
428		* Get the last element in the list
429		*
430		* @param l a list
431		* @returns the last element in the list, or NULL
432		*/
433		xmlLink *
434		xmlListEnd(xmlList *l)
435	0	{
436	0	if (l == NULL)
437	0	return(NULL);
438	0	return (l->sentinel->prev);
439	0	}
440
441		/**
442		* Get the number of elements in the list
443		*
444		* @param l a list
445		* @returns the number of elements in the list or -1 in case of error
446		*/
447		int
448		xmlListSize(xmlList *l)
449	0	{
450	0	xmlLinkPtr lk;
451	0	int count=0;
452
453	0	if (l == NULL)
454	0	return(-1);
455		/* TODO: keep a counter in xmlList instead */
456	0	for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next, count++);
457	0	return count;
458	0	}
459
460		/**
461		* Removes the first element in the list
462		*
463		* @param l a list
464		*/
465		void
466		xmlListPopFront(xmlList *l)
467	0	{
468	0	if(!xmlListEmpty(l))
469	0	xmlLinkDeallocator(l, l->sentinel->next);
470	0	}
471
472		/**
473		* Removes the last element in the list
474		*
475		* @param l a list
476		*/
477		void
478		xmlListPopBack(xmlList *l)
479	0	{
480	0	if(!xmlListEmpty(l))
481	0	xmlLinkDeallocator(l, l->sentinel->prev);
482	0	}
483
484		/**
485		* add the new data at the beginning of the list
486		*
487		* @param l a list
488		* @param data new data
489		* @returns 1 if successful, 0 otherwise
490		*/
491		int
492		xmlListPushFront(xmlList l, void data)
493	0	{
494	0	xmlLinkPtr lkPlace, lkNew;
495
496	0	if (l == NULL)
497	0	return(0);
498	0	lkPlace = l->sentinel;
499		/* Add the new link */
500	0	lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
501	0	if (lkNew == NULL)
502	0	return (0);
503	0	lkNew->data = data;
504	0	lkNew->next = lkPlace->next;
505	0	(lkPlace->next)->prev = lkNew;
506	0	lkPlace->next = lkNew;
507	0	lkNew->prev = lkPlace;
508	0	return 1;
509	0	}
510
511		/**
512		* add the new data at the end of the list
513		*
514		* @param l a list
515		* @param data new data
516		* @returns 1 if successful, 0 otherwise
517		*/
518		int
519		xmlListPushBack(xmlList l, void data)
520	0	{
521	0	xmlLinkPtr lkPlace, lkNew;
522
523	0	if (l == NULL)
524	0	return(0);
525	0	lkPlace = l->sentinel->prev;
526		/* Add the new link */
527	0	lkNew = (xmlLinkPtr)xmlMalloc(sizeof(xmlLink));
528	0	if (lkNew == NULL)
529	0	return (0);
530	0	lkNew->data = data;
531	0	lkNew->next = lkPlace->next;
532	0	(lkPlace->next)->prev = lkNew;
533	0	lkPlace->next = lkNew;
534	0	lkNew->prev = lkPlace;
535	0	return 1;
536	0	}
537
538		/**
539		* See Returns.
540		*
541		* @param lk a link
542		* @returns a pointer to the data referenced from this link
543		*/
544		void *
545		xmlLinkGetData(xmlLink *lk)
546	0	{
547	0	if (lk == NULL)
548	0	return(NULL);
549	0	return lk->data;
550	0	}
551
552		/**
553		* Reverse the order of the elements in the list
554		*
555		* @param l a list
556		*/
557		void
558		xmlListReverse(xmlList *l)
559	0	{
560	0	xmlLinkPtr lk;
561	0	xmlLinkPtr lkPrev;
562
563	0	if (l == NULL)
564	0	return;
565	0	lkPrev = l->sentinel;
566	0	for (lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
567	0	lkPrev->next = lkPrev->prev;
568	0	lkPrev->prev = lk;
569	0	lkPrev = lk;
570	0	}
571		/* Fix up the last node */
572	0	lkPrev->next = lkPrev->prev;
573	0	lkPrev->prev = lk;
574	0	}
575
576		/**
577		* Sort all the elements in the list
578		*
579		* @param l a list
580		*/
581		void
582		xmlListSort(xmlList *l)
583	0	{
584	0	xmlListPtr lTemp;
585
586	0	if (l == NULL)
587	0	return;
588	0	if(xmlListEmpty(l))
589	0	return;
590
591		/* I think that the real answer is to implement quicksort, the
592		* alternative is to implement some list copying procedure which
593		* would be based on a list copy followed by a clear followed by
594		* an insert. This is slow...
595		*/
596
597	0	lTemp = xmlListDup(l);
598	0	if (lTemp == NULL)
599	0	return;
600	0	xmlListClear(l);
601	0	xmlListMerge(l, lTemp);
602	0	xmlListDelete(lTemp);
603	0	}
604
605		/**
606		* Walk all the element of the first from first to last and
607		* apply the walker function to it
608		*
609		* @param l a list
610		* @param walker a processing function
611		* @param user a user parameter passed to the walker function
612		*/
613		void
614	0	xmlListWalk(xmlList l, xmlListWalker walker, void user) {
615	0	xmlLinkPtr lk;
616
617	0	if ((l == NULL) \|\| (walker == NULL))
618	0	return;
619	0	for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
620	0	if((walker(lk->data, user)) == 0)
621	0	break;
622	0	}
623	0	}
624
625		/**
626		* Walk all the element of the list in reverse order and
627		* apply the walker function to it
628		*
629		* @param l a list
630		* @param walker a processing function
631		* @param user a user parameter passed to the walker function
632		*/
633		void
634	0	xmlListReverseWalk(xmlList l, xmlListWalker walker, void user) {
635	0	xmlLinkPtr lk;
636
637	0	if ((l == NULL) \|\| (walker == NULL))
638	0	return;
639	0	for(lk = l->sentinel->prev; lk != l->sentinel; lk = lk->prev) {
640	0	if((walker(lk->data, user)) == 0)
641	0	break;
642	0	}
643	0	}
644
645		/**
646		* include all the elements of the second list in the first one and
647		* clear the second list
648		*
649		* @param l1 the original list
650		* @param l2 the new list
651		*/
652		void
653		xmlListMerge(xmlList l1, xmlList l2)
654	0	{
655	0	xmlListCopy(l1, l2);
656	0	xmlListClear(l2);
657	0	}
658
659		/**
660		* Duplicate the list
661		*
662		* @param old the list
663		* @returns a new copy of the list or NULL in case of error
664		*/
665		xmlList *
666		xmlListDup(xmlList *old)
667	0	{
668	0	xmlListPtr cur;
669
670	0	if (old == NULL)
671	0	return(NULL);
672		/* Hmmm, how to best deal with allocation issues when copying
673		* lists. If there is a de-allocator, should responsibility lie with
674		* the new list or the old list. Surely not both. I'll arbitrarily
675		* set it to be the old list for the time being whilst I work out
676		* the answer
677		*/
678	0	cur = xmlListCreate(NULL, old->linkCompare);
679	0	if (cur == NULL)
680	0	return (NULL);
681	0	if (0 != xmlListCopy(cur, old))
682	0	return NULL;
683	0	return cur;
684	0	}
685
686		/**
687		* Move all the element from the old list in the new list
688		*
689		* @param cur the new list
690		* @param old the old list
691		* @returns 0 in case of success 1 in case of error
692		*/
693		int
694		xmlListCopy(xmlList cur, xmlList old)
695	0	{
696		/* Walk the old tree and insert the data into the new one */
697	0	xmlLinkPtr lk;
698
699	0	if ((old == NULL) \|\| (cur == NULL))
700	0	return(1);
701	0	for(lk = old->sentinel->next; lk != old->sentinel; lk = lk->next) {
702	0	if (0 !=xmlListInsert(cur, lk->data)) {
703	0	xmlListDelete(cur);
704	0	return (1);
705	0	}
706	0	}
707	0	return (0);
708	0	}
709		/* xmlListUnique() */
710		/* xmlListSwap */