list.h File Reference

#include <libxml/xmlversion.h>

Include dependency graph for list.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
typedef struct _xmlLink	xmlLink
typedef xmlLink *	xmlLinkPtr
typedef struct _xmlList	xmlList
typedef xmlList *	xmlListPtr
typedef void(*	xmlListDeallocator) (xmlLinkPtr lk)
typedef int(*	xmlListDataCompare) (const void *data0, const void *data1)
typedef int(*	xmlListWalker) (const void *data, void *user)

Functions
XMLPUBFUN xmlListPtr	xmlListCreate (xmlListDeallocator deallocator, xmlListDataCompare compare)
XMLPUBFUN void	xmlListDelete (xmlListPtr l)
XMLPUBFUN void *	xmlListSearch (xmlListPtr l, void *data)
XMLPUBFUN void *	xmlListReverseSearch (xmlListPtr l, void *data)
XMLPUBFUN int	xmlListInsert (xmlListPtr l, void *data)
XMLPUBFUN int	xmlListAppend (xmlListPtr l, void *data)
XMLPUBFUN int	xmlListRemoveFirst (xmlListPtr l, void *data)
XMLPUBFUN int	xmlListRemoveLast (xmlListPtr l, void *data)
XMLPUBFUN int	xmlListRemoveAll (xmlListPtr l, void *data)
XMLPUBFUN void	xmlListClear (xmlListPtr l)
XMLPUBFUN int	xmlListEmpty (xmlListPtr l)
XMLPUBFUN xmlLinkPtr	xmlListFront (xmlListPtr l)
XMLPUBFUN xmlLinkPtr	xmlListEnd (xmlListPtr l)
XMLPUBFUN int	xmlListSize (xmlListPtr l)
XMLPUBFUN void	xmlListPopFront (xmlListPtr l)
XMLPUBFUN void	xmlListPopBack (xmlListPtr l)
XMLPUBFUN int	xmlListPushFront (xmlListPtr l, void *data)
XMLPUBFUN int	xmlListPushBack (xmlListPtr l, void *data)
XMLPUBFUN void	xmlListReverse (xmlListPtr l)
XMLPUBFUN void	xmlListSort (xmlListPtr l)
XMLPUBFUN void	xmlListWalk (xmlListPtr l, xmlListWalker walker, void *user)
XMLPUBFUN void	xmlListReverseWalk (xmlListPtr l, xmlListWalker walker, void *user)
XMLPUBFUN void	xmlListMerge (xmlListPtr l1, xmlListPtr l2)
XMLPUBFUN xmlListPtr	xmlListDup (const xmlListPtr old)
XMLPUBFUN int	xmlListCopy (xmlListPtr cur, const xmlListPtr old)
XMLPUBFUN void *	xmlLinkGetData (xmlLinkPtr lk)

Typedef Documentation

xmlLink

typedef struct _xmlLink xmlLink

Definition at line 20 of file list.h.

xmlLinkPtr

typedef xmlLink* xmlLinkPtr

Definition at line 21 of file list.h.

xmlList

typedef struct _xmlList xmlList

Definition at line 23 of file list.h.

xmlListDataCompare

typedef int(* xmlListDataCompare) (const void *data0, const void *data1)

xmlListDataCompare: @data0: the first data @data1: the second data

Callback function used to compare 2 data.

Returns 0 is equality, -1 or 1 otherwise depending on the ordering.

Definition at line 42 of file list.h.

xmlListDeallocator

typedef void(* xmlListDeallocator) (xmlLinkPtr lk)

xmlListDeallocator: @lk: the data to deallocate

Callback function used to free data from a list.

Definition at line 32 of file list.h.

xmlListPtr

typedef xmlList* xmlListPtr

Definition at line 24 of file list.h.

xmlListWalker

typedef int(* xmlListWalker) (const void *data, void *user)

xmlListWalker: @data: the data found in the list @user: extra user provided data to the walker

Callback function used when walking a list with xmlListWalk().

