ReactOS 0.4.16-dev-197-g92996da
list.c File Reference
#include "libxml.h"
#include <stdlib.h>
#include <string.h>
#include <libxml/xmlmemory.h>
#include <libxml/list.h>
#include <libxml/globals.h>
Include dependency graph for list.c:

Go to the source code of this file.

Classes

struct  _xmlLink
 
struct  _xmlList
 

Macros

#define IN_LIBXML
 

Functions

static void xmlLinkDeallocator (xmlListPtr l, xmlLinkPtr lk)
 
static int xmlLinkCompare (const void *data0, const void *data1)
 
static xmlLinkPtr xmlListLowerSearch (xmlListPtr l, void *data)
 
static xmlLinkPtr xmlListHigherSearch (xmlListPtr l, void *data)
 
static xmlLinkPtr xmlListLinkSearch (xmlListPtr l, void *data)
 
static xmlLinkPtr xmlListLinkReverseSearch (xmlListPtr l, void *data)
 
xmlListPtr xmlListCreate (xmlListDeallocator deallocator, xmlListDataCompare compare)
 
voidxmlListSearch (xmlListPtr l, void *data)
 
voidxmlListReverseSearch (xmlListPtr l, void *data)
 
int xmlListInsert (xmlListPtr l, void *data)
 
int xmlListAppend (xmlListPtr l, void *data)
 
void xmlListDelete (xmlListPtr l)
 
int xmlListRemoveFirst (xmlListPtr l, void *data)
 
int xmlListRemoveLast (xmlListPtr l, void *data)
 
int xmlListRemoveAll (xmlListPtr l, void *data)
 
void xmlListClear (xmlListPtr l)
 
int xmlListEmpty (xmlListPtr l)
 
xmlLinkPtr xmlListFront (xmlListPtr l)
 
xmlLinkPtr xmlListEnd (xmlListPtr l)
 
int xmlListSize (xmlListPtr l)
 
void xmlListPopFront (xmlListPtr l)
 
void xmlListPopBack (xmlListPtr l)
 
int xmlListPushFront (xmlListPtr l, void *data)
 
int xmlListPushBack (xmlListPtr l, void *data)
 
voidxmlLinkGetData (xmlLinkPtr lk)
 
void xmlListReverse (xmlListPtr l)
 
void xmlListSort (xmlListPtr l)
 
void xmlListWalk (xmlListPtr l, xmlListWalker walker, void *user)
 
void xmlListReverseWalk (xmlListPtr l, xmlListWalker walker, void *user)
 
void xmlListMerge (xmlListPtr l1, xmlListPtr l2)
 
xmlListPtr xmlListDup (const xmlListPtr old)
 
int xmlListCopy (xmlListPtr cur, const xmlListPtr old)
 

Macro Definition Documentation

◆ IN_LIBXML

#define IN_LIBXML

Definition at line 18 of file list.c.

Function Documentation

◆ xmlLinkCompare()

static int xmlLinkCompare ( const void data0,
const void data1 
)
static

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

Definition at line 79 of file list.c.

80{
81 if (data0 < data1)
82 return (-1);
83 else if (data0 == data1)
84 return (0);
85 return (1);
86}
Definition: tftpd.h:126

Referenced by xmlListCreate().

◆ xmlLinkDeallocator()

static void xmlLinkDeallocator ( xmlListPtr  l,
xmlLinkPtr  lk 
)
static

xmlLinkDeallocator: @l: a list @lk: a link

Unlink and deallocate @lk from list @l

Definition at line 59 of file list.c.

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}
r l[0]
Definition: byte_order.h:168
static unsigned __int64 next
Definition: rand_nt.c:6
XMLPUBVAR xmlFreeFunc xmlFree
Definition: globals.h:251

Referenced by xmlListClear(), xmlListPopBack(), xmlListPopFront(), xmlListRemoveFirst(), and xmlListRemoveLast().

◆ xmlLinkGetData()

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.

605{
606 if (lk == NULL)
607 return(NULL);
608 return lk->data;
609}
#define NULL
Definition: types.h:112

Referenced by xmlFreeRef().

◆ xmlListAppend()

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.

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) {
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}
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
XMLPUBVAR xmlMallocFunc xmlMalloc
Definition: globals.h:248
XMLPUBVAR void * xmlGenericErrorContext
Definition: globals.h:353
XMLPUBVAR xmlGenericErrorFunc xmlGenericError
Definition: globals.h:337
xmlLink * xmlLinkPtr
Definition: list.h:21
static xmlLinkPtr xmlListHigherSearch(xmlListPtr l, void *data)
Definition: list.c:118

Referenced by xmlAddRef().

◆ xmlListClear()

void xmlListClear ( xmlListPtr  l)

xmlListClear: @l: a list

Remove the all data in the list

Definition at line 422 of file list.c.

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
433 lk = next;
434 }
435}
static void xmlLinkDeallocator(xmlListPtr l, xmlLinkPtr lk)
Definition: list.c:59

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

◆ xmlListCopy()

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.

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)) {
771 return (1);
772 }
773 }
774 return (0);
775}
FxCollectionEntry * cur
void xmlListDelete(xmlListPtr l)
Definition: list.c:333
int xmlListInsert(xmlListPtr l, void *data)
Definition: list.c:273
xmlLinkPtr sentinel
Definition: list.c:40

Referenced by xmlListDup(), and xmlListMerge().

◆ xmlListCreate()

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.

189{
191 if (NULL == (l = (xmlListPtr )xmlMalloc( sizeof(xmlList)))) {
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)))) {
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}
#define compare
static int xmlLinkCompare(const void *data0, const void *data1)
Definition: list.c:79
#define memset(x, y, z)
Definition: compat.h:39
Definition: list.c:39
Definition: bug.cpp:8

