splay-tree.c

Go to the documentation of this file.

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%                      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-2008 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;

  unsigned long
    nodes;

  MagickBooleanType
    debug;

  SemaphoreInfo
    *semaphore;

  unsigned long
    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 a value to the splay-tree.
%
%  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;

  (void) 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_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;
          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->value=(void *) value;
          (void) UnlockSemaphoreInfo(splay_tree->semaphore);
          return(MagickTrue);
        }
    }
  node=(NodeInfo *) AcquireMagickMemory(sizeof(*node));
  if (node == (NodeInfo *) NULL)
    {
      (void) 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++;
  (void) 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 NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const unsigned long low,
  const unsigned long high)
{
  register NodeInfo
    *node;

  unsigned long
    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 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.
%
*/
MagickExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
  void *(*clone_key)(void *),void *(*clone_value)(void *))
{
  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);
  (void) LockSemaphoreInfo(splay_tree->semaphore);
  if (splay_tree->root != (NodeInfo *) NULL)
    {
      register NodeInfo
        *active,
        *next,
        *node;

      void
        *key,
        *value;

      key=splay_tree->root->key;
      if ((clone_key != (void *(*)(void *)) NULL) && (key != (void *) NULL))
        key=clone_key(key);
      value=splay_tree->root->value;
      if ((clone_value != (void *(*)(void *)) NULL) && (value != (void *) NULL))
        value=clone_value(value);
      (void) AddValueToSplayTree(clone_tree,key,value);
      for (node=splay_tree->root; node != (NodeInfo *) NULL; )
      {
        active=node;
        for (node=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
        {
          next=(NodeInfo *) NULL;
          if (active->left != (NodeInfo *) NULL)
            {
              next=node;
              key=active->left->key;
              if ((clone_key != (void *(*)(void *)) NULL) &&
                  (key != (void *) NULL))
                key=clone_key(key);
              value=active->left->value;
              if ((clone_value != (void *(*)(void *)) NULL) &&
                  (value != (void *) NULL))
                value=clone_value(value);
              (void) AddValueToSplayTree(clone_tree,key,value);
              node=active->left;
            }
          if (active->right != (NodeInfo *) NULL)
            {
              next=node;
              key=active->right->key;
              if ((clone_key != (void *(*)(void *)) NULL) &&
                  (key != (void *) NULL))
                key=clone_key(key);
              value=active->right->value;
              if ((clone_value != (void *(*)(void *)) NULL) &&
                  (value != (void *) NULL))
                value=clone_value(value);
              (void) AddValueToSplayTree(clone_tree,key,value);
              node=active->right;
            }
          active=next;
        }
      }
    }
  (void) 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.
%
*/

static 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 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(),"...");
  if (splay_tree->root == (NodeInfo *) NULL)
    return(MagickFalse);
  (void) 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;

        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)
          {
            (void) UnlockSemaphoreInfo(splay_tree->semaphore);
            return(MagickFalse);
          }
        left=splay_tree->root->left;
        right=splay_tree->root->right;
        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);
        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;
            (void) 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;
          }
        (void) UnlockSemaphoreInfo(splay_tree->semaphore);
        return(MagickTrue);
      }
  }
  (void) 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.
%
%  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);
  (void) 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)
    {
      (void) 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;
      (void) 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;
    }
  (void) 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;

  (void) LockSemaphoreInfo(splay_tree->semaphore);
  if (splay_tree->root != (NodeInfo *) NULL)
    {
      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;
      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);
      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_key != (void *(*)(void *)) NULL) &&
                  (active->left->key != (void *) NULL))
                active->left->key=splay_tree->relinquish_key(active->left->key);
              active->left->key=(void *) pend;
              if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
                  (active->left->value != (void *) NULL))
                active->left->value=splay_tree->relinquish_value(
                  active->left->value);
              pend=active->left;
            }
          if (active->right != (NodeInfo *) NULL)
            {
              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;
              if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
                  (active->right->value != (void *) NULL))
                active->right->value=splay_tree->relinquish_value(
                  active->right->value);
              pend=active->right;
            }
          node=active;
          active=(NodeInfo *) node->key;
          node=(NodeInfo *) RelinquishMagickMemory(node);
        }
      }
    }
  splay_tree->signature=(~MagickSignature);
  (void) 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:
%
%      void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay tree.
%
%    o key: the key.
%
*/
MagickExport 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);
  (void) 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;
  (void) 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:
%
%      void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay tree.
%
%    o key: the key.
%
*/
MagickExport 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);
  (void) 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;
  (void) 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.
%
%  The format of the GetValueFromSplayTree method is:
%
%      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 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);
  (void) 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)
    {
      (void) UnlockSemaphoreInfo(splay_tree->semaphore);
      return((void *) NULL);
    }
  value=splay_tree->root->value;
  (void) 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:
%
%      unsigned long GetNumberOfNodesInSplayTree(
%        const SplayTreeInfo *splay_tree)
%
%  A description of each parameter follows:
%
%    o splay_tree: the splay tree.
%
*/
MagickExport unsigned long 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                                   %
%                                                                             %
%