root/magick/splay-tree.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. AddValueToSplayTree
  2. LinkSplayTreeNodes
  3. SplayTreeToNodeArray
  4. BalanceSplayTree
  5. GetFirstSplayTreeNode
  6. CloneSplayTree
  7. CompareSplayTreeString
  8. CompareSplayTreeStringInfo
  9. DeleteNodeByValueFromSplayTree
  10. DeleteNodeFromSplayTree
  11. DestroySplayTree
  12. GetNextKeyInSplayTree
  13. GetNextValueInSplayTree
  14. GetValueFromSplayTree
  15. GetNumberOfNodesInSplayTree
  16. IterateOverSplayTree
  17. NewSplayTree
  18. RemoveNodeByValueFromSplayTree
  19. RemoveNodeFromSplayTree
  20. ResetSplayTree
  21. ResetSplayTreeIterator
  22. Splay
  23. SplaySplayTree

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%                      SSSSS  PPPP   L       AAA   Y   Y                      %
%                      SS     P   P  L      A   A   Y Y                       %
%                       SSS   PPPP   L      AAAAA    Y                        %
%                         SS  P      L      A   A    Y                        %
%                      SSSSS  P      LLLLL  A   A    Y                        %
%                                                                             %
%                         TTTTT  RRRR   EEEEE  EEEEE                          %
%                           T    R   R  E      E                              %
%                           T    RRRR   EEE    EEE                            %
%                           T    R R    E      E                              %
%                           T    R  R   EEEEE  EEEEE                          %
%                                                                             %
%                                                                             %
%             MagickCore Self-adjusting Binary Search Tree Methods            %
%                                                                             %
%                              Software Design                                %
%                                John Cristy                                  %
%                               December 2002                                 %
%                                                                             %
%                                                                             %
%  Copyright 1999-2013 ImageMagick Studio LLC, a non-profit organization      %
%  dedicated to making software imaging solutions freely available.           %
%                                                                             %
%  You may not use this file except in compliance with the License.  You may  %
%  obtain a copy of the License at                                            %
%                                                                             %
%    http://www.imagemagick.org/script/license.php                            %
%                                                                             %
%  Unless required by applicable law or agreed to in writing, software        %
%  distributed under the License is distributed on an "AS IS" BASIS,          %
%  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
%  See the License for the specific language governing permissions and        %
%  limitations under the License.                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  This module implements the standard handy splay-tree methods for storing and
%  retrieving large numbers of data elements.  It is loosely based on the Java
%  implementation of these algorithms.
%
*/

/*
  Include declarations.
*/
#include "magick/studio.h"
#include "magick/exception.h"
#include "magick/exception-private.h"
#include "magick/log.h"
#include "magick/memory_.h"
#include "magick/splay-tree.h"
#include "magick/semaphore.h"
#include "magick/string_.h"

/*
  Define declarations.
*/
#define MaxSplayTreeDepth  1024

/*
  Typedef declarations.
*/
typedef struct _NodeInfo
{
  void
    *key;

  void
    *value;

  struct _NodeInfo
    *left,
    *right;
} NodeInfo;

struct _SplayTreeInfo
{
  NodeInfo
    *root;

  int
    (*compare)(const void *,const void *);

  void
    *(*relinquish_key)(void *),
    *(*relinquish_value)(void *);

  MagickBooleanType
    balance;

  void
    *key,
    *next;

  size_t
    nodes;

  MagickBooleanType
    debug;

  SemaphoreInfo
    *semaphore;

  size_t
    signature;
};

/*
  Forward declarations.
*/
static int
  IterateOverSplayTree(SplayTreeInfo *,int (*)(NodeInfo *,const void *),
    const void *);

