list.c - external_libxml2 in 0xdroid

/*
 * 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
 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
 *
 * Author: Gary.Pennington@uk.sun.com
 */

#define IN_LIBXML
#include "libxml.h"

#include <stdlib.h>
#include <string.h>
#include <libxml/xmlmemory.h>
#include <libxml/list.h>
#include <libxml/globals.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                *
 *                                    *
 ************************************************************************/

/**
 * xmlLinkDeallocator:
 * @l:  a list
 * @lk:  a link
 *
 * Unlink and deallocate @lk from list @l
 */
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);
}

/**
 * xmlLinkCompare:
 * @data0:  first data
 * @data1:  second data
 *
 * Compares two arbitrary 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);
}

/**
 * xmlListLowerSearch:
 * @l:  a list
 * @data:  a data
 *
 * Search data in the ordered list walking from the beginning
 *
 * 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;    
}

/**
 * xmlListHigherSearch:
 * @l:  a list
 * @data:  a data
 *
 * Search data in the ordered list walking backward from the end
 *
 * 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;    
}

/**
 * xmlListSearch:
 * @l:  a list
 * @data:  a data
 *
 * Search data in the list
 *
 * 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;
    }
}

/**
 * xmlListLinkReverseSearch:
 * @l:  a list
 * @data:  a data
 *
 * Search data in the list processing backward
 *
 * 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;
    }
}

/**
 * xmlListCreate:
 * @deallocator:  an optional deallocator function
 * @compare:  an optional comparison function
 *
 * Create a new list
 *
 * Returns the new list or NULL in case of error
 */
xmlListPtr
xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)
{
    xmlListPtr l;
    if (NULL == (l = (xmlListPtr )xmlMalloc( sizeof(xmlList)))) {
        xmlGenericError(xmlGenericErrorContext, 
		        "Cannot initialize memory for list");
        return (NULL);
    }
    /* Initialize the list to NULL */
    memset(l, 0, sizeof(xmlList));
    
    /* Add the sentinel */
    if (NULL ==(l->sentinel = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
        xmlGenericError(xmlGenericErrorContext, 
		        "Cannot initialize memory for sentinel");
	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;
}
    
/**
 * xmlListSearch:
 * @l:  a list
 * @data:  a search value
 *
 * Search the list for an existing value of @data
 *
 * Returns the value associated to @data or NULL in case of error
 */
void *
xmlListSearch(xmlListPtr l, void *data) 
{
    xmlLinkPtr lk;
    if (l == NULL)
        return(NULL);
    lk = xmlListLinkSearch(l, data);
    if (lk)
        return (lk->data);
    return NULL;
}

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

/**
 * xmlListInsert:
 * @l:  a list
 * @data:  the data
 *
 * Insert data in the ordered list at the beginning for this value
 *
 * Returns 0 in case of success, 1 in case of failure
 */
int
xmlListInsert(xmlListPtr 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) {
        xmlGenericError(xmlGenericErrorContext, 
		        "Cannot initialize memory for new link");
        return (1);
    }
    lkNew->data = data;
    lkPlace = lkPlace->prev;
    lkNew->next = lkPlace->next;
    (lkPlace->next)->prev = lkNew;
    lkPlace->next = lkNew;
    lkNew->prev = lkPlace;
    return 0;
}

/**
 * xmlListAppend:
 * @l:  a list
 * @data:  the data
 *
 * Insert data in the ordered list at the end for this value
 *
 * Returns 0 in case of success, 1 in case of failure
 */
int xmlListAppend(xmlListPtr 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) {
        xmlGenericError(xmlGenericErrorContext, 
		        "Cannot initialize memory for new link");
        return (1);
    }
    lkNew->data = data;
    lkNew->next = lkPlace->next;
    (lkPlace->next)->prev = lkNew;
    lkPlace->next = lkNew;
    lkNew->prev = lkPlace;
    return 0;
}

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

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

/**
 * xmlListRemoveFirst:
 * @l:  a list
 * @data:  list data
 *
 * Remove the first instance associated to data in the list
 *
 * Returns 1 if a deallocation occured, or 0 if not found
 */
int
xmlListRemoveFirst(xmlListPtr 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;
}

/**
 * xmlListRemoveLast:
 * @l:  a list
 * @data:  list data
 *
 * Remove the last instance associated to data in the list
 *
 * Returns 1 if a deallocation occured, or 0 if not found
 */
