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