static void
  SplaySplayTree(SplayTreeInfo *,const void *);

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   A d d V a l u e T o S p l a y T r e e                                     %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  AddValueToSplayTree() adds the given key and value to the splay-tree.  Both
%  key and value are used as is, without coping or cloning.  It returns
%  MagickTrue on success, otherwise MagickFalse.
%
%  The format of the AddValueToSplayTree method is:
%
%      MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
%        const void *key,const void *value)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay-tree info.
%
%    o key: the key.
%
%    o value: the value.
%
*/
MagickExport MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
  const void *key,const void *value)
{
  int
    compare;

  register NodeInfo
    *node;

  LockSemaphoreInfo(splay_tree->semaphore);
  SplaySplayTree(splay_tree,key);
  compare=0;
  if (splay_tree->root != (NodeInfo *) NULL)
    {
      if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
        compare=splay_tree->compare(splay_tree->root->key,key);
      else
        compare=(splay_tree->root->key > key) ? 1 :
          ((splay_tree->root->key < key) ? -1 : 0);
      if (compare == 0)
        {
          if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
              (splay_tree->root->value != (void *) NULL))
            splay_tree->root->value=splay_tree->relinquish_value(
              splay_tree->root->value);
          if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
              (splay_tree->root->key != (void *) NULL))
            splay_tree->root->key=splay_tree->relinquish_key(
              splay_tree->root->key);
          splay_tree->root->key=(void *) key;
          splay_tree->root->value=(void *) value;
          UnlockSemaphoreInfo(splay_tree->semaphore);
          return(MagickTrue);
        }
    }
  node=(NodeInfo *) AcquireMagickMemory(sizeof(*node));
  if (node == (NodeInfo *) NULL)
    {
      UnlockSemaphoreInfo(splay_tree->semaphore);
      return(MagickFalse);
    }
  node->key=(void *) key;
  node->value=(void *) value;
  if (splay_tree->root == (NodeInfo *) NULL)
    {
      node->left=(NodeInfo *) NULL;
      node->right=(NodeInfo *) NULL;
    }
  else
    if (compare < 0)
      {
        node->left=splay_tree->root;
        node->right=node->left->right;
        node->left->right=(NodeInfo *) NULL;
      }
    else
      {
        node->right=splay_tree->root;
        node->left=node->right->left;
        node->right->left=(NodeInfo *) NULL;
      }
  splay_tree->root=node;
  splay_tree->key=(void *) NULL;
  splay_tree->nodes++;
  UnlockSemaphoreInfo(splay_tree->semaphore);
  return(MagickTrue);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   B a l a n c e S p l a y T r e e                                           %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  BalanceSplayTree() balances the splay-tree.
%
%  The format of the BalanceSplayTree method is:
%
%      void *BalanceSplayTree(SplayTreeInfo *splay_tree,const void *key)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay-tree info.
%
%    o key: the key.
%
*/

static inline NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const size_t low,
  const size_t high)
{
  register NodeInfo
    *node;

  size_t
    bisect;

  bisect=low+(high-low)/2;
  node=nodes[bisect];
  if ((low+1) > bisect)
    node->left=(NodeInfo *) NULL;
  else
    node->left=LinkSplayTreeNodes(nodes,low,bisect-1);
  if ((bisect+1) > high)
    node->right=(NodeInfo *) NULL;
  else
    node->right=LinkSplayTreeNodes(nodes,bisect+1,high);
  return(node);
}

static inline int SplayTreeToNodeArray(NodeInfo *node,const void *nodes)
{
  register const NodeInfo
    ***p;

  p=(const NodeInfo ***) nodes;
  *(*p)=node;
  (*p)++;
  return(0);
}

static void BalanceSplayTree(SplayTreeInfo *splay_tree)
{
  NodeInfo
    **node,
    **nodes;

  if (splay_tree->nodes <= 2)
    {
      splay_tree->balance=MagickFalse;
      return;
    }
  nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
    sizeof(*nodes));
  if (nodes == (NodeInfo **) NULL)
    ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
  node=nodes;
  (void) IterateOverSplayTree(splay_tree,SplayTreeToNodeArray,(const void *)
    &node);
  splay_tree->root=LinkSplayTreeNodes(nodes,0,splay_tree->nodes-1);
  splay_tree->balance=MagickFalse;
  nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   C l o n e S p l a y T r e e                                               %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  CloneSplayTree() clones the splay tree.
%
%  The format of the CloneSplayTree method is:
%
%      SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
%        void *(*clone_key)(void *),void *(*cline_value)(void *))
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay tree.
%
%    o clone_key: the key clone method, typically ConstantString(), called
%      whenever a key is added to the splay-tree.
%
%    o clone_value: the value clone method;  typically ConstantString(), called
%      whenever a value object is added to the splay-tree.
%
*/

static inline void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree)
{
  register NodeInfo
    *node;

  node=splay_tree->root;
  if (splay_tree->root == (NodeInfo *) NULL)
    return((NodeInfo *) NULL);
  while (node->left != (NodeInfo *) NULL)
    node=node->left;
  return(node->key);
}

MagickExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
  void *(*clone_key)(void *),void *(*clone_value)(void *))
{
  register NodeInfo
    *next,
    *node;

  SplayTreeInfo
    *clone_tree;

  assert(splay_tree != (SplayTreeInfo *) NULL);
  assert(splay_tree->signature == MagickSignature);
  if (splay_tree->debug != MagickFalse)
    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
  clone_tree=NewSplayTree(splay_tree->compare,splay_tree->relinquish_key,
    splay_tree->relinquish_value);
  LockSemaphoreInfo(splay_tree->semaphore);
  if (splay_tree->root == (NodeInfo *) NULL)
    {
      UnlockSemaphoreInfo(splay_tree->semaphore);
      return(clone_tree);
    }
  next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
  while (next != (NodeInfo *) NULL)
  {
    SplaySplayTree(splay_tree,next);
    (void) AddValueToSplayTree(clone_tree,clone_key(splay_tree->root->key),
      clone_value(splay_tree->root->value));
    next=(NodeInfo *) NULL;
    node=splay_tree->root->right;
    if (node != (NodeInfo *) NULL)
      {
        while (node->left != (NodeInfo *) NULL)
          node=node->left;
        next=(NodeInfo *) node->key;
      }
  }
  UnlockSemaphoreInfo(splay_tree->semaphore);
  return(clone_tree);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   C o m p a r e S p l a y T r e e S t r i n g                               %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  CompareSplayTreeString() method finds a node in a splay-tree based on the
%  contents of a string.
%
%  The format of the CompareSplayTreeString method is:
%
%      int CompareSplayTreeString(const void *target,const void *source)
%
%  A description of each parameter follows:
%
%    o target: the target string.
%
%    o source: the source string.
%
*/
MagickExport int CompareSplayTreeString(const void *target,const void *source)
{
  const char
    *p,
    *q;

  p=(const char *) target;
  q=(const char *) source;
  return(LocaleCompare(p,q));
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   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                       %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  CompareSplayTreeStringInfo() finds a node in a splay-tree based on the
%  contents of a string.
%
%  The format of the CompareSplayTreeStringInfo method is:
%
%      int CompareSplayTreeStringInfo(const void *target,const void *source)
%
%  A description of each parameter follows:
%
%    o target: the target string.
%
%    o source: the source string.
%
*/
MagickExport int CompareSplayTreeStringInfo(const void *target,
  const void *source)
{
  const StringInfo
    *p,
    *q;

  p=(const StringInfo *) target;
  q=(const StringInfo *) source;
  return(CompareStringInfo(p,q));
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   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               %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  DeleteNodeByValueFromSplayTree() deletes a node by value from the
%  splay-tree.
%
%  The format of the DeleteNodeByValueFromSplayTree method is:
%
%      MagickBooleanType DeleteNodeByValueFromSplayTree(
%        SplayTreeInfo *splay_tree,const void *value)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay-tree info.
%
%    o value: the value.
%
*/
MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree(
  SplayTreeInfo *splay_tree,const void *value)
{
  register NodeInfo
    *next,
    *node;

  assert(splay_tree != (SplayTreeInfo *) NULL);
  assert(splay_tree->signature == MagickSignature);
  if (splay_tree->debug != MagickFalse)
    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
  LockSemaphoreInfo(splay_tree->semaphore);
  if (splay_tree->root == (NodeInfo *) NULL)
    {
      UnlockSemaphoreInfo(splay_tree->semaphore);
      return(MagickFalse);
    }
  next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
  while (next != (NodeInfo *) NULL)
  {
    SplaySplayTree(splay_tree,next);
    next=(NodeInfo *) NULL;
    node=splay_tree->root->right;
    if (node != (NodeInfo *) NULL)
      {
        while (node->left != (NodeInfo *) NULL)
          node=node->left;
        next=(NodeInfo *) node->key;
      }
    if (splay_tree->root->value == value)
      {
        int
          compare;

        register NodeInfo
          *left,
          *right;

        void
          *key;

        /*
          We found the node that matches the value; now delete it.
        */
        key=splay_tree->root->key;
        SplaySplayTree(splay_tree,key);
        splay_tree->key=(void *) NULL;
        if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
          compare=splay_tree->compare(splay_tree->root->key,key);
        else
          compare=(splay_tree->root->key > key) ? 1 :
            ((splay_tree->root->key < key) ? -1 : 0);
        if (compare != 0)
          {
            UnlockSemaphoreInfo(splay_tree->semaphore);
            return(MagickFalse);
          }
        left=splay_tree->root->left;
        right=splay_tree->root->right;
        if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
            (splay_tree->root->value != (void *) NULL))
          splay_tree->root->value=splay_tree->relinquish_value(
            splay_tree->root->value);
        if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
            (splay_tree->root->key != (void *) NULL))
          splay_tree->root->key=splay_tree->relinquish_key(
            splay_tree->root->key);
        splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
        splay_tree->nodes--;
        if (left == (NodeInfo *) NULL)
          {
            splay_tree->root=right;
            UnlockSemaphoreInfo(splay_tree->semaphore);
            return(MagickTrue);
          }
        splay_tree->root=left;
        if (right != (NodeInfo *) NULL)
          {
            while (left->right != (NodeInfo *) NULL)
              left=left->right;
            left->right=right;
          }
        UnlockSemaphoreInfo(splay_tree->semaphore);
        return(MagickTrue);
      }
  }
  UnlockSemaphoreInfo(splay_tree->semaphore);
  return(MagickFalse);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   D e l e t e N o d e F r o m S p l a y T r e e                             %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  DeleteNodeFromSplayTree() deletes a node from the splay-tree.  It returns
%  MagickTrue if the option is found and successfully deleted from the
%  splay-tree.
%
%  The format of the DeleteNodeFromSplayTree method is:
%
%      MagickBooleanType DeleteNodeFromSplayTree(SplayTreeInfo *splay_tree,
%        const void *key)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay-tree info.
%
%    o key: the key.
%
*/
MagickExport MagickBooleanType DeleteNodeFromSplayTree(
  SplayTreeInfo *splay_tree,const void *key)
{
  int
    compare;

  register NodeInfo
    *left,
    *right;

  assert(splay_tree != (SplayTreeInfo *) NULL);
  assert(splay_tree->signature == MagickSignature);
  if (splay_tree->debug != MagickFalse)
    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
  if (splay_tree->root == (NodeInfo *) NULL)
    return(MagickFalse);
  LockSemaphoreInfo(splay_tree->semaphore);
  SplaySplayTree(splay_tree,key);
  splay_tree->key=(void *) NULL;
  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
    compare=splay_tree->compare(splay_tree->root->key,key);
  else
    compare=(splay_tree->root->key > key) ? 1 :
      ((splay_tree->root->key < key) ? -1 : 0);
  if (compare != 0)
    {
      UnlockSemaphoreInfo(splay_tree->semaphore);
      return(MagickFalse);
    }
  left=splay_tree->root->left;
  right=splay_tree->root->right;
  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
      (splay_tree->root->value != (void *) NULL))
    splay_tree->root->value=splay_tree->relinquish_value(
      splay_tree->root->value);
  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
      (splay_tree->root->key != (void *) NULL))
    splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
  splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
  splay_tree->nodes--;
  if (left == (NodeInfo *) NULL)
    {
      splay_tree->root=right;
      UnlockSemaphoreInfo(splay_tree->semaphore);
      return(MagickTrue);
    }
  splay_tree->root=left;
  if (right != (NodeInfo *) NULL)
    {
      while (left->right != (NodeInfo *) NULL)
        left=left->right;
      left->right=right;
    }
  UnlockSemaphoreInfo(splay_tree->semaphore);
  return(MagickTrue);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   D e s t r o y S p l a y T r e e                                           %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  DestroySplayTree() destroys the splay-tree.
%
%  The format of the DestroySplayTree method is:
%
%      SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay tree.
%
*/
MagickExport SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
{
  NodeInfo
    *node;

  register NodeInfo
    *active,
    *pend;

  LockSemaphoreInfo(splay_tree->semaphore);
  if (splay_tree->root != (NodeInfo *) NULL)
    {
      if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
          (splay_tree->root->value != (void *) NULL))
        splay_tree->root->value=splay_tree->relinquish_value(
          splay_tree->root->value);
      if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
          (splay_tree->root->key != (void *) NULL))
        splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
      splay_tree->root->key=(void *) NULL;
      for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
      {
        active=pend;
        for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
        {
          if (active->left != (NodeInfo *) NULL)
            {
              if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
                  (active->left->value != (void *) NULL))
                active->left->value=splay_tree->relinquish_value(
                  active->left->value);
              if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
                  (active->left->key != (void *) NULL))
                active->left->key=splay_tree->relinquish_key(active->left->key);
              active->left->key=(void *) pend;
              pend=active->left;
            }
          if (active->right != (NodeInfo *) NULL)
            {
              if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
                  (active->right->value != (void *) NULL))
                active->right->value=splay_tree->relinquish_value(
                  active->right->value);
              if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
                  (active->right->key != (void *) NULL))
                active->right->key=splay_tree->relinquish_key(
                  active->right->key);
              active->right->key=(void *) pend;
              pend=active->right;
            }
          node=active;
          active=(NodeInfo *) node->key;
          node=(NodeInfo *) RelinquishMagickMemory(node);
        }
      }
    }
  splay_tree->signature=(~MagickSignature);
  UnlockSemaphoreInfo(splay_tree->semaphore);
  DestroySemaphoreInfo(&splay_tree->semaphore);
  splay_tree=(SplayTreeInfo *) RelinquishMagickMemory(splay_tree);
  return(splay_tree);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   G e t N e x t K e y I n S p l a y T r e e                                 %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  GetNextKeyInSplayTree() gets the next key in the splay-tree.
