ReactOS  0.4.14-dev-815-ge410a12
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  * 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 {
42  int (*linkCompare)(const void *, const void*);
43 };
44 
45 /************************************************************************
46  * *
47  * Interfaces *
48  * *
49  ************************************************************************/
50 
58 static 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 
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 
97 static 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 
117 static 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 
137 static xmlLinkPtr
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 
162 static xmlLinkPtr
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 
189 {
190  xmlListPtr l;
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 
230 void *
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 
251 void *
253 {
254  xmlLinkPtr lk;
255  if (l == NULL)
256  return(NULL);
258  if (lk)
259  return (lk->data);
260  return NULL;
261 }
262 
272 int
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 
338  xmlListClear(l);
339  xmlFree(l->sentinel);
340  xmlFree(l);
341 }
342 
352 int
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 
377 int
379 {
380  xmlLinkPtr lk;
381 
382  if (l == NULL)
383  return(0);
384  /*Find the last instance of this data */
386  if (lk != NULL) {
387  xmlLinkDeallocator(l, lk);
388  return 1;
389  }
390  return 0;
391 }
392 
402 int
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 
421 void
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 
445 int
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 
493 int
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 
512 void
514 {
515  if(!xmlListEmpty(l))
516  xmlLinkDeallocator(l, l->sentinel->next);
517 }
518 
525 void
527 {
528  if(!xmlListEmpty(l))
529  xmlLinkDeallocator(l, l->sentinel->prev);
530 }
531 
541 int
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 
573 int
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 
603 void *
605 {
606  if (lk == NULL)
607  return(NULL);
608  return lk->data;
609 }
610 
617 void
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 
642 void
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 
675 void
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 
696 void
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 
716 void
718 {
719  xmlListCopy(l1, l2);
720  xmlListClear(l2);
721 }
722 
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 
760 int
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"
void * xmlListSearch(xmlListPtr l, void *data)
Definition: list.c:231
void xmlListClear(xmlListPtr l)
Definition: list.c:422
Definition: bug.cpp:7
void(* linkDeallocator)(xmlLinkPtr)
Definition: list.c:41
int xmlListSize(xmlListPtr l)
Definition: list.c:494
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
Definition: typeof.h:49
void xmlListSort(xmlListPtr l)
Definition: list.c:643
void xmlListReverseWalk(xmlListPtr l, xmlListWalker walker, void *user)
Definition: list.c:697
static void xmlLinkDeallocator(xmlListPtr l, xmlLinkPtr lk)
Definition: list.c:59
static xmlLinkPtr xmlListLinkReverseSearch(xmlListPtr l, void *data)
Definition: list.c:163
GLuint GLuint GLsizei count
Definition: gl.h:1545
int(* xmlListDataCompare)(const void *data0, const void *data1)
Definition: list.h:42
static xmlLinkPtr xmlListLowerSearch(xmlListPtr l, void *data)
Definition: list.c:98
int(* xmlListWalker)(const void *data, void *user)
Definition: list.h:52
Definition: tftpd.h:125
int xmlListRemoveAll(xmlListPtr l, void *data)
Definition: list.c:403
int xmlListEmpty(xmlListPtr l)
Definition: list.c:446
int xmlListPushBack(xmlListPtr l, void *data)
Definition: list.c:574
int xmlListInsert(xmlListPtr l, void *data)
Definition: list.c:273
void xmlListReverse(xmlListPtr l)
Definition: list.c:618
void xmlListPopFront(xmlListPtr l)
Definition: list.c:513
void * xmlLinkGetData(xmlLinkPtr lk)
Definition: list.c:604
XMLPUBVAR xmlGenericErrorFunc xmlGenericError
Definition: globals.h:346
xmlListPtr xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)
Definition: list.c:188
int xmlListCopy(xmlListPtr cur, const xmlListPtr old)
Definition: list.c:761
smooth NULL
Definition: ftsmooth.c:416
xmlLinkPtr xmlListFront(xmlListPtr l)
Definition: list.c:462
r l[0]
Definition: byte_order.h:167
static xmlLinkPtr xmlListHigherSearch(xmlListPtr l, void *data)
Definition: list.c:118
void xmlListMerge(xmlListPtr l1, xmlListPtr l2)
Definition: list.c:717
int xmlListAppend(xmlListPtr l, void *data)
Definition: list.c:305
static xmlLinkPtr xmlListLinkSearch(xmlListPtr l, void *data)
Definition: list.c:138
XMLPUBVAR xmlFreeFunc xmlFree
Definition: globals.h:250
xmlLink * xmlLinkPtr
Definition: list.h:21
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
xmlLinkPtr sentinel
Definition: list.c:40
int xmlListRemoveLast(xmlListPtr l, void *data)
Definition: list.c:378
void * xmlListReverseSearch(xmlListPtr l, void *data)
Definition: list.c:252
xmlLinkPtr xmlListEnd(xmlListPtr l)
Definition: list.c:478
int(* linkCompare)(const void *, const void *)
Definition: list.c:42
int xmlListPushFront(xmlListPtr l, void *data)
Definition: list.c:542
void xmlListDelete(xmlListPtr l)
Definition: list.c:333
void xmlListWalk(xmlListPtr l, xmlListWalker walker, void *user)
Definition: list.c:676
void xmlListPopBack(xmlListPtr l)
Definition: list.c:526
static unsigned __int64 next
Definition: rand_nt.c:6
int xmlListRemoveFirst(xmlListPtr l, void *data)
Definition: list.c:353
Definition: list.c:38
xmlListPtr xmlListDup(const xmlListPtr old)
Definition: list.c:732
XMLPUBVAR xmlMallocFunc xmlMalloc
Definition: globals.h:247
static int xmlLinkCompare(const void *data0, const void *data1)
Definition: list.c:79
#define compare
void(* xmlListDeallocator)(xmlLinkPtr lk)
Definition: list.h:32
#define memset(x, y, z)
Definition: compat.h:39
void user(int argc, const char *argv[])
Definition: cmds.c:1350
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
XMLPUBVAR void * xmlGenericErrorContext
Definition: globals.h:362