granicus.if.org Git - imagemagick/blob - MagickCore/splay-tree.c

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