%
%  The format of the GetNextKeyInSplayTree method is:
%
%      const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay tree.
%
%    o key: the key.
%
*/
MagickExport const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
{
  register NodeInfo
    *node;

  void
    *key;

  assert(splay_tree != (SplayTreeInfo *) NULL);
  assert(splay_tree->signature == MagickSignature);
  if (splay_tree->debug != MagickFalse)
    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
  if ((splay_tree->root == (NodeInfo *) NULL) ||
      (splay_tree->next == (void *) NULL))
    return((void *) NULL);
  LockSemaphoreInfo(splay_tree->semaphore);
  SplaySplayTree(splay_tree,splay_tree->next);
  splay_tree->next=(void *) NULL;
  node=splay_tree->root->right;
  if (node != (NodeInfo *) NULL)
    {
      while (node->left != (NodeInfo *) NULL)
        node=node->left;
      splay_tree->next=node->key;
    }
  key=splay_tree->root->key;
  UnlockSemaphoreInfo(splay_tree->semaphore);
  return(key);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   G e t N e x t V a l u e I n S p l a y T r e e                             %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  GetNextValueInSplayTree() gets the next value in the splay-tree.
%
%  The format of the GetNextValueInSplayTree method is:
%
%      const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay tree.
%
%    o key: the key.
%
*/
MagickExport const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
{
  register NodeInfo
    *node;

  void
    *value;

  assert(splay_tree != (SplayTreeInfo *) NULL);
  assert(splay_tree->signature == MagickSignature);
  if (splay_tree->debug != MagickFalse)
    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
  if ((splay_tree->root == (NodeInfo *) NULL) ||
      (splay_tree->next == (void *) NULL))
    return((void *) NULL);
  LockSemaphoreInfo(splay_tree->semaphore);
  SplaySplayTree(splay_tree,splay_tree->next);
  splay_tree->next=(void *) NULL;
  node=splay_tree->root->right;
  if (node != (NodeInfo *) NULL)
    {
      while (node->left != (NodeInfo *) NULL)
        node=node->left;
      splay_tree->next=node->key;
    }
  value=splay_tree->root->value;
  UnlockSemaphoreInfo(splay_tree->semaphore);
  return(value);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   G e t V a l u e F r o m S p l a y T r e e                                 %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  GetValueFromSplayTree() gets a value from the splay-tree by its key.
%
%  Note, the value is a constant.  Do not attempt to free it.
%
%  The format of the GetValueFromSplayTree method is:
%
%      const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
%        const void *key)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay tree.
%
%    o key: the key.
%
*/
MagickExport const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
  const void *key)
{
  int
    compare;

  void
    *value;

  assert(splay_tree != (SplayTreeInfo *) NULL);
  assert(splay_tree->signature == MagickSignature);
  if (splay_tree->debug != MagickFalse)
    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
  if (splay_tree->root == (NodeInfo *) NULL)
    return((void *) NULL);
  LockSemaphoreInfo(splay_tree->semaphore);
  SplaySplayTree(splay_tree,key);
  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
    compare=splay_tree->compare(splay_tree->root->key,key);
  else
    compare=(splay_tree->root->key > key) ? 1 :
      ((splay_tree->root->key < key) ? -1 : 0);
  if (compare != 0)
    {
      UnlockSemaphoreInfo(splay_tree->semaphore);
      return((void *) NULL);
    }
  value=splay_tree->root->value;
  UnlockSemaphoreInfo(splay_tree->semaphore);
  return(value);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   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                     %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  GetNumberOfNodesInSplayTree() returns the number of nodes in the splay-tree.
%
%  The format of the GetNumberOfNodesInSplayTree method is:
%
%      size_t GetNumberOfNodesInSplayTree(
%        const SplayTreeInfo *splay_tree)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay tree.
%
*/
MagickExport size_t GetNumberOfNodesInSplayTree(
  const SplayTreeInfo *splay_tree)
{
  assert(splay_tree != (SplayTreeInfo *) NULL);
  assert(splay_tree->signature == MagickSignature);
  if (splay_tree->debug != MagickFalse)
    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
  return(splay_tree->nodes);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   I t e r a t e O v e r S p l a y T r e e                                   %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  IterateOverSplayTree() iterates over the splay-tree.
%
%  The format of the IterateOverSplayTree method is:
%
%      int IterateOverSplayTree(SplayTreeInfo *splay_tree,
%        int (*method)(NodeInfo *,void *),const void *value)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay-tree info.
%
%    o method: the method.
%
%    o value: the value.
%
*/
static int IterateOverSplayTree(SplayTreeInfo *splay_tree,
  int (*method)(NodeInfo *,const void *),const void *value)
{
  typedef enum
  {
    LeftTransition,
    RightTransition,
    DownTransition,
    UpTransition
  } TransitionType;

  int
    status;

  MagickBooleanType
    final_transition;

  NodeInfo
    **nodes;

  register ssize_t
    i;

  register NodeInfo
    *node;

  TransitionType
    transition;

  unsigned char
    *transitions;

  if (splay_tree->root == (NodeInfo *) NULL)
    return(0);
  nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
    sizeof(*nodes));
  transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes,
    sizeof(*transitions));
  if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL))
    ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
  status=0;
  final_transition=MagickFalse;
  nodes[0]=splay_tree->root;
  transitions[0]=(unsigned char) LeftTransition;
  for (i=0; final_transition == MagickFalse; )
  {
    node=nodes[i];
    transition=(TransitionType) transitions[i];
    switch (transition)
    {
      case LeftTransition:
      {
        transitions[i]=(unsigned char) DownTransition;
        if (node->left == (NodeInfo *) NULL)
          break;
        i++;
        nodes[i]=node->left;
        transitions[i]=(unsigned char) LeftTransition;
        break;
      }
      case RightTransition:
      {
        transitions[i]=(unsigned char) UpTransition;
        if (node->right == (NodeInfo *) NULL)
          break;
        i++;
        nodes[i]=node->right;
        transitions[i]=(unsigned char) LeftTransition;
        break;
      }
      case DownTransition:
      default:
      {
        transitions[i]=(unsigned char) RightTransition;
        status=(*method)(node,value);
        if (status != 0)
          final_transition=MagickTrue;
        break;
      }
      case UpTransition:
      {
        if (i == 0)
          {
            final_transition=MagickTrue;
            break;
          }
        i--;
        break;
      }
    }
  }
  nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
  transitions=(unsigned char *) RelinquishMagickMemory(transitions);
  return(status);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   N e w S p l a y T r e e                                                   %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized
