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