Returns 0 to stop walking the list, 1 otherwise.

Definition at line 52 of file list.h.

Function Documentation

xmlLinkGetData()

XMLPUBFUN void * xmlLinkGetData

(

xmlLinkPtr

lk

)

xmlLinkGetData: @lk: a link

See Returns.

Returns a pointer to the data referenced from this link

Definition at line 604 of file list.c.

{
    if (lk == NULL)
        return(NULL);
    return lk->data;
}

Referenced by xmlFreeRef().

xmlListAppend()

XMLPUBFUN int xmlListAppend	(	xmlListPtr	l,
		void *	data
	)

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

Definition at line 305 of file list.c.

{
    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;
}

Referenced by xmlAddRef().

xmlListClear()

XMLPUBFUN void xmlListClear

(

xmlListPtr

l

)

xmlListClear: @l: a list

Remove the all data in the list

Definition at line 422 of file list.c.

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

Referenced by xmlListDelete(), xmlListMerge(), and xmlListSort().

xmlListCopy()

XMLPUBFUN int xmlListCopy	(	xmlListPtr	cur,
		const xmlListPtr	old
	)

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

Definition at line 761 of file list.c.

{
    /* 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);
}

Referenced by xmlListDup(), and xmlListMerge().

xmlListCreate()

XMLPUBFUN xmlListPtr xmlListCreate	(	xmlListDeallocator	deallocator,
		xmlListDataCompare	compare
	)

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

Definition at line 188 of file list.c.

{
    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;
}

Referenced by xmlAddRef(), and xmlListDup().

xmlListDelete()

XMLPUBFUN void xmlListDelete

(

xmlListPtr

l

)

xmlListDelete: @l: a list

Deletes the list and its associated data

Definition at line 333 of file list.c.

{
    if (l == NULL)
        return;
 
    xmlListClear(l);
    xmlFree(l->sentinel);
    xmlFree(l);
}

Referenced by xmlAddRef(), xmlFreeRefTableEntry(), xmlListCopy(), and xmlListSort().

xmlListDup()

XMLPUBFUN xmlListPtr xmlListDup

(

const xmlListPtr

old

)

xmlListDup: @old: the list

Duplicate the list

Returns a new copy of the list or NULL in case of error

Definition at line 732 of file list.c.

{
    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;
}

Referenced by xmlListSort().

xmlListEmpty()

XMLPUBFUN int xmlListEmpty

(

xmlListPtr

l

)

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

Definition at line 446 of file list.c.

{
    if (l == NULL)
        return(-1);
    return (l->sentinel->next == l->sentinel);
}

Referenced by xmlListPopBack(), xmlListPopFront(), xmlListSort(), and xmlRemoveRef().

xmlListEnd()

XMLPUBFUN xmlLinkPtr xmlListEnd

(

xmlListPtr

l

)

xmlListEnd: @l: a list

Get the last element in the list

Returns the last element in the list, or NULL

Definition at line 478 of file list.c.

{
    if (l == NULL)
        return(NULL);
    return (l->sentinel->prev);
}

xmlListFront()

XMLPUBFUN xmlLinkPtr xmlListFront

(

xmlListPtr

l

)

xmlListFront: @l: a list

Get the first element in the list

Returns the first element in the list, or NULL

Definition at line 462 of file list.c.

{
    if (l == NULL)
        return(NULL);
    return (l->sentinel->next);
}

xmlListInsert()

XMLPUBFUN int xmlListInsert	(	xmlListPtr	l,
		void *	data
	)

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

Definition at line 273 of file list.c.

{
    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;
}

Referenced by xmlListCopy().

xmlListMerge()

XMLPUBFUN void xmlListMerge	(	xmlListPtr	l1,
		xmlListPtr	l2
	)

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

Definition at line 717 of file list.c.

{
    xmlListCopy(l1, l2);
    xmlListClear(l2);
}

Referenced by xmlListSort().

xmlListPopBack()

XMLPUBFUN void xmlListPopBack

(

xmlListPtr

l

)

xmlListPopBack: @l: a list

Removes the last element in the list

Definition at line 526 of file list.c.

{
    if(!xmlListEmpty(l))
        xmlLinkDeallocator(l, l->sentinel->prev);
}

xmlListPopFront()

XMLPUBFUN void xmlListPopFront

(

xmlListPtr

l

)

xmlListPopFront: @l: a list

Removes the first element in the list

Definition at line 513 of file list.c.

{
    if(!xmlListEmpty(l))
        xmlLinkDeallocator(l, l->sentinel->next);
}

xmlListPushBack()

XMLPUBFUN int xmlListPushBack	(	xmlListPtr	l,
		void *	data
	)

xmlListPushBack: @l: a list @data: new data

add the new data at the end of the list

Returns 1 if successful, 0 otherwise

Definition at line 574 of file list.c.

{
    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;
}

xmlListPushFront()

XMLPUBFUN int xmlListPushFront	(	xmlListPtr	l,
		void *	data
	)

xmlListPushFront: @l: a list @data: new data

add the new data at the beginning of the list

Returns 1 if successful, 0 otherwise

Definition at line 542 of file list.c.

{
    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;
}

xmlListRemoveAll()

XMLPUBFUN int xmlListRemoveAll	(	xmlListPtr	l,
		void *	data
	)

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

Definition at line 403 of file list.c.

{
    int count=0;
 
    if (l == NULL)
        return(0);
 
    while(xmlListRemoveFirst(l, data))
        count++;
    return count;
}

xmlListRemoveFirst()

XMLPUBFUN int xmlListRemoveFirst	(	xmlListPtr	l,
		void *	data
	)

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

Definition at line 353 of file list.c.

{
    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;
}

Referenced by xmlListRemoveAll(), and xmlWalkRemoveRef().

xmlListRemoveLast()

XMLPUBFUN int xmlListRemoveLast	(	xmlListPtr	l,
		void *	data
	)

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

Definition at line 378 of file list.c.

{
    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;
}

xmlListReverse()

XMLPUBFUN void xmlListReverse

(

xmlListPtr

l

)

xmlListReverse: @l: a list

Reverse the order of the elements in the list

Definition at line 618 of file list.c.

{
    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;
}

xmlListReverseSearch()

XMLPUBFUN void * xmlListReverseSearch	(	xmlListPtr	l,
		void *	data
	)

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

Definition at line 252 of file list.c.

{
    xmlLinkPtr lk;
    if (l == NULL)
        return(NULL);
    lk = xmlListLinkReverseSearch(l, data);
    if (lk)
        return (lk->data);
    return NULL;
}

xmlListReverseWalk()

XMLPUBFUN void xmlListReverseWalk	(	xmlListPtr	l,
		xmlListWalker	walker,
		void *	user
	)

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

Definition at line 697 of file list.c.

                                                                   {
    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;
    }
}

xmlListSearch()

XMLPUBFUN void * xmlListSearch	(	xmlListPtr	l,
		void *	data
	)

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

Definition at line 231 of file list.c.

{
    xmlLinkPtr lk;
    if (l == NULL)
        return(NULL);
    lk = xmlListLinkSearch(l, data);
    if (lk)
        return (lk->data);
    return NULL;
}

xmlListSize()

XMLPUBFUN int xmlListSize

(

xmlListPtr

l

)

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

Definition at line 494 of file list.c.

{
    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;
}

xmlListSort()

XMLPUBFUN void xmlListSort

(

xmlListPtr

l

)

xmlListSort: @l: a list

Sort all the elements in the list

Definition at line 643 of file list.c.

{
    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()

XMLPUBFUN void xmlListWalk	(	xmlListPtr	l,
		xmlListWalker	walker,
		void *	user
	)

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

Definition at line 676 of file list.c.

                                                            {
    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;
    }
}

Referenced by xmlRemoveRef().