1 /* 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3 % % 4 % % 5 % % 6 % SSSSS PPPP L AAA Y Y % 7 % SS P P L A A Y Y % 8 % SSS PPPP L AAAAA Y % 9 % SS P L A A Y % 10 % SSSSS P LLLLL A A Y % 11 % % 12 % TTTTT RRRR EEEEE EEEEE % 13 % T R R E E % 14 % T RRRR EEE EEE % 15 % T R R E E % 16 % T R R EEEEE EEEEE % 17 % % 18 % % 19 % MagickCore Self-adjusting Binary Search Tree Methods % 20 % % 21 % Software Design % 22 % Cristy % 23 % December 2002 % 24 % % 25 % % 26 % Copyright 1999-2019 ImageMagick Studio LLC, a non-profit organization % 27 % dedicated to making software imaging solutions freely available. % 28 % % 29 % You may not use this file except in compliance with the License. You may % 30 % obtain a copy of the License at % 31 % % 32 % https://imagemagick.org/script/license.php % 33 % % 34 % Unless required by applicable law or agreed to in writing, software % 35 % distributed under the License is distributed on an "AS IS" BASIS, % 36 % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. % 37 % See the License for the specific language governing permissions and % 38 % limitations under the License. % 39 % % 40 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 41 % 42 % This module implements the standard handy splay-tree methods for storing and 43 % retrieving large numbers of data elements. It is loosely based on the Java 44 % implementation of these algorithms. 45 % 46 */ 47 48 /* 50 Include declarations. 51 */ 52 #include "MagickCore/studio.h" 53 #include "MagickCore/exception.h" 54 #include "MagickCore/exception-private.h" 55 #include "MagickCore/locale_.h" 56 #include "MagickCore/log.h" 57 #include "MagickCore/memory_.h" 58 #include "MagickCore/memory-private.h" 59 #include "MagickCore/splay-tree.h" 60 #include "MagickCore/semaphore.h" 61 #include "MagickCore/string_.h" 62 63 /* 65 Define declarations. 66 */ 67 #define MaxSplayTreeDepth 1024 68 69 /* 71 Typedef declarations. 72 */ 73 typedef struct _NodeInfo 74 { 75 void 76 *key; 77 78 void 79 *value; 80 81 struct _NodeInfo 82 *left, 83 *right; 84 } NodeInfo; 85 86 struct _SplayTreeInfo 87 { 88 NodeInfo 89 *root; 90 91 int 92 (*compare)(const void *,const void *); 93 94 void 95 *(*relinquish_key)(void *), 96 *(*relinquish_value)(void *); 97 98 MagickBooleanType 99 balance; 100 101 void 102 *key, 103 *next; 104 105 size_t 106 nodes; 107 108 MagickBooleanType 109 debug; 110 111 SemaphoreInfo 112 *semaphore; 113 114 size_t 115 signature; 116 }; 117 118 /* 120 Forward declarations. 121 */ 122 static int 123 IterateOverSplayTree(SplayTreeInfo *,int (*)(NodeInfo *,const void *), 124 const void *); 125 126 static void 127 SplaySplayTree(SplayTreeInfo *,const void *); 128 129 /* 131 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 132 % % 133 % % 134 % % 135 % A d d V a l u e T o S p l a y T r e e % 136 % % 137 % % 138 % % 139 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 140 % 141 % AddValueToSplayTree() adds the given key and value to the splay-tree. Both 142 % key and value are used as is, without coping or cloning. It returns 143 % MagickTrue on success, otherwise MagickFalse. 144 % 145 % The format of the AddValueToSplayTree method is: 146 % 147 % MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree, 148 % const void *key,const void *value) 149 % 150 % A description of each parameter follows: 151 % 152 % o splay_tree: the splay-tree info. 153 % 154 % o key: the key. 155 % 156 % o value: the value. 157 % 158 */ 159 MagickExport MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree, 160 const void *key,const void *value) 161 { 162 int 163 compare; 164 165 register NodeInfo 166 *node; 167 168 LockSemaphoreInfo(splay_tree->semaphore); 169 SplaySplayTree(splay_tree,key); 170 compare=0; 171 if (splay_tree->root != (NodeInfo *) NULL) 172 { 173 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 174 compare=splay_tree->compare(splay_tree->root->key,key); 175 else 176 compare=(splay_tree->root->key > key) ? 1 : 177 ((splay_tree->root->key < key) ? -1 : 0); 178 if (compare == 0) 179 { 180 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 181 (splay_tree->root->value != (void *) NULL)) 182 splay_tree->root->value=splay_tree->relinquish_value( 183 splay_tree->root->value); 184 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 185 (splay_tree->root->key != (void *) NULL)) 186 splay_tree->root->key=splay_tree->relinquish_key( 187 splay_tree->root->key); 188 splay_tree->root->key=(void *) key; 189 splay_tree->root->value=(void *) value; 190 UnlockSemaphoreInfo(splay_tree->semaphore); 191 return(MagickTrue); 192 } 193 } 194 node=(NodeInfo *) AcquireMagickMemory(sizeof(*node)); 195 if (node == (NodeInfo *) NULL) 196 { 197 UnlockSemaphoreInfo(splay_tree->semaphore); 198 return(MagickFalse); 199 } 200 node->key=(void *) key; 201 node->value=(void *) value; 202 if (splay_tree->root == (NodeInfo *) NULL) 203 { 204 node->left=(NodeInfo *) NULL; 205 node->right=(NodeInfo *) NULL; 206 } 207 else 208 if (compare < 0) 209 { 210 node->left=splay_tree->root; 211 node->right=node->left->right; 212 node->left->right=(NodeInfo *) NULL; 213 } 214 else 215 { 216 node->right=splay_tree->root; 217 node->left=node->right->left; 218 node->right->left=(NodeInfo *) NULL; 219 } 220 splay_tree->root=node; 221 splay_tree->key=(void *) NULL; 222 splay_tree->nodes++; 223 UnlockSemaphoreInfo(splay_tree->semaphore); 224 return(MagickTrue); 225 } 226 227 /* 229 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 230 % % 231 % % 232 % % 233 % B a l a n c e S p l a y T r e e % 234 % % 235 % % 236 % % 237 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 238 % 239 % BalanceSplayTree() balances the splay-tree. 240 % 241 % The format of the BalanceSplayTree method is: 242 % 243 % void *BalanceSplayTree(SplayTreeInfo *splay_tree,const void *key) 244 % 245 % A description of each parameter follows: 246 % 247 % o splay_tree: the splay-tree info. 248 % 249 % o key: the key. 250 % 251 */ 252 253 static NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const size_t low, 254 const size_t high) 255 { 256 register NodeInfo 257 *node; 258 259 size_t 260 bisect; 261 262 bisect=low+(high-low)/2; 263 node=nodes[bisect]; 264 if ((low+1) > bisect) 265 node->left=(NodeInfo *) NULL; 266 else 267 node->left=LinkSplayTreeNodes(nodes,low,bisect-1); 268 if ((bisect+1) > high) 269 node->right=(NodeInfo *) NULL; 270 else 271 node->right=LinkSplayTreeNodes(nodes,bisect+1,high); 272 return(node); 273 } 274 275 static inline int SplayTreeToNodeArray(NodeInfo *node,const void *nodes) 276 { 277 register const NodeInfo 278 ***p; 279 280 p=(const NodeInfo ***) nodes; 281 *(*p)=node; 282 (*p)++; 283 return(0); 284 } 285 286 static void BalanceSplayTree(SplayTreeInfo *splay_tree) 287 { 288 NodeInfo 289 **node, 290 **nodes; 291 292 if (splay_tree->nodes <= 2) 293 { 294 splay_tree->balance=MagickFalse; 295 return; 296 } 297 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes, 298 sizeof(*nodes)); 299 if (nodes == (NodeInfo **) NULL) 300 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); 301 node=nodes; 302 (void) IterateOverSplayTree(splay_tree,SplayTreeToNodeArray,(const void *) 303 &node); 304 splay_tree->root=LinkSplayTreeNodes(nodes,0,splay_tree->nodes-1); 305 splay_tree->balance=MagickFalse; 306 nodes=(NodeInfo **) RelinquishMagickMemory(nodes); 307 } 308 309 /* 311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 312 % % 313 % % 314 % % 315 % C l o n e S p l a y T r e e % 316 % % 317 % % 318 % % 319 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 320 % 321 % CloneSplayTree() clones the splay tree. 322 % 323 % The format of the CloneSplayTree method is: 324 % 325 % SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree, 326 % void *(*clone_key)(void *),void *(*cline_value)(void *)) 327 % 328 % A description of each parameter follows: 329 % 330 % o splay_tree: the splay tree. 331 % 332 % o clone_key: the key clone method, typically ConstantString(), called 333 % whenever a key is added to the splay-tree. 334 % 335 % o clone_value: the value clone method; typically ConstantString(), called 336 % whenever a value object is added to the splay-tree. 337 % 338 */ 339 340 static inline void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree) 341 { 342 register NodeInfo 343 *node; 344 345 node=splay_tree->root; 346 if (splay_tree->root == (NodeInfo *) NULL) 347 return((NodeInfo *) NULL); 348 while (node->left != (NodeInfo *) NULL) 349 node=node->left; 350 return(node->key); 351 } 352 353 MagickExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree, 354 void *(*clone_key)(void *),void *(*clone_value)(void *)) 355 { 356 register NodeInfo 357 *next, 358 *node; 359 360 SplayTreeInfo 361 *clone_tree; 362 363 assert(splay_tree != (SplayTreeInfo *) NULL); 364 assert(splay_tree->signature == MagickCoreSignature); 365 if (splay_tree->debug != MagickFalse) 366 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 367 clone_tree=NewSplayTree(splay_tree->compare,splay_tree->relinquish_key, 368 splay_tree->relinquish_value); 369 LockSemaphoreInfo(splay_tree->semaphore); 370 if (splay_tree->root == (NodeInfo *) NULL) 371 { 372 UnlockSemaphoreInfo(splay_tree->semaphore); 373 return(clone_tree); 374 } 375 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree); 376 while (next != (NodeInfo *) NULL) 377 { 378 SplaySplayTree(splay_tree,next); 379 (void) AddValueToSplayTree(clone_tree,clone_key(splay_tree->root->key), 380 clone_value(splay_tree->root->value)); 381 next=(NodeInfo *) NULL; 382 node=splay_tree->root->right; 383 if (node != (NodeInfo *) NULL) 384 { 385 while (node->left != (NodeInfo *) NULL) 386 node=node->left; 387 next=(NodeInfo *) node->key; 388 } 389 } 390 UnlockSemaphoreInfo(splay_tree->semaphore); 391 return(clone_tree); 392 } 393 394 /* 396 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 397 % % 398 % % 399 % % 400 % C o m p a r e S p l a y T r e e S t r i n g % 401 % % 402 % % 403 % % 404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 405 % 406 % CompareSplayTreeString() method finds a node in a splay-tree based on the 407 % contents of a string. 408 % 409 % The format of the CompareSplayTreeString method is: 410 % 411 % int CompareSplayTreeString(const void *target,const void *source) 412 % 413 % A description of each parameter follows: 414 % 415 % o target: the target string. 416 % 417 % o source: the source string. 418 % 419 */ 420 MagickExport int CompareSplayTreeString(const void *target,const void *source) 421 { 422 const char 423 *p, 424 *q; 425 426 p=(const char *) target; 427 q=(const char *) source; 428 return(LocaleCompare(p,q)); 429 } 430 431 /* 433 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 434 % % 435 % % 436 % % 437 % C o m p a r e S p l a y T r e e S t r i n g I n f o % 438 % % 439 % % 440 % % 441 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 442 % 443 % CompareSplayTreeStringInfo() finds a node in a splay-tree based on the 444 % contents of a string. 445 % 446 % The format of the CompareSplayTreeStringInfo method is: 447 % 448 % int CompareSplayTreeStringInfo(const void *target,const void *source) 449 % 450 % A description of each parameter follows: 451 % 452 % o target: the target string. 453 % 454 % o source: the source string. 455 % 456 */ 457 MagickExport int CompareSplayTreeStringInfo(const void *target, 458 const void *source) 459 { 460 const StringInfo 461 *p, 462 *q; 463 464 p=(const StringInfo *) target; 465 q=(const StringInfo *) source; 466 return(CompareStringInfo(p,q)); 467 } 468 469 /* 471 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 472 % % 473 % % 474 % % 475 % D e l e t e N o d e B y V a l u e F r o m S p l a y T r e e % 476 % % 477 % % 478 % % 479 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 480 % 481 % DeleteNodeByValueFromSplayTree() deletes a node by value from the 482 % splay-tree. 483 % 484 % The format of the DeleteNodeByValueFromSplayTree method is: 485 % 486 % MagickBooleanType DeleteNodeByValueFromSplayTree( 487 % SplayTreeInfo *splay_tree,const void *value) 488 % 489 % A description of each parameter follows: 490 % 491 % o splay_tree: the splay-tree info. 492 % 493 % o value: the value. 494 % 495 */ 496 MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree( 497 SplayTreeInfo *splay_tree,const void *value) 498 { 499 register NodeInfo 500 *next, 501 *node; 502 503 assert(splay_tree != (SplayTreeInfo *) NULL); 504 assert(splay_tree->signature == MagickCoreSignature); 505 if (splay_tree->debug != MagickFalse) 506 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 507 LockSemaphoreInfo(splay_tree->semaphore); 508 if (splay_tree->root == (NodeInfo *) NULL) 509 { 510 UnlockSemaphoreInfo(splay_tree->semaphore); 511 return(MagickFalse); 512 } 513 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree); 514 while (next != (NodeInfo *) NULL) 515 { 516 SplaySplayTree(splay_tree,next); 517 next=(NodeInfo *) NULL; 518 node=splay_tree->root->right; 519 if (node != (NodeInfo *) NULL) 520 { 521 while (node->left != (NodeInfo *) NULL) 522 node=node->left; 523 next=(NodeInfo *) node->key; 524 } 525 if (splay_tree->root->value == value) 526 { 527 int 528 compare; 529 530 register NodeInfo 531 *left, 532 *right; 533 534 void 535 *key; 536 537 /* 538 We found the node that matches the value; now delete it. 539 */ 540 key=splay_tree->root->key; 541 SplaySplayTree(splay_tree,key); 542 splay_tree->key=(void *) NULL; 543 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 544 compare=splay_tree->compare(splay_tree->root->key,key); 545 else 546 compare=(splay_tree->root->key > key) ? 1 : 547 ((splay_tree->root->key < key) ? -1 : 0); 548 if (compare != 0) 549 { 550 UnlockSemaphoreInfo(splay_tree->semaphore); 551 return(MagickFalse); 552 } 553 left=splay_tree->root->left; 554 right=splay_tree->root->right; 555 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 556 (splay_tree->root->value != (void *) NULL)) 557 splay_tree->root->value=splay_tree->relinquish_value( 558 splay_tree->root->value); 559 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 560 (splay_tree->root->key != (void *) NULL)) 561 splay_tree->root->key=splay_tree->relinquish_key( 562 splay_tree->root->key); 563 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root); 564 splay_tree->nodes--; 565 if (left == (NodeInfo *) NULL) 566 { 567 splay_tree->root=right; 568 UnlockSemaphoreInfo(splay_tree->semaphore); 569 return(MagickTrue); 570 } 571 splay_tree->root=left; 572 if (right != (NodeInfo *) NULL) 573 { 574 while (left->right != (NodeInfo *) NULL) 575 left=left->right; 576 left->right=right; 577 } 578 UnlockSemaphoreInfo(splay_tree->semaphore); 579 return(MagickTrue); 580 } 581 } 582 UnlockSemaphoreInfo(splay_tree->semaphore); 583 return(MagickFalse); 584 } 585 586 /* 588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 589 % % 590 % % 591 % % 592 % D e l e t e N o d e F r o m S p l a y T r e e % 593 % % 594 % % 595 % % 596 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 597 % 598 % DeleteNodeFromSplayTree() deletes a node from the splay-tree. It returns 599 % MagickTrue if the option is found and successfully deleted from the 600 % splay-tree. 601 % 602 % The format of the DeleteNodeFromSplayTree method is: 603 % 604 % MagickBooleanType DeleteNodeFromSplayTree(SplayTreeInfo *splay_tree, 605 % const void *key) 606 % 607 % A description of each parameter follows: 608 % 609 % o splay_tree: the splay-tree info. 610 % 611 % o key: the key. 612 % 613 */ 614 MagickExport MagickBooleanType DeleteNodeFromSplayTree( 615 SplayTreeInfo *splay_tree,const void *key) 616 { 617 int 618 compare; 619 620 register NodeInfo 621 *left, 622 *right; 623 624 assert(splay_tree != (SplayTreeInfo *) NULL); 625 assert(splay_tree->signature == MagickCoreSignature); 626 if (splay_tree->debug != MagickFalse) 627 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 628 if (splay_tree->root == (NodeInfo *) NULL) 629 return(MagickFalse); 630 LockSemaphoreInfo(splay_tree->semaphore); 631 SplaySplayTree(splay_tree,key); 632 splay_tree->key=(void *) NULL; 633 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 634 compare=splay_tree->compare(splay_tree->root->key,key); 635 else 636 compare=(splay_tree->root->key > key) ? 1 : 637 ((splay_tree->root->key < key) ? -1 : 0); 638 if (compare != 0) 639 { 640 UnlockSemaphoreInfo(splay_tree->semaphore); 641 return(MagickFalse); 642 } 643 left=splay_tree->root->left; 644 right=splay_tree->root->right; 645 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 646 (splay_tree->root->value != (void *) NULL)) 647 splay_tree->root->value=splay_tree->relinquish_value( 648 splay_tree->root->value); 649 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 650 (splay_tree->root->key != (void *) NULL)) 651 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key); 652 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root); 653 splay_tree->nodes--; 654 if (left == (NodeInfo *) NULL) 655 { 656 splay_tree->root=right; 657 UnlockSemaphoreInfo(splay_tree->semaphore); 658 return(MagickTrue); 659 } 660 splay_tree->root=left; 661 if (right != (NodeInfo *) NULL) 662 { 663 while (left->right != (NodeInfo *) NULL) 664 left=left->right; 665 left->right=right; 666 } 667 UnlockSemaphoreInfo(splay_tree->semaphore); 668 return(MagickTrue); 669 } 670 671 /* 673 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 674 % % 675 % % 676 % % 677 % D e s t r o y S p l a y T r e e % 678 % % 679 % % 680 % % 681 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 682 % 683 % DestroySplayTree() destroys the splay-tree. 684 % 685 % The format of the DestroySplayTree method is: 686 % 687 % SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree) 688 % 689 % A description of each parameter follows: 690 % 691 % o splay_tree: the splay tree. 692 % 693 */ 694 MagickExport SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree) 695 { 696 NodeInfo 697 *node; 698 699 register NodeInfo 700 *active, 701 *pend; 702 703 LockSemaphoreInfo(splay_tree->semaphore); 704 if (splay_tree->root != (NodeInfo *) NULL) 705 { 706 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 707 (splay_tree->root->value != (void *) NULL)) 708 splay_tree->root->value=splay_tree->relinquish_value( 709 splay_tree->root->value); 710 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 711 (splay_tree->root->key != (void *) NULL)) 712 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key); 713 splay_tree->root->key=(void *) NULL; 714 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; ) 715 { 716 active=pend; 717 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; ) 718 { 719 if (active->left != (NodeInfo *) NULL) 720 { 721 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 722 (active->left->value != (void *) NULL)) 723 active->left->value=splay_tree->relinquish_value( 724 active->left->value); 725 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 726 (active->left->key != (void *) NULL)) 727 active->left->key=splay_tree->relinquish_key(active->left->key); 728 active->left->key=(void *) pend; 729 pend=active->left; 730 } 731 if (active->right != (NodeInfo *) NULL) 732 { 733 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 734 (active->right->value != (void *) NULL)) 735 active->right->value=splay_tree->relinquish_value( 736 active->right->value); 737 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 738 (active->right->key != (void *) NULL)) 739 active->right->key=splay_tree->relinquish_key( 740 active->right->key); 741 active->right->key=(void *) pend; 742 pend=active->right; 743 } 744 node=active; 745 active=(NodeInfo *) node->key; 746 node=(NodeInfo *) RelinquishMagickMemory(node); 747 } 748 } 749 } 750 splay_tree->signature=(~MagickCoreSignature); 751 UnlockSemaphoreInfo(splay_tree->semaphore); 752 RelinquishSemaphoreInfo(&splay_tree->semaphore); 753 splay_tree=(SplayTreeInfo *) RelinquishMagickMemory(splay_tree); 754 return(splay_tree); 755 } 756 757 /* 759 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 760 % % 761 % % 762 % % 763 % G e t N e x t K e y I n S p l a y T r e e % 764 % % 765 % % 766 % % 767 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 768 % 769 % GetNextKeyInSplayTree() gets the next key in the splay-tree. 770 % 771 % The format of the GetNextKeyInSplayTree method is: 772 % 773 % const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree) 774 % 775 % A description of each parameter follows: 776 % 777 % o splay_tree: the splay tree. 778 % 779 % o key: the key. 780 % 781 */ 782 MagickExport const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree) 783 { 784 register NodeInfo 785 *node; 786 787 void 788 *key; 789 790 assert(splay_tree != (SplayTreeInfo *) NULL); 791 assert(splay_tree->signature == MagickCoreSignature); 792 if (splay_tree->debug != MagickFalse) 793 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 794 if ((splay_tree->root == (NodeInfo *) NULL) || 795 (splay_tree->next == (void *) NULL)) 796 return((void *) NULL); 797 LockSemaphoreInfo(splay_tree->semaphore); 798 SplaySplayTree(splay_tree,splay_tree->next); 799 splay_tree->next=(void *) NULL; 800 node=splay_tree->root->right; 801 if (node != (NodeInfo *) NULL) 802 { 803 while (node->left != (NodeInfo *) NULL) 804 node=node->left; 805 splay_tree->next=node->key; 806 } 807 key=splay_tree->root->key; 808 UnlockSemaphoreInfo(splay_tree->semaphore); 809 return(key); 810 } 811 812 /* 814 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 815 % % 816 % % 817 % % 818 % G e t N e x t V a l u e I n S p l a y T r e e % 819 % % 820 % % 821 % % 822 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 823 % 824 % GetNextValueInSplayTree() gets the next value in the splay-tree. 825 % 826 % The format of the GetNextValueInSplayTree method is: 827 % 828 % const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree) 829 % 830 % A description of each parameter follows: 831 % 832 % o splay_tree: the splay tree. 833 % 834 % o key: the key. 835 % 836 */ 837 MagickExport const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree) 838 { 839 register NodeInfo 840 *node; 841 842 void 843 *value; 844 845 assert(splay_tree != (SplayTreeInfo *) NULL); 846 assert(splay_tree->signature == MagickCoreSignature); 847 if (splay_tree->debug != MagickFalse) 848 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 849 if ((splay_tree->root == (NodeInfo *) NULL) || 850 (splay_tree->next == (void *) NULL)) 851 return((void *) NULL); 852 LockSemaphoreInfo(splay_tree->semaphore); 853 SplaySplayTree(splay_tree,splay_tree->next); 854 splay_tree->next=(void *) NULL; 855 node=splay_tree->root->right; 856 if (node != (NodeInfo *) NULL) 857 { 858 while (node->left != (NodeInfo *) NULL) 859 node=node->left; 860 splay_tree->next=node->key; 861 } 862 value=splay_tree->root->value; 863 UnlockSemaphoreInfo(splay_tree->semaphore); 864 return(value); 865 } 866 867 /* 869 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 870 % % 871 % % 872 % % 873 % G e t R o o t V a l u e F r o m S p l a y T r e e % 874 % % 875 % % 876 % % 877 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 878 % 879 % GetRootValueFromSplayTree() gets the root value from the splay-tree. 880 % 881 % The format of the GetRootValueFromSplayTree method is: 882 % 883 % const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree) 884 % 885 % A description of each parameter follows: 886 % 887 % o splay_tree: the splay tree. 888 % 889 % o key: the key. 890 % 891 */ 892 MagickExport const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree) 893 { 894 const void 895 *value; 896 897 assert(splay_tree != (SplayTreeInfo *) NULL); 898 assert(splay_tree->signature == MagickCoreSignature); 899 if (splay_tree->debug != MagickFalse) 900 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 901 value=(const void *) NULL; 902 LockSemaphoreInfo(splay_tree->semaphore); 903 if (splay_tree->root != (NodeInfo *) NULL) 904 value=splay_tree->root->value; 905 UnlockSemaphoreInfo(splay_tree->semaphore); 906 return(value); 907 } 908 909 /* 911 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 912 % % 913 % % 914 % % 915 % G e t V a l u e F r o m S p l a y T r e e % 916 % % 917 % % 918 % % 919 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 920 % 921 % GetValueFromSplayTree() gets a value from the splay-tree by its key. 922 % 923 % Note, the value is a constant. Do not attempt to free it. 924 % 925 % The format of the GetValueFromSplayTree method is: 926 % 927 % const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree, 928 % const void *key) 929 % 930 % A description of each parameter follows: 931 % 932 % o splay_tree: the splay tree. 933 % 934 % o key: the key. 935 % 936 */ 937 MagickExport const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree, 938 const void *key) 939 { 940 int 941 compare; 942 943 void 944 *value; 945 946 assert(splay_tree != (SplayTreeInfo *) NULL); 947 assert(splay_tree->signature == MagickCoreSignature); 948 if (splay_tree->debug != MagickFalse) 949 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 950 if (splay_tree->root == (NodeInfo *) NULL) 951 return((void *) NULL); 952 LockSemaphoreInfo(splay_tree->semaphore); 953 SplaySplayTree(splay_tree,key); 954 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 955 compare=splay_tree->compare(splay_tree->root->key,key); 956 else 957 compare=(splay_tree->root->key > key) ? 1 : 958 ((splay_tree->root->key < key) ? -1 : 0); 959 if (compare != 0) 960 { 961 UnlockSemaphoreInfo(splay_tree->semaphore); 962 return((void *) NULL); 963 } 964 value=splay_tree->root->value; 965 UnlockSemaphoreInfo(splay_tree->semaphore); 966 return(value); 967 } 968 969 /* 971 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 972 % % 973 % % 974 % % 975 % G e t N u m b e r O f N o d e s I n S p l a y T r e e % 976 % % 977 % % 978 % % 979 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 980 % 981 % GetNumberOfNodesInSplayTree() returns the number of nodes in the splay-tree. 982 % 983 % The format of the GetNumberOfNodesInSplayTree method is: 984 % 985 % size_t GetNumberOfNodesInSplayTree( 986 % const SplayTreeInfo *splay_tree) 987 % 988 % A description of each parameter follows: 989 % 990 % o splay_tree: the splay tree. 991 % 992 */ 993 MagickExport size_t GetNumberOfNodesInSplayTree( 994 const SplayTreeInfo *splay_tree) 995 { 996 assert(splay_tree != (SplayTreeInfo *) NULL); 997 assert(splay_tree->signature == MagickCoreSignature); 998 if (splay_tree->debug != MagickFalse) 999 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 1000 return(splay_tree->nodes); 1001 } 1002 1003 /* 1005 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1006 % % 1007 % % 1008 % % 1009 % I t e r a t e O v e r S p l a y T r e e % 1010 % % 1011 % % 1012 % % 1013 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1014 % 1015 % IterateOverSplayTree() iterates over the splay-tree. 1016 % 1017 % The format of the IterateOverSplayTree method is: 1018 % 1019 % int IterateOverSplayTree(SplayTreeInfo *splay_tree, 1020 % int (*method)(NodeInfo *,void *),const void *value) 1021 % 1022 % A description of each parameter follows: 1023 % 1024 % o splay_tree: the splay-tree info. 1025 % 1026 % o method: the method. 1027 % 1028 % o value: the value. 1029 % 1030 */ 1031 static int IterateOverSplayTree(SplayTreeInfo *splay_tree, 1032 int (*method)(NodeInfo *,const void *),const void *value) 1033 { 1034 typedef enum 1035 { 1036 LeftTransition, 1037 RightTransition, 1038 DownTransition, 1039 UpTransition 1040 } TransitionType; 1041 1042 int 1043 status; 1044 1045 MagickBooleanType 1046 final_transition; 1047 1048 NodeInfo 1049 **nodes; 1050 1051 register ssize_t 1052 i; 1053 1054 register NodeInfo 1055 *node; 1056 1057 TransitionType 1058 transition; 1059 1060 unsigned char 1061 *transitions; 1062 1063 if (splay_tree->root == (NodeInfo *) NULL) 1064 return(0); 1065 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes, 1066 sizeof(*nodes)); 1067 transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes, 1068 sizeof(*transitions)); 1069 if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL)) 1070 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); 1071 status=0; 1072 final_transition=MagickFalse; 1073 nodes[0]=splay_tree->root; 1074 transitions[0]=(unsigned char) LeftTransition; 1075 for (i=0; final_transition == MagickFalse; ) 1076 { 1077 node=nodes[i]; 1078 transition=(TransitionType) transitions[i]; 1079 switch (transition) 1080 { 1081 case LeftTransition: 1082 { 1083 transitions[i]=(unsigned char) DownTransition; 1084 if (node->left == (NodeInfo *) NULL) 1085 break; 1086 i++; 1087 nodes[i]=node->left; 1088 transitions[i]=(unsigned char) LeftTransition; 1089 break; 1090 } 1091 case RightTransition: 1092 { 1093 transitions[i]=(unsigned char) UpTransition; 1094 if (node->right == (NodeInfo *) NULL) 1095 break; 1096 i++; 1097 nodes[i]=node->right; 1098 transitions[i]=(unsigned char) LeftTransition; 1099 break; 1100 } 1101 case DownTransition: 1102 default: 1103 { 1104 transitions[i]=(unsigned char) RightTransition; 1105 status=(*method)(node,value); 1106 if (status != 0) 1107 final_transition=MagickTrue; 1108 break; 1109 } 1110 case UpTransition: 1111 { 1112 if (i == 0) 1113 { 1114 final_transition=MagickTrue; 1115 break; 1116 } 1117 i--; 1118 break; 1119 } 1120 } 1121 } 1122 nodes=(NodeInfo **) RelinquishMagickMemory(nodes); 1123 transitions=(unsigned char *) RelinquishMagickMemory(transitions); 1124 return(status); 1125 } 1126 1127 /* 1129 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1130 % % 1131 % % 1132 % % 1133 % N e w S p l a y T r e e % 1134 % % 1135 % % 1136 % % 1137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1138 % 1139 % NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized 1140 % to default values. 1141 % 1142 % The format of the NewSplayTree method is: 1143 % 1144 % SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *), 1145 % void *(*relinquish_key)(void *),void *(*relinquish_value)(void *)) 1146 % 1147 % A description of each parameter follows: 1148 % 1149 % o compare: the compare method. 1150 % 1151 % o relinquish_key: the key deallocation method, typically 1152 % RelinquishMagickMemory(), called whenever a key is removed from the 1153 % splay-tree. 1154 % 1155 % o relinquish_value: the value deallocation method; typically 1156 % RelinquishMagickMemory(), called whenever a value object is removed from 1157 % the splay-tree. 1158 % 1159 */ 1160 MagickExport SplayTreeInfo *NewSplayTree( 1161 int (*compare)(const void *,const void *),void *(*relinquish_key)(void *), 1162 void *(*relinquish_value)(void *)) 1163 { 1164 SplayTreeInfo 1165 *splay_tree; 1166 1167 splay_tree=(SplayTreeInfo *) AcquireCriticalMemory(sizeof(*splay_tree)); 1168 (void) memset(splay_tree,0,sizeof(*splay_tree)); 1169 splay_tree->root=(NodeInfo *) NULL; 1170 splay_tree->compare=compare; 1171 splay_tree->relinquish_key=relinquish_key; 1172 splay_tree->relinquish_value=relinquish_value; 1173 splay_tree->balance=MagickFalse; 1174 splay_tree->key=(void *) NULL; 1175 splay_tree->next=(void *) NULL; 1176 splay_tree->nodes=0; 1177 splay_tree->debug=IsEventLogging(); 1178 splay_tree->semaphore=AcquireSemaphoreInfo(); 1179 splay_tree->signature=MagickCoreSignature; 1180 return(splay_tree); 1181 } 1182 1183 /* 1185 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1186 % % 1187 % % 1188 % % 1189 % R e m o v e N o d e B y V a l u e F r o m S p l a y T r e e % 1190 % % 1191 % % 1192 % % 1193 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1194 % 1195 % RemoveNodeByValueFromSplayTree() removes a node by value from the splay-tree 1196 % and returns its key. 1197 % 1198 % The format of the RemoveNodeByValueFromSplayTree method is: 1199 % 1200 % void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree, 1201 % const void *value) 1202 % 1203 % A description of each parameter follows: 1204 % 1205 % o splay_tree: the splay-tree info. 1206 % 1207 % o value: the value. 1208 % 1209 */ 1210 MagickExport void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree, 1211 const void *value) 1212 { 1213 register NodeInfo 1214 *next, 1215 *node; 1216 1217 void 1218 *key; 1219 1220 assert(splay_tree != (SplayTreeInfo *) NULL); 1221 assert(splay_tree->signature == MagickCoreSignature); 1222 if (splay_tree->debug != MagickFalse) 1223 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 1224 key=(void *) NULL; 1225 if (splay_tree->root == (NodeInfo *) NULL) 1226 return(key); 1227 LockSemaphoreInfo(splay_tree->semaphore); 1228 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree); 1229 while (next != (NodeInfo *) NULL) 1230 { 1231 SplaySplayTree(splay_tree,next); 1232 next=(NodeInfo *) NULL; 1233 node=splay_tree->root->right; 1234 if (node != (NodeInfo *) NULL) 1235 { 1236 while (node->left != (NodeInfo *) NULL) 1237 node=node->left; 1238 next=(NodeInfo *) node->key; 1239 } 1240 if (splay_tree->root->value == value) 1241 { 1242 int 1243 compare; 1244 1245 register NodeInfo 1246 *left, 1247 *right; 1248 1249 /* 1250 We found the node that matches the value; now remove it. 1251 */ 1252 key=splay_tree->root->key; 1253 SplaySplayTree(splay_tree,key); 1254 splay_tree->key=(void *) NULL; 1255 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 1256 compare=splay_tree->compare(splay_tree->root->key,key); 1257 else 1258 compare=(splay_tree->root->key > key) ? 1 : 1259 ((splay_tree->root->key < key) ? -1 : 0); 1260 if (compare != 0) 1261 { 1262 UnlockSemaphoreInfo(splay_tree->semaphore); 1263 return(key); 1264 } 1265 left=splay_tree->root->left; 1266 right=splay_tree->root->right; 1267 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 1268 (splay_tree->root->value != (void *) NULL)) 1269 splay_tree->root->value=splay_tree->relinquish_value( 1270 splay_tree->root->value); 1271 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root); 1272 splay_tree->nodes--; 1273 if (left == (NodeInfo *) NULL) 1274 { 1275 splay_tree->root=right; 1276 UnlockSemaphoreInfo(splay_tree->semaphore); 1277 return(key); 1278 } 1279 splay_tree->root=left; 1280 if (right != (NodeInfo *) NULL) 1281 { 1282 while (left->right != (NodeInfo *) NULL) 1283 left=left->right; 1284 left->right=right; 1285 } 1286 UnlockSemaphoreInfo(splay_tree->semaphore); 1287 return(key); 1288 } 1289 } 1290 UnlockSemaphoreInfo(splay_tree->semaphore); 1291 return(key); 1292 } 1293 1294 /* 1296 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1297 % % 1298 % % 1299 % % 1300 % R e m o v e N o d e F r o m S p l a y T r e e % 1301 % % 1302 % % 1303 % % 1304 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1305 % 1306 % RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its 1307 % value. 1308 % 1309 % The format of the RemoveNodeFromSplayTree method is: 1310 % 1311 % void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key) 1312 % 1313 % A description of each parameter follows: 1314 % 1315 % o splay_tree: the splay-tree info. 1316 % 1317 % o key: the key. 1318 % 1319 */ 1320 MagickExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree, 1321 const void *key) 1322 { 1323 int 1324 compare; 1325 1326 register NodeInfo 1327 *left, 1328 *right; 1329 1330 void 1331 *value; 1332 1333 assert(splay_tree != (SplayTreeInfo *) NULL); 1334 assert(splay_tree->signature == MagickCoreSignature); 1335 if (splay_tree->debug != MagickFalse) 1336 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 1337 value=(void *) NULL; 1338 if (splay_tree->root == (NodeInfo *) NULL) 1339 return(value); 1340 LockSemaphoreInfo(splay_tree->semaphore); 1341 SplaySplayTree(splay_tree,key); 1342 splay_tree->key=(void *) NULL; 1343 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 1344 compare=splay_tree->compare(splay_tree->root->key,key); 1345 else 1346 compare=(splay_tree->root->key > key) ? 1 : 1347 ((splay_tree->root->key < key) ? -1 : 0); 1348 if (compare != 0) 1349 { 1350 UnlockSemaphoreInfo(splay_tree->semaphore); 1351 return(value); 1352 } 1353 left=splay_tree->root->left; 1354 right=splay_tree->root->right; 1355 value=splay_tree->root->value; 1356 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 1357 (splay_tree->root->key != (void *) NULL)) 1358 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key); 1359 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root); 1360 splay_tree->nodes--; 1361 if (left == (NodeInfo *) NULL) 1362 { 1363 splay_tree->root=right; 1364 UnlockSemaphoreInfo(splay_tree->semaphore); 1365 return(value); 1366 } 1367 splay_tree->root=left; 1368 if (right != (NodeInfo *) NULL) 1369 { 1370 while (left->right != (NodeInfo *) NULL) 1371 left=left->right; 1372 left->right=right; 1373 } 1374 UnlockSemaphoreInfo(splay_tree->semaphore); 1375 return(value); 1376 } 1377 1378 /* 1380 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1381 % % 1382 % % 1383 % % 1384 % R e s e t S p l a y T r e e % 1385 % % 1386 % % 1387 % % 1388 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1389 % 1390 % ResetSplayTree() resets the splay-tree. That is, it deletes all the nodes 1391 % from the tree. 1392 % 1393 % The format of the ResetSplayTree method is: 1394 % 1395 % ResetSplayTree(SplayTreeInfo *splay_tree) 1396 % 1397 % A description of each parameter follows: 1398 % 1399 % o splay_tree: the splay tree. 1400 % 1401 */ 1402 MagickExport void ResetSplayTree(SplayTreeInfo *splay_tree) 1403 { 1404 NodeInfo 1405 *node; 1406 1407 register NodeInfo 1408 *active, 1409 *pend; 1410 1411 assert(splay_tree != (SplayTreeInfo *) NULL); 1412 assert(splay_tree->signature == MagickCoreSignature); 1413 if (splay_tree->debug != MagickFalse) 1414 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 1415 LockSemaphoreInfo(splay_tree->semaphore); 1416 if (splay_tree->root != (NodeInfo *) NULL) 1417 { 1418 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 1419 (splay_tree->root->value != (void *) NULL)) 1420 splay_tree->root->value=splay_tree->relinquish_value( 1421 splay_tree->root->value); 1422 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 1423 (splay_tree->root->key != (void *) NULL)) 1424 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key); 1425 splay_tree->root->key=(void *) NULL; 1426 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; ) 1427 { 1428 active=pend; 1429 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; ) 1430 { 1431 if (active->left != (NodeInfo *) NULL) 1432 { 1433 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 1434 (active->left->value != (void *) NULL)) 1435 active->left->value=splay_tree->relinquish_value( 1436 active->left->value); 1437 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 1438 (active->left->key != (void *) NULL)) 1439 active->left->key=splay_tree->relinquish_key(active->left->key); 1440 active->left->key=(void *) pend; 1441 pend=active->left; 1442 } 1443 if (active->right != (NodeInfo *) NULL) 1444 { 1445 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 1446 (active->right->value != (void *) NULL)) 1447 active->right->value=splay_tree->relinquish_value( 1448 active->right->value); 1449 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 1450 (active->right->key != (void *) NULL)) 1451 active->right->key=splay_tree->relinquish_key( 1452 active->right->key); 1453 active->right->key=(void *) pend; 1454 pend=active->right; 1455 } 1456 node=active; 1457 active=(NodeInfo *) node->key; 1458 node=(NodeInfo *) RelinquishMagickMemory(node); 1459 } 1460 } 1461 } 1462 splay_tree->root=(NodeInfo *) NULL; 1463 splay_tree->key=(void *) NULL; 1464 splay_tree->next=(void *) NULL; 1465 splay_tree->nodes=0; 1466 splay_tree->balance=MagickFalse; 1467 UnlockSemaphoreInfo(splay_tree->semaphore); 1468 } 1469 1470 /* 1472 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1473 % % 1474 % % 1475 % % 1476 % R e s e t S p l a y T r e e I t e r a t o r % 1477 % % 1478 % % 1479 % % 1480 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1481 % 1482 % ResetSplayTreeIterator() resets the splay-tree iterator. Use it in 1483 % conjunction with GetNextValueInSplayTree() to iterate over all the nodes in 1484 % the splay-tree. 1485 % 1486 % The format of the ResetSplayTreeIterator method is: 1487 % 1488 % ResetSplayTreeIterator(SplayTreeInfo *splay_tree) 1489 % 1490 % A description of each parameter follows: 1491 % 1492 % o splay_tree: the splay tree. 1493 % 1494 */ 1495 MagickExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree) 1496 { 1497 assert(splay_tree != (SplayTreeInfo *) NULL); 1498 assert(splay_tree->signature == MagickCoreSignature); 1499 if (splay_tree->debug != MagickFalse) 1500 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 1501 LockSemaphoreInfo(splay_tree->semaphore); 1502 splay_tree->next=GetFirstSplayTreeNode(splay_tree); 1503 UnlockSemaphoreInfo(splay_tree->semaphore); 1504 } 1505 1506 /* 1508 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1509 % % 1510 % % 1511 % % 1512 % S p l a y S p l a y T r e e % 1513 % % 1514 % % 1515 % % 1516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1517 % 1518 % SplaySplayTree() splays the splay-tree. 1519 % 1520 % The format of the SplaySplayTree method is: 1521 % 1522 % void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key, 1523 % NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent) 1524 % 1525 % A description of each parameter follows: 1526 % 1527 % o splay_tree: the splay-tree info. 1528 % 1529 % o key: the key. 1530 % 1531 % o node: the node. 1532 % 1533 % o parent: the parent node. 1534 % 1535 % o grandparent: the grandparent node. 1536 % 1537 */ 1538 1539 static NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth, 1540 const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent) 1541 { 1542 int 1543 compare; 1544 1545 NodeInfo 1546 **next; 1547 1548 register NodeInfo 1549 *n, 1550 *p; 1551 1552 n=(*node); 1553 if (n == (NodeInfo *) NULL) 1554 return(*parent); 1555 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 1556 compare=splay_tree->compare(n->key,key); 1557 else 1558 compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0); 1559 next=(NodeInfo **) NULL; 1560 if (compare > 0) 1561 next=(&n->left); 1562 else 1563 if (compare < 0) 1564 next=(&n->right); 1565 if (next != (NodeInfo **) NULL) 1566 { 1567 if (depth >= MaxSplayTreeDepth) 1568 { 1569 splay_tree->balance=MagickTrue; 1570 return(n); 1571 } 1572 n=Splay(splay_tree,depth+1,key,next,node,parent); 1573 if ((n != *node) || (splay_tree->balance != MagickFalse)) 1574 return(n); 1575 } 1576 if (parent == (NodeInfo **) NULL) 1577 return(n); 1578 if (grandparent == (NodeInfo **) NULL) 1579 { 1580 if (n == (*parent)->left) 1581 { 1582 *node=n->right; 1583 n->right=(*parent); 1584 } 1585 else 1586 { 1587 *node=n->left; 1588 n->left=(*parent); 1589 } 1590 *parent=n; 1591 return(n); 1592 } 1593 if ((n == (*parent)->left) && (*parent == (*grandparent)->left)) 1594 { 1595 p=(*parent); 1596 (*grandparent)->left=p->right; 1597 p->right=(*grandparent); 1598 p->left=n->right; 1599 n->right=p; 1600 *grandparent=n; 1601 return(n); 1602 } 1603 if ((n == (*parent)->right) && (*parent == (*grandparent)->right)) 1604 { 1605 p=(*parent); 1606 (*grandparent)->right=p->left; 1607 p->left=(*grandparent); 1608 p->right=n->left; 1609 n->left=p; 1610 *grandparent=n; 1611 return(n); 1612 } 1613 if (n == (*parent)->left) 1614 { 1615 (*parent)->left=n->right; 1616 n->right=(*parent); 1617 (*grandparent)->right=n->left; 1618 n->left=(*grandparent); 1619 *grandparent=n; 1620 return(n); 1621 } 1622 (*parent)->right=n->left; 1623 n->left=(*parent); 1624 (*grandparent)->left=n->right; 1625 n->right=(*grandparent); 1626 *grandparent=n; 1627 return(n); 1628 } 1629 1630 static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key) 1631 { 1632 if (splay_tree->root == (NodeInfo *) NULL) 1633 return; 1634 if (splay_tree->key != (void *) NULL) 1635 { 1636 int 1637 compare; 1638 1639 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 1640 compare=splay_tree->compare(splay_tree->root->key,key); 1641 else 1642 compare=(splay_tree->key > key) ? 1 : 1643 ((splay_tree->key < key) ? -1 : 0); 1644 if (compare == 0) 1645 return; 1646 } 1647 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL, 1648 (NodeInfo **) NULL); 1649 if (splay_tree->balance != MagickFalse) 1650 { 1651 BalanceSplayTree(splay_tree); 1652 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL, 1653 (NodeInfo **) NULL); 1654 if (splay_tree->balance != MagickFalse) 1655 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); 1656 } 1657 splay_tree->key=(void *) key; 1658 } 1659