int
xmlListRemoveLast(xmlListPtr 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;
}

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

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

/**
 * xmlListClear:
 * @l:  a list
 *
 * Remove the all data in the list
 */
void
xmlListClear(xmlListPtr l)
{
    xmlLinkPtr  lk;
    
    if (l == NULL)
        return;
    lk = l->sentinel->next;
    while(lk != l->sentinel) {
        xmlLinkPtr next = lk->next;

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

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

/**
 * xmlListFront:
 * @l:  a list
 *
 * Get the first element in the list
 *
 * Returns the first element in the list, or NULL
 */
xmlLinkPtr 
xmlListFront(xmlListPtr l)
{
    if (l == NULL)
        return(NULL);
    return (l->sentinel->next);
}
    
/**
 * xmlListEnd:
 * @l:  a list
 *
 * Get the last element in the list
 *
 * Returns the last element in the list, or NULL
 */
xmlLinkPtr 
xmlListEnd(xmlListPtr l)
{
    if (l == NULL)
        return(NULL);
    return (l->sentinel->prev);
}
    
/**
 * xmlListSize:
 * @l:  a list
 *
 * Get the number of elements in the list
 *
 * Returns the number of elements in the list or -1 in case of error
 */
int
xmlListSize(xmlListPtr 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;
}

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

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

/**
 * xmlListPushFront:
 * @l:  a list
 * @data:  new data
 *
 * add the new data at the beginning of the list
 *
 * Returns 1 if successful, 0 otherwise
 */
int
xmlListPushFront(xmlListPtr 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) {
        xmlGenericError(xmlGenericErrorContext, 
		        "Cannot initialize memory for new link");
        return (0);
    }
    lkNew->data = data;
    lkNew->next = lkPlace->next;
    (lkPlace->next)->prev = lkNew;
    lkPlace->next = lkNew;
    lkNew->prev = lkPlace;
    return 1;
}

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

    if (l == NULL)
        return(0);
    lkPlace = l->sentinel->prev;
    /* Add the new link */
    if (NULL ==(lkNew = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
        xmlGenericError(xmlGenericErrorContext, 
		        "Cannot initialize memory for new link");
        return (0);
    }
    lkNew->data = data;
    lkNew->next = lkPlace->next;
    (lkPlace->next)->prev = lkNew;
    lkPlace->next = lkNew;
    lkNew->prev = lkPlace;
    return 1;
}

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

/**
 * xmlListReverse:
 * @l:  a list
 *
 * Reverse the order of the elements in the list
 */
void
xmlListReverse(xmlListPtr 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;
}

/**
 * xmlListSort:
 * @l:  a list
 *
 * Sort all the elements in the list
 */
void
xmlListSort(xmlListPtr 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...
     */

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

/**
 * xmlListWalk:
 * @l:  a list
 * @walker:  a processing function
 * @user:  a user parameter passed to the walker function
 *
 * Walk all the element of the first from first to last and
 * apply the walker function to it
 */
void
xmlListWalk(xmlListPtr l, xmlListWalker walker, const 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;
    }
}

/**
 * xmlListReverseWalk:
 * @l:  a list
 * @walker:  a processing function
 * @user:  a user parameter passed to the walker function
 *
 * Walk all the element of the list in reverse order and
 * apply the walker function to it
 */
void
xmlListReverseWalk(xmlListPtr l, xmlListWalker walker, const 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;
    }
}

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

/**
 * xmlListDup:
 * @old:  the list
 *
 * Duplicate the list
 * 
 * Returns a new copy of the list or NULL in case of error
 */
xmlListPtr 
xmlListDup(const xmlListPtr 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
     */
    if (NULL ==(cur = xmlListCreate(NULL, old->linkCompare)))
        return (NULL);
    if (0 != xmlListCopy(cur, old))
        return NULL;
    return cur;
}

/**
 * xmlListCopy:
 * @cur:  the new list
 * @old:  the old list
 *
 * Move all the element from the old list in the new list
 * 
 * Returns 0 in case of success 1 in case of error
 */
int
xmlListCopy(xmlListPtr cur, const xmlListPtr 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 */
#define bottom_list
#include "elfgcchack.h"

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
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 occured, 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 occured, 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, 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	*/
696	void
697	xmlListReverseWalk(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	*/
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 */
778	#define bottom_list
779	#include "elfgcchack.h"

Gitorious