/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@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 occurred, 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 occurred, 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, 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, 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 */

Coverage Report

Created: 2023-10-27 07:47

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@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	0	{
61	0	(lk->prev)->next = lk->next;
62	0	(lk->next)->prev = lk->prev;
63	0	if(l->linkDeallocator)
64	0	l->linkDeallocator(lk);
65	0	xmlFree(lk);
66	0	}
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	0	{
81	0	if (data0 < data1)
82	0	return (-1);
83	0	else if (data0 == data1)
84	0	return (0);
85	0	return (1);
86	0	}
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	0	{
100	0	xmlLinkPtr lk;
101
102	0	if (l == NULL)
103	0	return(NULL);
104	0	for(lk = l->sentinel->next;lk != l->sentinel && l->linkCompare(lk->data, data) <0 ;lk = lk->next);
105	0	return lk;
106	0	}
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	0	{
120	0	xmlLinkPtr lk;
121
122	0	if (l == NULL)
123	0	return(NULL);
124	0	for(lk = l->sentinel->prev;lk != l->sentinel && l->linkCompare(lk->data, data) >0 ;lk = lk->prev);
125	0	return lk;
126	0	}
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	0	{
140	0	xmlLinkPtr lk;
141	0	if (l == NULL)
142	0	return(NULL);
143	0	lk = xmlListLowerSearch(l, data);
144	0	if (lk == l->sentinel)
145	0	return NULL;
146	0	else {
147	0	if (l->linkCompare(lk->data, data) ==0)
148	0	return lk;
149	0	return NULL;
150	0	}
151	0	}
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	0	{
165	0	xmlLinkPtr lk;
166	0	if (l == NULL)
167	0	return(NULL);
168	0	lk = xmlListHigherSearch(l, data);
169	0	if (lk == l->sentinel)
170	0	return NULL;
171	0	else {
172	0	if (l->linkCompare(lk->data, data) ==0)
173	0	return lk;
174	0	return NULL;
175	0	}
176	0	}
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	0	{
190	0	xmlListPtr l;
191	0	if (NULL == (l = (xmlListPtr )xmlMalloc( sizeof(xmlList)))) {
192	0	xmlGenericError(xmlGenericErrorContext,
193	0	"Cannot initialize memory for list");
194	0	return (NULL);
195	0	}
196		/* Initialize the list to NULL */
197	0	memset(l, 0, sizeof(xmlList));
198
199		/* Add the sentinel */
200	0	if (NULL ==(l->sentinel = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
201	0	xmlGenericError(xmlGenericErrorContext,
202	0	"Cannot initialize memory for sentinel");
203	0	xmlFree(l);
204	0	return (NULL);
205	0	}
206	0	l->sentinel->next = l->sentinel;
207	0	l->sentinel->prev = l->sentinel;
208	0	l->sentinel->data = NULL;
209
210		/* If there is a link deallocator, use it */
211	0	if (deallocator != NULL)
212	0	l->linkDeallocator = deallocator;
213		/* If there is a link comparator, use it */
214	0	if (compare != NULL)
215	0	l->linkCompare = compare;
216	0	else /* Use our own */
217	0	l->linkCompare = xmlLinkCompare;
218	0	return l;
219	0	}
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	0	{
233	0	xmlLinkPtr lk;
234	0	if (l == NULL)
235	0	return(NULL);
236	0	lk = xmlListLinkSearch(l, data);
237	0	if (lk)
238	0	return (lk->data);
239	0	return NULL;
240	0	}
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	0	{
254	0	xmlLinkPtr lk;
255	0	if (l == NULL)
256	0	return(NULL);
257	0	lk = xmlListLinkReverseSearch(l, data);
258	0	if (lk)
259	0	return (lk->data);
260	0	return NULL;
261	0	}
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	0	{
275	0	xmlLinkPtr lkPlace, lkNew;
276
277	0	if (l == NULL)
278	0	return(1);
279	0	lkPlace = xmlListLowerSearch(l, data);
280		/* Add the new link */
281	0	lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
282	0	if (lkNew == NULL) {
283	0	xmlGenericError(xmlGenericErrorContext,
284	0	"Cannot initialize memory for new link");
285	0	return (1);
286	0	}
287	0	lkNew->data = data;
288	0	lkPlace = lkPlace->prev;
289	0	lkNew->next = lkPlace->next;
290	0	(lkPlace->next)->prev = lkNew;
291	0	lkPlace->next = lkNew;
292	0	lkNew->prev = lkPlace;
293	0	return 0;
294	0	}
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	0	{
307	0	xmlLinkPtr lkPlace, lkNew;
308
309	0	if (l == NULL)
310	0	return(1);
311	0	lkPlace = xmlListHigherSearch(l, data);
312		/* Add the new link */
313	0	lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
314	0	if (lkNew == NULL) {
315	0	xmlGenericError(xmlGenericErrorContext,
316	0	"Cannot initialize memory for new link");
317	0	return (1);
318	0	}
319	0	lkNew->data = data;
320	0	lkNew->next = lkPlace->next;
321	0	(lkPlace->next)->prev = lkNew;
322	0	lkPlace->next = lkNew;
323	0	lkNew->prev = lkPlace;
324	0	return 0;
325	0	}
326
327		/**
328		* xmlListDelete:
329		* @l: a list
330		*
331		* Deletes the list and its associated data
332		*/
333		void xmlListDelete(xmlListPtr l)
334	0	{
335	0	if (l == NULL)
336	0	return;
337
338	0	xmlListClear(l);
339	0	xmlFree(l->sentinel);
340	0	xmlFree(l);
341	0	}
342
343		/**
344		* xmlListRemoveFirst:
345		* @l: a list
346		* @data: list data
347		*
348		* Remove the first instance associated to data in the list
349		*
350		* Returns 1 if a deallocation occurred, or 0 if not found
351		*/
352		int
353		xmlListRemoveFirst(xmlListPtr l, void *data)
354	0	{
355	0	xmlLinkPtr lk;
356
357	0	if (l == NULL)
358	0	return(0);
359		/Find the first instance of this data /
360	0	lk = xmlListLinkSearch(l, data);
361	0	if (lk != NULL) {
362	0	xmlLinkDeallocator(l, lk);
363	0	return 1;
364	0	}
365	0	return 0;
366	0	}
367
368		/**
369		* xmlListRemoveLast:
370		* @l: a list
371		* @data: list data
372		*
373		* Remove the last instance associated to data in the list
374		*
375		* Returns 1 if a deallocation occurred, or 0 if not found
376		*/
377		int
378		xmlListRemoveLast(xmlListPtr l, void *data)
379	0	{
380	0	xmlLinkPtr lk;
381
382	0	if (l == NULL)
383	0	return(0);
384		/Find the last instance of this data /
385	0	lk = xmlListLinkReverseSearch(l, data);
386	0	if (lk != NULL) {
387	0	xmlLinkDeallocator(l, lk);
388	0	return 1;
389	0	}
390	0	return 0;
391	0	}
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	0	{
405	0	int count=0;
406
407	0	if (l == NULL)
408	0	return(0);
409
410	0	while(xmlListRemoveFirst(l, data))
411	0	count++;
412	0	return count;
413	0	}
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	0	{
424	0	xmlLinkPtr lk;
425
426	0	if (l == NULL)
427	0	return;
428	0	lk = l->sentinel->next;
429	0	while(lk != l->sentinel) {
430	0	xmlLinkPtr next = lk->next;
431
432	0	xmlLinkDeallocator(l, lk);
433	0	lk = next;
434	0	}
435	0	}
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	0	{
448	0	if (l == NULL)
449	0	return(-1);
450	0	return (l->sentinel->next == l->sentinel);
451	0	}
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	0	{
464	0	if (l == NULL)
465	0	return(NULL);
466	0	return (l->sentinel->next);
467	0	}
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	0	{
480	0	if (l == NULL)
481	0	return(NULL);
482	0	return (l->sentinel->prev);
483	0	}
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	0	{
496	0	xmlLinkPtr lk;
497	0	int count=0;
498
499	0	if (l == NULL)
500	0	return(-1);
501		/* TODO: keep a counter in xmlList instead */
502	0	for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next, count++);
503	0	return count;
504	0	}
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	0	{
515	0	if(!xmlListEmpty(l))
516	0	xmlLinkDeallocator(l, l->sentinel->next);
517	0	}
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	0	{
528	0	if(!xmlListEmpty(l))
529	0	xmlLinkDeallocator(l, l->sentinel->prev);
530	0	}
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	0	{
544	0	xmlLinkPtr lkPlace, lkNew;
545
546	0	if (l == NULL)
547	0	return(0);
548	0	lkPlace = l->sentinel;
549		/* Add the new link */
550	0	lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
551	0	if (lkNew == NULL) {
552	0	xmlGenericError(xmlGenericErrorContext,
553	0	"Cannot initialize memory for new link");
554	0	return (0);
555	0	}
556	0	lkNew->data = data;
557	0	lkNew->next = lkPlace->next;
558	0	(lkPlace->next)->prev = lkNew;
559	0	lkPlace->next = lkNew;
560	0	lkNew->prev = lkPlace;
561	0	return 1;
562	0	}
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	0	{
576	0	xmlLinkPtr lkPlace, lkNew;
577
578	0	if (l == NULL)
579	0	return(0);
580	0	lkPlace = l->sentinel->prev;
581		/* Add the new link */
582	0	if (NULL ==(lkNew = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
583	0	xmlGenericError(xmlGenericErrorContext,
584	0	"Cannot initialize memory for new link");
585	0	return (0);
586	0	}
587	0	lkNew->data = data;
588	0	lkNew->next = lkPlace->next;
589	0	(lkPlace->next)->prev = lkNew;
590	0	lkPlace->next = lkNew;
591	0	lkNew->prev = lkPlace;
592	0	return 1;
593	0	}
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	0	{
606	0	if (lk == NULL)
607	0	return(NULL);
608	0	return lk->data;
609	0	}
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	0	{
620	0	xmlLinkPtr lk;
621	0	xmlLinkPtr lkPrev;
622
623	0	if (l == NULL)
624	0	return;
625	0	lkPrev = l->sentinel;
626	0	for (lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
627	0	lkPrev->next = lkPrev->prev;
628	0	lkPrev->prev = lk;
629	0	lkPrev = lk;
630	0	}
631		/* Fix up the last node */
632	0	lkPrev->next = lkPrev->prev;
633	0	lkPrev->prev = lk;
634	0	}
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	0	{
645	0	xmlListPtr lTemp;
646
647	0	if (l == NULL)
648	0	return;
649	0	if(xmlListEmpty(l))
650	0	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	0	if (NULL ==(lTemp = xmlListDup(l)))
659	0	return;
660	0	xmlListClear(l);
661	0	xmlListMerge(l, lTemp);
662	0	xmlListDelete(lTemp);
663	0	return;
664	0	}
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	0	xmlListWalk(xmlListPtr l, xmlListWalker walker, void *user) {
677	0	xmlLinkPtr lk;
678
679	0	if ((l == NULL) \|\| (walker == NULL))
680	0	return;
681	0	for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
682	0	if((walker(lk->data, user)) == 0)
683	0	break;
684	0	}
685	0	}
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	0	xmlListReverseWalk(xmlListPtr l, xmlListWalker walker, void *user) {
698	0	xmlLinkPtr lk;
699
700	0	if ((l == NULL) \|\| (walker == NULL))
701	0	return;
702	0	for(lk = l->sentinel->prev; lk != l->sentinel; lk = lk->prev) {
703	0	if((walker(lk->data, user)) == 0)
704	0	break;
705	0	}
706	0	}
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	0	{
719	0	xmlListCopy(l1, l2);
720	0	xmlListClear(l2);
721	0	}
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	0	{
734	0	xmlListPtr cur;
735
736	0	if (old == NULL)
737	0	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	0	if (NULL ==(cur = xmlListCreate(NULL, old->linkCompare)))
745	0	return (NULL);
746	0	if (0 != xmlListCopy(cur, old))
747	0	return NULL;
748	0	return cur;
749	0	}
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	0	{
763		/* Walk the old tree and insert the data into the new one */
764	0	xmlLinkPtr lk;
765
766	0	if ((old == NULL) \|\| (cur == NULL))
767	0	return(1);
768	0	for(lk = old->sentinel->next; lk != old->sentinel; lk = lk->next) {
769	0	if (0 !=xmlListInsert(cur, lk->data)) {
770	0	xmlListDelete(cur);
771	0	return (1);
772	0	}
773	0	}
774	0	return (0);
775	0	}
776		/* xmlListUnique() */
777		/* xmlListSwap */