%  to default values.
%
%  The format of the NewSplayTree method is:
%
%      SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *),
%        void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
%
%  A description of each parameter follows:
%
%    o compare: the compare method.
%
%    o relinquish_key: the key deallocation method, typically
%      RelinquishMagickMemory(), called whenever a key is removed from the
%      splay-tree.
%
%    o relinquish_value: the value deallocation method;  typically
%      RelinquishMagickMemory(), called whenever a value object is removed from
%      the splay-tree.
%
*/
MagickExport SplayTreeInfo *NewSplayTree(
  int (*compare)(const void *,const void *),void *(*relinquish_key)(void *),
  void *(*relinquish_value)(void *))
{
  SplayTreeInfo
    *splay_tree;

  splay_tree=(SplayTreeInfo *) AcquireMagickMemory(sizeof(*splay_tree));
  if (splay_tree == (SplayTreeInfo *) NULL)
    ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
  (void) ResetMagickMemory(splay_tree,0,sizeof(*splay_tree));
  splay_tree->root=(NodeInfo *) NULL;
  splay_tree->compare=compare;
  splay_tree->relinquish_key=relinquish_key;
  splay_tree->relinquish_value=relinquish_value;
  splay_tree->balance=MagickFalse;
  splay_tree->key=(void *) NULL;
  splay_tree->next=(void *) NULL;
  splay_tree->nodes=0;
  splay_tree->debug=IsEventLogging();
  splay_tree->semaphore=AllocateSemaphoreInfo();
  splay_tree->signature=MagickSignature;
  return(splay_tree);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   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               %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  RemoveNodeByValueFromSplayTree() removes a node by value from the splay-tree
%  and returns its key.
%
%  The format of the RemoveNodeByValueFromSplayTree method is:
%
%      void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
%        const void *value)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay-tree info.
%
%    o value: the value.
%
*/
MagickExport void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
  const void *value)
{
  register NodeInfo
    *next,
    *node;

  void
    *key;

  assert(splay_tree != (SplayTreeInfo *) NULL);
  assert(splay_tree->signature == MagickSignature);
  if (splay_tree->debug != MagickFalse)
    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
  key=(void *) NULL;
  if (splay_tree->root == (NodeInfo *) NULL)
    return(key);
  LockSemaphoreInfo(splay_tree->semaphore);
  next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
  while (next != (NodeInfo *) NULL)
  {
    SplaySplayTree(splay_tree,next);
    next=(NodeInfo *) NULL;
    node=splay_tree->root->right;
    if (node != (NodeInfo *) NULL)
      {
        while (node->left != (NodeInfo *) NULL)
          node=node->left;
        next=(NodeInfo *) node->key;
      }
    if (splay_tree->root->value == value)
      {
        int
          compare;

        register NodeInfo
          *left,
          *right;

        /*
          We found the node that matches the value; now remove it.
        */
        key=splay_tree->root->key;
        SplaySplayTree(splay_tree,key);
        splay_tree->key=(void *) NULL;
        if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
          compare=splay_tree->compare(splay_tree->root->key,key);
        else
          compare=(splay_tree->root->key > key) ? 1 :
            ((splay_tree->root->key < key) ? -1 : 0);
        if (compare != 0)
          {
            UnlockSemaphoreInfo(splay_tree->semaphore);
            return(key);
          }
        left=splay_tree->root->left;
        right=splay_tree->root->right;
        if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
            (splay_tree->root->value != (void *) NULL))
          splay_tree->root->value=splay_tree->relinquish_value(
            splay_tree->root->value);
        splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
        splay_tree->nodes--;
        if (left == (NodeInfo *) NULL)
          {
            splay_tree->root=right;
            UnlockSemaphoreInfo(splay_tree->semaphore);
            return(key);
          }
        splay_tree->root=left;
        if (right != (NodeInfo *) NULL)
          {
            while (left->right != (NodeInfo *) NULL)
              left=left->right;
            left->right=right;
          }
        UnlockSemaphoreInfo(splay_tree->semaphore);
        return(key);
      }
  }
  UnlockSemaphoreInfo(splay_tree->semaphore);
  return(key);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   R e m o v e N o d e F r o m S p l a y T r e e                             %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its
