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