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 occurred, 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 occurred, 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"