|
|
/* |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
|
% % |
|
|
% % |
|
|
% % |
|
|
% 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-2016 ImageMagick Studio LLC, a non-profit organization % |
|
|
% dedicated to making software imaging solutions freely available. % |
|
|
% % |
|
|
% You may not use this file except in compliance with the License. You may % |
|
|
% obtain a copy of the License at % |
|
|
% % |
|
|
% http://www.imagemagick.org/script/license.php % |
|
|
% % |
|
|
% Unless required by applicable law or agreed to in writing, software % |
|
|
% distributed under the License is distributed on an "AS IS" BASIS, % |
|
|
% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. % |
|
|
% See the License for the specific language governing permissions and % |
|
|
% limitations under the License. % |
|
|
% % |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
|
% |
|
|
% This module implements the standard handy splay-tree methods for storing and |
|
|
% retrieving large numbers of data elements. It is loosely based on the Java |
|
|
% implementation of these algorithms. |
|
|
% |
|
|
*/ |
|
|
|
|
|
/* |
|
|
Include declarations. |
|
|
*/ |
|
|
#include "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/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; |
|
|
|
|
|
register NodeInfo |
|
|
*node; |
|
|
|
|
|
LockSemaphoreInfo(splay_tree->semaphore); |
|
|
SplaySplayTree(splay_tree,key); |
|
|
compare=0; |
|
|
if (splay_tree->root != (NodeInfo *) NULL) |
|
|
{ |
|
|
if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) |
|
|
compare=splay_tree->compare(splay_tree->root->key,key); |
|
|
else |
|
|
compare=(splay_tree->root->key > key) ? 1 : |
|
|
((splay_tree->root->key < key) ? -1 : 0); |
|
|
if (compare == 0) |
|
|
{ |
|
|
if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && |
|
|
(splay_tree->root->value != (void *) NULL)) |
|
|
splay_tree->root->value=splay_tree->relinquish_value( |
|
|
splay_tree->root->value); |
|
|
if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && |
|
|
(splay_tree->root->key != (void *) NULL)) |
|
|
splay_tree->root->key=splay_tree->relinquish_key( |
|
|
splay_tree->root->key); |
|
|
splay_tree->root->key=(void *) key; |
|
|
splay_tree->root->value=(void *) value; |
|
|
UnlockSemaphoreInfo(splay_tree->semaphore); |
|
|
return(MagickTrue); |
|
|
} |
|
|
} |
|
|
node=(NodeInfo *) AcquireMagickMemory(sizeof(*node)); |
|
|
if (node == (NodeInfo *) NULL) |
|
|
{ |
|
|
UnlockSemaphoreInfo(splay_tree->semaphore); |
|
|
return(MagickFalse); |
|
|
} |
|
|
node->key=(void *) key; |
|
|
node->value=(void *) value; |
|
|
if (splay_tree->root == (NodeInfo *) NULL) |
|
|
{ |
|
|
node->left=(NodeInfo *) NULL; |
|
|
node->right=(NodeInfo *) NULL; |
|
|
} |
|
|
else |
|
|
if (compare < 0) |
|
|
{ |
|
|
node->left=splay_tree->root; |
|
|
node->right=node->left->right; |
|
|
node->left->right=(NodeInfo *) NULL; |
|
|
} |
|
|
else |
|
|
{ |
|
|
node->right=splay_tree->root; |
|
|
node->left=node->right->left; |
|
|
node->right->left=(NodeInfo *) NULL; |
|
|
} |
|
|
splay_tree->root=node; |
|
|
splay_tree->key=(void *) NULL; |
|
|
splay_tree->nodes++; |
|
|
UnlockSemaphoreInfo(splay_tree->semaphore); |
|
|
return(MagickTrue); |
|
|
} |
|
|
|
|
|
/* |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
|
% % |
|
|
% % |
|
|
% % |
|
|
% B a l a n c e S p l a y T r e e % |
|
|
% % |
|
|
% % |
|
|
% % |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
|
% |
|
|
% BalanceSplayTree() balances the splay-tree. |
|
|
% |
|
|
% The format of the BalanceSplayTree method is: |
|
|
% |
|
|
% void *BalanceSplayTree(SplayTreeInfo *splay_tree,const void *key) |
|
|
% |
|
|
% A description of each parameter follows: |
|
|
% |
|
|
% o splay_tree: the splay-tree info. |
|
|
% |
|
|
% o key: the key. |
|
|
% |
|
|
*/ |
|
|
|
|
|
static NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const size_t low, |
|
|
const size_t high) |
|
|
{ |
|
|
register NodeInfo |
|
|
*node; |
|
|
|
|
|
size_t |
|
|
bisect; |
|
|
|
|
|
bisect=low+(high-low)/2; |
|
|
node=nodes[bisect]; |
|
|
if ((low+1) > bisect) |
|
|
node->left=(NodeInfo *) NULL; |
|
|
else |
|
|
node->left=LinkSplayTreeNodes(nodes,low,bisect-1); |
|
|
if ((bisect+1) > high) |
|
|
node->right=(NodeInfo *) NULL; |
|
|
else |
|
|
node->right=LinkSplayTreeNodes(nodes,bisect+1,high); |
|
|
return(node); |
|
|
} |
|
|
|
|
|
static inline int SplayTreeToNodeArray(NodeInfo *node,const void *nodes) |
|
|
{ |
|
|
register const NodeInfo |
|
|
***p; |
|
|
|
|
|
p=(const NodeInfo ***) nodes; |
|
|
*(*p)=node; |
|
|
(*p)++; |
|
|
return(0); |
|
|
} |
|
|
|
|
|
static void BalanceSplayTree(SplayTreeInfo *splay_tree) |
|
|
{ |
|
|
NodeInfo |
|
|
**node, |
|
|
**nodes; |
|
|
|
|
|
if (splay_tree->nodes <= 2) |
|
|
{ |
|
|
splay_tree->balance=MagickFalse; |
|
|
return; |
|
|
} |
|
|
nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes, |
|
|
sizeof(*nodes)); |
|
|
if (nodes == (NodeInfo **) NULL) |
|
|
ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); |
|
|
node=nodes; |
|
|
(void) IterateOverSplayTree(splay_tree,SplayTreeToNodeArray,(const void *) |
|
|
&node); |
|
|
splay_tree->root=LinkSplayTreeNodes(nodes,0,splay_tree->nodes-1); |
|
|
splay_tree->balance=MagickFalse; |
|
|
nodes=(NodeInfo **) RelinquishMagickMemory(nodes); |
|
|
} |
|
|
|
|
|
/* |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
|
% % |
|
|
% % |
|
|
% % |
|
|
% C l o n e S p l a y T r e e % |
|
|
% % |
|
|
% % |
|
|
% % |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
|
% |
|
|
% CloneSplayTree() clones the splay tree. |
|
|
% |
|
|
% The format of the CloneSplayTree method is: |
|
|
% |
|
|
% SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree, |
|
|
% void *(*clone_key)(void *),void *(*cline_value)(void *)) |
|
|
% |
|
|
% A description of each parameter follows: |
|
|
% |
|
|
% o splay_tree: the splay tree. |
|
|
% |
|
|
% o clone_key: the key clone method, typically ConstantString(), called |
|
|
% whenever a key is added to the splay-tree. |
|
|
% |
|
|
% o clone_value: the value clone method; typically ConstantString(), called |
|
|
% whenever a value object is added to the splay-tree. |
|
|
% |
|
|
*/ |
|
|
|
|
|
static inline void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree) |
|
|
{ |
|
|
register NodeInfo |
|
|
*node; |
|
|
|
|
|
node=splay_tree->root; |
|
|
if (splay_tree->root == (NodeInfo *) NULL) |
|
|
return((NodeInfo *) NULL); |
|
|
while (node->left != (NodeInfo *) NULL) |
|
|
node=node->left; |
|
|
return(node->key); |
|
|
} |
|
|
|
|
|
MagickExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree, |
|
|
void *(*clone_key)(void *),void *(*clone_value)(void *)) |
|
|
{ |
|
|
register NodeInfo |
|
|
*next, |
|
|
*node; |
|
|
|
|
|
SplayTreeInfo |
|
|
*clone_tree; |
|
|
|
|
|
assert(splay_tree != (SplayTreeInfo *) NULL); |
|
|
assert(splay_tree->signature == 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) |
|
|
{ |
|
|
register 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; |
|
|
|
|
|
register NodeInfo |
|
|
*left, |
|
|
*right; |
|
|
|
|
|
void |
|
|
*key; |
|
|
|
|
|
/* |
|
|
We found the node that matches the value; now delete it. |
|
|
*/ |
|
|
key=splay_tree->root->key; |
|
|
SplaySplayTree(splay_tree,key); |
|
|
splay_tree->key=(void *) NULL; |
|
|
if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) |
|
|
compare=splay_tree->compare(splay_tree->root->key,key); |
|
|
else |
|
|
compare=(splay_tree->root->key > key) ? 1 : |
|
|
((splay_tree->root->key < key) ? -1 : 0); |
|
|
if (compare != 0) |
|
|
{ |
|
|
UnlockSemaphoreInfo(splay_tree->semaphore); |
|
|
return(MagickFalse); |
|
|
} |
|
|
left=splay_tree->root->left; |
|
|
right=splay_tree->root->right; |
|
|
if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && |
|
|
(splay_tree->root->value != (void *) NULL)) |
|
|
splay_tree->root->value=splay_tree->relinquish_value( |
|
|
splay_tree->root->value); |
|
|
if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && |
|
|
(splay_tree->root->key != (void *) NULL)) |
|
|
splay_tree->root->key=splay_tree->relinquish_key( |
|
|
splay_tree->root->key); |
|
|
splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root); |
|
|
splay_tree->nodes--; |
|
|
if (left == (NodeInfo *) NULL) |
|
|
{ |
|
|
splay_tree->root=right; |
|
|
UnlockSemaphoreInfo(splay_tree->semaphore); |
|
|
return(MagickTrue); |
|
|
} |
|
|
splay_tree->root=left; |
|
|
if (right != (NodeInfo *) NULL) |
|
|
{ |
|
|
while (left->right != (NodeInfo *) NULL) |
|
|
left=left->right; |
|
|
left->right=right; |
|
|
} |
|
|
UnlockSemaphoreInfo(splay_tree->semaphore); |
|
|
return(MagickTrue); |
|
|
} |
|
|
} |
|
|
UnlockSemaphoreInfo(splay_tree->semaphore); |
|
|
return(MagickFalse); |
|
|
} |
|
|
|
|
|
/* |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
|
% % |
|
|
% % |
|
|
% % |
|
|
% D e l e t e N o d e F r o m S p l a y T r e e % |
|
|
% % |
|
|
% % |
|
|
% % |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
|
% |
|
|
% DeleteNodeFromSplayTree() deletes a node from the splay-tree. It returns |
|
|
% MagickTrue if the option is found and successfully deleted from the |
|
|
% splay-tree. |
|
|
% |
|
|
% The format of the DeleteNodeFromSplayTree method is: |
|
|
% |
|
|
% MagickBooleanType DeleteNodeFromSplayTree(SplayTreeInfo *splay_tree, |
|
|
% const void *key) |
|
|
% |
|
|
% A description of each parameter follows: |
|
|
% |
|
|
% o splay_tree: the splay-tree info. |
|
|
% |
|
|
% o key: the key. |
|
|
% |
|
|
*/ |
|
|
MagickExport MagickBooleanType DeleteNodeFromSplayTree( |
|
|
SplayTreeInfo *splay_tree,const void *key) |
|
|
{ |
|
|
int |
|
|
compare; |
|
|
|
|
|
register NodeInfo |
|
|
*left, |
|
|
*right; |
|
|
|
|
|
assert(splay_tree != (SplayTreeInfo *) NULL); |
|
|
assert(splay_tree->signature == 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; |
|
|
|
|
|
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=(~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) |
|
|
{ |
|
|
register 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) |
|
|
{ |
|
|
register 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 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; |
|
|
|
|
|
register ssize_t |
|
|
i; |
|
|
|
|
|
register NodeInfo |
|
|
*node; |
|
|
|
|
|
TransitionType |
|
|
transition; |
|
|
|
|
|
unsigned char |
|
|
*transitions; |
|
|
|
|
|
if (splay_tree->root == (NodeInfo *) NULL) |
|
|
return(0); |
|
|
nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes, |
|
|
sizeof(*nodes)); |
|
|
transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes, |
|
|
sizeof(*transitions)); |
|
|
if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL)) |
|
|
ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); |
|
|
status=0; |
|
|
final_transition=MagickFalse; |
|
|
nodes[0]=splay_tree->root; |
|
|
transitions[0]=(unsigned char) LeftTransition; |
|
|
for (i=0; final_transition == MagickFalse; ) |
|
|
{ |
|
|
node=nodes[i]; |
|
|
transition=(TransitionType) transitions[i]; |
|
|
switch (transition) |
|
|
{ |
|
|
case LeftTransition: |
|
|
{ |
|
|
transitions[i]=(unsigned char) DownTransition; |
|
|
if (node->left == (NodeInfo *) NULL) |
|
|
break; |
|
|
i++; |
|
|
nodes[i]=node->left; |
|
|
transitions[i]=(unsigned char) LeftTransition; |
|
|
break; |
|
|
} |
|
|
case RightTransition: |
|
|
{ |
|
|
transitions[i]=(unsigned char) UpTransition; |
|
|
if (node->right == (NodeInfo *) NULL) |
|
|
break; |
|
|
i++; |
|
|
nodes[i]=node->right; |
|
|
transitions[i]=(unsigned char) LeftTransition; |
|
|
break; |
|
|
} |
|
|
case DownTransition: |
|
|
default: |
|
|
{ |
|
|
transitions[i]=(unsigned char) RightTransition; |
|
|
status=(*method)(node,value); |
|
|
if (status != 0) |
|
|
final_transition=MagickTrue; |
|
|
break; |
|
|
} |
|
|
case UpTransition: |
|
|
{ |
|
|
if (i == 0) |
|
|
{ |
|
|
final_transition=MagickTrue; |
|
|
break; |
|
|
} |
|
|
i--; |
|
|
break; |
|
|
} |
|
|
} |
|
|
} |
|
|
nodes=(NodeInfo **) RelinquishMagickMemory(nodes); |
|
|
transitions=(unsigned char *) RelinquishMagickMemory(transitions); |
|
|
return(status); |
|
|
} |
|
|
|
|
|
/* |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
|
% % |
|
|
% % |
|
|
% % |
|
|
% N e w S p l a y T r e e % |
|
|
% % |
|
|
% % |
|
|
% % |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
|
% |
|
|
% NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized |
|
|
% to default values. |
|
|
% |
|
|
% The format of the NewSplayTree method is: |
|
|
% |
|
|
% SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *), |
|
|
% void *(*relinquish_key)(void *),void *(*relinquish_value)(void *)) |
|
|
% |
|
|
% A description of each parameter follows: |
|
|
% |
|
|
% o compare: the compare method. |
|
|
% |
|
|
% o relinquish_key: the key deallocation method, typically |
|
|
% RelinquishMagickMemory(), called whenever a key is removed from the |
|
|
% splay-tree. |
|
|
% |
|
|
% o relinquish_value: the value deallocation method; typically |
|
|
% RelinquishMagickMemory(), called whenever a value object is removed from |
|
|
% the splay-tree. |
|
|
% |
|
|
*/ |
|
|
MagickExport SplayTreeInfo *NewSplayTree( |
|
|
int (*compare)(const void *,const void *),void *(*relinquish_key)(void *), |
|
|
void *(*relinquish_value)(void *)) |
|
|
{ |
|
|
SplayTreeInfo |
|
|
*splay_tree; |
|
|
|
|
|
splay_tree=(SplayTreeInfo *) AcquireMagickMemory(sizeof(*splay_tree)); |
|
|
if (splay_tree == (SplayTreeInfo *) NULL) |
|
|
ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); |
|
|
(void) ResetMagickMemory(splay_tree,0,sizeof(*splay_tree)); |
|
|
splay_tree->root=(NodeInfo *) NULL; |
|
|
splay_tree->compare=compare; |
|
|
splay_tree->relinquish_key=relinquish_key; |
|
|
splay_tree->relinquish_value=relinquish_value; |
|
|
splay_tree->balance=MagickFalse; |
|
|
splay_tree->key=(void *) NULL; |
|
|
splay_tree->next=(void *) NULL; |
|
|
splay_tree->nodes=0; |
|
|
splay_tree->debug=IsEventLogging(); |
|
|
splay_tree->semaphore=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) |
|
|
{ |
|
|
register 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; |
|
|
|
|
|
register NodeInfo |
|
|
*left, |
|
|
*right; |
|
|
|
|
|
/* |
|
|
We found the node that matches the value; now remove it. |
|
|
*/ |
|
|
key=splay_tree->root->key; |
|
|
SplaySplayTree(splay_tree,key); |
|
|
splay_tree->key=(void *) NULL; |
|
|
if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) |
|
|
compare=splay_tree->compare(splay_tree->root->key,key); |
|
|
else |
|
|
compare=(splay_tree->root->key > key) ? 1 : |
|
|
((splay_tree->root->key < key) ? -1 : 0); |
|
|
if (compare != 0) |
|
|
{ |
|
|
UnlockSemaphoreInfo(splay_tree->semaphore); |
|
|
return(key); |
|
|
} |
|
|
left=splay_tree->root->left; |
|
|
right=splay_tree->root->right; |
|
|
if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && |
|
|
(splay_tree->root->value != (void *) NULL)) |
|
|
splay_tree->root->value=splay_tree->relinquish_value( |
|
|
splay_tree->root->value); |
|
|
splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root); |
|
|
splay_tree->nodes--; |
|
|
if (left == (NodeInfo *) NULL) |
|
|
{ |
|
|
splay_tree->root=right; |
|
|
UnlockSemaphoreInfo(splay_tree->semaphore); |
|
|
return(key); |
|
|
} |
|
|
splay_tree->root=left; |
|
|
if (right != (NodeInfo *) NULL) |
|
|
{ |
|
|
while (left->right != (NodeInfo *) NULL) |
|
|
left=left->right; |
|
|
left->right=right; |
|
|
} |
|
|
UnlockSemaphoreInfo(splay_tree->semaphore); |
|
|
return(key); |
|
|
} |
|
|
} |
|
|
UnlockSemaphoreInfo(splay_tree->semaphore); |
|
|
return(key); |
|
|
} |
|
|
|
|
|
/* |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
|
% % |
|
|
% % |
|
|
% % |
|
|
% R e m o v e N o d e F r o m S p l a y T r e e % |
|
|
% % |
|
|
% % |
|
|
% % |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
|
% |
|
|
% RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its |
|
|
% value. |
|
|
% |
|
|
% The format of the RemoveNodeFromSplayTree method is: |
|
|
% |
|
|
% void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key) |
|
|
% |
|
|
% A description of each parameter follows: |
|
|
% |
|
|
% o splay_tree: the splay-tree info. |
|
|
% |
|
|
% o key: the key. |
|
|
% |
|
|
*/ |
|
|
MagickExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree, |
|
|
const void *key) |
|
|
{ |
|
|
int |
|
|
compare; |
|
|
|
|
|
register NodeInfo |
|
|
*left, |
|
|
*right; |
|
|
|
|
|
void |
|
|
*value; |
|
|
|
|
|
assert(splay_tree != (SplayTreeInfo *) NULL); |
|
|
assert(splay_tree->signature == 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; |
|
|
|
|
|
register 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; |
|
|
|
|
|
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; |
|
|
}
|
|
|
|
