p71924506
/
aosp12
1
0
Fork 0
Code Issues Pull Requests Projects Releases Wiki Activity
aosp12/external/ImageMagick/MagickCore/splay-tree.c

1635 lines
55 KiB
C
Raw Permalink Normal View History

init from android-12.1.0_r8
2023-01-09 17:11:35 +08:00
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% 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;
}