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