1 /* 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3 % % 4 % % 5 % % 6 % L IIIII N N K K EEEEE DDDD L IIIII SSSSS TTTTT % 7 % L I NN N K K E D D L I SS T % 8 % L I N N N KKK EEE D D = L I SSS T % 9 % L I N NN K K E D D L I SS T % 10 % LLLLL IIIII N N K K EEEEE DDDD LLLLL IIIII SSSSS T % 11 % % 12 % % 13 % MagickCore Linked-list Methods % 14 % % 15 % Software Design % 16 % Cristy % 17 % December 2002 % 18 % % 19 % % 20 % Copyright 1999-2016 ImageMagick Studio LLC, a non-profit organization % 21 % dedicated to making software imaging solutions freely available. % 22 % % 23 % You may not use this file except in compliance with the License. You may % 24 % obtain a copy of the License at % 25 % % 26 % http://www.imagemagick.org/script/license.php % 27 % % 28 % Unless required by applicable law or agreed to in writing, software % 29 % distributed under the License is distributed on an "AS IS" BASIS, % 30 % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. % 31 % See the License for the specific language governing permissions and % 32 % limitations under the License. % 33 % % 34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 35 % 36 % This module implements the standard handy hash and linked-list methods for 37 % storing and retrieving large numbers of data elements. It is loosely based 38 % on the Java implementation of these algorithms. 39 % 40 */ 41 42 /* 44 Include declarations. 45 */ 46 #include "MagickCore/studio.h" 47 #include "MagickCore/exception.h" 48 #include "MagickCore/exception-private.h" 49 #include "MagickCore/linked-list.h" 50 #include "MagickCore/locale_.h" 51 #include "MagickCore/memory_.h" 52 #include "MagickCore/semaphore.h" 53 #include "MagickCore/signature-private.h" 54 #include "MagickCore/string_.h" 55 56 /* 58 Typedef declarations. 59 */ 60 typedef struct _ElementInfo 61 { 62 void 63 *value; 64 65 struct _ElementInfo 66 *next; 67 } ElementInfo; 68 69 struct _LinkedListInfo 70 { 71 size_t 72 capacity, 73 elements; 74 75 ElementInfo 76 *head, 77 *tail, 78 *next; 79 80 SemaphoreInfo 81 *semaphore; 82 83 size_t 84 signature; 85 }; 86 87 /* 89 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 90 % % 91 % % 92 % % 93 % A p p e n d V a l u e T o L i n k e d L i s t % 94 % % 95 % % 96 % % 97 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 98 % 99 % AppendValueToLinkedList() appends a value to the end of the linked-list. 100 % 101 % The format of the AppendValueToLinkedList method is: 102 % 103 % MagickBooleanType AppendValueToLinkedList(LinkedListInfo *list_info, 104 % const void *value) 105 % 106 % A description of each parameter follows: 107 % 108 % o list_info: the linked-list info. 109 % 110 % o value: the value. 111 % 112 */ 113 MagickExport MagickBooleanType AppendValueToLinkedList( 114 LinkedListInfo *list_info,const void *value) 115 { 116 register ElementInfo 117 *next; 118 119 assert(list_info != (LinkedListInfo *) NULL); 120 assert(list_info->signature == MagickCoreSignature); 121 if (list_info->elements == list_info->capacity) 122 return(MagickFalse); 123 next=(ElementInfo *) AcquireMagickMemory(sizeof(*next)); 124 if (next == (ElementInfo *) NULL) 125 return(MagickFalse); 126 next->value=(void *) value; 127 next->next=(ElementInfo *) NULL; 128 LockSemaphoreInfo(list_info->semaphore); 129 if (list_info->next == (ElementInfo *) NULL) 130 list_info->next=next; 131 if (list_info->elements == 0) 132 list_info->head=next; 133 else 134 list_info->tail->next=next; 135 list_info->tail=next; 136 list_info->elements++; 137 UnlockSemaphoreInfo(list_info->semaphore); 138 return(MagickTrue); 139 } 140 141 /* 143 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 144 % % 145 % % 146 % % 147 % C l e a r L i n k e d L i s t % 148 % % 149 % % 150 % % 151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 152 % 153 % ClearLinkedList() clears all the elements from the linked-list. 154 % 155 % The format of the ClearLinkedList method is: 156 % 157 % void ClearLinkedList(LinkedListInfo *list_info, 158 % void *(*relinquish_value)(void *)) 159 % 160 % A description of each parameter follows: 161 % 162 % o list_info: the linked-list info. 163 % 164 % o relinquish_value: the value deallocation method; typically 165 % RelinquishMagickMemory(). 166 % 167 */ 168 MagickExport void ClearLinkedList(LinkedListInfo *list_info, 169 void *(*relinquish_value)(void *)) 170 { 171 ElementInfo 172 *element; 173 174 register ElementInfo 175 *next; 176 177 assert(list_info != (LinkedListInfo *) NULL); 178 assert(list_info->signature == MagickCoreSignature); 179 LockSemaphoreInfo(list_info->semaphore); 180 next=list_info->head; 181 while (next != (ElementInfo *) NULL) 182 { 183 if (relinquish_value != (void *(*)(void *)) NULL) 184 next->value=relinquish_value(next->value); 185 element=next; 186 next=next->next; 187 element=(ElementInfo *) RelinquishMagickMemory(element); 188 } 189 list_info->head=(ElementInfo *) NULL; 190 list_info->tail=(ElementInfo *) NULL; 191 list_info->next=(ElementInfo *) NULL; 192 list_info->elements=0; 193 UnlockSemaphoreInfo(list_info->semaphore); 194 } 195 196 /* 197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 198 % % 199 % % 200 % % 201 % D e s t r o y L i n k e d L i s t % 202 % % 203 % % 204 % % 205 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 206 % 207 % DestroyLinkedList() frees the linked-list and all associated resources. 208 % 209 % The format of the DestroyLinkedList method is: 210 % 211 % LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info, 212 % void *(*relinquish_value)(void *)) 213 % 214 % A description of each parameter follows: 215 % 216 % o list_info: the linked-list info. 217 % 218 % o relinquish_value: the value deallocation method; typically 219 % RelinquishMagickMemory(). 220 % 221 */ 222 MagickExport LinkedListInfo *DestroyLinkedList(LinkedListInfo *list_info, 223 void *(*relinquish_value)(void *)) 224 { 225 ElementInfo 226 *entry; 227 228 register ElementInfo 229 *next; 230 231 assert(list_info != (LinkedListInfo *) NULL); 232 assert(list_info->signature == MagickCoreSignature); 233 LockSemaphoreInfo(list_info->semaphore); 234 for (next=list_info->head; next != (ElementInfo *) NULL; ) 235 { 236 if (relinquish_value != (void *(*)(void *)) NULL) 237 next->value=relinquish_value(next->value); 238 entry=next; 239 next=next->next; 240 entry=(ElementInfo *) RelinquishMagickMemory(entry); 241 } 242 list_info->signature=(~MagickCoreSignature); 243 UnlockSemaphoreInfo(list_info->semaphore); 244 RelinquishSemaphoreInfo(&list_info->semaphore); 245 list_info=(LinkedListInfo *) RelinquishMagickMemory(list_info); 246 return(list_info); 247 } 248 249 /* 251 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 252 % % 253 % % 254 % % 255 % G e t L a s t V a l u e I n L i n k e d L i s t % 256 % % 257 % % 258 % % 259 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 260 % 261 % GetLastValueInLinkedList() gets the last value in the linked-list. 262 % 263 % The format of the GetLastValueInLinkedList method is: 264 % 265 % void *GetLastValueInLinkedList(LinkedListInfo *list_info) 266 % 267 % A description of each parameter follows: 268 % 269 % o list_info: the linked_list info. 270 % 271 */ 272 MagickExport void *GetLastValueInLinkedList(LinkedListInfo *list_info) 273 { 274 void 275 *value; 276 277 assert(list_info != (LinkedListInfo *) NULL); 278 assert(list_info->signature == MagickCoreSignature); 279 if (list_info->elements == 0) 280 return((void *) NULL); 281 LockSemaphoreInfo(list_info->semaphore); 282 value=list_info->tail->value; 283 UnlockSemaphoreInfo(list_info->semaphore); 284 return(value); 285 } 286 287 /* 288 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 289 % % 290 % % 291 % % 292 % G e t N e x t V a l u e I n L i n k e d L i s t % 293 % % 294 % % 295 % % 296 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 297 % 298 % GetNextValueInLinkedList() gets the next value in the linked-list. 299 % 300 % The format of the GetNextValueInLinkedList method is: 301 % 302 % void *GetNextValueInLinkedList(LinkedListInfo *list_info) 303 % 304 % A description of each parameter follows: 305 % 306 % o list_info: the linked-list info. 307 % 308 */ 309 MagickExport void *GetNextValueInLinkedList(LinkedListInfo *list_info) 310 { 311 void 312 *value; 313 314 assert(list_info != (LinkedListInfo *) NULL); 315 assert(list_info->signature == MagickCoreSignature); 316 LockSemaphoreInfo(list_info->semaphore); 317 if (list_info->next == (ElementInfo *) NULL) 318 { 319 UnlockSemaphoreInfo(list_info->semaphore); 320 return((void *) NULL); 321 } 322 value=list_info->next->value; 323 list_info->next=list_info->next->next; 324 UnlockSemaphoreInfo(list_info->semaphore); 325 return(value); 326 } 327 328 /* 330 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 331 % % 332 % % 333 % % 334 % G e t N u m b e r O f E l e m e n t s I n L i n k e d L i s t % 335 % % 336 % % 337 % % 338 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 339 % 340 % GetNumberOfElementsInLinkedList() returns the number of entries in the 341 % linked-list. 342 % 343 % The format of the GetNumberOfElementsInLinkedList method is: 344 % 345 % size_t GetNumberOfElementsInLinkedList( 346 % const LinkedListInfo *list_info) 347 % 348 % A description of each parameter follows: 349 % 350 % o list_info: the linked-list info. 351 % 352 */ 353 MagickExport size_t GetNumberOfElementsInLinkedList( 354 const LinkedListInfo *list_info) 355 { 356 assert(list_info != (LinkedListInfo *) NULL); 357 assert(list_info->signature == MagickCoreSignature); 358 return(list_info->elements); 359 } 360 361 /* 362 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 363 % % 364 % % 365 % % 366 % G e t V a l u e F r o m L i n k e d L i s t % 367 % % 368 % % 369 % % 370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 371 % 372 % GetValueFromLinkedList() gets a value from the linked-list at the specified 373 % location. 374 % 375 % The format of the GetValueFromLinkedList method is: 376 % 377 % void *GetValueFromLinkedList(LinkedListInfo *list_info, 378 % const size_t index) 379 % 380 % A description of each parameter follows: 381 % 382 % o list_info: the linked_list info. 383 % 384 % o index: the list index. 385 % 386 */ 387 MagickExport void *GetValueFromLinkedList(LinkedListInfo *list_info, 388 const size_t index) 389 { 390 register ElementInfo 391 *next; 392 393 register ssize_t 394 i; 395 396 void 397 *value; 398 399 assert(list_info != (LinkedListInfo *) NULL); 400 assert(list_info->signature == MagickCoreSignature); 401 if (index >= list_info->elements) 402 return((void *) NULL); 403 LockSemaphoreInfo(list_info->semaphore); 404 if (index == 0) 405 { 406 value=list_info->head->value; 407 UnlockSemaphoreInfo(list_info->semaphore); 408 return(value); 409 } 410 if (index == (list_info->elements-1)) 411 { 412 value=list_info->tail->value; 413 UnlockSemaphoreInfo(list_info->semaphore); 414 return(value); 415 } 416 next=list_info->head; 417 for (i=0; i < (ssize_t) index; i++) 418 next=next->next; 419 value=next->value; 420 UnlockSemaphoreInfo(list_info->semaphore); 421 return(value); 422 } 423 424 /* 425 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 426 % % 427 % % 428 % % 429 % I n s e r t V a l u e I n L i n k e d L i s t % 430 % % 431 % % 432 % % 433 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 434 % 435 % InsertValueInLinkedList() inserts an element in the linked-list at the 436 % specified location. 437 % 438 % The format of the InsertValueInLinkedList method is: 439 % 440 % MagickBooleanType InsertValueInLinkedList(ListInfo *list_info, 441 % const size_t index,const void *value) 442 % 443 % A description of each parameter follows: 444 % 445 % o list_info: the hashmap info. 446 % 447 % o index: the index. 448 % 449 % o value: the value. 450 % 451 */ 452 MagickExport MagickBooleanType InsertValueInLinkedList( 453 LinkedListInfo *list_info,const size_t index,const void *value) 454 { 455 register ElementInfo 456 *next; 457 458 register ssize_t 459 i; 460 461 assert(list_info != (LinkedListInfo *) NULL); 462 assert(list_info->signature == MagickCoreSignature); 463 if (value == (const void *) NULL) 464 return(MagickFalse); 465 if ((index > list_info->elements) || 466 (list_info->elements == list_info->capacity)) 467 return(MagickFalse); 468 next=(ElementInfo *) AcquireMagickMemory(sizeof(*next)); 469 if (next == (ElementInfo *) NULL) 470 return(MagickFalse); 471 next->value=(void *) value; 472 next->next=(ElementInfo *) NULL; 473 LockSemaphoreInfo(list_info->semaphore); 474 if (list_info->elements == 0) 475 { 476 if (list_info->next == (ElementInfo *) NULL) 477 list_info->next=next; 478 list_info->head=next; 479 list_info->tail=next; 480 } 481 else 482 { 483 if (index == 0) 484 { 485 if (list_info->next == list_info->head) 486 list_info->next=next; 487 next->next=list_info->head; 488 list_info->head=next; 489 } 490 else 491 if (index == list_info->elements) 492 { 493 if (list_info->next == (ElementInfo *) NULL) 494 list_info->next=next; 495 list_info->tail->next=next; 496 list_info->tail=next; 497 } 498 else 499 { 500 ElementInfo 501 *element; 502 503 element=list_info->head; 504 next->next=element->next; 505 for (i=1; i < (ssize_t) index; i++) 506 { 507 element=element->next; 508 next->next=element->next; 509 } 510 next=next->next; 511 element->next=next; 512 if (list_info->next == next->next) 513 list_info->next=next; 514 } 515 } 516 list_info->elements++; 517 UnlockSemaphoreInfo(list_info->semaphore); 518 return(MagickTrue); 519 } 520 521 /* 523 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 524 % % 525 % % 526 % % 527 % I n s e r t V a l u e I n S o r t e d L i n k e d L i s t % 528 % % 529 % % 530 % % 531 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 532 % 533 % InsertValueInSortedLinkedList() inserts a value in the sorted linked-list. 534 % 535 % The format of the InsertValueInSortedLinkedList method is: 536 % 537 % MagickBooleanType InsertValueInSortedLinkedList(ListInfo *list_info, 538 % int (*compare)(const void *,const void *),void **replace, 539 % const void *value) 540 % 541 % A description of each parameter follows: 542 % 543 % o list_info: the hashmap info. 544 % 545 % o index: the index. 546 % 547 % o compare: the compare method. 548 % 549 % o replace: return previous element here. 550 % 551 % o value: the value. 552 % 553 */ 554 MagickExport MagickBooleanType InsertValueInSortedLinkedList( 555 LinkedListInfo *list_info,int (*compare)(const void *,const void *), 556 void **replace,const void *value) 557 { 558 ElementInfo 559 *element; 560 561 register ElementInfo 562 *next; 563 564 register ssize_t 565 i; 566 567 assert(list_info != (LinkedListInfo *) NULL); 568 assert(list_info->signature == MagickCoreSignature); 569 if ((compare == (int (*)(const void *,const void *)) NULL) || 570 (value == (const void *) NULL)) 571 return(MagickFalse); 572 if (list_info->elements == list_info->capacity) 573 return(MagickFalse); 574 next=(ElementInfo *) AcquireMagickMemory(sizeof(*next)); 575 if (next == (ElementInfo *) NULL) 576 return(MagickFalse); 577 next->value=(void *) value; 578 element=(ElementInfo *) NULL; 579 LockSemaphoreInfo(list_info->semaphore); 580 next->next=list_info->head; 581 while (next->next != (ElementInfo *) NULL) 582 { 583 i=(ssize_t) compare(value,next->next->value); 584 if ((i < 0) || ((replace != (void **) NULL) && (i == 0))) 585 { 586 if (i == 0) 587 { 588 *replace=next->next->value; 589 next->next=next->next->next; 590 if (element != (ElementInfo *) NULL) 591 element->next=(ElementInfo *) RelinquishMagickMemory( 592 element->next); 593 list_info->elements--; 594 } 595 if (element != (ElementInfo *) NULL) 596 element->next=next; 597 else 598 list_info->head=next; 599 break; 600 } 601 element=next->next; 602 next->next=next->next->next; 603 } 604 if (next->next == (ElementInfo *) NULL) 605 { 606 if (element != (ElementInfo *) NULL) 607 element->next=next; 608 else 609 list_info->head=next; 610 list_info->tail=next; 611 } 612 list_info->elements++; 613 UnlockSemaphoreInfo(list_info->semaphore); 614 return(MagickTrue); 615 } 616 617 /* 618 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 619 % % 620 % % 621 % % 622 % I s L i n k e d L i s t E m p t y % 623 % % 624 % % 625 % % 626 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 627 % 628 % IsLinkedListEmpty() returns MagickTrue if the linked-list is empty. 629 % 630 % The format of the IsLinkedListEmpty method is: 631 % 632 % MagickBooleanType IsLinkedListEmpty(LinkedListInfo *list_info) 633 % 634 % A description of each parameter follows: 635 % 636 % o list_info: the linked-list info. 637 % 638 */ 639 MagickExport MagickBooleanType IsLinkedListEmpty( 640 const LinkedListInfo *list_info) 641 { 642 assert(list_info != (LinkedListInfo *) NULL); 643 assert(list_info->signature == MagickCoreSignature); 644 return(list_info->elements == 0 ? MagickTrue : MagickFalse); 645 } 646 647 /* 649 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 650 % % 651 % % 652 % % 653 % L i n k e d L i s t T o A r r a y % 654 % % 655 % % 656 % % 657 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 658 % 659 % LinkedListToArray() converts the linked-list to an array. 660 % 661 % The format of the LinkedListToArray method is: 662 % 663 % MagickBooleanType LinkedListToArray(LinkedListInfo *list_info, 664 % void **array) 665 % 666 % A description of each parameter follows: 667 % 668 % o list_info: the linked-list info. 669 % 670 % o array: the array. 671 % 672 */ 673 MagickExport MagickBooleanType LinkedListToArray(LinkedListInfo *list_info, 674 void **array) 675 { 676 register ElementInfo 677 *next; 678 679 register ssize_t 680 i; 681 682 assert(list_info != (LinkedListInfo *) NULL); 683 assert(list_info->signature == MagickCoreSignature); 684 if (array == (void **) NULL) 685 return(MagickFalse); 686 LockSemaphoreInfo(list_info->semaphore); 687 next=list_info->head; 688 for (i=0; next != (ElementInfo *) NULL; i++) 689 { 690 array[i]=next->value; 691 next=next->next; 692 } 693 UnlockSemaphoreInfo(list_info->semaphore); 694 return(MagickTrue); 695 } 696 697 /* 699 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 700 % % 701 % % 702 % % 703 % N e w L i n k e d L i s t I n f o % 704 % % 705 % % 706 % % 707 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 708 % 709 % NewLinkedList() returns a pointer to a LinkedListInfo structure 710 % initialized to default values. 711 % 712 % The format of the NewLinkedList method is: 713 % 714 % LinkedListInfo *NewLinkedList(const size_t capacity) 715 % 716 % A description of each parameter follows: 717 % 718 % o capacity: the maximum number of elements in the list. 719 % 720 */ 721 MagickExport LinkedListInfo *NewLinkedList(const size_t capacity) 722 { 723 LinkedListInfo 724 *list_info; 725 726 list_info=(LinkedListInfo *) AcquireMagickMemory(sizeof(*list_info)); 727 if (list_info == (LinkedListInfo *) NULL) 728 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); 729 (void) ResetMagickMemory(list_info,0,sizeof(*list_info)); 730 list_info->capacity=capacity == 0 ? (size_t) (~0) : capacity; 731 list_info->elements=0; 732 list_info->head=(ElementInfo *) NULL; 733 list_info->tail=(ElementInfo *) NULL; 734 list_info->next=(ElementInfo *) NULL; 735 list_info->semaphore=AcquireSemaphoreInfo(); 736 list_info->signature=MagickCoreSignature; 737 return(list_info); 738 } 739 740 /* 742 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 743 % % 744 % % 745 % % 746 % R e m o v e E l e m e n t B y V a l u e F r o m L i n k e d L i s t % 747 % % 748 % % 749 % % 750 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 751 % 752 % RemoveElementByValueFromLinkedList() removes an element from the linked-list 753 % by value. 754 % 755 % The format of the RemoveElementByValueFromLinkedList method is: 756 % 757 % void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info, 758 % const void *value) 759 % 760 % A description of each parameter follows: 761 % 762 % o list_info: the list info. 763 % 764 % o value: the value. 765 % 766 */ 767 MagickExport void *RemoveElementByValueFromLinkedList(LinkedListInfo *list_info, 768 const void *value) 769 { 770 ElementInfo 771 *next; 772 773 assert(list_info != (LinkedListInfo *) NULL); 774 assert(list_info->signature == MagickCoreSignature); 775 if ((list_info->elements == 0) || (value == (const void *) NULL)) 776 return((void *) NULL); 777 LockSemaphoreInfo(list_info->semaphore); 778 if (value == list_info->head->value) 779 { 780 if (list_info->next == list_info->head) 781 list_info->next=list_info->head->next; 782 next=list_info->head; 783 list_info->head=list_info->head->next; 784 next=(ElementInfo *) RelinquishMagickMemory(next); 785 } 786 else 787 { 788 ElementInfo 789 *element; 790 791 next=list_info->head; 792 while ((next->next != (ElementInfo *) NULL) && 793 (next->next->value != value)) 794 next=next->next; 795 if (next->next == (ElementInfo *) NULL) 796 { 797 UnlockSemaphoreInfo(list_info->semaphore); 798 return((void *) NULL); 799 } 800 element=next->next; 801 next->next=element->next; 802 if (element == list_info->tail) 803 list_info->tail=next; 804 if (list_info->next == element) 805 list_info->next=element->next; 806 element=(ElementInfo *) RelinquishMagickMemory(element); 807 } 808 list_info->elements--; 809 UnlockSemaphoreInfo(list_info->semaphore); 810 return((void *) value); 811 } 812 813 /* 815 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 816 % % 817 % % 818 % % 819 % R e m o v e E l e m e n t F r o m L i n k e d L i s t % 820 % % 821 % % 822 % % 823 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 824 % 825 % RemoveElementFromLinkedList() removes an element from the linked-list at the 826 % specified location. 827 % 828 % The format of the RemoveElementFromLinkedList method is: 829 % 830 % void *RemoveElementFromLinkedList(LinkedListInfo *list_info, 831 % const size_t index) 832 % 833 % A description of each parameter follows: 834 % 835 % o list_info: the linked-list info. 836 % 837 % o index: the index. 838 % 839 */ 840 MagickExport void *RemoveElementFromLinkedList(LinkedListInfo *list_info, 841 const size_t index) 842 { 843 ElementInfo 844 *next; 845 846 register ssize_t 847 i; 848 849 void 850 *value; 851 852 assert(list_info != (LinkedListInfo *) NULL); 853 assert(list_info->signature == MagickCoreSignature); 854 if (index >= list_info->elements) 855 return((void *) NULL); 856 LockSemaphoreInfo(list_info->semaphore); 857 if (index == 0) 858 { 859 if (list_info->next == list_info->head) 860 list_info->next=list_info->head->next; 861 value=list_info->head->value; 862 next=list_info->head; 863 list_info->head=list_info->head->next; 864 next=(ElementInfo *) RelinquishMagickMemory(next); 865 } 866 else 867 { 868 ElementInfo 869 *element; 870 871 next=list_info->head; 872 for (i=1; i < (ssize_t) index; i++) 873 next=next->next; 874 element=next->next; 875 next->next=element->next; 876 if (element == list_info->tail) 877 list_info->tail=next; 878 if (list_info->next == element) 879 list_info->next=element->next; 880 value=element->value; 881 element=(ElementInfo *) RelinquishMagickMemory(element); 882 } 883 list_info->elements--; 884 UnlockSemaphoreInfo(list_info->semaphore); 885 return(value); 886 } 887 888 /* 889 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 890 % % 891 % % 892 % % 893 % R e m o v e L a s t E l e m e n t F r o m L i n k e d L i s t % 894 % % 895 % % 896 % % 897 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 898 % 899 % RemoveLastElementFromLinkedList() removes the last element from the 900 % linked-list. 901 % 902 % The format of the RemoveLastElementFromLinkedList method is: 903 % 904 % void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info) 905 % 906 % A description of each parameter follows: 907 % 908 % o list_info: the linked-list info. 909 % 910 */ 911 MagickExport void *RemoveLastElementFromLinkedList(LinkedListInfo *list_info) 912 { 913 void 914 *value; 915 916 assert(list_info != (LinkedListInfo *) NULL); 917 assert(list_info->signature == MagickCoreSignature); 918 if (list_info->elements == 0) 919 return((void *) NULL); 920 LockSemaphoreInfo(list_info->semaphore); 921 if (list_info->next == list_info->tail) 922 list_info->next=(ElementInfo *) NULL; 923 if (list_info->elements == 1UL) 924 { 925 value=list_info->head->value; 926 list_info->head=(ElementInfo *) NULL; 927 list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail); 928 } 929 else 930 { 931 ElementInfo 932 *next; 933 934 value=list_info->tail->value; 935 next=list_info->head; 936 while (next->next != list_info->tail) 937 next=next->next; 938 list_info->tail=(ElementInfo *) RelinquishMagickMemory(list_info->tail); 939 list_info->tail=next; 940 next->next=(ElementInfo *) NULL; 941 } 942 list_info->elements--; 943 UnlockSemaphoreInfo(list_info->semaphore); 944 return(value); 945 } 946 947 /* 949 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 950 % % 951 % % 952 % % 953 % R e s e t L i n k e d L i s t I t e r a t o r % 954 % % 955 % % 956 % % 957 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 958 % 959 % ResetLinkedListIterator() resets the lined-list iterator. Use it in 960 % conjunction with GetNextValueInLinkedList() to iterate over all the values 961 % in the linked-list. 962 % 963 % The format of the ResetLinkedListIterator method is: 964 % 965 % ResetLinkedListIterator(LinkedListInfo *list_info) 966 % 967 % A description of each parameter follows: 968 % 969 % o list_info: the linked-list info. 970 % 971 */ 972 MagickExport void ResetLinkedListIterator(LinkedListInfo *list_info) 973 { 974 assert(list_info != (LinkedListInfo *) NULL); 975 assert(list_info->signature == MagickCoreSignature); 976 LockSemaphoreInfo(list_info->semaphore); 977 list_info->next=list_info->head; 978 UnlockSemaphoreInfo(list_info->semaphore); 979 } 980
