|
|
/*
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
% %
|
|
|
% %
|
|
|
% %
|
|
|
% 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 %
|
|
|
% Cristy %
|
|
|
% December 2002 %
|
|
|
% %
|
|
|
% %
|
|
|
% Copyright 1999-2021 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 %
|
|
|
% %
|
|
|
% https://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 "MagickCore/studio.h"
|
|
|
#include "MagickCore/exception.h"
|
|
|
#include "MagickCore/exception-private.h"
|
|
|
#include "MagickCore/locale_.h"
|
|
|
#include "MagickCore/log.h"
|
|
|
#include "MagickCore/memory_.h"
|
|
|
#include "MagickCore/memory-private.h"
|
|
|
#include "MagickCore/splay-tree.h"
|
|
|
#include "MagickCore/semaphore.h"
|
|
|
#include "MagickCore/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;
|
|
|
|
|
|
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 NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const size_t low,
|
|
|
const size_t high)
|
|
|
{
|
|
|
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)
|
|
|
{
|
|
|
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)
|
|
|
{
|
|
|
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 *))
|
|
|
{
|
|
|
NodeInfo
|
|
|
*next,
|
|
|
*node;
|
|
|
|
|
|
SplayTreeInfo
|
|
|
*clone_tree;
|
|
|
|
|
|
assert(splay_tree != (SplayTreeInfo *) NULL);
|
|
|
assert(splay_tree->signature == MagickCoreSignature);
|
|
|
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)
|
|
|
{
|
|
|
NodeInfo
|
|
|
*next,
|
|
|
*node;
|
|
|
|
|
|
assert(splay_tree != (SplayTreeInfo *) NULL);
|
|
|
assert(splay_tree->signature == MagickCoreSignature);
|
|
|
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;
|
|
|
|
|
|
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;
|
|
|
|
|
|
NodeInfo
|
|
|
*left,
|
|
|
*right;
|
|
|
|
|
|
assert(splay_tree != (SplayTreeInfo *) NULL);
|
|
|
assert(splay_tree->signature == MagickCoreSignature);
|
|
|
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;
|
|
|
|
|
|
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=(~MagickCoreSignature);
|
|
|
UnlockSemaphoreInfo(splay_tree->semaphore);
|
|
|
RelinquishSemaphoreInfo(&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)
|
|
|
{
|
|
|
NodeInfo
|
|
|
*node;
|
|
|
|
|
|
void
|
|
|
*key;
|
|
|
|
|
|
assert(splay_tree != (SplayTreeInfo *) NULL);
|
|
|
assert(splay_tree->signature == MagickCoreSignature);
|
|
|
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)
|
|
|
{
|
|
|
NodeInfo
|
|
|
*node;
|
|
|
|
|
|
void
|
|
|
*value;
|
|
|
|
|
|
assert(splay_tree != (SplayTreeInfo *) NULL);
|
|
|
assert(splay_tree->signature == MagickCoreSignature);
|
|
|
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 R o o t V a l u e F r o m S p l a y T r e e %
|
|
|
% %
|
|
|
% %
|
|
|
% %
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
%
|
|
|
% GetRootValueFromSplayTree() gets the root value from the splay-tree.
|
|
|
%
|
|
|
% The format of the GetRootValueFromSplayTree method is:
|
|
|
%
|
|
|
% const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
|
|
|
%
|
|
|
% A description of each parameter follows:
|
|
|
%
|
|
|
% o splay_tree: the splay tree.
|
|
|
%
|
|
|
% o key: the key.
|
|
|
%
|
|
|
*/
|
|
|
MagickExport const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
|
|
|
{
|
|
|
const void
|
|
|
*value;
|
|
|
|
|
|
assert(splay_tree != (SplayTreeInfo *) NULL);
|
|
|
assert(splay_tree->signature == MagickCoreSignature);
|
|
|
if (splay_tree->debug != MagickFalse)
|
|
|
(void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
|
|
|
value=(const void *) NULL;
|
|
|
LockSemaphoreInfo(splay_tree->semaphore);
|
|
|
if (splay_tree->root != (NodeInfo *) NULL)
|
|
|
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 == MagickCoreSignature);
|
|
|
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 == MagickCoreSignature);
|
|
|
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;
|
|
|
|
|
|
ssize_t
|
|
|
i;
|
|
|
|
|
|
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 *) AcquireCriticalMemory(sizeof(*splay_tree));
|
|
|
(void) memset(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=AcquireSemaphoreInfo();
|
|
|
splay_tree->signature=MagickCoreSignature;
|
|
|
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)
|
|
|
{
|
|
|
NodeInfo
|
|
|
*next,
|
|
|
*node;
|
|
|
|
|
|
void
|
|
|
*key;
|
|
|
|
|
|
assert(splay_tree != (SplayTreeInfo *) NULL);
|
|
|
assert(splay_tree->signature == MagickCoreSignature);
|
|
|
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;
|
|
|
|
|
|
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;
|
|
|
|
|
|
NodeInfo
|
|
|
*left,
|
|
|
*right;
|
|
|
|
|
|
void
|
|
|
*value;
|
|
|
|
|
|
assert(splay_tree != (SplayTreeInfo *) NULL);
|
|
|
assert(splay_tree->signature == MagickCoreSignature);
|
|
|
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;
|
|
|
|
|
|
NodeInfo
|
|
|
*active,
|
|
|
*pend;
|
|
|
|
|
|
assert(splay_tree != (SplayTreeInfo *) NULL);
|
|
|
assert(splay_tree->signature == MagickCoreSignature);
|
|
|
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 == MagickCoreSignature);
|
|
|
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 NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth,
|
|
|
const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
|
|
|
{
|
|
|
int
|
|
|
compare;
|
|
|
|
|
|
NodeInfo
|
|
|
**next;
|
|
|
|
|
|
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;
|
|
|
}
|
