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