third_party/libxml/src/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     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
 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  */
 117 static xmlLinkPtr
 118 xmlListHigherSearch(xmlListPtr l, void *data)
 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
 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  */
 137 static xmlLinkPtr
 138 xmlListLinkSearch(xmlListPtr l, void *data)
 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
 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  */
 162 static xmlLinkPtr
 163 xmlListLinkReverseSearch(xmlListPtr l, void *data)
 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
 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  */
 187 xmlListPtr
 188 xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)
 189 {
 190     xmlListPtr l;
 191     if (NULL == (l = (xmlListPtr )xmlMalloc( sizeof(xmlList)))) {
 192         xmlGenericError(xmlGenericErrorContext,
 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)))) {
 201         xmlGenericError(xmlGenericErrorContext,
 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
 221 /**
 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  */
 230 void *
 231 xmlListSearch(xmlListPtr l, void *data)
 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
 242 /**
 243  * xmlListReverseSearch:
 244  * @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  */
 251 void *
 252 xmlListReverseSearch(xmlListPtr l, void *data)
 253 {
 254     xmlLinkPtr lk;
 255     if (l == NULL)
 256         return(NULL);
 257     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  */
 272 int
 273 xmlListInsert(xmlListPtr l, void *data)
 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) {
 283         xmlGenericError(xmlGenericErrorContext,
 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
 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  */
 305 int xmlListAppend(xmlListPtr l, void *data)
 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) {
 315         xmlGenericError(xmlGenericErrorContext,
 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
 327 /**
 328  * xmlListDelete:
 329  * @l:  a list
 330  *
 331  * Deletes the list and its associated data
 332  */
 333 void xmlListDelete(xmlListPtr l)
 334 {
 335     if (l == NULL)
 336         return;
 337
 338     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  */
 352 int
 353 xmlListRemoveFirst(xmlListPtr l, void *data)
 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
 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  */
 377 int
 378 xmlListRemoveLast(xmlListPtr l, void *data)
 379 {
 380     xmlLinkPtr lk;
 381
 382     if (l == NULL)
 383         return(0);
 384     /*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  */
 402 int
 403 xmlListRemoveAll(xmlListPtr l, void *data)
 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
 415 /**
 416  * xmlListClear:
 417  * @l:  a list
 418  *
 419  * Remove the all data in the list
 420  */
 421 void
 422 xmlListClear(xmlListPtr l)
 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
 437 /**
 438  * xmlListEmpty:
 439  * @l:  a list
 440  *
 441  * Is the list empty ?
 442  *
 443  * Returns 1 if the list is empty, 0 if not empty and -1 in case of error
 444  */
 445 int
 446 xmlListEmpty(xmlListPtr l)
 447 {
 448     if (l == NULL)
 449         return(-1);
 450     return (l->sentinel->next == l->sentinel);
 451 }
 452
 453 /**
 454  * xmlListFront:
 455  * @l:  a list
 456  *
 457  * Get the first element in the list
 458  *
 459  * Returns the first element in the list, or NULL
 460  */
 461 xmlLinkPtr
 462 xmlListFront(xmlListPtr l)
 463 {
 464     if (l == NULL)
 465         return(NULL);
 466     return (l->sentinel->next);
 467 }
 468
 469 /**
 470  * xmlListEnd:
 471  * @l:  a list
 472  *
 473  * Get the last element in the list
 474  *
 475  * Returns the last element in the list, or NULL
 476  */
 477 xmlLinkPtr
 478 xmlListEnd(xmlListPtr l)
 479 {
 480     if (l == NULL)
 481         return(NULL);
 482     return (l->sentinel->prev);
 483 }
 484
 485 /**
 486  * xmlListSize:
 487  * @l:  a list
 488  *
 489  * Get the number of elements in the list
 490  *
 491  * Returns the number of elements in the list or -1 in case of error
 492  */
 493 int
 494 xmlListSize(xmlListPtr l)
 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
 506 /**
 507  * xmlListPopFront:
 508  * @l:  a list
 509  *
 510  * Removes the first element in the list
 511  */
 512 void
 513 xmlListPopFront(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  */
 525 void
 526 xmlListPopBack(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  */
 541 int
 542 xmlListPushFront(xmlListPtr l, void *data)
 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) {
 552         xmlGenericError(xmlGenericErrorContext,
 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
 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  */
 573 int
 574 xmlListPushBack(xmlListPtr l, void *data)
 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)))) {
 583         xmlGenericError(xmlGenericErrorContext,
 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
 595 /**
 596  * xmlLinkGetData:
 597  * @lk:  a link
 598  *
 599  * See Returns.
 600  *
 601  * Returns a pointer to the data referenced from this link
 602  */
 603 void *
 604 xmlLinkGetData(xmlLinkPtr lk)
 605 {
 606     if (lk == NULL)
 607         return(NULL);
 608     return lk->data;
 609 }
 610
 611 /**
 612  * xmlListReverse:
 613  * @l:  a list
 614  *
 615  * Reverse the order of the elements in the list
 616  */
 617 void
 618 xmlListReverse(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 */
 632     lkPrev->next = lkPrev->prev;
 633     lkPrev->prev = lk;
 634 }
 635
 636 /**
 637  * xmlListSort:
 638  * @l:  a list
 639  *
 640  * Sort all the elements in the list
 641  */
 642 void
 643 xmlListSort(xmlListPtr l)
 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
 666 /**
 667  * xmlListWalk:
 668  * @l:  a list
 669  * @walker:  a processing function
 670  * @user:  a user parameter passed to the walker function
 671  *
 672  * Walk all the element of the first from first to last and
 673  * apply the walker function to it
 674  */
 675 void
 676 xmlListWalk(xmlListPtr l, xmlListWalker walker, const void *user) {
 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
 687 /**
 688  * xmlListReverseWalk:
 689  * @l:  a list
 690  * @walker:  a processing function
 691  * @user:  a user parameter passed to the walker function
 692  *
 693  * Walk all the element of the list in reverse order and
 694  * apply the walker function to it
 695  */
 696 void
 697 xmlListReverseWalk(xmlListPtr l, xmlListWalker walker, const void *user) {
 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
 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  */
 716 void
 717 xmlListMerge(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
 728  *
 729  * Returns a new copy of the list or NULL in case of error
 730  */
 731 xmlListPtr
 732 xmlListDup(const xmlListPtr old)
 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
 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
 757  *
 758  * Returns 0 in case of success 1 in case of error
 759  */
 760 int
 761 xmlListCopy(xmlListPtr cur, const xmlListPtr old)
 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"