%  value.
%
%  The format of the RemoveNodeFromSplayTree method is:
%
%      void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay-tree info.
%
%    o key: the key.
%
*/
MagickExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,
  const void *key)
{
  int
    compare;

  register NodeInfo
    *left,
    *right;

  void
    *value;

  assert(splay_tree != (SplayTreeInfo *) NULL);
  assert(splay_tree->signature == MagickSignature);
  if (splay_tree->debug != MagickFalse)
    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
  value=(void *) NULL;
  if (splay_tree->root == (NodeInfo *) NULL)
    return(value);
  LockSemaphoreInfo(splay_tree->semaphore);
  SplaySplayTree(splay_tree,key);
  splay_tree->key=(void *) NULL;
  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
    compare=splay_tree->compare(splay_tree->root->key,key);
  else
    compare=(splay_tree->root->key > key) ? 1 :
      ((splay_tree->root->key < key) ? -1 : 0);
  if (compare != 0)
    {
      UnlockSemaphoreInfo(splay_tree->semaphore);
      return(value);
    }
  left=splay_tree->root->left;
  right=splay_tree->root->right;
  value=splay_tree->root->value;
  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
      (splay_tree->root->key != (void *) NULL))
    splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
  splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
  splay_tree->nodes--;
  if (left == (NodeInfo *) NULL)
    {
      splay_tree->root=right;
      UnlockSemaphoreInfo(splay_tree->semaphore);
      return(value);
    }
  splay_tree->root=left;
  if (right != (NodeInfo *) NULL)
    {
      while (left->right != (NodeInfo *) NULL)
        left=left->right;
      left->right=right;
    }
  UnlockSemaphoreInfo(splay_tree->semaphore);
  return(value);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   R e s e t S p l a y T r e e                                               %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  ResetSplayTree() resets the splay-tree.  That is, it deletes all the nodes
