ReactOS 0.4.16-dev-340-g0540c21
list.c
Go to the documentation of this file.
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
32{
33 struct _xmlLink *next;
34 struct _xmlLink *prev;
35 void *data;
36};
37
39{
42 int (*linkCompare)(const void *, const void*);
43};
44
45/************************************************************************
46 * *
47 * Interfaces *
48 * *
49 ************************************************************************/
50
58static void
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
78static int
79xmlLinkCompare(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
97static xmlLinkPtr
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
117static xmlLinkPtr
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
137static xmlLinkPtr
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}
152
162static xmlLinkPtr
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}
177
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}
220
230void *
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
251void *
253{
254 xmlLinkPtr lk;
255 if (l == NULL)
256 return(NULL);
258 if (lk)
259 return (lk->data);
260 return NULL;
261}
262
272int
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}
295
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}
326
334{
335 if (l == NULL)
336 return;
337
339 xmlFree(l->sentinel);
340 xmlFree(l);
341}
342
352int
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}
367
377int
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}
392
402int
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
421void
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}
436
445int
447{
448 if (l == NULL)
449 return(-1);
450 return (l->sentinel->next == l->sentinel);
451}
452
463{
464 if (l == NULL)
465 return(NULL);
466 return (l->sentinel->next);
467}
468
479{
480 if (l == NULL)
481 return(NULL);
482 return (l->sentinel->prev);
483}
484
493int
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
512void
514{
515 if(!xmlListEmpty(l))
516 xmlLinkDeallocator(l, l->sentinel->next);
517}
518
525void
527{
528 if(!xmlListEmpty(l))
529 xmlLinkDeallocator(l, l->sentinel->prev);
530}
531
541int
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}
563
573int
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}
594
603void *
605{
606 if (lk == NULL)
607 return(NULL);
608 return lk->data;
609}
610
617void
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
642void
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}
665
675void
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
696void
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
716void
718{
719 xmlListCopy(l1, l2);
720 xmlListClear(l2);
721}
722
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}
750
760int
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}
776/* xmlListUnique() */
777/* xmlListSwap */
#define compare
void user(int argc, const char *argv[])
Definition: cmds.c:1350
r l[0]
Definition: byte_order.h:168
#define NULL
Definition: types.h:112
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
FxCollectionEntry * cur
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
static unsigned __int64 next
Definition: rand_nt.c:6
XMLPUBVAR xmlMallocFunc xmlMalloc
Definition: globals.h:248
XMLPUBVAR xmlFreeFunc xmlFree
Definition: globals.h:251
XMLPUBVAR void * xmlGenericErrorContext
Definition: globals.h:353
XMLPUBVAR xmlGenericErrorFunc xmlGenericError
Definition: globals.h:337
xmlLink * xmlLinkPtr
Definition: list.h:21
int(* xmlListWalker)(const void *data, void *user)
Definition: list.h:52
void(* xmlListDeallocator)(xmlLinkPtr lk)
Definition: list.h:32
int(* xmlListDataCompare)(const void *data0, const void *data1)
Definition: list.h:42
static xmlLinkPtr xmlListLinkSearch(xmlListPtr l, void *data)
Definition: list.c:138
int xmlListRemoveLast(xmlListPtr l, void *data)
Definition: list.c:378
void xmlListSort(xmlListPtr l)
Definition: list.c:643
void xmlListReverse(xmlListPtr l)
Definition: list.c:618
static xmlLinkPtr xmlListHigherSearch(xmlListPtr l, void *data)
Definition: list.c:118
void * xmlListReverseSearch(xmlListPtr l, void *data)
Definition: list.c:252
static void xmlLinkDeallocator(xmlListPtr l, xmlLinkPtr lk)
Definition: list.c:59
int xmlListEmpty(xmlListPtr l)
Definition: list.c:446
static int xmlLinkCompare(const void *data0, const void *data1)
Definition: list.c:79
xmlLinkPtr xmlListEnd(xmlListPtr l)
Definition: list.c:478
void xmlListWalk(xmlListPtr l, xmlListWalker walker, void *user)
Definition: list.c:676
void xmlListPopFront(xmlListPtr l)
Definition: list.c:513
void xmlListPopBack(xmlListPtr l)
Definition: list.c:526
int xmlListPushBack(xmlListPtr l, void *data)
Definition: list.c:574
void xmlListReverseWalk(xmlListPtr l, xmlListWalker walker, void *user)
Definition: list.c:697
xmlListPtr xmlListDup(const xmlListPtr old)
Definition: list.c:732
xmlLinkPtr xmlListFront(xmlListPtr l)
Definition: list.c:462
int xmlListAppend(xmlListPtr l, void *data)
Definition: list.c:305
void * xmlLinkGetData(xmlLinkPtr lk)
Definition: list.c:604
xmlListPtr xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)
Definition: list.c:188
int xmlListRemoveAll(xmlListPtr l, void *data)
Definition: list.c:403
void * xmlListSearch(xmlListPtr l, void *data)
Definition: list.c:231
void xmlListClear(xmlListPtr l)
Definition: list.c:422
int xmlListCopy(xmlListPtr cur, const xmlListPtr old)
Definition: list.c:761
int xmlListRemoveFirst(xmlListPtr l, void *data)
Definition: list.c:353
int xmlListPushFront(xmlListPtr l, void *data)
Definition: list.c:542
int xmlListSize(xmlListPtr l)
Definition: list.c:494
void xmlListDelete(xmlListPtr l)
Definition: list.c:333
void xmlListMerge(xmlListPtr l1, xmlListPtr l2)
Definition: list.c:717
static xmlLinkPtr xmlListLowerSearch(xmlListPtr l, void *data)
Definition: list.c:98
int xmlListInsert(xmlListPtr l, void *data)
Definition: list.c:273
static xmlLinkPtr xmlListLinkReverseSearch(xmlListPtr l, void *data)
Definition: list.c:163
#define memset(x, y, z)
Definition: compat.h:39
Definition: list.c:39
int(* linkCompare)(const void *, const void *)
Definition: list.c:42
xmlLinkPtr sentinel
Definition: list.c:40
void(* linkDeallocator)(xmlLinkPtr)
Definition: list.c:41
Definition: bug.cpp:8
Definition: tftpd.h:126