2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6 % SSSSS PPPP L AAA Y Y %
10 % SSSSS P LLLLL A A Y %
12 % TTTTT RRRR EEEEE EEEEE %
19 % MagickCore Self-adjusting Binary Search Tree Methods %
26 % Copyright 1999-2012 ImageMagick Studio LLC, a non-profit organization %
27 % dedicated to making software imaging solutions freely available. %
29 % You may not use this file except in compliance with the License. You may %
30 % obtain a copy of the License at %
32 % http://www.imagemagick.org/script/license.php %
34 % Unless required by applicable law or agreed to in writing, software %
35 % distributed under the License is distributed on an "AS IS" BASIS, %
36 % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %
37 % See the License for the specific language governing permissions and %
38 % limitations under the License. %
40 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
42 % This module implements the standard handy splay-tree methods for storing and
43 % retrieving large numbers of data elements. It is loosely based on the Java
44 % implementation of these algorithms.
51 #include "MagickCore/studio.h"
52 #include "MagickCore/exception.h"
53 #include "MagickCore/exception-private.h"
54 #include "MagickCore/log.h"
55 #include "MagickCore/memory_.h"
56 #include "MagickCore/splay-tree.h"
57 #include "MagickCore/semaphore.h"
58 #include "MagickCore/string_.h"
63 #define MaxSplayTreeDepth 1024
68 typedef struct _NodeInfo
87 (*compare)(const void *,const void *);
90 *(*relinquish_key)(void *),
91 *(*relinquish_value)(void *);
114 Forward declarations.
117 IterateOverSplayTree(SplayTreeInfo *,int (*)(NodeInfo *,const void *),
121 SplaySplayTree(SplayTreeInfo *,const void *);
124 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
128 % A d d V a l u e T o S p l a y T r e e %
132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
134 % AddValueToSplayTree() adds a value to the splay-tree.
136 % The format of the AddValueToSplayTree method is:
138 % MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
139 % const void *key,const void *value)
141 % A description of each parameter follows:
143 % o splay_tree: the splay-tree info.
147 % o value: the value.
150 MagickExport MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
151 const void *key,const void *value)
159 LockSemaphoreInfo(splay_tree->semaphore);
160 SplaySplayTree(splay_tree,key);
162 if (splay_tree->root != (NodeInfo *) NULL)
164 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
165 compare=splay_tree->compare(splay_tree->root->key,key);
167 compare=(splay_tree->root->key > key) ? 1 :
168 ((splay_tree->root->key < key) ? -1 : 0);
171 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
172 (splay_tree->root->value != (void *) NULL))
173 splay_tree->root->value=splay_tree->relinquish_value(
174 splay_tree->root->value);
175 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
176 (splay_tree->root->key != (void *) NULL))
177 splay_tree->root->key=splay_tree->relinquish_key(
178 splay_tree->root->key);
179 splay_tree->root->key=(void *) key;
180 splay_tree->root->value=(void *) value;
181 UnlockSemaphoreInfo(splay_tree->semaphore);
185 node=(NodeInfo *) AcquireMagickMemory(sizeof(*node));
186 if (node == (NodeInfo *) NULL)
188 UnlockSemaphoreInfo(splay_tree->semaphore);
191 node->key=(void *) key;
192 node->value=(void *) value;
193 if (splay_tree->root == (NodeInfo *) NULL)
195 node->left=(NodeInfo *) NULL;
196 node->right=(NodeInfo *) NULL;
201 node->left=splay_tree->root;
202 node->right=node->left->right;
203 node->left->right=(NodeInfo *) NULL;
207 node->right=splay_tree->root;
208 node->left=node->right->left;
209 node->right->left=(NodeInfo *) NULL;
211 splay_tree->root=node;
212 splay_tree->key=(void *) NULL;
214 UnlockSemaphoreInfo(splay_tree->semaphore);
219 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
223 % B a l a n c e S p l a y T r e e %
227 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
229 % BalanceSplayTree() balances the splay-tree.
231 % The format of the BalanceSplayTree method is:
233 % void *BalanceSplayTree(SplayTreeInfo *splay_tree,const void *key)
235 % A description of each parameter follows:
237 % o splay_tree: the splay-tree info.
243 static NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const size_t low,
252 bisect=low+(high-low)/2;
254 if ((low+1) > bisect)
255 node->left=(NodeInfo *) NULL;
257 node->left=LinkSplayTreeNodes(nodes,low,bisect-1);
258 if ((bisect+1) > high)
259 node->right=(NodeInfo *) NULL;
261 node->right=LinkSplayTreeNodes(nodes,bisect+1,high);
265 static int SplayTreeToNodeArray(NodeInfo *node,const void *nodes)
267 register const NodeInfo
270 p=(const NodeInfo ***) nodes;
276 static void BalanceSplayTree(SplayTreeInfo *splay_tree)
282 if (splay_tree->nodes <= 2)
284 splay_tree->balance=MagickFalse;
287 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
289 if (nodes == (NodeInfo **) NULL)
290 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
292 (void) IterateOverSplayTree(splay_tree,SplayTreeToNodeArray,
293 (const void *) &node);
294 splay_tree->root=LinkSplayTreeNodes(nodes,0,splay_tree->nodes-1);
295 splay_tree->balance=MagickFalse;
296 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
300 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
304 % C l o n e S p l a y T r e e %
308 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
310 % CloneSplayTree() clones the splay tree.
312 % The format of the CloneSplayTree method is:
314 % SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
315 % void *(*clone_key)(void *),void *(*cline_value)(void *))
317 % A description of each parameter follows:
319 % o splay_tree: the splay tree.
321 % o clone_key: the key clone method, typically ConstantString(), called
322 % whenever a key is added to the splay-tree.
324 % o clone_value: the value clone method; typically ConstantString(), called
325 % whenever a value object is added to the splay-tree.
329 static void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree)
334 node=splay_tree->root;
335 if (splay_tree->root == (NodeInfo *) NULL)
336 return((NodeInfo *) NULL);
337 while (node->left != (NodeInfo *) NULL)
342 MagickExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
343 void *(*clone_key)(void *),void *(*clone_value)(void *))
352 assert(splay_tree != (SplayTreeInfo *) NULL);
353 assert(splay_tree->signature == MagickSignature);
354 if (splay_tree->debug != MagickFalse)
355 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
356 clone_tree=NewSplayTree(splay_tree->compare,splay_tree->relinquish_key,
357 splay_tree->relinquish_value);
358 LockSemaphoreInfo(splay_tree->semaphore);
359 if (splay_tree->root == (NodeInfo *) NULL)
361 UnlockSemaphoreInfo(splay_tree->semaphore);
364 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
365 while (next != (NodeInfo *) NULL)
367 SplaySplayTree(splay_tree,next);
368 (void) AddValueToSplayTree(clone_tree,clone_key(splay_tree->root->key),
369 clone_value(splay_tree->root->value));
370 next=(NodeInfo *) NULL;
371 node=splay_tree->root->right;
372 if (node != (NodeInfo *) NULL)
374 while (node->left != (NodeInfo *) NULL)
376 next=(NodeInfo *) node->key;
379 UnlockSemaphoreInfo(splay_tree->semaphore);
384 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
388 % C o m p a r e S p l a y T r e e S t r i n g %
392 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
394 % CompareSplayTreeString() method finds a node in a splay-tree based on the
395 % contents of a string.
397 % The format of the CompareSplayTreeString method is:
399 % int CompareSplayTreeString(const void *target,const void *source)
401 % A description of each parameter follows:
403 % o target: the target string.
405 % o source: the source string.
408 MagickExport int CompareSplayTreeString(const void *target,const void *source)
414 p=(const char *) target;
415 q=(const char *) source;
416 return(LocaleCompare(p,q));
420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
424 % 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 %
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
430 % CompareSplayTreeStringInfo() finds a node in a splay-tree based on the
431 % contents of a string.
433 % The format of the CompareSplayTreeStringInfo method is:
435 % int CompareSplayTreeStringInfo(const void *target,const void *source)
437 % A description of each parameter follows:
439 % o target: the target string.
441 % o source: the source string.
444 MagickExport int CompareSplayTreeStringInfo(const void *target,
451 p=(const StringInfo *) target;
452 q=(const StringInfo *) source;
453 return(CompareStringInfo(p,q));
457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
461 % 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 %
465 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
467 % DeleteNodeByValueFromSplayTree() deletes a node by value from the
470 % The format of the DeleteNodeByValueFromSplayTree method is:
472 % MagickBooleanType DeleteNodeByValueFromSplayTree(
473 % SplayTreeInfo *splay_tree,const void *value)
475 % A description of each parameter follows:
477 % o splay_tree: the splay-tree info.
479 % o value: the value.
482 MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree(
483 SplayTreeInfo *splay_tree,const void *value)
489 assert(splay_tree != (SplayTreeInfo *) NULL);
490 assert(splay_tree->signature == MagickSignature);
491 if (splay_tree->debug != MagickFalse)
492 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
493 LockSemaphoreInfo(splay_tree->semaphore);
494 if (splay_tree->root == (NodeInfo *) NULL)
496 UnlockSemaphoreInfo(splay_tree->semaphore);
499 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
500 while (next != (NodeInfo *) NULL)
502 SplaySplayTree(splay_tree,next);
503 next=(NodeInfo *) NULL;
504 node=splay_tree->root->right;
505 if (node != (NodeInfo *) NULL)
507 while (node->left != (NodeInfo *) NULL)
509 next=(NodeInfo *) node->key;
511 if (splay_tree->root->value == value)
524 We found the node that matches the value; now delete it.
526 key=splay_tree->root->key;
527 SplaySplayTree(splay_tree,key);
528 splay_tree->key=(void *) NULL;
529 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
530 compare=splay_tree->compare(splay_tree->root->key,key);
532 compare=(splay_tree->root->key > key) ? 1 :
533 ((splay_tree->root->key < key) ? -1 : 0);
536 UnlockSemaphoreInfo(splay_tree->semaphore);
539 left=splay_tree->root->left;
540 right=splay_tree->root->right;
541 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
542 (splay_tree->root->value != (void *) NULL))
543 splay_tree->root->value=splay_tree->relinquish_value(
544 splay_tree->root->value);
545 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
546 (splay_tree->root->key != (void *) NULL))
547 splay_tree->root->key=splay_tree->relinquish_key(
548 splay_tree->root->key);
549 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
551 if (left == (NodeInfo *) NULL)
553 splay_tree->root=right;
554 UnlockSemaphoreInfo(splay_tree->semaphore);
557 splay_tree->root=left;
558 if (right != (NodeInfo *) NULL)
560 while (left->right != (NodeInfo *) NULL)
564 UnlockSemaphoreInfo(splay_tree->semaphore);
568 UnlockSemaphoreInfo(splay_tree->semaphore);
573 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
577 % D e l e t e N o d e F r o m S p l a y T r e e %
581 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
583 % DeleteNodeFromSplayTree() deletes a node from the splay-tree.
585 % The format of the DeleteNodeFromSplayTree method is:
587 % MagickBooleanType DeleteNodeFromSplayTree(SplayTreeInfo *splay_tree,
590 % A description of each parameter follows:
592 % o splay_tree: the splay-tree info.
597 MagickExport MagickBooleanType DeleteNodeFromSplayTree(
598 SplayTreeInfo *splay_tree,const void *key)
607 assert(splay_tree != (SplayTreeInfo *) NULL);
608 assert(splay_tree->signature == MagickSignature);
609 if (splay_tree->debug != MagickFalse)
610 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
611 if (splay_tree->root == (NodeInfo *) NULL)
613 LockSemaphoreInfo(splay_tree->semaphore);
614 SplaySplayTree(splay_tree,key);
615 splay_tree->key=(void *) NULL;
616 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
617 compare=splay_tree->compare(splay_tree->root->key,key);
619 compare=(splay_tree->root->key > key) ? 1 :
620 ((splay_tree->root->key < key) ? -1 : 0);
623 UnlockSemaphoreInfo(splay_tree->semaphore);
626 left=splay_tree->root->left;
627 right=splay_tree->root->right;
628 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
629 (splay_tree->root->value != (void *) NULL))
630 splay_tree->root->value=splay_tree->relinquish_value(
631 splay_tree->root->value);
632 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
633 (splay_tree->root->key != (void *) NULL))
634 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
635 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
637 if (left == (NodeInfo *) NULL)
639 splay_tree->root=right;
640 UnlockSemaphoreInfo(splay_tree->semaphore);
643 splay_tree->root=left;
644 if (right != (NodeInfo *) NULL)
646 while (left->right != (NodeInfo *) NULL)
650 UnlockSemaphoreInfo(splay_tree->semaphore);
655 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
659 % D e s t r o y S p l a y T r e e %
663 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
665 % DestroySplayTree() destroys the splay-tree.
667 % The format of the DestroySplayTree method is:
669 % SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
671 % A description of each parameter follows:
673 % o splay_tree: the splay tree.
676 MagickExport SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
685 LockSemaphoreInfo(splay_tree->semaphore);
686 if (splay_tree->root != (NodeInfo *) NULL)
688 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
689 (splay_tree->root->value != (void *) NULL))
690 splay_tree->root->value=splay_tree->relinquish_value(
691 splay_tree->root->value);
692 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
693 (splay_tree->root->key != (void *) NULL))
694 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
695 splay_tree->root->key=(void *) NULL;
696 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
699 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
701 if (active->left != (NodeInfo *) NULL)
703 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
704 (active->left->value != (void *) NULL))
705 active->left->value=splay_tree->relinquish_value(
706 active->left->value);
707 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
708 (active->left->key != (void *) NULL))
709 active->left->key=splay_tree->relinquish_key(active->left->key);
710 active->left->key=(void *) pend;
713 if (active->right != (NodeInfo *) NULL)
715 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
716 (active->right->value != (void *) NULL))
717 active->right->value=splay_tree->relinquish_value(
718 active->right->value);
719 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
720 (active->right->key != (void *) NULL))
721 active->right->key=splay_tree->relinquish_key(
723 active->right->key=(void *) pend;
727 active=(NodeInfo *) node->key;
728 node=(NodeInfo *) RelinquishMagickMemory(node);
732 splay_tree->signature=(~MagickSignature);
733 UnlockSemaphoreInfo(splay_tree->semaphore);
734 DestroySemaphoreInfo(&splay_tree->semaphore);
735 splay_tree=(SplayTreeInfo *) RelinquishMagickMemory(splay_tree);
740 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
744 % G e t N e x t K e y I n S p l a y T r e e %
748 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
750 % GetNextKeyInSplayTree() gets the next key in the splay-tree.
752 % The format of the GetNextKeyInSplayTree method is:
754 % const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
756 % A description of each parameter follows:
758 % o splay_tree: the splay tree.
763 MagickExport const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
771 assert(splay_tree != (SplayTreeInfo *) NULL);
772 assert(splay_tree->signature == MagickSignature);
773 if (splay_tree->debug != MagickFalse)
774 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
775 if ((splay_tree->root == (NodeInfo *) NULL) ||
776 (splay_tree->next == (void *) NULL))
777 return((void *) NULL);
778 LockSemaphoreInfo(splay_tree->semaphore);
779 SplaySplayTree(splay_tree,splay_tree->next);
780 splay_tree->next=(void *) NULL;
781 node=splay_tree->root->right;
782 if (node != (NodeInfo *) NULL)
784 while (node->left != (NodeInfo *) NULL)
786 splay_tree->next=node->key;
788 key=splay_tree->root->key;
789 UnlockSemaphoreInfo(splay_tree->semaphore);
794 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
798 % G e t N e x t V a l u e I n S p l a y T r e e %
802 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
804 % GetNextValueInSplayTree() gets the next value in the splay-tree.
806 % The format of the GetNextValueInSplayTree method is:
808 % const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
810 % A description of each parameter follows:
812 % o splay_tree: the splay tree.
817 MagickExport const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
825 assert(splay_tree != (SplayTreeInfo *) NULL);
826 assert(splay_tree->signature == MagickSignature);
827 if (splay_tree->debug != MagickFalse)
828 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
829 if ((splay_tree->root == (NodeInfo *) NULL) ||
830 (splay_tree->next == (void *) NULL))
831 return((void *) NULL);
832 LockSemaphoreInfo(splay_tree->semaphore);
833 SplaySplayTree(splay_tree,splay_tree->next);
834 splay_tree->next=(void *) NULL;
835 node=splay_tree->root->right;
836 if (node != (NodeInfo *) NULL)
838 while (node->left != (NodeInfo *) NULL)
840 splay_tree->next=node->key;
842 value=splay_tree->root->value;
843 UnlockSemaphoreInfo(splay_tree->semaphore);
848 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
852 % G e t V a l u e F r o m S p l a y T r e e %
856 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
858 % GetValueFromSplayTree() gets a value from the splay-tree by its key.
860 % Note, the value is a constant. Do not attempt to free it.
862 % The format of the GetValueFromSplayTree method is:
864 % const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
867 % A description of each parameter follows:
869 % o splay_tree: the splay tree.
874 MagickExport const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
883 assert(splay_tree != (SplayTreeInfo *) NULL);
884 assert(splay_tree->signature == MagickSignature);
885 if (splay_tree->debug != MagickFalse)
886 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
887 if (splay_tree->root == (NodeInfo *) NULL)
888 return((void *) NULL);
889 LockSemaphoreInfo(splay_tree->semaphore);
890 SplaySplayTree(splay_tree,key);
891 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
892 compare=splay_tree->compare(splay_tree->root->key,key);
894 compare=(splay_tree->root->key > key) ? 1 :
895 ((splay_tree->root->key < key) ? -1 : 0);
898 UnlockSemaphoreInfo(splay_tree->semaphore);
899 return((void *) NULL);
901 value=splay_tree->root->value;
902 UnlockSemaphoreInfo(splay_tree->semaphore);
907 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
911 % 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 %
915 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
917 % GetNumberOfNodesInSplayTree() returns the number of nodes in the splay-tree.
919 % The format of the GetNumberOfNodesInSplayTree method is:
921 % size_t GetNumberOfNodesInSplayTree(
922 % const SplayTreeInfo *splay_tree)
924 % A description of each parameter follows:
926 % o splay_tree: the splay tree.
929 MagickExport size_t GetNumberOfNodesInSplayTree(
930 const SplayTreeInfo *splay_tree)
932 assert(splay_tree != (SplayTreeInfo *) NULL);
933 assert(splay_tree->signature == MagickSignature);
934 if (splay_tree->debug != MagickFalse)
935 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
936 return(splay_tree->nodes);
940 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
944 % I t e r a t e O v e r S p l a y T r e e %
948 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
950 % IterateOverSplayTree() iterates over the splay-tree.
952 % The format of the IterateOverSplayTree method is:
954 % int IterateOverSplayTree(SplayTreeInfo *splay_tree,
955 % int (*method)(NodeInfo *,void *),const void *value)
957 % A description of each parameter follows:
959 % o splay_tree: the splay-tree info.
961 % o method: the method.
963 % o value: the value.
966 static int IterateOverSplayTree(SplayTreeInfo *splay_tree,
967 int (*method)(NodeInfo *,const void *),const void *value)
998 if (splay_tree->root == (NodeInfo *) NULL)
1000 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
1002 transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes,
1003 sizeof(*transitions));
1004 if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL))
1005 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1007 final_transition=MagickFalse;
1008 nodes[0]=splay_tree->root;
1009 transitions[0]=(unsigned char) LeftTransition;
1010 for (i=0; final_transition == MagickFalse; )
1013 transition=(TransitionType) transitions[i];
1016 case LeftTransition:
1018 transitions[i]=(unsigned char) DownTransition;
1019 if (node->left == (NodeInfo *) NULL)
1022 nodes[i]=node->left;
1023 transitions[i]=(unsigned char) LeftTransition;
1026 case RightTransition:
1028 transitions[i]=(unsigned char) UpTransition;
1029 if (node->right == (NodeInfo *) NULL)
1032 nodes[i]=node->right;
1033 transitions[i]=(unsigned char) LeftTransition;
1036 case DownTransition:
1039 transitions[i]=(unsigned char) RightTransition;
1040 status=(*method)(node,value);
1042 final_transition=MagickTrue;
1049 final_transition=MagickTrue;
1057 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
1058 transitions=(unsigned char *) RelinquishMagickMemory(transitions);
1063 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1067 % N e w S p l a y T r e e %
1071 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1073 % NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized
1074 % to default values.
1076 % The format of the NewSplayTree method is:
1078 % SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *),
1079 % void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1081 % A description of each parameter follows:
1083 % o compare: the compare method.
1085 % o relinquish_key: the key deallocation method, typically
1086 % RelinquishMagickMemory(), called whenever a key is removed from the
1089 % o relinquish_value: the value deallocation method; typically
1090 % RelinquishMagickMemory(), called whenever a value object is removed from
1094 MagickExport SplayTreeInfo *NewSplayTree(
1095 int (*compare)(const void *,const void *),void *(*relinquish_key)(void *),
1096 void *(*relinquish_value)(void *))
1101 splay_tree=(SplayTreeInfo *) AcquireMagickMemory(sizeof(*splay_tree));
1102 if (splay_tree == (SplayTreeInfo *) NULL)
1103 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1104 (void) ResetMagickMemory(splay_tree,0,sizeof(*splay_tree));
1105 splay_tree->root=(NodeInfo *) NULL;
1106 splay_tree->compare=compare;
1107 splay_tree->relinquish_key=relinquish_key;
1108 splay_tree->relinquish_value=relinquish_value;
1109 splay_tree->balance=MagickFalse;
1110 splay_tree->key=(void *) NULL;
1111 splay_tree->next=(void *) NULL;
1112 splay_tree->nodes=0;
1113 splay_tree->debug=IsEventLogging();
1114 splay_tree->semaphore=AllocateSemaphoreInfo();
1115 splay_tree->signature=MagickSignature;
1120 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1124 % 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 %
1128 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1130 % RemoveNodeByValueFromSplayTree() removes a node by value from the splay-tree
1131 % and returns its key.
1133 % The format of the RemoveNodeByValueFromSplayTree method is:
1135 % void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1136 % const void *value)
1138 % A description of each parameter follows:
1140 % o splay_tree: the splay-tree info.
1142 % o value: the value.
1145 MagickExport void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1155 assert(splay_tree != (SplayTreeInfo *) NULL);
1156 assert(splay_tree->signature == MagickSignature);
1157 if (splay_tree->debug != MagickFalse)
1158 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1160 if (splay_tree->root == (NodeInfo *) NULL)
1162 LockSemaphoreInfo(splay_tree->semaphore);
1163 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
1164 while (next != (NodeInfo *) NULL)
1166 SplaySplayTree(splay_tree,next);
1167 next=(NodeInfo *) NULL;
1168 node=splay_tree->root->right;
1169 if (node != (NodeInfo *) NULL)
1171 while (node->left != (NodeInfo *) NULL)
1173 next=(NodeInfo *) node->key;
1175 if (splay_tree->root->value == value)
1185 We found the node that matches the value; now remove it.
1187 key=splay_tree->root->key;
1188 SplaySplayTree(splay_tree,key);
1189 splay_tree->key=(void *) NULL;
1190 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1191 compare=splay_tree->compare(splay_tree->root->key,key);
1193 compare=(splay_tree->root->key > key) ? 1 :
1194 ((splay_tree->root->key < key) ? -1 : 0);
1197 UnlockSemaphoreInfo(splay_tree->semaphore);
1200 left=splay_tree->root->left;
1201 right=splay_tree->root->right;
1202 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1203 (splay_tree->root->value != (void *) NULL))
1204 splay_tree->root->value=splay_tree->relinquish_value(
1205 splay_tree->root->value);
1206 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1207 splay_tree->nodes--;
1208 if (left == (NodeInfo *) NULL)
1210 splay_tree->root=right;
1211 UnlockSemaphoreInfo(splay_tree->semaphore);
1214 splay_tree->root=left;
1215 if (right != (NodeInfo *) NULL)
1217 while (left->right != (NodeInfo *) NULL)
1221 UnlockSemaphoreInfo(splay_tree->semaphore);
1225 UnlockSemaphoreInfo(splay_tree->semaphore);
1230 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1234 % R e m o v e N o d e F r o m S p l a y T r e e %
1238 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1240 % RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its
1243 % The format of the RemoveNodeFromSplayTree method is:
1245 % void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key)
1247 % A description of each parameter follows:
1249 % o splay_tree: the splay-tree info.
1254 MagickExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,
1267 assert(splay_tree != (SplayTreeInfo *) NULL);
1268 assert(splay_tree->signature == MagickSignature);
1269 if (splay_tree->debug != MagickFalse)
1270 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1271 value=(void *) NULL;
1272 if (splay_tree->root == (NodeInfo *) NULL)
1274 LockSemaphoreInfo(splay_tree->semaphore);
1275 SplaySplayTree(splay_tree,key);
1276 splay_tree->key=(void *) NULL;
1277 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1278 compare=splay_tree->compare(splay_tree->root->key,key);
1280 compare=(splay_tree->root->key > key) ? 1 :
1281 ((splay_tree->root->key < key) ? -1 : 0);
1284 UnlockSemaphoreInfo(splay_tree->semaphore);
1287 left=splay_tree->root->left;
1288 right=splay_tree->root->right;
1289 value=splay_tree->root->value;
1290 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1291 (splay_tree->root->key != (void *) NULL))
1292 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1293 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1294 splay_tree->nodes--;
1295 if (left == (NodeInfo *) NULL)
1297 splay_tree->root=right;
1298 UnlockSemaphoreInfo(splay_tree->semaphore);
1301 splay_tree->root=left;
1302 if (right != (NodeInfo *) NULL)
1304 while (left->right != (NodeInfo *) NULL)
1308 UnlockSemaphoreInfo(splay_tree->semaphore);
1313 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1317 % R e s e t S p l a y T r e e %
1321 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1323 % ResetSplayTree() resets the splay-tree. That is, it deletes all the nodes
1326 % The format of the ResetSplayTree method is:
1328 % ResetSplayTree(SplayTreeInfo *splay_tree)
1330 % A description of each parameter follows:
1332 % o splay_tree: the splay tree.
1335 MagickExport void ResetSplayTree(SplayTreeInfo *splay_tree)
1344 assert(splay_tree != (SplayTreeInfo *) NULL);
1345 assert(splay_tree->signature == MagickSignature);
1346 if (splay_tree->debug != MagickFalse)
1347 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1348 LockSemaphoreInfo(splay_tree->semaphore);
1349 if (splay_tree->root != (NodeInfo *) NULL)
1351 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1352 (splay_tree->root->value != (void *) NULL))
1353 splay_tree->root->value=splay_tree->relinquish_value(
1354 splay_tree->root->value);
1355 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1356 (splay_tree->root->key != (void *) NULL))
1357 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1358 splay_tree->root->key=(void *) NULL;
1359 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
1362 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
1364 if (active->left != (NodeInfo *) NULL)
1366 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1367 (active->left->value != (void *) NULL))
1368 active->left->value=splay_tree->relinquish_value(
1369 active->left->value);
1370 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1371 (active->left->key != (void *) NULL))
1372 active->left->key=splay_tree->relinquish_key(active->left->key);
1373 active->left->key=(void *) pend;
1376 if (active->right != (NodeInfo *) NULL)
1378 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1379 (active->right->value != (void *) NULL))
1380 active->right->value=splay_tree->relinquish_value(
1381 active->right->value);
1382 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1383 (active->right->key != (void *) NULL))
1384 active->right->key=splay_tree->relinquish_key(
1385 active->right->key);
1386 active->right->key=(void *) pend;
1390 active=(NodeInfo *) node->key;
1391 node=(NodeInfo *) RelinquishMagickMemory(node);
1395 splay_tree->root=(NodeInfo *) NULL;
1396 splay_tree->key=(void *) NULL;
1397 splay_tree->next=(void *) NULL;
1398 splay_tree->nodes=0;
1399 splay_tree->balance=MagickFalse;
1400 UnlockSemaphoreInfo(splay_tree->semaphore);
1404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1408 % R e s e t S p l a y T r e e I t e r a t o r %
1412 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1414 % ResetSplayTreeIterator() resets the splay-tree iterator. Use it in
1415 % conjunction with GetNextValueInSplayTree() to iterate over all the nodes in
1418 % The format of the ResetSplayTreeIterator method is:
1420 % ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1422 % A description of each parameter follows:
1424 % o splay_tree: the splay tree.
1427 MagickExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1429 assert(splay_tree != (SplayTreeInfo *) NULL);
1430 assert(splay_tree->signature == MagickSignature);
1431 if (splay_tree->debug != MagickFalse)
1432 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1433 LockSemaphoreInfo(splay_tree->semaphore);
1434 splay_tree->next=GetFirstSplayTreeNode(splay_tree);
1435 UnlockSemaphoreInfo(splay_tree->semaphore);
1439 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1443 % S p l a y S p l a y T r e e %
1447 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1449 % SplaySplayTree() splays the splay-tree.
1451 % The format of the SplaySplayTree method is:
1453 % void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key,
1454 % NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1456 % A description of each parameter follows:
1458 % o splay_tree: the splay-tree info.
1464 % o parent: the parent node.
1466 % o grandparent: the grandparent node.
1470 static NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth,
1471 const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1484 if (n == (NodeInfo *) NULL)
1486 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1487 compare=splay_tree->compare(n->key,key);
1489 compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
1490 next=(NodeInfo **) NULL;
1496 if (next != (NodeInfo **) NULL)
1498 if (depth >= MaxSplayTreeDepth)
1500 splay_tree->balance=MagickTrue;
1503 n=Splay(splay_tree,depth+1,key,next,node,parent);
1504 if ((n != *node) || (splay_tree->balance != MagickFalse))
1507 if (parent == (NodeInfo **) NULL)
1509 if (grandparent == (NodeInfo **) NULL)
1511 if (n == (*parent)->left)
1524 if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
1527 (*grandparent)->left=p->right;
1528 p->right=(*grandparent);
1534 if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
1537 (*grandparent)->right=p->left;
1538 p->left=(*grandparent);
1544 if (n == (*parent)->left)
1546 (*parent)->left=n->right;
1548 (*grandparent)->right=n->left;
1549 n->left=(*grandparent);
1553 (*parent)->right=n->left;
1555 (*grandparent)->left=n->right;
1556 n->right=(*grandparent);
1561 static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key)
1563 if (splay_tree->root == (NodeInfo *) NULL)
1565 if (splay_tree->key != (void *) NULL)
1570 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1571 compare=splay_tree->compare(splay_tree->root->key,key);
1573 compare=(splay_tree->key > key) ? 1 :
1574 ((splay_tree->key < key) ? -1 : 0);
1578 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1579 (NodeInfo **) NULL);
1580 if (splay_tree->balance != MagickFalse)
1582 BalanceSplayTree(splay_tree);
1583 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1584 (NodeInfo **) NULL);
1585 if (splay_tree->balance != MagickFalse)
1586 ThrowFatalException(ResourceLimitFatalError,
1587 "MemoryAllocationFailed");
1589 splay_tree->key=(void *) key;