%  from the tree.
%
%  The format of the ResetSplayTree method is:
%
%      ResetSplayTree(SplayTreeInfo *splay_tree)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay tree.
%
*/
MagickExport void ResetSplayTree(SplayTreeInfo *splay_tree)
{
  NodeInfo
    *node;

  register NodeInfo
    *active,
    *pend;

  assert(splay_tree != (SplayTreeInfo *) NULL);
  assert(splay_tree->signature == MagickSignature);
  if (splay_tree->debug != MagickFalse)
    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
  LockSemaphoreInfo(splay_tree->semaphore);
  if (splay_tree->root != (NodeInfo *) NULL)
    {
      if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
          (splay_tree->root->value != (void *) NULL))
        splay_tree->root->value=splay_tree->relinquish_value(
          splay_tree->root->value);
      if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
          (splay_tree->root->key != (void *) NULL))
        splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
      splay_tree->root->key=(void *) NULL;
      for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
      {
        active=pend;
        for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
        {
          if (active->left != (NodeInfo *) NULL)
            {
              if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
                  (active->left->value != (void *) NULL))
                active->left->value=splay_tree->relinquish_value(
                  active->left->value);
              if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
                  (active->left->key != (void *) NULL))
                active->left->key=splay_tree->relinquish_key(active->left->key);
              active->left->key=(void *) pend;
              pend=active->left;
            }
          if (active->right != (NodeInfo *) NULL)
            {
              if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
                  (active->right->value != (void *) NULL))
                active->right->value=splay_tree->relinquish_value(
                  active->right->value);
              if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
                  (active->right->key != (void *) NULL))
                active->right->key=splay_tree->relinquish_key(
                  active->right->key);
              active->right->key=(void *) pend;
              pend=active->right;
            }
          node=active;
          active=(NodeInfo *) node->key;
          node=(NodeInfo *) RelinquishMagickMemory(node);
        }
      }
    }
  splay_tree->root=(NodeInfo *) NULL;
  splay_tree->key=(void *) NULL;
  splay_tree->next=(void *) NULL;
  splay_tree->nodes=0;
  splay_tree->balance=MagickFalse;
  UnlockSemaphoreInfo(splay_tree->semaphore);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   R e s e t S p l a y T r e e I t e r a t o r                               %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  ResetSplayTreeIterator() resets the splay-tree iterator.  Use it in
