51#include "MagickCore/studio.h"
52#include "MagickCore/exception.h"
53#include "MagickCore/exception-private.h"
54#include "MagickCore/locale_.h"
55#include "MagickCore/log.h"
56#include "MagickCore/memory_.h"
57#include "MagickCore/memory-private.h"
58#include "MagickCore/splay-tree.h"
59#include "MagickCore/semaphore.h"
60#include "MagickCore/string_.h"
65#define MaxSplayTreeDepth 1024
89 (*compare)(
const void *,
const void *);
92 *(*relinquish_key)(
void *),
93 *(*relinquish_value)(
void *);
119 IterateOverSplayTree(SplayTreeInfo *,
int (*)(NodeInfo *,
const void *),
123 SplaySplayTree(SplayTreeInfo *,
const void *);
126static NodeInfo *DetachRootFromSplayTree(SplayTreeInfo *splay_tree)
133 node=splay_tree->root;
136 if (splay_tree->next == node->key)
142 if (successor != (NodeInfo *) NULL)
143 while (successor->left != (NodeInfo *) NULL)
144 successor=successor->left;
145 splay_tree->next=successor != (NodeInfo *) NULL ?
146 successor->key : (void *) NULL;
148 splay_tree->root=right;
149 if (left != (NodeInfo *) NULL)
151 splay_tree->root=left;
152 if (right != (NodeInfo *) NULL)
154 while (left->right != (NodeInfo *) NULL)
192MagickExport MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
193 const void *key,
const void *value)
201 LockSemaphoreInfo(splay_tree->semaphore);
202 SplaySplayTree(splay_tree,key);
204 if (splay_tree->root != (NodeInfo *) NULL)
206 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
207 compare=splay_tree->compare(splay_tree->root->key,key);
209 compare=(splay_tree->root->key > key) ? 1 :
210 ((splay_tree->root->key < key) ? -1 : 0);
213 if (splay_tree->relinquish_key != (
void *(*)(
void *)) NULL)
215 if ((key != (
const void *) NULL) &&
216 (key != splay_tree->root->key))
217 (void) splay_tree->relinquish_key((
void *) key);
221 if (splay_tree->next == splay_tree->root->key)
222 splay_tree->next=(
void *) key;
223 splay_tree->root->key=(
void *) key;
225 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
226 (splay_tree->root->value != (
void *) NULL))
227 splay_tree->root->value=splay_tree->relinquish_value(
228 splay_tree->root->value);
229 splay_tree->root->value=(
void *) value;
230 UnlockSemaphoreInfo(splay_tree->semaphore);
234 node=(NodeInfo *) AcquireMagickMemory(
sizeof(*node));
235 if (node == (NodeInfo *) NULL)
237 UnlockSemaphoreInfo(splay_tree->semaphore);
240 node->key=(
void *) key;
241 node->value=(
void *) value;
242 if (splay_tree->root == (NodeInfo *) NULL)
244 node->left=(NodeInfo *) NULL;
245 node->right=(NodeInfo *) NULL;
250 node->left=splay_tree->root;
251 node->right=node->left->right;
252 node->left->right=(NodeInfo *) NULL;
256 node->right=splay_tree->root;
257 node->left=node->right->left;
258 node->right->left=(NodeInfo *) NULL;
260 splay_tree->root=node;
261 splay_tree->key=(
void *) NULL;
263 UnlockSemaphoreInfo(splay_tree->semaphore);
292static NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,
const size_t low,
301 bisect=low+(high-low)/2;
303 if ((low+1) > bisect)
304 node->left=(NodeInfo *) NULL;
306 node->left=LinkSplayTreeNodes(nodes,low,bisect-1);
307 if ((bisect+1) > high)
308 node->right=(NodeInfo *) NULL;
310 node->right=LinkSplayTreeNodes(nodes,bisect+1,high);
314static inline int SplayTreeToNodeArray(NodeInfo *node,
const void *nodes)
319 p=(
const NodeInfo ***) nodes;
325static void BalanceSplayTree(SplayTreeInfo *splay_tree)
331 if (splay_tree->nodes <= 2)
333 splay_tree->balance=MagickFalse;
336 nodes=(NodeInfo **) AcquireQuantumMemory((
size_t) splay_tree->nodes,
338 if (nodes == (NodeInfo **) NULL)
339 ThrowFatalException(ResourceLimitFatalError,
"MemoryAllocationFailed");
341 (void) IterateOverSplayTree(splay_tree,SplayTreeToNodeArray,(
const void *)
343 splay_tree->root=LinkSplayTreeNodes(nodes,0,splay_tree->nodes-1);
344 splay_tree->balance=MagickFalse;
345 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
378static inline void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree)
383 node=splay_tree->root;
384 if (splay_tree->root == (NodeInfo *) NULL)
385 return((NodeInfo *) NULL);
386 while (node->left != (NodeInfo *) NULL)
391MagickExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
392 void *(*clone_key)(
void *),
void *(*clone_value)(
void *))
401 assert(splay_tree != (SplayTreeInfo *) NULL);
402 assert(splay_tree->signature == MagickCoreSignature);
403 if (IsEventLogging() != MagickFalse)
404 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
405 clone_tree=NewSplayTree(splay_tree->compare,splay_tree->relinquish_key,
406 splay_tree->relinquish_value);
407 LockSemaphoreInfo(splay_tree->semaphore);
408 if (splay_tree->root == (NodeInfo *) NULL)
410 UnlockSemaphoreInfo(splay_tree->semaphore);
413 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
414 while (next != (NodeInfo *) NULL)
416 SplaySplayTree(splay_tree,next);
417 (void) AddValueToSplayTree(clone_tree,clone_key(splay_tree->root->key),
418 clone_value(splay_tree->root->value));
419 next=(NodeInfo *) NULL;
420 node=splay_tree->root->right;
421 if (node != (NodeInfo *) NULL)
423 while (node->left != (NodeInfo *) NULL)
425 next=(NodeInfo *) node->key;
428 UnlockSemaphoreInfo(splay_tree->semaphore);
457MagickExport
int CompareSplayTreeString(
const void *target,
const void *source)
463 p=(
const char *) target;
464 q=(
const char *) source;
465 return(LocaleCompare(p,q));
493MagickExport
int CompareSplayTreeStringInfo(
const void *target,
500 p=(
const StringInfo *) target;
501 q=(
const StringInfo *) source;
502 return(CompareStringInfo(p,q));
531MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree(
532 SplayTreeInfo *splay_tree,
const void *value)
538 assert(splay_tree != (SplayTreeInfo *) NULL);
539 assert(splay_tree->signature == MagickCoreSignature);
540 if (IsEventLogging() != MagickFalse)
541 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
542 LockSemaphoreInfo(splay_tree->semaphore);
543 if (splay_tree->root == (NodeInfo *) NULL)
545 UnlockSemaphoreInfo(splay_tree->semaphore);
548 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
549 while (next != (NodeInfo *) NULL)
551 SplaySplayTree(splay_tree,next);
552 next=(NodeInfo *) NULL;
553 node=splay_tree->root->right;
554 if (node != (NodeInfo *) NULL)
556 while (node->left != (NodeInfo *) NULL)
558 next=(NodeInfo *) node->key;
560 if (splay_tree->root->value == value)
571 key=splay_tree->root->key;
572 SplaySplayTree(splay_tree,key);
573 splay_tree->key=(
void *) NULL;
574 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
575 compare=splay_tree->compare(splay_tree->root->key,key);
577 compare=(splay_tree->root->key > key) ? 1 :
578 ((splay_tree->root->key < key) ? -1 : 0);
581 UnlockSemaphoreInfo(splay_tree->semaphore);
584 node=DetachRootFromSplayTree(splay_tree);
585 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
586 (node->value != (
void *) NULL))
587 node->value=splay_tree->relinquish_value(node->value);
588 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
589 (node->key != (
void *) NULL))
590 node->key=splay_tree->relinquish_key(node->key);
591 node=(NodeInfo *) RelinquishMagickMemory(node);
592 UnlockSemaphoreInfo(splay_tree->semaphore);
596 UnlockSemaphoreInfo(splay_tree->semaphore);
627MagickExport MagickBooleanType DeleteNodeFromSplayTree(
628 SplayTreeInfo *splay_tree,
const void *key)
636 assert(splay_tree != (SplayTreeInfo *) NULL);
637 assert(splay_tree->signature == MagickCoreSignature);
638 if (IsEventLogging() != MagickFalse)
639 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
640 if (splay_tree->root == (NodeInfo *) NULL)
642 LockSemaphoreInfo(splay_tree->semaphore);
643 SplaySplayTree(splay_tree,key);
644 splay_tree->key=(
void *) NULL;
645 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
646 compare=splay_tree->compare(splay_tree->root->key,key);
648 compare=(splay_tree->root->key > key) ? 1 :
649 ((splay_tree->root->key < key) ? -1 : 0);
652 UnlockSemaphoreInfo(splay_tree->semaphore);
655 node=DetachRootFromSplayTree(splay_tree);
656 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
657 (node->value != (
void *) NULL))
658 node->value=splay_tree->relinquish_value(node->value);
659 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
660 (node->key != (
void *) NULL))
661 node->key=splay_tree->relinquish_key(node->key);
662 node=(NodeInfo *) RelinquishMagickMemory(node);
663 UnlockSemaphoreInfo(splay_tree->semaphore);
689MagickExport SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
696 LockSemaphoreInfo(splay_tree->semaphore);
697 if (splay_tree->root != (NodeInfo *) NULL)
699 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
700 (splay_tree->root->value != (
void *) NULL))
701 splay_tree->root->value=splay_tree->relinquish_value(
702 splay_tree->root->value);
703 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
704 (splay_tree->root->key != (
void *) NULL))
705 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
706 splay_tree->root->key=(
void *) NULL;
707 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
710 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
712 if (active->left != (NodeInfo *) NULL)
714 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
715 (active->left->value != (
void *) NULL))
716 active->left->value=splay_tree->relinquish_value(
717 active->left->value);
718 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
719 (active->left->key != (
void *) NULL))
720 active->left->key=splay_tree->relinquish_key(active->left->key);
721 active->left->key=(
void *) pend;
724 if (active->right != (NodeInfo *) NULL)
726 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
727 (active->right->value != (
void *) NULL))
728 active->right->value=splay_tree->relinquish_value(
729 active->right->value);
730 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
731 (active->right->key != (
void *) NULL))
732 active->right->key=splay_tree->relinquish_key(
734 active->right->key=(
void *) pend;
738 active=(NodeInfo *) node->key;
739 node=(NodeInfo *) RelinquishMagickMemory(node);
743 splay_tree->signature=(~MagickCoreSignature);
744 UnlockSemaphoreInfo(splay_tree->semaphore);
745 RelinquishSemaphoreInfo(&splay_tree->semaphore);
746 splay_tree=(SplayTreeInfo *) RelinquishMagickMemory(splay_tree);
774MagickExport
const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
782 assert(splay_tree != (SplayTreeInfo *) NULL);
783 assert(splay_tree->signature == MagickCoreSignature);
784 if (IsEventLogging() != MagickFalse)
785 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
786 LockSemaphoreInfo(splay_tree->semaphore);
787 if ((splay_tree->root == (NodeInfo *) NULL) ||
788 (splay_tree->next == (
void *) NULL))
790 UnlockSemaphoreInfo(splay_tree->semaphore);
791 return((
void *) NULL);
793 SplaySplayTree(splay_tree,splay_tree->next);
794 splay_tree->next=(
void *) NULL;
795 node=splay_tree->root->right;
796 if (node != (NodeInfo *) NULL)
798 while (node->left != (NodeInfo *) NULL)
800 splay_tree->next=node->key;
802 key=splay_tree->root->key;
803 UnlockSemaphoreInfo(splay_tree->semaphore);
831MagickExport
const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
839 assert(splay_tree != (SplayTreeInfo *) NULL);
840 assert(splay_tree->signature == MagickCoreSignature);
841 if (IsEventLogging() != MagickFalse)
842 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
843 LockSemaphoreInfo(splay_tree->semaphore);
844 if ((splay_tree->root == (NodeInfo *) NULL) ||
845 (splay_tree->next == (
void *) NULL))
847 UnlockSemaphoreInfo(splay_tree->semaphore);
848 return((
void *) NULL);
850 SplaySplayTree(splay_tree,splay_tree->next);
851 splay_tree->next=(
void *) NULL;
852 node=splay_tree->root->right;
853 if (node != (NodeInfo *) NULL)
855 while (node->left != (NodeInfo *) NULL)
857 splay_tree->next=node->key;
859 value=splay_tree->root->value;
860 UnlockSemaphoreInfo(splay_tree->semaphore);
888MagickExport
const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
893 assert(splay_tree != (SplayTreeInfo *) NULL);
894 assert(splay_tree->signature == MagickCoreSignature);
895 if (IsEventLogging() != MagickFalse)
896 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
897 value=(
const void *) NULL;
898 LockSemaphoreInfo(splay_tree->semaphore);
899 if (splay_tree->root != (NodeInfo *) NULL)
900 value=splay_tree->root->value;
901 UnlockSemaphoreInfo(splay_tree->semaphore);
932MagickExport
const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
941 assert(splay_tree != (SplayTreeInfo *) NULL);
942 assert(splay_tree->signature == MagickCoreSignature);
943 if (IsEventLogging() != MagickFalse)
944 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
945 if (splay_tree->root == (NodeInfo *) NULL)
946 return((
void *) NULL);
947 LockSemaphoreInfo(splay_tree->semaphore);
948 SplaySplayTree(splay_tree,key);
949 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
950 compare=splay_tree->compare(splay_tree->root->key,key);
952 compare=(splay_tree->root->key > key) ? 1 :
953 ((splay_tree->root->key < key) ? -1 : 0);
956 UnlockSemaphoreInfo(splay_tree->semaphore);
957 return((
void *) NULL);
959 value=splay_tree->root->value;
960 UnlockSemaphoreInfo(splay_tree->semaphore);
987MagickExport
size_t GetNumberOfNodesInSplayTree(
988 const SplayTreeInfo *splay_tree)
990 assert(splay_tree != (SplayTreeInfo *) NULL);
991 assert(splay_tree->signature == MagickCoreSignature);
992 if (IsEventLogging() != MagickFalse)
993 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
994 return(splay_tree->nodes);
1024static int IterateOverSplayTree(SplayTreeInfo *splay_tree,
1025 int (*method)(NodeInfo *,
const void *),
const void *value)
1054 if (splay_tree->root == (NodeInfo *) NULL)
1056 nodes=(NodeInfo **) AcquireQuantumMemory((
size_t) splay_tree->nodes,
1058 transitions=(
unsigned char *) AcquireQuantumMemory((
size_t) splay_tree->nodes,
1059 sizeof(*transitions));
1060 if ((nodes == (NodeInfo **) NULL) || (transitions == (
unsigned char *) NULL))
1061 ThrowFatalException(ResourceLimitFatalError,
"MemoryAllocationFailed");
1063 final_transition=MagickFalse;
1064 nodes[0]=splay_tree->root;
1065 transitions[0]=(
unsigned char) LeftTransition;
1066 for (i=0; final_transition == MagickFalse; )
1069 transition=(TransitionType) transitions[i];
1072 case LeftTransition:
1074 transitions[i]=(
unsigned char) DownTransition;
1075 if (node->left == (NodeInfo *) NULL)
1078 nodes[i]=node->left;
1079 transitions[i]=(
unsigned char) LeftTransition;
1082 case RightTransition:
1084 transitions[i]=(
unsigned char) UpTransition;
1085 if (node->right == (NodeInfo *) NULL)
1088 nodes[i]=node->right;
1089 transitions[i]=(
unsigned char) LeftTransition;
1092 case DownTransition:
1095 transitions[i]=(
unsigned char) RightTransition;
1096 status=(*method)(node,value);
1098 final_transition=MagickTrue;
1105 final_transition=MagickTrue;
1113 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
1114 transitions=(
unsigned char *) RelinquishMagickMemory(transitions);
1150MagickExport SplayTreeInfo *NewSplayTree(
1151 int (*compare)(
const void *,
const void *),
void *(*relinquish_key)(
void *),
1152 void *(*relinquish_value)(
void *))
1157 splay_tree=(SplayTreeInfo *) AcquireCriticalMemory(
sizeof(*splay_tree));
1158 (void) memset(splay_tree,0,
sizeof(*splay_tree));
1159 splay_tree->root=(NodeInfo *) NULL;
1160 splay_tree->compare=compare;
1161 splay_tree->relinquish_key=relinquish_key;
1162 splay_tree->relinquish_value=relinquish_value;
1163 splay_tree->balance=MagickFalse;
1164 splay_tree->key=(
void *) NULL;
1165 splay_tree->next=(
void *) NULL;
1166 splay_tree->nodes=0;
1167 splay_tree->debug=IsEventLogging();
1168 splay_tree->semaphore=AcquireSemaphoreInfo();
1169 splay_tree->signature=MagickCoreSignature;
1199MagickExport
void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1209 assert(splay_tree != (SplayTreeInfo *) NULL);
1210 assert(splay_tree->signature == MagickCoreSignature);
1211 if (IsEventLogging() != MagickFalse)
1212 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
1214 if (splay_tree->root == (NodeInfo *) NULL)
1216 LockSemaphoreInfo(splay_tree->semaphore);
1217 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
1218 while (next != (NodeInfo *) NULL)
1220 SplaySplayTree(splay_tree,next);
1221 next=(NodeInfo *) NULL;
1222 node=splay_tree->root->right;
1223 if (node != (NodeInfo *) NULL)
1225 while (node->left != (NodeInfo *) NULL)
1227 next=(NodeInfo *) node->key;
1229 if (splay_tree->root->value == value)
1237 key=splay_tree->root->key;
1238 SplaySplayTree(splay_tree,key);
1239 splay_tree->key=(
void *) NULL;
1240 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
1241 compare=splay_tree->compare(splay_tree->root->key,key);
1243 compare=(splay_tree->root->key > key) ? 1 :
1244 ((splay_tree->root->key < key) ? -1 : 0);
1247 UnlockSemaphoreInfo(splay_tree->semaphore);
1250 node=DetachRootFromSplayTree(splay_tree);
1251 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
1252 (node->value != (
void *) NULL))
1253 node->value=splay_tree->relinquish_value(node->value);
1254 node=(NodeInfo *) RelinquishMagickMemory(node);
1255 UnlockSemaphoreInfo(splay_tree->semaphore);
1259 UnlockSemaphoreInfo(splay_tree->semaphore);
1288MagickExport
void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,
1300 assert(splay_tree != (SplayTreeInfo *) NULL);
1301 assert(splay_tree->signature == MagickCoreSignature);
1302 if (IsEventLogging() != MagickFalse)
1303 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
1304 value=(
void *) NULL;
1305 if (splay_tree->root == (NodeInfo *) NULL)
1307 LockSemaphoreInfo(splay_tree->semaphore);
1308 SplaySplayTree(splay_tree,key);
1309 splay_tree->key=(
void *) NULL;
1310 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
1311 compare=splay_tree->compare(splay_tree->root->key,key);
1313 compare=(splay_tree->root->key > key) ? 1 :
1314 ((splay_tree->root->key < key) ? -1 : 0);
1317 UnlockSemaphoreInfo(splay_tree->semaphore);
1320 node=DetachRootFromSplayTree(splay_tree);
1322 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
1323 (node->key != (
void *) NULL))
1324 node->key=splay_tree->relinquish_key(node->key);
1325 node=(NodeInfo *) RelinquishMagickMemory(node);
1326 UnlockSemaphoreInfo(splay_tree->semaphore);
1353MagickExport
void ResetSplayTree(SplayTreeInfo *splay_tree)
1360 assert(splay_tree != (SplayTreeInfo *) NULL);
1361 assert(splay_tree->signature == MagickCoreSignature);
1362 if (IsEventLogging() != MagickFalse)
1363 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
1364 LockSemaphoreInfo(splay_tree->semaphore);
1365 if (splay_tree->root != (NodeInfo *) NULL)
1367 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
1368 (splay_tree->root->value != (
void *) NULL))
1369 splay_tree->root->value=splay_tree->relinquish_value(
1370 splay_tree->root->value);
1371 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
1372 (splay_tree->root->key != (
void *) NULL))
1373 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1374 splay_tree->root->key=(
void *) NULL;
1375 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
1378 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
1380 if (active->left != (NodeInfo *) NULL)
1382 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
1383 (active->left->value != (
void *) NULL))
1384 active->left->value=splay_tree->relinquish_value(
1385 active->left->value);
1386 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
1387 (active->left->key != (
void *) NULL))
1388 active->left->key=splay_tree->relinquish_key(active->left->key);
1389 active->left->key=(
void *) pend;
1392 if (active->right != (NodeInfo *) NULL)
1394 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
1395 (active->right->value != (
void *) NULL))
1396 active->right->value=splay_tree->relinquish_value(
1397 active->right->value);
1398 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
1399 (active->right->key != (
void *) NULL))
1400 active->right->key=splay_tree->relinquish_key(
1401 active->right->key);
1402 active->right->key=(
void *) pend;
1406 active=(NodeInfo *) node->key;
1407 node=(NodeInfo *) RelinquishMagickMemory(node);
1411 splay_tree->root=(NodeInfo *) NULL;
1412 splay_tree->key=(
void *) NULL;
1413 splay_tree->next=(
void *) NULL;
1414 splay_tree->nodes=0;
1415 splay_tree->balance=MagickFalse;
1416 UnlockSemaphoreInfo(splay_tree->semaphore);
1443MagickExport
void ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1445 assert(splay_tree != (SplayTreeInfo *) NULL);
1446 assert(splay_tree->signature == MagickCoreSignature);
1447 if (IsEventLogging() != MagickFalse)
1448 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
1449 LockSemaphoreInfo(splay_tree->semaphore);
1450 splay_tree->next=GetFirstSplayTreeNode(splay_tree);
1451 UnlockSemaphoreInfo(splay_tree->semaphore);
1486static NodeInfo *Splay(SplayTreeInfo *splay_tree,
const size_t depth,
1487 const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1498 if (n == (NodeInfo *) NULL)
1500 if (parent != (NodeInfo **) NULL)
1503 return((NodeInfo *) NULL);
1505 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
1506 compare=splay_tree->compare(n->key,key);
1508 compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
1509 next=(NodeInfo **) NULL;
1515 if (next != (NodeInfo **) NULL)
1517 if (depth >= MaxSplayTreeDepth)
1519 splay_tree->balance=MagickTrue;
1522 n=Splay(splay_tree,depth+1,key,next,node,parent);
1523 if ((n != *node) || (splay_tree->balance != MagickFalse))
1526 if (parent == (NodeInfo **) NULL)
1528 if (grandparent == (NodeInfo **) NULL)
1530 if (n == (*parent)->left)
1543 if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
1546 (*grandparent)->left=p->right;
1547 p->right=(*grandparent);
1553 if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
1556 (*grandparent)->right=p->left;
1557 p->left=(*grandparent);
1563 if (n == (*parent)->left)
1565 (*parent)->left=n->right;
1567 (*grandparent)->right=n->left;
1568 n->left=(*grandparent);
1572 (*parent)->right=n->left;
1574 (*grandparent)->left=n->right;
1575 n->right=(*grandparent);
1580static void SplaySplayTree(SplayTreeInfo *splay_tree,
const void *key)
1582 if (splay_tree->root == (NodeInfo *) NULL)
1584 if (splay_tree->key != (
void *) NULL)
1589 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
1590 compare=splay_tree->compare(splay_tree->root->key,key);
1592 compare=(splay_tree->key > key) ? 1 :
1593 ((splay_tree->key < key) ? -1 : 0);
1597 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1598 (NodeInfo **) NULL);
1599 if (splay_tree->balance != MagickFalse)
1601 BalanceSplayTree(splay_tree);
1602 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1603 (NodeInfo **) NULL);
1604 if (splay_tree->balance != MagickFalse)
1605 ThrowFatalException(ResourceLimitFatalError,
"MemoryAllocationFailed");
1607 splay_tree->key=(
void *) key;