Referenced by xmlAddRef(), and xmlListDup().

◆ xmlListDelete()

void xmlListDelete ( xmlListPtr  l)

xmlListDelete: @l: a list

Deletes the list and its associated data

Definition at line 333 of file list.c.

334{
335 if (l == NULL)
336 return;
337
339 xmlFree(l->sentinel);
340 xmlFree(l);
341}
void xmlListClear(xmlListPtr l)
Definition: list.c:422

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

◆ xmlListDup()

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.

733{
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}
xmlListPtr xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)
Definition: list.c:188
int xmlListCopy(xmlListPtr cur, const xmlListPtr old)
Definition: list.c:761
int(* linkCompare)(const void *, const void *)
Definition: list.c:42

Referenced by xmlListSort().

◆ xmlListEmpty()

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.

447{
448 if (l == NULL)
449 return(-1);
450 return (l->sentinel->next == l->sentinel);
451}

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

◆ xmlListEnd()

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.

479{
480 if (l == NULL)
481 return(NULL);
482 return (l->sentinel->prev);
483}

◆ xmlListFront()

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.

463{
464 if (l == NULL)
465 return(NULL);
466 return (l->sentinel->next);
467}

◆ xmlListHigherSearch()

static xmlLinkPtr xmlListHigherSearch ( xmlListPtr  l,
void data 
)
static

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

Definition at line 118 of file list.c.

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}

Referenced by xmlListAppend(), and xmlListLinkReverseSearch().

◆ xmlListInsert()

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.

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) {
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}
static xmlLinkPtr xmlListLowerSearch(xmlListPtr l, void *data)
Definition: list.c:98

Referenced by xmlListCopy().

◆ xmlListLinkReverseSearch()

static xmlLinkPtr xmlListLinkReverseSearch ( xmlListPtr  l,
void data 
)
static

xmlListLinkReverseSearch: @l: a list @data: a data

Search data in the list processing backward

Returns the link containing the data or NULL

Definition at line 163 of file list.c.

164{
165 xmlLinkPtr lk;
166 if (l == NULL)
167 return(NULL);
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}

Referenced by xmlListRemoveLast(), and xmlListReverseSearch().

◆ xmlListLinkSearch()

static xmlLinkPtr xmlListLinkSearch ( xmlListPtr  l,
void data 
)
static

xmlListSearch: @l: a list @data: a data

Search data in the list

Returns the link containing the data or NULL

Definition at line 138 of file list.c.

139{
140 xmlLinkPtr lk;
141 if (l == NULL)
142 return(NULL);
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}

Referenced by xmlListRemoveFirst(), and xmlListSearch().

◆ xmlListLowerSearch()

static xmlLinkPtr xmlListLowerSearch ( xmlListPtr  l,
void data 
)
static

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

Definition at line 98 of file list.c.

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}

Referenced by xmlListInsert(), and xmlListLinkSearch().

◆ xmlListMerge()

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.

718{
719 xmlListCopy(l1, l2);
720 xmlListClear(l2);
721}

Referenced by xmlListSort().

◆ xmlListPopBack()

void xmlListPopBack ( xmlListPtr  l)

xmlListPopBack: @l: a list

Removes the last element in the list

Definition at line 526 of file list.c.

527{
528 if(!xmlListEmpty(l))
529 xmlLinkDeallocator(l, l->sentinel->prev);
530}
int xmlListEmpty(xmlListPtr l)
Definition: list.c:446

◆ xmlListPopFront()

void xmlListPopFront ( xmlListPtr  l)

xmlListPopFront: @l: a list

Removes the first element in the list

Definition at line 513 of file list.c.

514{
515 if(!xmlListEmpty(l))
516 xmlLinkDeallocator(l, l->sentinel->next);
517}

◆ xmlListPushBack()

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.

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

◆ xmlListPushFront()

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.

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

◆ xmlListRemoveAll()

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.

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}
GLuint GLuint GLsizei count
Definition: gl.h:1545
int xmlListRemoveFirst(xmlListPtr l, void *data)
Definition: list.c:353

◆ xmlListRemoveFirst()

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.

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) {
363 return 1;
364 }
365 return 0;
366}
static xmlLinkPtr xmlListLinkSearch(xmlListPtr l, void *data)
Definition: list.c:138

Referenced by xmlListRemoveAll(), and xmlWalkRemoveRef().

◆ xmlListRemoveLast()

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.

379{
380 xmlLinkPtr lk;
381
382 if (l == NULL)
383 return(0);
384 /*Find the last instance of this data */
386 if (lk != NULL) {
388 return 1;
389 }
390 return 0;
391}
static xmlLinkPtr xmlListLinkReverseSearch(xmlListPtr l, void *data)
Definition: list.c:163

◆ xmlListReverse()

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.

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}

◆ xmlListReverseSearch()

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.

253{
254 xmlLinkPtr lk;
255 if (l == NULL)
256 return(NULL);
258 if (lk)
259 return (lk->data);
260 return NULL;
261}

◆ xmlListReverseWalk()

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.

697 {
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}
void user(int argc, const char *argv[])
Definition: cmds.c:1350

◆ xmlListSearch()

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.

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}

◆ xmlListSize()

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.

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}

◆ xmlListSort()

void xmlListSort ( xmlListPtr  l)

xmlListSort: @l: a list

Sort all the elements in the list

Definition at line 643 of file list.c.

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;
661 xmlListMerge(l, lTemp);
662 xmlListDelete(lTemp);
663 return;
664}
xmlListPtr xmlListDup(const xmlListPtr old)
Definition: list.c:732
void xmlListMerge(xmlListPtr l1, xmlListPtr l2)
Definition: list.c:717

◆ xmlListWalk()

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.

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

Referenced by xmlRemoveRef().