src/external/3rd/library/libxml/list.c

   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 {
  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  */
  58 static void
  59 xmlLinkDeallocator(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  */
  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
  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  */
  97 static xmlLinkPtr
  98 xmlListLowerSearch(xmlListPtr l, void *data)
  99 {
 100     xmlLinkPtr lk;
 101
 102     for(lk = l->sentinel->next;lk != l->sentinel && l->linkCompare(lk->data, data) <0 ;lk = lk->next);
 103     return lk;
 104 }
 105
 106 /**
 107  * xmlListHigherSearch:
 108  * @l:  a list
 109  * @data:  a data
 110  *
 111  * Search data in the ordered list walking backward from the end
 112  *
 113  * Returns the link containing the data or NULL
 114  */
 115 static xmlLinkPtr
 116 xmlListHigherSearch(xmlListPtr l, void *data)
 117 {
 118     xmlLinkPtr lk;
 119
 120     for(lk = l->sentinel->prev;lk != l->sentinel && l->linkCompare(lk->data, data) >0 ;lk = lk->prev);
 121     return lk;
 122 }
 123
 124 /**
 125  * xmlListSearch:
 126  * @l:  a list
 127  * @data:  a data
 128  *
 129  * Search data in the list
 130  *
 131  * Returns the link containing the data or NULL
 132  */
 133 static xmlLinkPtr
 134 xmlListLinkSearch(xmlListPtr l, void *data)
 135 {
 136     xmlLinkPtr lk;
 137     lk = xmlListLowerSearch(l, data);
 138     if (lk == l->sentinel)
 139         return NULL;
 140     else {
 141         if (l->linkCompare(lk->data, data) ==0)
 142             return lk;
 143         return NULL;
 144     }
 145 }
 146
 147 /**
 148  * xmlListLinkReverseSearch:
 149  * @l:  a list
 150  * @data:  a data
 151  *
 152  * Search data in the list processing backward
 153  *
 154  * Returns the link containing the data or NULL
 155  */
 156 static xmlLinkPtr
 157 xmlListLinkReverseSearch(xmlListPtr l, void *data)
 158 {
 159     xmlLinkPtr lk;
 160     lk = xmlListHigherSearch(l, data);
 161     if (lk == l->sentinel)
 162         return NULL;
 163     else {
 164         if (l->linkCompare(lk->data, data) ==0)
 165             return lk;
 166         return NULL;
 167     }
 168 }
 169
 170 /**
 171  * xmlListCreate:
 172  * @deallocator:  an optional deallocator function
 173  * @compare:  an optional comparison function
 174  *
 175  * Create a new list
 176  *
 177  * Returns the new list or NULL in case of error
 178  */
 179 xmlListPtr
 180 xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)
 181 {
 182     xmlListPtr l;
 183     if (NULL == (l = (xmlListPtr )xmlMalloc( sizeof(xmlList)))) {
 184         xmlGenericError(xmlGenericErrorContext,
 185                         "Cannot initialize memory for list");
 186         return (NULL);
 187     }
 188     /* Initialize the list to NULL */
 189     memset(l, 0, sizeof(xmlList));
 190
 191     /* Add the sentinel */
 192     if (NULL ==(l->sentinel = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
 193         xmlGenericError(xmlGenericErrorContext,
 194                         "Cannot initialize memory for sentinel");
 195         xmlFree(l);
 196         return (NULL);
 197     }
 198     l->sentinel->next = l->sentinel;
 199     l->sentinel->prev = l->sentinel;
 200     l->sentinel->data = NULL;
 201
 202     /* If there is a link deallocator, use it */
 203     if (deallocator != NULL)
 204         l->linkDeallocator = deallocator;
 205     /* If there is a link comparator, use it */
 206     if (compare != NULL)
 207         l->linkCompare = compare;
 208     else /* Use our own */
 209         l->linkCompare = xmlLinkCompare;
 210     return l;
 211 }
 212
 213 /**
 214  * xmlListSearch:
 215  * @l:  a list
 216  * @data:  a search value
 217  *
 218  * Search the list for an existing value of @data
 219  *
 220  * Returns the value associated to @data or NULL in case of error
 221  */
 222 void *
 223 xmlListSearch(xmlListPtr l, void *data)
 224 {
 225     xmlLinkPtr lk;
 226     lk = xmlListLinkSearch(l, data);
 227     if (lk)
 228         return (lk->data);
 229     return NULL;
 230 }
 231
 232 /**
 233  * xmlListReverseSearch:
 234  * @l:  a list
 235  * @data:  a search value
 236  *
 237  * Search the list in reverse order for an existing value of @data
 238  *
 239  * Returns the value associated to @data or NULL in case of error
 240  */
 241 void *
 242 xmlListReverseSearch(xmlListPtr l, void *data)
 243 {
 244     xmlLinkPtr lk;
 245     lk = xmlListLinkReverseSearch(l, data);
 246     if (lk)
 247         return (lk->data);
 248     return NULL;
 249 }
 250
 251 /**
 252  * xmlListInsert:
 253  * @l:  a list
 254  * @data:  the data
 255  *
 256  * Insert data in the ordered list at the beginning for this value
 257  *
 258  * Returns 0 in case of success, 1 in case of failure
 259  */
 260 int
 261 xmlListInsert(xmlListPtr l, void *data)
 262 {
 263     xmlLinkPtr lkPlace, lkNew;
 264
 265     lkPlace = xmlListLowerSearch(l, data);
 266     /* Add the new link */
 267     lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
 268     if (lkNew == NULL) {
 269         xmlGenericError(xmlGenericErrorContext,
 270                         "Cannot initialize memory for new link");
 271         return (1);
 272     }
 273     lkNew->data = data;
 274     lkPlace = lkPlace->prev;
 275     lkNew->next = lkPlace->next;
 276     (lkPlace->next)->prev = lkNew;
 277     lkPlace->next = lkNew;
 278     lkNew->prev = lkPlace;
 279     return 0;
 280 }
 281
 282 /**
 283  * xmlListAppend:
 284  * @l:  a list
 285  * @data:  the data
 286  *
 287  * Insert data in the ordered list at the end for this value
 288  *
 289  * Returns 0 in case of success, 1 in case of failure
 290  */
 291 int xmlListAppend(xmlListPtr l, void *data)
 292 {
 293     xmlLinkPtr lkPlace, lkNew;
 294
 295     lkPlace = xmlListHigherSearch(l, data);
 296     /* Add the new link */
 297     lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
 298     if (lkNew == NULL) {
 299         xmlGenericError(xmlGenericErrorContext,
 300                         "Cannot initialize memory for new link");
 301         return (0);
 302     }
 303     lkNew->data = data;
 304     lkNew->next = lkPlace->next;
 305     (lkPlace->next)->prev = lkNew;
 306     lkPlace->next = lkNew;
 307     lkNew->prev = lkPlace;
 308     return 1;
 309 }
 310
 311 /**
 312  * xmlListDelete:
 313  * @l:  a list
 314  *
 315  * Deletes the list and its associated data
 316  */
 317 void xmlListDelete(xmlListPtr l)
 318 {
 319     xmlListClear(l);
 320     xmlFree(l->sentinel);
 321     xmlFree(l);
 322 }
 323
 324 /**
 325  * xmlListRemoveFirst:
 326  * @l:  a list
 327  * @data:  list data
 328  *
 329  * Remove the first instance associated to data in the list
 330  *
 331  * Returns 1 if a deallocation occured, or 0 if not found
 332  */
 333 int
 334 xmlListRemoveFirst(xmlListPtr l, void *data)
 335 {
 336     xmlLinkPtr lk;
 337
 338     /*Find the first instance of this data */
 339     lk = xmlListLinkSearch(l, data);
 340     if (lk != NULL) {
 341         xmlLinkDeallocator(l, lk);
 342         return 1;
 343     }
 344     return 0;
 345 }
 346
 347 /**
 348  * xmlListRemoveLast:
 349  * @l:  a list
 350  * @data:  list data
 351  *
 352  * Remove the last instance associated to data in the list
 353  *
 354  * Returns 1 if a deallocation occured, or 0 if not found
 355  */
 356 int
 357 xmlListRemoveLast(xmlListPtr l, void *data)
 358 {
 359     xmlLinkPtr lk;
 360
 361     /*Find the last instance of this data */
 362     lk = xmlListLinkReverseSearch(l, data);
 363     if (lk != NULL) {
 364         xmlLinkDeallocator(l, lk);
 365         return 1;
 366     }
 367     return 0;
 368 }
 369
 370 /**
 371  * xmlListRemoveAll:
 372  * @l:  a list
 373  * @data:  list data
 374  *
 375  * Remove the all instance associated to data in the list
 376  *
 377  * Returns the number of deallocation, or 0 if not found
 378  */
 379 int
 380 xmlListRemoveAll(xmlListPtr l, void *data)
 381 {
 382     int count=0;
 383
 384
 385     while(xmlListRemoveFirst(l, data))
 386         count++;
 387     return count;
 388 }
 389
 390 /**
 391  * xmlListClear:
 392  * @l:  a list
 393  *
 394  * Remove the all data in the list
 395  */
 396 void
 397 xmlListClear(xmlListPtr l)
 398 {
 399     xmlLinkPtr  lk = l->sentinel->next;
 400
 401     while(lk != l->sentinel) {
 402         xmlLinkPtr next = lk->next;
 403
 404         xmlLinkDeallocator(l, lk);
 405         lk = next;
 406     }
 407 }
 408
 409 /**
 410  * xmlListEmpty:
 411  * @l:  a list
 412  *
 413  * Is the list empty ?
 414  *
 415  * Returns 1 if the list is empty, 0 otherwise
 416  */
 417 int
 418 xmlListEmpty(xmlListPtr l)
 419 {
 420     return (l->sentinel->next == l->sentinel);
 421 }
 422
 423 /**
 424  * xmlListFront:
 425  * @l:  a list
 426  *
 427  * Get the first element in the list
 428  *
 429  * Returns the first element in the list, or NULL
 430  */
 431 xmlLinkPtr
 432 xmlListFront(xmlListPtr l)
 433 {
 434     return (l->sentinel->next);
 435 }
 436
 437 /**
 438  * xmlListEnd:
 439  * @l:  a list
 440  *
 441  * Get the last element in the list
 442  *
 443  * Returns the last element in the list, or NULL
 444  */
 445 xmlLinkPtr
 446 xmlListEnd(xmlListPtr l)
 447 {
 448     return (l->sentinel->prev);
 449 }
 450
 451 /**
 452  * xmlListSize:
 453  * @l:  a list
 454  *
 455  * Get the number of elements in the list
 456  *
 457  * Returns the number of elements in the list
 458  */
 459 int
 460 xmlListSize(xmlListPtr l)
 461 {
 462     xmlLinkPtr lk;
 463     int count=0;
 464
 465     /* TODO: keep a counter in xmlList instead */
 466     for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next, count++);
 467     return count;
 468 }
 469
 470 /**
 471  * xmlListPopFront:
 472  * @l:  a list
 473  *
 474  * Removes the first element in the list
 475  */
 476 void
 477 xmlListPopFront(xmlListPtr l)
 478 {
 479     if(!xmlListEmpty(l))
 480         xmlLinkDeallocator(l, l->sentinel->next);
 481 }
 482
 483 /**
 484  * xmlListPopBack:
 485  * @l:  a list
 486  *
 487  * Removes the last element in the list
 488  */
 489 void
 490 xmlListPopBack(xmlListPtr l)
 491 {
 492     if(!xmlListEmpty(l))
 493         xmlLinkDeallocator(l, l->sentinel->prev);
 494 }
 495
 496 /**
 497  * xmlListPushFront:
 498  * @l:  a list
 499  * @data:  new data
 500  *
 501  * add the new data at the beginning of the list
 502  *
 503  * Returns 1 if successful, 0 otherwise
 504  */
 505 int
 506 xmlListPushFront(xmlListPtr l, void *data)
 507 {
 508     xmlLinkPtr lkPlace, lkNew;
 509
 510     lkPlace = l->sentinel;
 511     /* Add the new link */
 512     lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
 513     if (lkNew == NULL) {
 514         xmlGenericError(xmlGenericErrorContext,
 515                         "Cannot initialize memory for new link");
 516         return (0);
 517     }
 518     lkNew->data = data;
 519     lkNew->next = lkPlace->next;
 520     (lkPlace->next)->prev = lkNew;
 521     lkPlace->next = lkNew;
 522     lkNew->prev = lkPlace;
 523     return 1;
 524 }
 525
 526 /**
 527  * xmlListPushBack:
 528  * @l:  a list
 529  * @data:  new data
 530  *
 531  * add the new data at the end of the list
 532  *
 533  * Returns 1 if successful, 0 otherwise
 534  */
 535 int
 536 xmlListPushBack(xmlListPtr l, void *data)
 537 {
 538     xmlLinkPtr lkPlace, lkNew;
 539
 540     lkPlace = l->sentinel->prev;
 541     /* Add the new link */
 542     if (NULL ==(lkNew = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
 543         xmlGenericError(xmlGenericErrorContext,
 544                         "Cannot initialize memory for new link");
 545         return (0);
 546     }
 547     lkNew->data = data;
 548     lkNew->next = lkPlace->next;
 549     (lkPlace->next)->prev = lkNew;
 550     lkPlace->next = lkNew;
 551     lkNew->prev = lkPlace;
 552     return 1;
 553 }
 554
 555 /**
 556  * xmlLinkGetData:
 557  * @lk:  a link
 558  *
 559  * See Returns.
 560  *
 561  * Returns a pointer to the data referenced from this link
 562  */
 563 void *
 564 xmlLinkGetData(xmlLinkPtr lk)
 565 {
 566     return lk->data;
 567 }
 568
 569 /**
 570  * xmlListReverse:
 571  * @l:  a list
 572  *
 573  * Reverse the order of the elements in the list
 574  */
 575 void
 576 xmlListReverse(xmlListPtr l) {
 577   xmlLinkPtr lk;
 578   xmlLinkPtr lkPrev = l->sentinel;
 579
 580   for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
 581     lkPrev->next = lkPrev->prev;
 582     lkPrev->prev = lk;
 583     lkPrev = lk;
 584   }
 585   /* Fix up the last node */
 586   lkPrev->next = lkPrev->prev;
 587   lkPrev->prev = lk;
 588 }
 589
 590 /**
 591  * xmlListSort:
 592  * @l:  a list
 593  *
 594  * Sort all the elements in the list
 595  */
 596 void
 597 xmlListSort(xmlListPtr l)
 598 {
 599     xmlListPtr lTemp;
 600
 601     if(xmlListEmpty(l))
 602         return;
 603
 604     /* I think that the real answer is to implement quicksort, the
 605      * alternative is to implement some list copying procedure which
 606      * would be based on a list copy followed by a clear followed by
 607      * an insert. This is slow...
 608      */
 609
 610     if (NULL ==(lTemp = xmlListDup(l)))
 611         return;
 612     xmlListClear(l);
 613     xmlListMerge(l, lTemp);
 614     xmlListDelete(lTemp);
 615     return;
 616 }
 617
 618 /**
 619  * xmlListWalk:
 620  * @l:  a list
 621  * @walker:  a processing function
 622  * @user:  a user parameter passed to the walker function
 623  *
 624  * Walk all the element of the first from first to last and
 625  * apply the walker function to it
 626  */
 627 void
 628 xmlListWalk(xmlListPtr l, xmlListWalker walker, const void *user) {
 629     xmlLinkPtr lk;
 630
 631     for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
 632         if((walker(lk->data, user)) == 0)
 633                 break;
 634     }
 635 }
 636
 637 /**
 638  * xmlListReverseWalk:
 639  * @l:  a list
 640  * @walker:  a processing function
 641  * @user:  a user parameter passed to the walker function
 642  *
 643  * Walk all the element of the list in reverse order and
 644  * apply the walker function to it
 645  */
 646 void
 647 xmlListReverseWalk(xmlListPtr l, xmlListWalker walker, const void *user) {
 648     xmlLinkPtr lk;
 649
 650     for(lk = l->sentinel->prev; lk != l->sentinel; lk = lk->prev) {
 651         if((walker(lk->data, user)) == 0)
 652                 break;
 653     }
 654 }
 655
 656 /**
 657  * xmlListMerge:
 658  * @l1:  the original list
 659  * @l2:  the new list
 660  *
 661  * include all the elements of the second list in the first one and
 662  * clear the second list
 663  */
 664 void
 665 xmlListMerge(xmlListPtr l1, xmlListPtr l2)
 666 {
 667     xmlListCopy(l1, l2);
 668     xmlListClear(l2);
 669 }
 670
 671 /**
 672  * xmlListDup:
 673  * @old:  the list
 674  *
 675  * Duplicate the list
 676  *
 677  * Returns a new copy of the list or NULL in case of error
 678  */
 679 xmlListPtr
 680 xmlListDup(const xmlListPtr old)
 681 {
 682     xmlListPtr cur;
 683     /* Hmmm, how to best deal with allocation issues when copying
 684      * lists. If there is a de-allocator, should responsibility lie with
 685      * the new list or the old list. Surely not both. I'll arbitrarily
 686      * set it to be the old list for the time being whilst I work out
 687      * the answer
 688      */
 689     if (NULL ==(cur = xmlListCreate(NULL, old->linkCompare)))
 690         return (NULL);
 691     if (0 != xmlListCopy(cur, old))
 692         return NULL;
 693     return cur;
 694 }
 695
 696 /**
 697  * xmlListCopy:
 698  * @cur:  the new list
 699  * @old:  the old list
 700  *
 701  * Move all the element from the old list in the new list
 702  *
 703  * Returns 0 in case of success 1 in case of error
 704  */
 705 int
 706 xmlListCopy(xmlListPtr cur, const xmlListPtr old)
 707 {
 708     /* Walk the old tree and insert the data into the new one */
 709     xmlLinkPtr lk;
 710
 711     for(lk = old->sentinel->next; lk != old->sentinel; lk = lk->next) {
 712         if (0 !=xmlListInsert(cur, lk->data)) {
 713             xmlListDelete(cur);
 714             return (1);
 715         }
 716     }
 717     return (0);
 718 }
 719 /* xmlListUnique() */
 720 /* xmlListSwap */