51 #include "magick/studio.h"
52 #include "magick/exception.h"
53 #include "magick/exception-private.h"
54 #include "magick/locale_.h"
55 #include "magick/log.h"
56 #include "magick/memory_.h"
57 #include "magick/splay-tree.h"
58 #include "magick/semaphore.h"
59 #include "magick/string_.h"
64 #define MaxSplayTreeDepth 1024
88 (*compare)(
const void *,
const void *);
91 *(*relinquish_key)(
void *),
92 *(*relinquish_value)(
void *);
153 MagickExport MagickBooleanType AddValueToSplayTree(
SplayTreeInfo *splay_tree,
154 const void *key,
const void *value)
162 LockSemaphoreInfo(splay_tree->semaphore);
163 SplaySplayTree(splay_tree,key);
165 if (splay_tree->root != (
NodeInfo *) NULL)
167 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
168 compare=splay_tree->compare(splay_tree->root->key,key);
170 compare=(splay_tree->root->key > key) ? 1 :
171 ((splay_tree->root->key < key) ? -1 : 0);
174 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
175 (splay_tree->root->value != (
void *) NULL))
176 splay_tree->root->value=splay_tree->relinquish_value(
177 splay_tree->root->value);
178 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
179 (splay_tree->root->key != (
void *) NULL))
180 splay_tree->root->key=splay_tree->relinquish_key(
181 splay_tree->root->key);
182 splay_tree->root->key=(
void *) key;
183 splay_tree->root->value=(
void *) value;
184 UnlockSemaphoreInfo(splay_tree->semaphore);
188 node=(
NodeInfo *) AcquireMagickMemory(
sizeof(*node));
191 UnlockSemaphoreInfo(splay_tree->semaphore);
194 node->key=(
void *) key;
195 node->value=(
void *) value;
196 if (splay_tree->root == (
NodeInfo *) NULL)
204 node->left=splay_tree->root;
205 node->right=node->left->right;
206 node->left->right=(
NodeInfo *) NULL;
210 node->right=splay_tree->root;
211 node->left=node->right->left;
212 node->right->left=(
NodeInfo *) NULL;
214 splay_tree->root=node;
215 splay_tree->key=(
void *) NULL;
217 UnlockSemaphoreInfo(splay_tree->semaphore);
255 bisect=low+(high-low)/2;
257 if ((low+1) > bisect)
260 node->left=LinkSplayTreeNodes(nodes,low,bisect-1);
261 if ((bisect+1) > high)
264 node->right=LinkSplayTreeNodes(nodes,bisect+1,high);
268 static inline int SplayTreeToNodeArray(
NodeInfo *node,
const void *nodes)
285 if (splay_tree->nodes <= 2)
287 splay_tree->balance=MagickFalse;
290 nodes=(
NodeInfo **) AcquireQuantumMemory((
size_t) splay_tree->nodes,
293 ThrowFatalException(ResourceLimitFatalError,
"MemoryAllocationFailed");
295 (void) IterateOverSplayTree(splay_tree,SplayTreeToNodeArray,(
const void *)
297 splay_tree->root=LinkSplayTreeNodes(nodes,0,splay_tree->nodes-1);
298 splay_tree->balance=MagickFalse;
299 nodes=(
NodeInfo **) RelinquishMagickMemory(nodes);
332 static inline void *GetFirstSplayTreeNode(
SplayTreeInfo *splay_tree)
337 node=splay_tree->root;
338 if (splay_tree->root == (
NodeInfo *) NULL)
340 while (node->left != (
NodeInfo *) NULL)
346 void *(*clone_key)(
void *),
void *(*clone_value)(
void *))
356 assert(splay_tree->signature == MagickCoreSignature);
357 if (IsEventLogging() != MagickFalse)
358 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
359 clone_tree=NewSplayTree(splay_tree->compare,splay_tree->relinquish_key,
360 splay_tree->relinquish_value);
361 LockSemaphoreInfo(splay_tree->semaphore);
362 if (splay_tree->root == (
NodeInfo *) NULL)
364 UnlockSemaphoreInfo(splay_tree->semaphore);
367 next=(
NodeInfo *) GetFirstSplayTreeNode(splay_tree);
370 SplaySplayTree(splay_tree,next);
371 (void) AddValueToSplayTree(clone_tree,clone_key(splay_tree->root->key),
372 clone_value(splay_tree->root->value));
374 node=splay_tree->root->right;
377 while (node->left != (
NodeInfo *) NULL)
382 UnlockSemaphoreInfo(splay_tree->semaphore);
411 MagickExport
int CompareSplayTreeString(
const void *target,
const void *source)
417 p=(
const char *) target;
418 q=(
const char *) source;
419 return(LocaleCompare(p,q));
447 MagickExport
int CompareSplayTreeStringInfo(
const void *target,
456 return(CompareStringInfo(p,q));
485 MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree(
493 assert(splay_tree->signature == MagickCoreSignature);
494 if (IsEventLogging() != MagickFalse)
495 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
496 LockSemaphoreInfo(splay_tree->semaphore);
497 if (splay_tree->root == (
NodeInfo *) NULL)
499 UnlockSemaphoreInfo(splay_tree->semaphore);
502 next=(
NodeInfo *) GetFirstSplayTreeNode(splay_tree);
505 SplaySplayTree(splay_tree,next);
507 node=splay_tree->root->right;
510 while (node->left != (
NodeInfo *) NULL)
514 if (splay_tree->root->value == value)
529 key=splay_tree->root->key;
530 SplaySplayTree(splay_tree,key);
531 splay_tree->key=(
void *) NULL;
532 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
533 compare=splay_tree->compare(splay_tree->root->key,key);
535 compare=(splay_tree->root->key > key) ? 1 :
536 ((splay_tree->root->key < key) ? -1 : 0);
539 UnlockSemaphoreInfo(splay_tree->semaphore);
542 left=splay_tree->root->left;
543 right=splay_tree->root->right;
544 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
545 (splay_tree->root->value != (
void *) NULL))
546 splay_tree->root->value=splay_tree->relinquish_value(
547 splay_tree->root->value);
548 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
549 (splay_tree->root->key != (
void *) NULL))
550 splay_tree->root->key=splay_tree->relinquish_key(
551 splay_tree->root->key);
552 splay_tree->root=(
NodeInfo *) RelinquishMagickMemory(splay_tree->root);
556 splay_tree->root=right;
557 UnlockSemaphoreInfo(splay_tree->semaphore);
560 splay_tree->root=left;
563 while (left->right != (
NodeInfo *) NULL)
567 UnlockSemaphoreInfo(splay_tree->semaphore);
571 UnlockSemaphoreInfo(splay_tree->semaphore);
602 MagickExport MagickBooleanType DeleteNodeFromSplayTree(
613 assert(splay_tree->signature == MagickCoreSignature);
614 if (IsEventLogging() != MagickFalse)
615 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
616 if (splay_tree->root == (
NodeInfo *) NULL)
618 LockSemaphoreInfo(splay_tree->semaphore);
619 SplaySplayTree(splay_tree,key);
620 splay_tree->key=(
void *) NULL;
621 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
622 compare=splay_tree->compare(splay_tree->root->key,key);
624 compare=(splay_tree->root->key > key) ? 1 :
625 ((splay_tree->root->key < key) ? -1 : 0);
628 UnlockSemaphoreInfo(splay_tree->semaphore);
631 left=splay_tree->root->left;
632 right=splay_tree->root->right;
633 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
634 (splay_tree->root->value != (
void *) NULL))
635 splay_tree->root->value=splay_tree->relinquish_value(
636 splay_tree->root->value);
637 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
638 (splay_tree->root->key != (
void *) NULL))
639 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
640 splay_tree->root=(
NodeInfo *) RelinquishMagickMemory(splay_tree->root);
644 splay_tree->root=right;
645 UnlockSemaphoreInfo(splay_tree->semaphore);
648 splay_tree->root=left;
651 while (left->right != (
NodeInfo *) NULL)
655 UnlockSemaphoreInfo(splay_tree->semaphore);
690 LockSemaphoreInfo(splay_tree->semaphore);
691 if (splay_tree->root != (
NodeInfo *) NULL)
693 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
694 (splay_tree->root->value != (
void *) NULL))
695 splay_tree->root->value=splay_tree->relinquish_value(
696 splay_tree->root->value);
697 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
698 (splay_tree->root->key != (
void *) NULL))
699 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
700 splay_tree->root->key=(
void *) NULL;
701 for (pend=splay_tree->root; pend != (
NodeInfo *) NULL; )
706 if (active->left != (
NodeInfo *) NULL)
708 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
709 (active->left->value != (
void *) NULL))
710 active->left->value=splay_tree->relinquish_value(
711 active->left->value);
712 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
713 (active->left->key != (
void *) NULL))
714 active->left->key=splay_tree->relinquish_key(active->left->key);
715 active->left->key=(
void *) pend;
718 if (active->right != (
NodeInfo *) NULL)
720 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
721 (active->right->value != (
void *) NULL))
722 active->right->value=splay_tree->relinquish_value(
723 active->right->value);
724 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
725 (active->right->key != (
void *) NULL))
726 active->right->key=splay_tree->relinquish_key(
728 active->right->key=(
void *) pend;
733 node=(
NodeInfo *) RelinquishMagickMemory(node);
737 splay_tree->signature=(~MagickCoreSignature);
738 UnlockSemaphoreInfo(splay_tree->semaphore);
739 DestroySemaphoreInfo(&splay_tree->semaphore);
740 splay_tree=(
SplayTreeInfo *) RelinquishMagickMemory(splay_tree);
768 MagickExport
const void *GetNextKeyInSplayTree(
SplayTreeInfo *splay_tree)
777 assert(splay_tree->signature == MagickCoreSignature);
778 if (IsEventLogging() != MagickFalse)
779 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
780 if ((splay_tree->root == (
NodeInfo *) NULL) ||
781 (splay_tree->next == (
void *) NULL))
782 return((
void *) NULL);
783 LockSemaphoreInfo(splay_tree->semaphore);
784 SplaySplayTree(splay_tree,splay_tree->next);
785 splay_tree->next=(
void *) NULL;
786 node=splay_tree->root->right;
789 while (node->left != (
NodeInfo *) NULL)
791 splay_tree->next=node->key;
793 key=splay_tree->root->key;
794 UnlockSemaphoreInfo(splay_tree->semaphore);
822 MagickExport
const void *GetNextValueInSplayTree(
SplayTreeInfo *splay_tree)
831 assert(splay_tree->signature == MagickCoreSignature);
832 if (IsEventLogging() != MagickFalse)
833 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
834 if ((splay_tree->root == (
NodeInfo *) NULL) ||
835 (splay_tree->next == (
void *) NULL))
836 return((
void *) NULL);
837 LockSemaphoreInfo(splay_tree->semaphore);
838 SplaySplayTree(splay_tree,splay_tree->next);
839 splay_tree->next=(
void *) NULL;
840 node=splay_tree->root->right;
843 while (node->left != (
NodeInfo *) NULL)
845 splay_tree->next=node->key;
847 value=splay_tree->root->value;
848 UnlockSemaphoreInfo(splay_tree->semaphore);
876 MagickExport
const void *GetRootValueFromSplayTree(
SplayTreeInfo *splay_tree)
882 assert(splay_tree->signature == MagickCoreSignature);
883 if (IsEventLogging() != MagickFalse)
884 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
885 value=(
const void *) NULL;
886 LockSemaphoreInfo(splay_tree->semaphore);
887 if (splay_tree->root != (
NodeInfo *) NULL)
888 value=splay_tree->root->value;
889 UnlockSemaphoreInfo(splay_tree->semaphore);
920 MagickExport
const void *GetValueFromSplayTree(
SplayTreeInfo *splay_tree,
930 assert(splay_tree->signature == MagickCoreSignature);
931 if (IsEventLogging() != MagickFalse)
932 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
933 if (splay_tree->root == (
NodeInfo *) NULL)
934 return((
void *) NULL);
935 LockSemaphoreInfo(splay_tree->semaphore);
936 SplaySplayTree(splay_tree,key);
937 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
938 compare=splay_tree->compare(splay_tree->root->key,key);
940 compare=(splay_tree->root->key > key) ? 1 :
941 ((splay_tree->root->key < key) ? -1 : 0);
944 UnlockSemaphoreInfo(splay_tree->semaphore);
945 return((
void *) NULL);
947 value=splay_tree->root->value;
948 UnlockSemaphoreInfo(splay_tree->semaphore);
975 MagickExport
size_t GetNumberOfNodesInSplayTree(
979 assert(splay_tree->signature == MagickCoreSignature);
980 if (IsEventLogging() != MagickFalse)
981 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
982 return(splay_tree->nodes);
1013 int (*method)(
NodeInfo *,
const void *),
const void *value)
1044 if (splay_tree->root == (
NodeInfo *) NULL)
1046 nodes=(
NodeInfo **) AcquireQuantumMemory((
size_t) splay_tree->nodes,
1048 transitions=(
unsigned char *) AcquireQuantumMemory((
size_t) splay_tree->nodes,
1049 sizeof(*transitions));
1050 if ((nodes == (
NodeInfo **) NULL) || (transitions == (
unsigned char *) NULL))
1051 ThrowFatalException(ResourceLimitFatalError,
"MemoryAllocationFailed");
1053 final_transition=MagickFalse;
1054 nodes[0]=splay_tree->root;
1055 transitions[0]=(
unsigned char) LeftTransition;
1056 for (i=0; final_transition == MagickFalse; )
1059 transition=(TransitionType) transitions[i];
1062 case LeftTransition:
1064 transitions[i]=(
unsigned char) DownTransition;
1065 if (node->left == (
NodeInfo *) NULL)
1068 nodes[i]=node->left;
1069 transitions[i]=(
unsigned char) LeftTransition;
1072 case RightTransition:
1074 transitions[i]=(
unsigned char) UpTransition;
1075 if (node->right == (
NodeInfo *) NULL)
1078 nodes[i]=node->right;
1079 transitions[i]=(
unsigned char) LeftTransition;
1082 case DownTransition:
1085 transitions[i]=(
unsigned char) RightTransition;
1086 status=(*method)(node,value);
1088 final_transition=MagickTrue;
1095 final_transition=MagickTrue;
1103 nodes=(
NodeInfo **) RelinquishMagickMemory(nodes);
1104 transitions=(
unsigned char *) RelinquishMagickMemory(transitions);
1141 int (*compare)(
const void *,
const void *),
void *(*relinquish_key)(
void *),
1142 void *(*relinquish_value)(
void *))
1147 splay_tree=(
SplayTreeInfo *) AcquireMagickMemory(
sizeof(*splay_tree));
1149 ThrowFatalException(ResourceLimitFatalError,
"MemoryAllocationFailed");
1150 (void) memset(splay_tree,0,
sizeof(*splay_tree));
1151 splay_tree->root=(
NodeInfo *) NULL;
1152 splay_tree->compare=compare;
1153 splay_tree->relinquish_key=relinquish_key;
1154 splay_tree->relinquish_value=relinquish_value;
1155 splay_tree->balance=MagickFalse;
1156 splay_tree->key=(
void *) NULL;
1157 splay_tree->next=(
void *) NULL;
1158 splay_tree->nodes=0;
1159 splay_tree->debug=IsEventLogging();
1160 splay_tree->semaphore=AllocateSemaphoreInfo();
1161 splay_tree->signature=MagickCoreSignature;
1191 MagickExport
void *RemoveNodeByValueFromSplayTree(
SplayTreeInfo *splay_tree,
1202 assert(splay_tree->signature == MagickCoreSignature);
1203 if (IsEventLogging() != MagickFalse)
1204 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
1206 if (splay_tree->root == (
NodeInfo *) NULL)
1208 LockSemaphoreInfo(splay_tree->semaphore);
1209 next=(
NodeInfo *) GetFirstSplayTreeNode(splay_tree);
1212 SplaySplayTree(splay_tree,next);
1214 node=splay_tree->root->right;
1217 while (node->left != (
NodeInfo *) NULL)
1221 if (splay_tree->root->value == value)
1233 key=splay_tree->root->key;
1234 SplaySplayTree(splay_tree,key);
1235 splay_tree->key=(
void *) NULL;
1236 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
1237 compare=splay_tree->compare(splay_tree->root->key,key);
1239 compare=(splay_tree->root->key > key) ? 1 :
1240 ((splay_tree->root->key < key) ? -1 : 0);
1243 UnlockSemaphoreInfo(splay_tree->semaphore);
1246 left=splay_tree->root->left;
1247 right=splay_tree->root->right;
1248 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
1249 (splay_tree->root->value != (
void *) NULL))
1250 splay_tree->root->value=splay_tree->relinquish_value(
1251 splay_tree->root->value);
1252 splay_tree->root=(
NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1253 splay_tree->nodes--;
1256 splay_tree->root=right;
1257 UnlockSemaphoreInfo(splay_tree->semaphore);
1260 splay_tree->root=left;
1263 while (left->right != (
NodeInfo *) NULL)
1267 UnlockSemaphoreInfo(splay_tree->semaphore);
1271 UnlockSemaphoreInfo(splay_tree->semaphore);
1300 MagickExport
void *RemoveNodeFromSplayTree(
SplayTreeInfo *splay_tree,
1314 assert(splay_tree->signature == MagickCoreSignature);
1315 if (IsEventLogging() != MagickFalse)
1316 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
1317 value=(
void *) NULL;
1318 if (splay_tree->root == (
NodeInfo *) NULL)
1320 LockSemaphoreInfo(splay_tree->semaphore);
1321 SplaySplayTree(splay_tree,key);
1322 splay_tree->key=(
void *) NULL;
1323 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
1324 compare=splay_tree->compare(splay_tree->root->key,key);
1326 compare=(splay_tree->root->key > key) ? 1 :
1327 ((splay_tree->root->key < key) ? -1 : 0);
1330 UnlockSemaphoreInfo(splay_tree->semaphore);
1333 left=splay_tree->root->left;
1334 right=splay_tree->root->right;
1335 value=splay_tree->root->value;
1336 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
1337 (splay_tree->root->key != (
void *) NULL))
1338 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1339 splay_tree->root=(
NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1340 splay_tree->nodes--;
1343 splay_tree->root=right;
1344 UnlockSemaphoreInfo(splay_tree->semaphore);
1347 splay_tree->root=left;
1350 while (left->right != (
NodeInfo *) NULL)
1354 UnlockSemaphoreInfo(splay_tree->semaphore);
1391 assert(splay_tree->signature == MagickCoreSignature);
1392 if (IsEventLogging() != MagickFalse)
1393 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
1394 LockSemaphoreInfo(splay_tree->semaphore);
1395 if (splay_tree->root != (
NodeInfo *) NULL)
1397 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
1398 (splay_tree->root->value != (
void *) NULL))
1399 splay_tree->root->value=splay_tree->relinquish_value(
1400 splay_tree->root->value);
1401 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
1402 (splay_tree->root->key != (
void *) NULL))
1403 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1404 splay_tree->root->key=(
void *) NULL;
1405 for (pend=splay_tree->root; pend != (
NodeInfo *) NULL; )
1410 if (active->left != (
NodeInfo *) NULL)
1412 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
1413 (active->left->value != (
void *) NULL))
1414 active->left->value=splay_tree->relinquish_value(
1415 active->left->value);
1416 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
1417 (active->left->key != (
void *) NULL))
1418 active->left->key=splay_tree->relinquish_key(active->left->key);
1419 active->left->key=(
void *) pend;
1422 if (active->right != (
NodeInfo *) NULL)
1424 if ((splay_tree->relinquish_value != (
void *(*)(
void *)) NULL) &&
1425 (active->right->value != (
void *) NULL))
1426 active->right->value=splay_tree->relinquish_value(
1427 active->right->value);
1428 if ((splay_tree->relinquish_key != (
void *(*)(
void *)) NULL) &&
1429 (active->right->key != (
void *) NULL))
1430 active->right->key=splay_tree->relinquish_key(
1431 active->right->key);
1432 active->right->key=(
void *) pend;
1437 node=(
NodeInfo *) RelinquishMagickMemory(node);
1441 splay_tree->root=(
NodeInfo *) NULL;
1442 splay_tree->key=(
void *) NULL;
1443 splay_tree->next=(
void *) NULL;
1444 splay_tree->nodes=0;
1445 splay_tree->balance=MagickFalse;
1446 UnlockSemaphoreInfo(splay_tree->semaphore);
1473 MagickExport
void ResetSplayTreeIterator(
SplayTreeInfo *splay_tree)
1476 assert(splay_tree->signature == MagickCoreSignature);
1477 if (IsEventLogging() != MagickFalse)
1478 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
1479 LockSemaphoreInfo(splay_tree->semaphore);
1480 splay_tree->next=GetFirstSplayTreeNode(splay_tree);
1481 UnlockSemaphoreInfo(splay_tree->semaphore);
1537 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
1538 compare=splay_tree->compare(n->key,key);
1540 compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
1549 if (depth >= MaxSplayTreeDepth)
1551 splay_tree->balance=MagickTrue;
1554 n=Splay(splay_tree,depth+1,key,next,node,parent);
1555 if ((n != *node) || (splay_tree->balance != MagickFalse))
1560 if (grandparent == (
NodeInfo **) NULL)
1562 if (n == (*parent)->left)
1575 if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
1578 (*grandparent)->left=p->right;
1579 p->right=(*grandparent);
1585 if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
1588 (*grandparent)->right=p->left;
1589 p->left=(*grandparent);
1595 if (n == (*parent)->left)
1597 (*parent)->left=n->right;
1599 (*grandparent)->right=n->left;
1600 n->left=(*grandparent);
1604 (*parent)->right=n->left;
1606 (*grandparent)->left=n->right;
1607 n->right=(*grandparent);
1612 static void SplaySplayTree(
SplayTreeInfo *splay_tree,
const void *key)
1614 if (splay_tree->root == (
NodeInfo *) NULL)
1616 if (splay_tree->key != (
void *) NULL)
1621 if (splay_tree->compare != (int (*)(
const void *,
const void *)) NULL)
1622 compare=splay_tree->compare(splay_tree->root->key,key);
1624 compare=(splay_tree->key > key) ? 1 :
1625 ((splay_tree->key < key) ? -1 : 0);
1629 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(
NodeInfo **) NULL,
1631 if (splay_tree->balance != MagickFalse)
1633 BalanceSplayTree(splay_tree);
1634 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(
NodeInfo **) NULL,
1636 if (splay_tree->balance != MagickFalse)
1637 ThrowFatalException(ResourceLimitFatalError,
"MemoryAllocationFailed");
1639 splay_tree->key=(
void *) key;