blob: d33d92818a52006d288751fdefbb11f2169e637f [file] [log] [blame]
Owen Taylor3473f882001-02-23 17:55:21 +00001/*
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
Daniel Veillard34ce8be2002-03-18 19:37:11 +000018#define IN_LIBXML
Bjorn Reese70a9da52001-04-21 16:57:29 +000019#include "libxml.h"
Owen Taylor3473f882001-02-23 17:55:21 +000020
21#include <stdlib.h>
22#include <string.h>
23#include <libxml/xmlmemory.h>
24#include <libxml/list.h>
Daniel Veillard3c01b1d2001-10-17 15:58:35 +000025#include <libxml/globals.h>
Owen Taylor3473f882001-02-23 17:55:21 +000026
27/*
28 * Type definition are kept internal
29 */
30
31struct _xmlLink
32{
33 struct _xmlLink *next;
34 struct _xmlLink *prev;
35 void *data;
36};
37
38struct _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 */
58static void
59xmlLinkDeallocator(xmlListPtr l, xmlLinkPtr lk)
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
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 */
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
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 */
Daniel Veillardf8e3db02012-09-11 13:26:36 +080097static xmlLinkPtr
98xmlListLowerSearch(xmlListPtr l, void *data)
Owen Taylor3473f882001-02-23 17:55:21 +000099{
100 xmlLinkPtr lk;
101
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000102 if (l == NULL)
103 return(NULL);
Owen Taylor3473f882001-02-23 17:55:21 +0000104 for(lk = l->sentinel->next;lk != l->sentinel && l->linkCompare(lk->data, data) <0 ;lk = lk->next);
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800105 return lk;
Owen Taylor3473f882001-02-23 17:55:21 +0000106}
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 */
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800117static xmlLinkPtr
118xmlListHigherSearch(xmlListPtr l, void *data)
Owen Taylor3473f882001-02-23 17:55:21 +0000119{
120 xmlLinkPtr lk;
121
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000122 if (l == NULL)
123 return(NULL);
Owen Taylor3473f882001-02-23 17:55:21 +0000124 for(lk = l->sentinel->prev;lk != l->sentinel && l->linkCompare(lk->data, data) >0 ;lk = lk->prev);
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800125 return lk;
Owen Taylor3473f882001-02-23 17:55:21 +0000126}
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 */
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800137static xmlLinkPtr
138xmlListLinkSearch(xmlListPtr l, void *data)
Owen Taylor3473f882001-02-23 17:55:21 +0000139{
140 xmlLinkPtr lk;
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000141 if (l == NULL)
142 return(NULL);
Owen Taylor3473f882001-02-23 17:55:21 +0000143 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
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 */
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800162static xmlLinkPtr
163xmlListLinkReverseSearch(xmlListPtr l, void *data)
Owen Taylor3473f882001-02-23 17:55:21 +0000164{
165 xmlLinkPtr lk;
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000166 if (l == NULL)
167 return(NULL);
Owen Taylor3473f882001-02-23 17:55:21 +0000168 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
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 */
187xmlListPtr
188xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)
189{
190 xmlListPtr l;
191 if (NULL == (l = (xmlListPtr )xmlMalloc( sizeof(xmlList)))) {
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800192 xmlGenericError(xmlGenericErrorContext,
Daniel Veillard3487c8d2002-09-05 11:33:25 +0000193 "Cannot initialize memory for list");
Owen Taylor3473f882001-02-23 17:55:21 +0000194 return (NULL);
195 }
196 /* Initialize the list to NULL */
197 memset(l, 0, sizeof(xmlList));
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800198
Owen Taylor3473f882001-02-23 17:55:21 +0000199 /* Add the sentinel */
200 if (NULL ==(l->sentinel = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800201 xmlGenericError(xmlGenericErrorContext,
Daniel Veillard3487c8d2002-09-05 11:33:25 +0000202 "Cannot initialize memory for sentinel");
Owen Taylor3473f882001-02-23 17:55:21 +0000203 xmlFree(l);
204 return (NULL);
205 }
206 l->sentinel->next = l->sentinel;
207 l->sentinel->prev = l->sentinel;
208 l->sentinel->data = NULL;
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800209
Owen Taylor3473f882001-02-23 17:55:21 +0000210 /* 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}
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800220
Owen Taylor3473f882001-02-23 17:55:21 +0000221/**
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 */
230void *
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800231xmlListSearch(xmlListPtr l, void *data)
Owen Taylor3473f882001-02-23 17:55:21 +0000232{
233 xmlLinkPtr lk;
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000234 if (l == NULL)
235 return(NULL);
Owen Taylor3473f882001-02-23 17:55:21 +0000236 lk = xmlListLinkSearch(l, data);
237 if (lk)
238 return (lk->data);
239 return NULL;
240}
241
242/**
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000243 * xmlListReverseSearch:
Owen Taylor3473f882001-02-23 17:55:21 +0000244 * @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 */
251void *
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800252xmlListReverseSearch(xmlListPtr l, void *data)
Owen Taylor3473f882001-02-23 17:55:21 +0000253{
254 xmlLinkPtr lk;
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000255 if (l == NULL)
256 return(NULL);
Owen Taylor3473f882001-02-23 17:55:21 +0000257 lk = xmlListLinkReverseSearch(l, data);
258 if (lk)
259 return (lk->data);
260 return NULL;
261}
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 */
272int
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800273xmlListInsert(xmlListPtr l, void *data)
Owen Taylor3473f882001-02-23 17:55:21 +0000274{
275 xmlLinkPtr lkPlace, lkNew;
276
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000277 if (l == NULL)
278 return(1);
Owen Taylor3473f882001-02-23 17:55:21 +0000279 lkPlace = xmlListLowerSearch(l, data);
280 /* Add the new link */
281 lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
282 if (lkNew == NULL) {
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800283 xmlGenericError(xmlGenericErrorContext,
Daniel Veillard3487c8d2002-09-05 11:33:25 +0000284 "Cannot initialize memory for new link");
Owen Taylor3473f882001-02-23 17:55:21 +0000285 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
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 */
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800305int xmlListAppend(xmlListPtr l, void *data)
Owen Taylor3473f882001-02-23 17:55:21 +0000306{
307 xmlLinkPtr lkPlace, lkNew;
308
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000309 if (l == NULL)
310 return(1);
Owen Taylor3473f882001-02-23 17:55:21 +0000311 lkPlace = xmlListHigherSearch(l, data);
312 /* Add the new link */
313 lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
314 if (lkNew == NULL) {
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800315 xmlGenericError(xmlGenericErrorContext,
Daniel Veillard3487c8d2002-09-05 11:33:25 +0000316 "Cannot initialize memory for new link");
Daniel Veillardf6cf57a2007-05-09 23:53:30 +0000317 return (1);
Owen Taylor3473f882001-02-23 17:55:21 +0000318 }
319 lkNew->data = data;
320 lkNew->next = lkPlace->next;
321 (lkPlace->next)->prev = lkNew;
322 lkPlace->next = lkNew;
323 lkNew->prev = lkPlace;
Daniel Veillardf6cf57a2007-05-09 23:53:30 +0000324 return 0;
Owen Taylor3473f882001-02-23 17:55:21 +0000325}
326
327/**
328 * xmlListDelete:
329 * @l: a list
330 *
331 * Deletes the list and its associated data
332 */
333void xmlListDelete(xmlListPtr l)
334{
Daniel Veillarde43cc572004-11-03 11:50:29 +0000335 if (l == NULL)
336 return;
337
Owen Taylor3473f882001-02-23 17:55:21 +0000338 xmlListClear(l);
339 xmlFree(l->sentinel);
340 xmlFree(l);
341}
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 occured, or 0 if not found
351 */
352int
353xmlListRemoveFirst(xmlListPtr l, void *data)
354{
355 xmlLinkPtr lk;
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800356
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000357 if (l == NULL)
358 return(0);
Owen Taylor3473f882001-02-23 17:55:21 +0000359 /*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
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 occured, or 0 if not found
376 */
377int
378xmlListRemoveLast(xmlListPtr l, void *data)
379{
380 xmlLinkPtr lk;
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800381
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000382 if (l == NULL)
383 return(0);
Owen Taylor3473f882001-02-23 17:55:21 +0000384 /*Find the last instance of this data */
385 lk = xmlListLinkReverseSearch(l, data);
386 if (lk != NULL) {
387 xmlLinkDeallocator(l, lk);
388 return 1;
389 }
390 return 0;
391}
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 */
402int
403xmlListRemoveAll(xmlListPtr l, void *data)
404{
405 int count=0;
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800406
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000407 if (l == NULL)
408 return(0);
Owen Taylor3473f882001-02-23 17:55:21 +0000409
410 while(xmlListRemoveFirst(l, data))
411 count++;
412 return count;
413}
414
415/**
416 * xmlListClear:
417 * @l: a list
418 *
419 * Remove the all data in the list
420 */
421void
422xmlListClear(xmlListPtr l)
423{
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000424 xmlLinkPtr lk;
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800425
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000426 if (l == NULL)
427 return;
428 lk = l->sentinel->next;
Owen Taylor3473f882001-02-23 17:55:21 +0000429 while(lk != l->sentinel) {
430 xmlLinkPtr next = lk->next;
431
432 xmlLinkDeallocator(l, lk);
433 lk = next;
434 }
435}
436
437/**
438 * xmlListEmpty:
439 * @l: a list
440 *
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000441 * Is the list empty ?
442 *
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000443 * Returns 1 if the list is empty, 0 if not empty and -1 in case of error
Owen Taylor3473f882001-02-23 17:55:21 +0000444 */
445int
446xmlListEmpty(xmlListPtr l)
447{
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000448 if (l == NULL)
449 return(-1);
Owen Taylor3473f882001-02-23 17:55:21 +0000450 return (l->sentinel->next == l->sentinel);
451}
452
453/**
454 * xmlListFront:
455 * @l: a list
456 *
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000457 * Get the first element in the list
458 *
Owen Taylor3473f882001-02-23 17:55:21 +0000459 * Returns the first element in the list, or NULL
460 */
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800461xmlLinkPtr
Owen Taylor3473f882001-02-23 17:55:21 +0000462xmlListFront(xmlListPtr l)
463{
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000464 if (l == NULL)
465 return(NULL);
Owen Taylor3473f882001-02-23 17:55:21 +0000466 return (l->sentinel->next);
467}
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800468
Owen Taylor3473f882001-02-23 17:55:21 +0000469/**
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000470 * xmlListEnd:
Owen Taylor3473f882001-02-23 17:55:21 +0000471 * @l: a list
472 *
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000473 * Get the last element in the list
474 *
Owen Taylor3473f882001-02-23 17:55:21 +0000475 * Returns the last element in the list, or NULL
476 */
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800477xmlLinkPtr
Owen Taylor3473f882001-02-23 17:55:21 +0000478xmlListEnd(xmlListPtr l)
479{
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000480 if (l == NULL)
481 return(NULL);
Owen Taylor3473f882001-02-23 17:55:21 +0000482 return (l->sentinel->prev);
483}
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800484
Owen Taylor3473f882001-02-23 17:55:21 +0000485/**
486 * xmlListSize:
487 * @l: a list
488 *
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000489 * Get the number of elements in the list
490 *
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000491 * Returns the number of elements in the list or -1 in case of error
Owen Taylor3473f882001-02-23 17:55:21 +0000492 */
493int
494xmlListSize(xmlListPtr l)
495{
496 xmlLinkPtr lk;
497 int count=0;
498
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000499 if (l == NULL)
500 return(-1);
Owen Taylor3473f882001-02-23 17:55:21 +0000501 /* 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
506/**
507 * xmlListPopFront:
508 * @l: a list
509 *
510 * Removes the first element in the list
511 */
512void
513xmlListPopFront(xmlListPtr l)
514{
515 if(!xmlListEmpty(l))
516 xmlLinkDeallocator(l, l->sentinel->next);
517}
518
519/**
520 * xmlListPopBack:
521 * @l: a list
522 *
523 * Removes the last element in the list
524 */
525void
526xmlListPopBack(xmlListPtr l)
527{
528 if(!xmlListEmpty(l))
529 xmlLinkDeallocator(l, l->sentinel->prev);
530}
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 */
541int
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800542xmlListPushFront(xmlListPtr l, void *data)
Owen Taylor3473f882001-02-23 17:55:21 +0000543{
544 xmlLinkPtr lkPlace, lkNew;
545
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000546 if (l == NULL)
547 return(0);
Owen Taylor3473f882001-02-23 17:55:21 +0000548 lkPlace = l->sentinel;
549 /* Add the new link */
550 lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
551 if (lkNew == NULL) {
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800552 xmlGenericError(xmlGenericErrorContext,
Daniel Veillard3487c8d2002-09-05 11:33:25 +0000553 "Cannot initialize memory for new link");
Owen Taylor3473f882001-02-23 17:55:21 +0000554 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
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 */
573int
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800574xmlListPushBack(xmlListPtr l, void *data)
Owen Taylor3473f882001-02-23 17:55:21 +0000575{
576 xmlLinkPtr lkPlace, lkNew;
577
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000578 if (l == NULL)
579 return(0);
Owen Taylor3473f882001-02-23 17:55:21 +0000580 lkPlace = l->sentinel->prev;
581 /* Add the new link */
582 if (NULL ==(lkNew = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800583 xmlGenericError(xmlGenericErrorContext,
Daniel Veillard3487c8d2002-09-05 11:33:25 +0000584 "Cannot initialize memory for new link");
Owen Taylor3473f882001-02-23 17:55:21 +0000585 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
595/**
596 * xmlLinkGetData:
597 * @lk: a link
598 *
599 * See Returns.
600 *
601 * Returns a pointer to the data referenced from this link
602 */
603void *
604xmlLinkGetData(xmlLinkPtr lk)
605{
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000606 if (lk == NULL)
607 return(NULL);
Owen Taylor3473f882001-02-23 17:55:21 +0000608 return lk->data;
609}
610
611/**
612 * xmlListReverse:
613 * @l: a list
614 *
615 * Reverse the order of the elements in the list
616 */
617void
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000618xmlListReverse(xmlListPtr l)
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 */
Owen Taylor3473f882001-02-23 17:55:21 +0000632 lkPrev->next = lkPrev->prev;
633 lkPrev->prev = lk;
Owen Taylor3473f882001-02-23 17:55:21 +0000634}
635
636/**
637 * xmlListSort:
638 * @l: a list
639 *
640 * Sort all the elements in the list
641 */
642void
643xmlListSort(xmlListPtr l)
644{
645 xmlListPtr lTemp;
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800646
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000647 if (l == NULL)
648 return;
Owen Taylor3473f882001-02-23 17:55:21 +0000649 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
666/**
667 * xmlListWalk:
668 * @l: a list
669 * @walker: a processing function
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000670 * @user: a user parameter passed to the walker function
Owen Taylor3473f882001-02-23 17:55:21 +0000671 *
672 * Walk all the element of the first from first to last and
673 * apply the walker function to it
674 */
675void
676xmlListWalk(xmlListPtr l, xmlListWalker walker, const void *user) {
677 xmlLinkPtr lk;
678
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000679 if ((l == NULL) || (walker == NULL))
680 return;
Owen Taylor3473f882001-02-23 17:55:21 +0000681 for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
682 if((walker(lk->data, user)) == 0)
683 break;
684 }
685}
686
687/**
688 * xmlListReverseWalk:
689 * @l: a list
690 * @walker: a processing function
Daniel Veillard5e2dace2001-07-18 19:30:27 +0000691 * @user: a user parameter passed to the walker function
Owen Taylor3473f882001-02-23 17:55:21 +0000692 *
693 * Walk all the element of the list in reverse order and
694 * apply the walker function to it
695 */
696void
697xmlListReverseWalk(xmlListPtr l, xmlListWalker walker, const void *user) {
698 xmlLinkPtr lk;
699
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000700 if ((l == NULL) || (walker == NULL))
701 return;
Owen Taylor3473f882001-02-23 17:55:21 +0000702 for(lk = l->sentinel->prev; lk != l->sentinel; lk = lk->prev) {
703 if((walker(lk->data, user)) == 0)
704 break;
705 }
706}
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 */
716void
717xmlListMerge(xmlListPtr l1, xmlListPtr l2)
718{
719 xmlListCopy(l1, l2);
720 xmlListClear(l2);
721}
722
723/**
724 * xmlListDup:
725 * @old: the list
726 *
727 * Duplicate the list
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800728 *
Owen Taylor3473f882001-02-23 17:55:21 +0000729 * Returns a new copy of the list or NULL in case of error
730 */
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800731xmlListPtr
Owen Taylor3473f882001-02-23 17:55:21 +0000732xmlListDup(const xmlListPtr old)
733{
734 xmlListPtr cur;
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000735
736 if (old == NULL)
737 return(NULL);
Owen Taylor3473f882001-02-23 17:55:21 +0000738 /* 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
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
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800757 *
Owen Taylor3473f882001-02-23 17:55:21 +0000758 * Returns 0 in case of success 1 in case of error
759 */
760int
761xmlListCopy(xmlListPtr cur, const xmlListPtr old)
762{
763 /* Walk the old tree and insert the data into the new one */
764 xmlLinkPtr lk;
765
Daniel Veillardd005b9e2004-11-03 17:07:05 +0000766 if ((old == NULL) || (cur == NULL))
767 return(1);
Owen Taylor3473f882001-02-23 17:55:21 +0000768 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 }
Daniel Veillardf8e3db02012-09-11 13:26:36 +0800774 return (0);
Owen Taylor3473f882001-02-23 17:55:21 +0000775}
776/* xmlListUnique() */
777/* xmlListSwap */
Daniel Veillard5d4644e2005-04-01 13:11:58 +0000778#define bottom_list
779#include "elfgcchack.h"