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