This source file includes following definitions.
- AddValueToSplayTree
- LinkSplayTreeNodes
- SplayTreeToNodeArray
- BalanceSplayTree
- GetFirstSplayTreeNode
- CloneSplayTree
- CompareSplayTreeString
- CompareSplayTreeStringInfo
- DeleteNodeByValueFromSplayTree
- DeleteNodeFromSplayTree
- DestroySplayTree
- GetNextKeyInSplayTree
- GetNextValueInSplayTree
- GetValueFromSplayTree
- GetNumberOfNodesInSplayTree
- IterateOverSplayTree
- NewSplayTree
- RemoveNodeByValueFromSplayTree
- RemoveNodeFromSplayTree
- ResetSplayTree
- ResetSplayTreeIterator
- Splay
- SplaySplayTree
#include "magick/studio.h"
#include "magick/exception.h"
#include "magick/exception-private.h"
#include "magick/locale_.h"
#include "magick/log.h"
#include "magick/memory_.h"
#include "magick/splay-tree.h"
#include "magick/semaphore.h"
#include "magick/string_.h"
#define MaxSplayTreeDepth 1024
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;
};
static int
IterateOverSplayTree(SplayTreeInfo *,int (*)(NodeInfo *,const void *),
const void *);
static void
SplaySplayTree(SplayTreeInfo *,const void *);
MagickExport MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
const void *key,const void *value)
{
int
compare;
register NodeInfo
*node;
LockSemaphoreInfo(splay_tree->semaphore);
SplaySplayTree(splay_tree,key);
compare=0;
if (splay_tree->root != (NodeInfo *) NULL)
{
if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
compare=splay_tree->compare(splay_tree->root->key,key);
else
compare=(splay_tree->root->key > key) ? 1 :
((splay_tree->root->key < key) ? -1 : 0);
if (compare == 0)
{
if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
(splay_tree->root->value != (void *) NULL))
splay_tree->root->value=splay_tree->relinquish_value(
splay_tree->root->value);
if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
(splay_tree->root->key != (void *) NULL))
splay_tree->root->key=splay_tree->relinquish_key(
splay_tree->root->key);
splay_tree->root->key=(void *) key;
splay_tree->root->value=(void *) value;
UnlockSemaphoreInfo(splay_tree->semaphore);
return(MagickTrue);
}
}
node=(NodeInfo *) AcquireMagickMemory(sizeof(*node));
if (node == (NodeInfo *) NULL)
{
UnlockSemaphoreInfo(splay_tree->semaphore);
return(MagickFalse);
}
node->key=(void *) key;
node->value=(void *) value;
if (splay_tree->root == (NodeInfo *) NULL)
{
node->left=(NodeInfo *) NULL;
node->right=(NodeInfo *) NULL;
}
else
if (compare < 0)
{
node->left=splay_tree->root;
node->right=node->left->right;
node->left->right=(NodeInfo *) NULL;
}
else
{
node->right=splay_tree->root;
node->left=node->right->left;
node->right->left=(NodeInfo *) NULL;
}
splay_tree->root=node;
splay_tree->key=(void *) NULL;
splay_tree->nodes++;
UnlockSemaphoreInfo(splay_tree->semaphore);
return(MagickTrue);
}
static NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const size_t low,
const size_t high)
{
register NodeInfo
*node;
size_t
bisect;
bisect=low+(high-low)/2;
node=nodes[bisect];
if ((low+1) > bisect)
node->left=(NodeInfo *) NULL;
else
node->left=LinkSplayTreeNodes(nodes,low,bisect-1);
if ((bisect+1) > high)
node->right=(NodeInfo *) NULL;
else
node->right=LinkSplayTreeNodes(nodes,bisect+1,high);
return(node);
}
static inline int SplayTreeToNodeArray(NodeInfo *node,const void *nodes)
{
register const NodeInfo
***p;
p=(const NodeInfo ***) nodes;
*(*p)=node;
(*p)++;
return(0);
}
static void BalanceSplayTree(SplayTreeInfo *splay_tree)
{
NodeInfo
**node,
**nodes;
if (splay_tree->nodes <= 2)
{
splay_tree->balance=MagickFalse;
return;
}
nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
sizeof(*nodes));
if (nodes == (NodeInfo **) NULL)
ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
node=nodes;
(void) IterateOverSplayTree(splay_tree,SplayTreeToNodeArray,(const void *)
&node);
splay_tree->root=LinkSplayTreeNodes(nodes,0,splay_tree->nodes-1);
splay_tree->balance=MagickFalse;
nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
}
static inline void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree)
{
register NodeInfo
*node;
node=splay_tree->root;
if (splay_tree->root == (NodeInfo *) NULL)
return((NodeInfo *) NULL);
while (node->left != (NodeInfo *) NULL)
node=node->left;
return(node->key);
}
MagickExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
void *(*clone_key)(void *),void *(*clone_value)(void *))
{
register NodeInfo
*next,
*node;
SplayTreeInfo
*clone_tree;
assert(splay_tree != (SplayTreeInfo *) NULL);
assert(splay_tree->signature == MagickSignature);
if (splay_tree->debug != MagickFalse)
(void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
clone_tree=NewSplayTree(splay_tree->compare,splay_tree->relinquish_key,
splay_tree->relinquish_value);
LockSemaphoreInfo(splay_tree->semaphore);
if (splay_tree->root == (NodeInfo *) NULL)
{
UnlockSemaphoreInfo(splay_tree->semaphore);
return(clone_tree);
}
next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
while (next != (NodeInfo *) NULL)
{
SplaySplayTree(splay_tree,next);
(void) AddValueToSplayTree(clone_tree,clone_key(splay_tree->root->key),
clone_value(splay_tree->root->value));
next=(NodeInfo *) NULL;
node=splay_tree->root->right;
if (node != (NodeInfo *) NULL)
{
while (node->left != (NodeInfo *) NULL)
node=node->left;
next=(NodeInfo *) node->key;
}
}
UnlockSemaphoreInfo(splay_tree->semaphore);
return(clone_tree);
}
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));
}
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));
}
MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree(
SplayTreeInfo *splay_tree,const void *value)
{
register NodeInfo
*next,
*node;
assert(splay_tree != (SplayTreeInfo *) NULL);
assert(splay_tree->signature == MagickSignature);
if (splay_tree->debug != MagickFalse)
(void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
LockSemaphoreInfo(splay_tree->semaphore);
if (splay_tree->root == (NodeInfo *) NULL)
{
UnlockSemaphoreInfo(splay_tree->semaphore);
return(MagickFalse);
}
next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
while (next != (NodeInfo *) NULL)
{
SplaySplayTree(splay_tree,next);
next=(NodeInfo *) NULL;
node=splay_tree->root->right;
if (node != (NodeInfo *) NULL)
{
while (node->left != (NodeInfo *) NULL)
node=node->left;
next=(NodeInfo *) node->key;
}
if (splay_tree->root->value == value)
{
int
compare;
register NodeInfo
*left,
*right;
void
*key;
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);
}
MagickExport MagickBooleanType DeleteNodeFromSplayTree(
SplayTreeInfo *splay_tree,const void *key)
{
int
compare;
register NodeInfo
*left,
*right;
assert(splay_tree != (SplayTreeInfo *) NULL);
assert(splay_tree->signature == MagickSignature);
if (splay_tree->debug != MagickFalse)
(void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
if (splay_tree->root == (NodeInfo *) NULL)
return(MagickFalse);
LockSemaphoreInfo(splay_tree->semaphore);
SplaySplayTree(splay_tree,key);
splay_tree->key=(void *) NULL;
if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
compare=splay_tree->compare(splay_tree->root->key,key);
else
compare=(splay_tree->root->key > key) ? 1 :
((splay_tree->root->key < key) ? -1 : 0);
if (compare != 0)
{
UnlockSemaphoreInfo(splay_tree->semaphore);
return(MagickFalse);
}
left=splay_tree->root->left;
right=splay_tree->root->right;
if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
(splay_tree->root->value != (void *) NULL))
splay_tree->root->value=splay_tree->relinquish_value(
splay_tree->root->value);
if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
(splay_tree->root->key != (void *) NULL))
splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
splay_tree->nodes--;
if (left == (NodeInfo *) NULL)
{
splay_tree->root=right;
UnlockSemaphoreInfo(splay_tree->semaphore);
return(MagickTrue);
}
splay_tree->root=left;
if (right != (NodeInfo *) NULL)
{
while (left->right != (NodeInfo *) NULL)
left=left->right;
left->right=right;
}
UnlockSemaphoreInfo(splay_tree->semaphore);
return(MagickTrue);
}
MagickExport SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
{
NodeInfo
*node;
register NodeInfo
*active,
*pend;
LockSemaphoreInfo(splay_tree->semaphore);
if (splay_tree->root != (NodeInfo *) NULL)
{
if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
(splay_tree->root->value != (void *) NULL))
splay_tree->root->value=splay_tree->relinquish_value(
splay_tree->root->value);
if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
(splay_tree->root->key != (void *) NULL))
splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
splay_tree->root->key=(void *) NULL;
for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
{
active=pend;
for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
{
if (active->left != (NodeInfo *) NULL)
{
if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
(active->left->value != (void *) NULL))
active->left->value=splay_tree->relinquish_value(
active->left->value);
if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
(active->left->key != (void *) NULL))
active->left->key=splay_tree->relinquish_key(active->left->key);
active->left->key=(void *) pend;
pend=active->left;
}
if (active->right != (NodeInfo *) NULL)
{
if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
(active->right->value != (void *) NULL))
active->right->value=splay_tree->relinquish_value(
active->right->value);
if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
(active->right->key != (void *) NULL))
active->right->key=splay_tree->relinquish_key(
active->right->key);
active->right->key=(void *) pend;
pend=active->right;
}
node=active;
active=(NodeInfo *) node->key;
node=(NodeInfo *) RelinquishMagickMemory(node);
}
}
}
splay_tree->signature=(~MagickSignature);
UnlockSemaphoreInfo(splay_tree->semaphore);
DestroySemaphoreInfo(&splay_tree->semaphore);
splay_tree=(SplayTreeInfo *) RelinquishMagickMemory(splay_tree);
return(splay_tree);
}
MagickExport const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
{
register NodeInfo
*node;
void
*key;
assert(splay_tree != (SplayTreeInfo *) NULL);
assert(splay_tree->signature == MagickSignature);
if (splay_tree->debug != MagickFalse)
(void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
if ((splay_tree->root == (NodeInfo *) NULL) ||
(splay_tree->next == (void *) NULL))
return((void *) NULL);
LockSemaphoreInfo(splay_tree->semaphore);
SplaySplayTree(splay_tree,splay_tree->next);
splay_tree->next=(void *) NULL;
node=splay_tree->root->right;
if (node != (NodeInfo *) NULL)
{
while (node->left != (NodeInfo *) NULL)
node=node->left;
splay_tree->next=node->key;
}
key=splay_tree->root->key;
UnlockSemaphoreInfo(splay_tree->semaphore);
return(key);
}
MagickExport const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
{
register NodeInfo
*node;
void
*value;
assert(splay_tree != (SplayTreeInfo *) NULL);
assert(splay_tree->signature == MagickSignature);
if (splay_tree->debug != MagickFalse)
(void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
if ((splay_tree->root == (NodeInfo *) NULL) ||
(splay_tree->next == (void *) NULL))
return((void *) NULL);
LockSemaphoreInfo(splay_tree->semaphore);
SplaySplayTree(splay_tree,splay_tree->next);
splay_tree->next=(void *) NULL;
node=splay_tree->root->right;
if (node != (NodeInfo *) NULL)
{
while (node->left != (NodeInfo *) NULL)
node=node->left;
splay_tree->next=node->key;
}
value=splay_tree->root->value;
UnlockSemaphoreInfo(splay_tree->semaphore);
return(value);
}
MagickExport const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
const void *key)
{
int
compare;
void
*value;
assert(splay_tree != (SplayTreeInfo *) NULL);
assert(splay_tree->signature == MagickSignature);
if (splay_tree->debug != MagickFalse)
(void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
if (splay_tree->root == (NodeInfo *) NULL)
return((void *) NULL);
LockSemaphoreInfo(splay_tree->semaphore);
SplaySplayTree(splay_tree,key);
if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
compare=splay_tree->compare(splay_tree->root->key,key);
else
compare=(splay_tree->root->key > key) ? 1 :
((splay_tree->root->key < key) ? -1 : 0);
if (compare != 0)
{
UnlockSemaphoreInfo(splay_tree->semaphore);
return((void *) NULL);
}
value=splay_tree->root->value;
UnlockSemaphoreInfo(splay_tree->semaphore);
return(value);
}
MagickExport size_t GetNumberOfNodesInSplayTree(
const SplayTreeInfo *splay_tree)
{
assert(splay_tree != (SplayTreeInfo *) NULL);
assert(splay_tree->signature == MagickSignature);
if (splay_tree->debug != MagickFalse)
(void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
return(splay_tree->nodes);
}
static int IterateOverSplayTree(SplayTreeInfo *splay_tree,
int (*method)(NodeInfo *,const void *),const void *value)
{
typedef enum
{
LeftTransition,
RightTransition,
DownTransition,
UpTransition
} TransitionType;
int
status;
MagickBooleanType
final_transition;
NodeInfo
**nodes;
register ssize_t
i;
register NodeInfo
*node;
TransitionType
transition;
unsigned char
*transitions;
if (splay_tree->root == (NodeInfo *) NULL)
return(0);
nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
sizeof(*nodes));
transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes,
sizeof(*transitions));
if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL))
ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
status=0;
final_transition=MagickFalse;
nodes[0]=splay_tree->root;
transitions[0]=(unsigned char) LeftTransition;
for (i=0; final_transition == MagickFalse; )
{
node=nodes[i];
transition=(TransitionType) transitions[i];
switch (transition)
{
case LeftTransition:
{
transitions[i]=(unsigned char) DownTransition;
if (node->left == (NodeInfo *) NULL)
break;
i++;
nodes[i]=node->left;
transitions[i]=(unsigned char) LeftTransition;
break;
}
case RightTransition:
{
transitions[i]=(unsigned char) UpTransition;
if (node->right == (NodeInfo *) NULL)
break;
i++;
nodes[i]=node->right;
transitions[i]=(unsigned char) LeftTransition;
break;
}
case DownTransition:
default:
{
transitions[i]=(unsigned char) RightTransition;
status=(*method)(node,value);
if (status != 0)
final_transition=MagickTrue;
break;
}
case UpTransition:
{
if (i == 0)
{
final_transition=MagickTrue;
break;
}
i--;
break;
}
}
}
nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
transitions=(unsigned char *) RelinquishMagickMemory(transitions);
return(status);
}
MagickExport SplayTreeInfo *NewSplayTree(
int (*compare)(const void *,const void *),void *(*relinquish_key)(void *),
void *(*relinquish_value)(void *))
{
SplayTreeInfo
*splay_tree;
splay_tree=(SplayTreeInfo *) AcquireMagickMemory(sizeof(*splay_tree));
if (splay_tree == (SplayTreeInfo *) NULL)
ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
(void) ResetMagickMemory(splay_tree,0,sizeof(*splay_tree));
splay_tree->root=(NodeInfo *) NULL;
splay_tree->compare=compare;
splay_tree->relinquish_key=relinquish_key;
splay_tree->relinquish_value=relinquish_value;
splay_tree->balance=MagickFalse;
splay_tree->key=(void *) NULL;
splay_tree->next=(void *) NULL;
splay_tree->nodes=0;
splay_tree->debug=IsEventLogging();
splay_tree->semaphore=AllocateSemaphoreInfo();
splay_tree->signature=MagickSignature;
return(splay_tree);
}
MagickExport void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
const void *value)
{
register NodeInfo
*next,
*node;
void
*key;
assert(splay_tree != (SplayTreeInfo *) NULL);
assert(splay_tree->signature == MagickSignature);
if (splay_tree->debug != MagickFalse)
(void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
key=(void *) NULL;
if (splay_tree->root == (NodeInfo *) NULL)
return(key);
LockSemaphoreInfo(splay_tree->semaphore);
next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
while (next != (NodeInfo *) NULL)
{
SplaySplayTree(splay_tree,next);
next=(NodeInfo *) NULL;
node=splay_tree->root->right;
if (node != (NodeInfo *) NULL)
{
while (node->left != (NodeInfo *) NULL)
node=node->left;
next=(NodeInfo *) node->key;
}
if (splay_tree->root->value == value)
{
int
compare;
register NodeInfo
*left,
*right;
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);
}
MagickExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,
const void *key)
{
int
compare;
register NodeInfo
*left,
*right;
void
*value;
assert(splay_tree != (SplayTreeInfo *) NULL);
assert(splay_tree->signature == MagickSignature);
if (splay_tree->debug != MagickFalse)
(void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
value=(void *) NULL;
if (splay_tree->root == (NodeInfo *) NULL)
return(value);
LockSemaphoreInfo(splay_tree->semaphore);
SplaySplayTree(splay_tree,key);
splay_tree->key=(void *) NULL;
if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
compare=splay_tree->compare(splay_tree->root->key,key);
else
compare=(splay_tree->root->key > key) ? 1 :
((splay_tree->root->key < key) ? -1 : 0);
if (compare != 0)
{
UnlockSemaphoreInfo(splay_tree->semaphore);
return(value);
}
left=splay_tree->root->left;
right=splay_tree->root->right;
value=splay_tree->root->value;
if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
(splay_tree->root->key != (void *) NULL))
splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
splay_tree->nodes--;
if (left == (NodeInfo *) NULL)
{
splay_tree->root=right;
UnlockSemaphoreInfo(splay_tree->semaphore);
return(value);
}
splay_tree->root=left;
if (right != (NodeInfo *) NULL)
{
while (left->right != (NodeInfo *) NULL)
left=left->right;
left->right=right;
}
UnlockSemaphoreInfo(splay_tree->semaphore);
return(value);
}
MagickExport void ResetSplayTree(SplayTreeInfo *splay_tree)
{
NodeInfo
*node;
register NodeInfo
*active,
*pend;
assert(splay_tree != (SplayTreeInfo *) NULL);
assert(splay_tree->signature == MagickSignature);
if (splay_tree->debug != MagickFalse)
(void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
LockSemaphoreInfo(splay_tree->semaphore);
if (splay_tree->root != (NodeInfo *) NULL)
{
if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
(splay_tree->root->value != (void *) NULL))
splay_tree->root->value=splay_tree->relinquish_value(
splay_tree->root->value);
if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
(splay_tree->root->key != (void *) NULL))
splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
splay_tree->root->key=(void *) NULL;
for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
{
active=pend;
for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
{
if (active->left != (NodeInfo *) NULL)
{
if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
(active->left->value != (void *) NULL))
active->left->value=splay_tree->relinquish_value(
active->left->value);
if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
(active->left->key != (void *) NULL))
active->left->key=splay_tree->relinquish_key(active->left->key);
active->left->key=(void *) pend;
pend=active->left;
}
if (active->right != (NodeInfo *) NULL)
{
if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
(active->right->value != (void *) NULL))
active->right->value=splay_tree->relinquish_value(
active->right->value);
if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
(active->right->key != (void *) NULL))
active->right->key=splay_tree->relinquish_key(
active->right->key);
active->right->key=(void *) pend;
pend=active->right;
}
node=active;
active=(NodeInfo *) node->key;
node=(NodeInfo *) RelinquishMagickMemory(node);
}
}
}
splay_tree->root=(NodeInfo *) NULL;
splay_tree->key=(void *) NULL;
splay_tree->next=(void *) NULL;
splay_tree->nodes=0;
splay_tree->balance=MagickFalse;
UnlockSemaphoreInfo(splay_tree->semaphore);
}
MagickExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
{
assert(splay_tree != (SplayTreeInfo *) NULL);
assert(splay_tree->signature == MagickSignature);
if (splay_tree->debug != MagickFalse)
(void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
LockSemaphoreInfo(splay_tree->semaphore);
splay_tree->next=GetFirstSplayTreeNode(splay_tree);
UnlockSemaphoreInfo(splay_tree->semaphore);
}
static NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth,
const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
{
int
compare;
NodeInfo
**next;
register NodeInfo
*n,
*p;
n=(*node);
if (n == (NodeInfo *) NULL)
return(*parent);
if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
compare=splay_tree->compare(n->key,key);
else
compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
next=(NodeInfo **) NULL;
if (compare > 0)
next=(&n->left);
else
if (compare < 0)
next=(&n->right);
if (next != (NodeInfo **) NULL)
{
if (depth >= MaxSplayTreeDepth)
{
splay_tree->balance=MagickTrue;
return(n);
}
n=Splay(splay_tree,depth+1,key,next,node,parent);
if ((n != *node) || (splay_tree->balance != MagickFalse))
return(n);
}
if (parent == (NodeInfo **) NULL)
return(n);
if (grandparent == (NodeInfo **) NULL)
{
if (n == (*parent)->left)
{
*node=n->right;
n->right=(*parent);
}
else
{
*node=n->left;
n->left=(*parent);
}
*parent=n;
return(n);
}
if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
{
p=(*parent);
(*grandparent)->left=p->right;
p->right=(*grandparent);
p->left=n->right;
n->right=p;
*grandparent=n;
return(n);
}
if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
{
p=(*parent);
(*grandparent)->right=p->left;
p->left=(*grandparent);
p->right=n->left;
n->left=p;
*grandparent=n;
return(n);
}
if (n == (*parent)->left)
{
(*parent)->left=n->right;
n->right=(*parent);
(*grandparent)->right=n->left;
n->left=(*grandparent);
*grandparent=n;
return(n);
}
(*parent)->right=n->left;
n->left=(*parent);
(*grandparent)->left=n->right;
n->right=(*grandparent);
*grandparent=n;
return(n);
}
static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key)
{
if (splay_tree->root == (NodeInfo *) NULL)
return;
if (splay_tree->key != (void *) NULL)
{
int
compare;
if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
compare=splay_tree->compare(splay_tree->root->key,key);
else
compare=(splay_tree->key > key) ? 1 :
((splay_tree->key < key) ? -1 : 0);
if (compare == 0)
return;
}
(void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
(NodeInfo **) NULL);
if (splay_tree->balance != MagickFalse)
{
BalanceSplayTree(splay_tree);
(void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
(NodeInfo **) NULL);
if (splay_tree->balance != MagickFalse)
ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
}
splay_tree->key=(void *) key;
}