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-2010 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 "magick/studio.h"
52 #include "magick/exception.h"
53 #include "magick/exception-private.h"
54 #include "magick/log.h"
55 #include "magick/memory_.h"
56 #include "magick/splay-tree.h"
57 #include "magick/semaphore.h"
58 #include "magick/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_key != (void *(*)(void *)) NULL) &&
172 (splay_tree->root->key != (void *) NULL))
173 splay_tree->root->key=splay_tree->relinquish_key(
174 splay_tree->root->key);
175 splay_tree->root->key=(void *) key;
176 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
177 (splay_tree->root->value != (void *) NULL))
178 splay_tree->root->value=splay_tree->relinquish_value(
179 splay_tree->root->value);
180 splay_tree->root->value=(void *) value;
181 UnlockSemaphoreInfo(splay_tree->semaphore);
185 node=(NodeInfo *) AcquireAlignedMemory(1,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 unsigned long low,
244 const unsigned long high)
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_key != (void *(*)(void *)) NULL) &&
542 (splay_tree->root->key != (void *) NULL))
543 splay_tree->root->key=splay_tree->relinquish_key(
544 splay_tree->root->key);
545 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
546 (splay_tree->root->value != (void *) NULL))
547 splay_tree->root->value=splay_tree->relinquish_value(
548 splay_tree->root->value);
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_key != (void *(*)(void *)) NULL) &&
689 (splay_tree->root->key != (void *) NULL))
690 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
691 splay_tree->root->key=(void *) NULL;
692 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
693 (splay_tree->root->value != (void *) NULL))
694 splay_tree->root->value=splay_tree->relinquish_value(
695 splay_tree->root->value);
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_key != (void *(*)(void *)) NULL) &&
704 (active->left->key != (void *) NULL))
705 active->left->key=splay_tree->relinquish_key(active->left->key);
706 active->left->key=(void *) pend;
707 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
708 (active->left->value != (void *) NULL))
709 active->left->value=splay_tree->relinquish_value(
710 active->left->value);
713 if (active->right != (NodeInfo *) NULL)
715 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
716 (active->right->key != (void *) NULL))
717 active->right->key=splay_tree->relinquish_key(
719 active->right->key=(void *) pend;
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);
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 % void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
756 % A description of each parameter follows:
758 % o splay_tree: the splay tree.
763 MagickExport 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 % void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
810 % A description of each parameter follows:
812 % o splay_tree: the splay tree.
817 MagickExport 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 % The format of the GetValueFromSplayTree method is:
862 % void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,const void *key)
864 % A description of each parameter follows:
866 % o splay_tree: the splay tree.
871 MagickExport void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
880 assert(splay_tree != (SplayTreeInfo *) NULL);
881 assert(splay_tree->signature == MagickSignature);
882 if (splay_tree->debug != MagickFalse)
883 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
884 if (splay_tree->root == (NodeInfo *) NULL)
885 return((void *) NULL);
886 LockSemaphoreInfo(splay_tree->semaphore);
887 SplaySplayTree(splay_tree,key);
888 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
889 compare=splay_tree->compare(splay_tree->root->key,key);
891 compare=(splay_tree->root->key > key) ? 1 :
892 ((splay_tree->root->key < key) ? -1 : 0);
895 UnlockSemaphoreInfo(splay_tree->semaphore);
896 return((void *) NULL);
898 value=splay_tree->root->value;
899 UnlockSemaphoreInfo(splay_tree->semaphore);
904 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
908 % 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 %
912 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
914 % GetNumberOfNodesInSplayTree() returns the number of nodes in the splay-tree.
916 % The format of the GetNumberOfNodesInSplayTree method is:
918 % unsigned long GetNumberOfNodesInSplayTree(
919 % const SplayTreeInfo *splay_tree)
921 % A description of each parameter follows:
923 % o splay_tree: the splay tree.
926 MagickExport unsigned long GetNumberOfNodesInSplayTree(
927 const SplayTreeInfo *splay_tree)
929 assert(splay_tree != (SplayTreeInfo *) NULL);
930 assert(splay_tree->signature == MagickSignature);
931 if (splay_tree->debug != MagickFalse)
932 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
933 return(splay_tree->nodes);
937 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
941 % I t e r a t e O v e r S p l a y T r e e %
945 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
947 % IterateOverSplayTree() iterates over the splay-tree.
949 % The format of the IterateOverSplayTree method is:
951 % int IterateOverSplayTree(SplayTreeInfo *splay_tree,
952 % int (*method)(NodeInfo *,void *),const void *value)
954 % A description of each parameter follows:
956 % o splay_tree: the splay-tree info.
958 % o method: the method.
960 % o value: the value.
963 static int IterateOverSplayTree(SplayTreeInfo *splay_tree,
964 int (*method)(NodeInfo *,const void *),const void *value)
995 if (splay_tree->root == (NodeInfo *) NULL)
997 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
999 transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes,
1000 sizeof(*transitions));
1001 if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL))
1002 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1004 final_transition=MagickFalse;
1005 nodes[0]=splay_tree->root;
1006 transitions[0]=(unsigned char) LeftTransition;
1007 for (i=0; final_transition == MagickFalse; )
1010 transition=(TransitionType) transitions[i];
1013 case LeftTransition:
1015 transitions[i]=(unsigned char) DownTransition;
1016 if (node->left == (NodeInfo *) NULL)
1019 nodes[i]=node->left;
1020 transitions[i]=(unsigned char) LeftTransition;
1023 case RightTransition:
1025 transitions[i]=(unsigned char) UpTransition;
1026 if (node->right == (NodeInfo *) NULL)
1029 nodes[i]=node->right;
1030 transitions[i]=(unsigned char) LeftTransition;
1033 case DownTransition:
1036 transitions[i]=(unsigned char) RightTransition;
1037 status=(*method)(node,value);
1039 final_transition=MagickTrue;
1046 final_transition=MagickTrue;
1054 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
1055 transitions=(unsigned char *) RelinquishMagickMemory(transitions);
1060 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1064 % N e w S p l a y T r e e %
1068 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1070 % NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized
1071 % to default values.
1073 % The format of the NewSplayTree method is:
1075 % SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *),
1076 % void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1078 % A description of each parameter follows:
1080 % o compare: the compare method.
1082 % o relinquish_key: the key deallocation method, typically
1083 % RelinquishMagickMemory(), called whenever a key is removed from the
1086 % o relinquish_value: the value deallocation method; typically
1087 % RelinquishMagickMemory(), called whenever a value object is removed from
1091 MagickExport SplayTreeInfo *NewSplayTree(
1092 int (*compare)(const void *,const void *),void *(*relinquish_key)(void *),
1093 void *(*relinquish_value)(void *))
1098 splay_tree=(SplayTreeInfo *) AcquireAlignedMemory(1,sizeof(*splay_tree));
1099 if (splay_tree == (SplayTreeInfo *) NULL)
1100 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1101 (void) ResetMagickMemory(splay_tree,0,sizeof(*splay_tree));
1102 splay_tree->root=(NodeInfo *) NULL;
1103 splay_tree->compare=compare;
1104 splay_tree->relinquish_key=relinquish_key;
1105 splay_tree->relinquish_value=relinquish_value;
1106 splay_tree->balance=MagickFalse;
1107 splay_tree->key=(void *) NULL;
1108 splay_tree->next=(void *) NULL;
1109 splay_tree->nodes=0;
1110 splay_tree->debug=IsEventLogging();
1111 splay_tree->semaphore=AllocateSemaphoreInfo();
1112 splay_tree->signature=MagickSignature;
1117 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1121 % 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 %
1125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1127 % RemoveNodeByValueFromSplayTree() removes a node by value from the splay-tree
1128 % and returns its key.
1130 % The format of the RemoveNodeByValueFromSplayTree method is:
1132 % void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1133 % const void *value)
1135 % A description of each parameter follows:
1137 % o splay_tree: the splay-tree info.
1139 % o value: the value.
1142 MagickExport void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1152 assert(splay_tree != (SplayTreeInfo *) NULL);
1153 assert(splay_tree->signature == MagickSignature);
1154 if (splay_tree->debug != MagickFalse)
1155 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1157 if (splay_tree->root == (NodeInfo *) NULL)
1159 LockSemaphoreInfo(splay_tree->semaphore);
1160 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
1161 while (next != (NodeInfo *) NULL)
1163 SplaySplayTree(splay_tree,next);
1164 next=(NodeInfo *) NULL;
1165 node=splay_tree->root->right;
1166 if (node != (NodeInfo *) NULL)
1168 while (node->left != (NodeInfo *) NULL)
1170 next=(NodeInfo *) node->key;
1172 if (splay_tree->root->value == value)
1182 We found the node that matches the value; now remove it.
1184 key=splay_tree->root->key;
1185 SplaySplayTree(splay_tree,key);
1186 splay_tree->key=(void *) NULL;
1187 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1188 compare=splay_tree->compare(splay_tree->root->key,key);
1190 compare=(splay_tree->root->key > key) ? 1 :
1191 ((splay_tree->root->key < key) ? -1 : 0);
1194 UnlockSemaphoreInfo(splay_tree->semaphore);
1197 left=splay_tree->root->left;
1198 right=splay_tree->root->right;
1199 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1200 (splay_tree->root->value != (void *) NULL))
1201 splay_tree->root->value=splay_tree->relinquish_value(
1202 splay_tree->root->value);
1203 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1204 splay_tree->nodes--;
1205 if (left == (NodeInfo *) NULL)
1207 splay_tree->root=right;
1208 UnlockSemaphoreInfo(splay_tree->semaphore);
1211 splay_tree->root=left;
1212 if (right != (NodeInfo *) NULL)
1214 while (left->right != (NodeInfo *) NULL)
1218 UnlockSemaphoreInfo(splay_tree->semaphore);
1222 UnlockSemaphoreInfo(splay_tree->semaphore);
1227 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1231 % R e m o v e N o d e F r o m S p l a y T r e e %
1235 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1237 % RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its
1240 % The format of the RemoveNodeFromSplayTree method is:
1242 % void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key)
1244 % A description of each parameter follows:
1246 % o splay_tree: the splay-tree info.
1251 MagickExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,
1264 assert(splay_tree != (SplayTreeInfo *) NULL);
1265 assert(splay_tree->signature == MagickSignature);
1266 if (splay_tree->debug != MagickFalse)
1267 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1268 value=(void *) NULL;
1269 if (splay_tree->root == (NodeInfo *) NULL)
1271 LockSemaphoreInfo(splay_tree->semaphore);
1272 SplaySplayTree(splay_tree,key);
1273 splay_tree->key=(void *) NULL;
1274 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1275 compare=splay_tree->compare(splay_tree->root->key,key);
1277 compare=(splay_tree->root->key > key) ? 1 :
1278 ((splay_tree->root->key < key) ? -1 : 0);
1281 UnlockSemaphoreInfo(splay_tree->semaphore);
1284 left=splay_tree->root->left;
1285 right=splay_tree->root->right;
1286 value=splay_tree->root->value;
1287 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1288 (splay_tree->root->key != (void *) NULL))
1289 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1290 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1291 splay_tree->nodes--;
1292 if (left == (NodeInfo *) NULL)
1294 splay_tree->root=right;
1295 UnlockSemaphoreInfo(splay_tree->semaphore);
1298 splay_tree->root=left;
1299 if (right != (NodeInfo *) NULL)
1301 while (left->right != (NodeInfo *) NULL)
1305 UnlockSemaphoreInfo(splay_tree->semaphore);
1310 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1314 % R e s e t S p l a y T r e e %
1318 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1320 % ResetSplayTree() resets the splay-tree. That is, it deletes all the nodes
1323 % The format of the ResetSplayTree method is:
1325 % ResetSplayTree(SplayTreeInfo *splay_tree)
1327 % A description of each parameter follows:
1329 % o splay_tree: the splay tree.
1332 MagickExport void ResetSplayTree(SplayTreeInfo *splay_tree)
1341 assert(splay_tree != (SplayTreeInfo *) NULL);
1342 assert(splay_tree->signature == MagickSignature);
1343 if (splay_tree->debug != MagickFalse)
1344 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1345 LockSemaphoreInfo(splay_tree->semaphore);
1346 if (splay_tree->root != (NodeInfo *) NULL)
1348 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1349 (splay_tree->root->key != (void *) NULL))
1350 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1351 splay_tree->root->key=(void *) NULL;
1352 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1353 (splay_tree->root->value != (void *) NULL))
1354 splay_tree->root->value=splay_tree->relinquish_value(
1355 splay_tree->root->value);
1356 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
1359 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
1361 if (active->left != (NodeInfo *) NULL)
1363 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1364 (active->left->key != (void *) NULL))
1365 active->left->key=splay_tree->relinquish_key(active->left->key);
1366 active->left->key=(void *) pend;
1367 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1368 (active->left->value != (void *) NULL))
1369 active->left->value=splay_tree->relinquish_value(
1370 active->left->value);
1373 if (active->right != (NodeInfo *) NULL)
1375 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1376 (active->right->key != (void *) NULL))
1377 active->right->key=splay_tree->relinquish_key(
1378 active->right->key);
1379 active->right->key=(void *) pend;
1380 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1381 (active->right->value != (void *) NULL))
1382 active->right->value=splay_tree->relinquish_value(
1383 active->right->value);
1387 active=(NodeInfo *) node->key;
1388 node=(NodeInfo *) RelinquishMagickMemory(node);
1392 splay_tree->root=(NodeInfo *) NULL;
1393 splay_tree->key=(void *) NULL;
1394 splay_tree->next=(void *) NULL;
1395 splay_tree->nodes=0;
1396 splay_tree->balance=MagickFalse;
1397 UnlockSemaphoreInfo(splay_tree->semaphore);
1401 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1405 % R e s e t S p l a y T r e e I t e r a t o r %
1409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1411 % ResetSplayTreeIterator() resets the splay-tree iterator. Use it in
1412 % conjunction with GetNextValueInSplayTree() to iterate over all the nodes in
1415 % The format of the ResetSplayTreeIterator method is:
1417 % ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1419 % A description of each parameter follows:
1421 % o splay_tree: the splay tree.
1424 MagickExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1426 assert(splay_tree != (SplayTreeInfo *) NULL);
1427 assert(splay_tree->signature == MagickSignature);
1428 if (splay_tree->debug != MagickFalse)
1429 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1430 LockSemaphoreInfo(splay_tree->semaphore);
1431 splay_tree->next=GetFirstSplayTreeNode(splay_tree);
1432 UnlockSemaphoreInfo(splay_tree->semaphore);
1436 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1440 % S p l a y S p l a y T r e e %
1444 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1446 % SplaySplayTree() splays the splay-tree.
1448 % The format of the SplaySplayTree method is:
1450 % void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key,
1451 % NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1453 % A description of each parameter follows:
1455 % o splay_tree: the splay-tree info.
1461 % o parent: the parent node.
1463 % o grandparent: the grandparent node.
1467 static NodeInfo *Splay(SplayTreeInfo *splay_tree,const unsigned long depth,
1468 const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1481 if (n == (NodeInfo *) NULL)
1483 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1484 compare=splay_tree->compare(n->key,key);
1486 compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
1487 next=(NodeInfo **) NULL;
1493 if (next != (NodeInfo **) NULL)
1495 if (depth >= MaxSplayTreeDepth)
1497 splay_tree->balance=MagickTrue;
1500 n=Splay(splay_tree,depth+1,key,next,node,parent);
1501 if ((n != *node) || (splay_tree->balance != MagickFalse))
1504 if (parent == (NodeInfo **) NULL)
1506 if (grandparent == (NodeInfo **) NULL)
1508 if (n == (*parent)->left)
1521 if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
1524 (*grandparent)->left=p->right;
1525 p->right=(*grandparent);
1531 if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
1534 (*grandparent)->right=p->left;
1535 p->left=(*grandparent);
1541 if (n == (*parent)->left)
1543 (*parent)->left=n->right;
1545 (*grandparent)->right=n->left;
1546 n->left=(*grandparent);
1550 (*parent)->right=n->left;
1552 (*grandparent)->left=n->right;
1553 n->right=(*grandparent);
1558 static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key)
1560 if (splay_tree->root == (NodeInfo *) NULL)
1562 if (splay_tree->key != (void *) NULL)
1567 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1568 compare=splay_tree->compare(splay_tree->root->key,key);
1570 compare=(splay_tree->key > key) ? 1 :
1571 ((splay_tree->key < key) ? -1 : 0);
1575 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1576 (NodeInfo **) NULL);
1577 if (splay_tree->balance != MagickFalse)
1579 BalanceSplayTree(splay_tree);
1580 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1581 (NodeInfo **) NULL);
1582 if (splay_tree->balance != MagickFalse)
1583 ThrowFatalException(ResourceLimitFatalError,
1584 "MemoryAllocationFailed");
1586 splay_tree->key=(void *) key;