%  conjunction with GetNextValueInSplayTree() to iterate over all the nodes in
%  the splay-tree.
%
%  The format of the ResetSplayTreeIterator method is:
%
%      ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay tree.
%
*/
MagickExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
{
  assert(splay_tree != (SplayTreeInfo *) NULL);
  assert(splay_tree->signature == MagickSignature);
  if (splay_tree->debug != MagickFalse)
    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
  LockSemaphoreInfo(splay_tree->semaphore);
  splay_tree->next=GetFirstSplayTreeNode(splay_tree);
  UnlockSemaphoreInfo(splay_tree->semaphore);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%   S p l a y S p l a y T r e e                                               %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  SplaySplayTree() splays the splay-tree.
%
%  The format of the SplaySplayTree method is:
%
%      void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key,
%        NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay-tree info.
%
%    o key: the key.
%
%    o node: the node.
%
%    o parent: the parent node.
%
%    o grandparent: the grandparent node.
%
*/

static inline NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth,
  const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
{
  int
    compare;

  NodeInfo
    **next;

  register NodeInfo
    *n,
    *p;

  n=(*node);
  if (n == (NodeInfo *) NULL)
    return(*parent);
  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
    compare=splay_tree->compare(n->key,key);
  else
    compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
  next=(NodeInfo **) NULL;
  if (compare > 0)
    next=(&n->left);
  else
    if (compare < 0)
      next=(&n->right);
  if (next != (NodeInfo **) NULL)
    {
      if (depth >= MaxSplayTreeDepth)
        {
          splay_tree->balance=MagickTrue;
          return(n);
        }
      n=Splay(splay_tree,depth+1,key,next,node,parent);
      if ((n != *node) || (splay_tree->balance != MagickFalse))
        return(n);
    }
  if (parent == (NodeInfo **) NULL)
    return(n);
  if (grandparent == (NodeInfo **) NULL)
    {
      if (n == (*parent)->left)
        {
          *node=n->right;
          n->right=(*parent);
        }
      else
        {
          *node=n->left;
          n->left=(*parent);
        }
      *parent=n;
      return(n);
    }
  if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
    {
      p=(*parent);
      (*grandparent)->left=p->right;
      p->right=(*grandparent);
      p->left=n->right;
      n->right=p;
      *grandparent=n;
      return(n);
    }
  if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
    {
      p=(*parent);
      (*grandparent)->right=p->left;
      p->left=(*grandparent);
      p->right=n->left;
      n->left=p;
      *grandparent=n;
      return(n);
    }
  if (n == (*parent)->left)
    {
      (*parent)->left=n->right;
      n->right=(*parent);
      (*grandparent)->right=n->left;
      n->left=(*grandparent);
      *grandparent=n;
      return(n);
    }
  (*parent)->right=n->left;
  n->left=(*parent);
  (*grandparent)->left=n->right;
  n->right=(*grandparent);
  *grandparent=n;
  return(n);
}

static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key)
{
  if (splay_tree->root == (NodeInfo *) NULL)
    return;
  if (splay_tree->key != (void *) NULL)
    {
      int
        compare;

      if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
        compare=splay_tree->compare(splay_tree->root->key,key);
      else
        compare=(splay_tree->key > key) ? 1 :
          ((splay_tree->key < key) ? -1 : 0);
      if (compare == 0)
        return;
    }
  (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
    (NodeInfo **) NULL);
  if (splay_tree->balance != MagickFalse)
    {
      BalanceSplayTree(splay_tree);
      (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
        (NodeInfo **) NULL);
      if (splay_tree->balance != MagickFalse)
        ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
    }
  splay_tree->key=(void *) key;
}

/* [<][>][^][v][top][bottom][index][help] */