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-2014 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 the given key and value to the splay-tree. Both
135 % key and value are used as is, without coping or cloning. It returns
136 % MagickTrue on success, otherwise MagickFalse.
138 % The format of the AddValueToSplayTree method is:
140 % MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
141 % const void *key,const void *value)
143 % A description of each parameter follows:
145 % o splay_tree: the splay-tree info.
149 % o value: the value.
152 MagickExport MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
153 const void *key,const void *value)
161 LockSemaphoreInfo(splay_tree->semaphore);
162 SplaySplayTree(splay_tree,key);
164 if (splay_tree->root != (NodeInfo *) NULL)
166 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
167 compare=splay_tree->compare(splay_tree->root->key,key);
169 compare=(splay_tree->root->key > key) ? 1 :
170 ((splay_tree->root->key < key) ? -1 : 0);
173 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
174 (splay_tree->root->value != (void *) NULL))
175 splay_tree->root->value=splay_tree->relinquish_value(
176 splay_tree->root->value);
177 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
178 (splay_tree->root->key != (void *) NULL))
179 splay_tree->root->key=splay_tree->relinquish_key(
180 splay_tree->root->key);
181 splay_tree->root->key=(void *) key;
182 splay_tree->root->value=(void *) value;
183 UnlockSemaphoreInfo(splay_tree->semaphore);
187 node=(NodeInfo *) AcquireMagickMemory(sizeof(*node));
188 if (node == (NodeInfo *) NULL)
190 UnlockSemaphoreInfo(splay_tree->semaphore);
193 node->key=(void *) key;
194 node->value=(void *) value;
195 if (splay_tree->root == (NodeInfo *) NULL)
197 node->left=(NodeInfo *) NULL;
198 node->right=(NodeInfo *) NULL;
203 node->left=splay_tree->root;
204 node->right=node->left->right;
205 node->left->right=(NodeInfo *) NULL;
209 node->right=splay_tree->root;
210 node->left=node->right->left;
211 node->right->left=(NodeInfo *) NULL;
213 splay_tree->root=node;
214 splay_tree->key=(void *) NULL;
216 UnlockSemaphoreInfo(splay_tree->semaphore);
221 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
225 % B a l a n c e S p l a y T r e e %
229 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
231 % BalanceSplayTree() balances the splay-tree.
233 % The format of the BalanceSplayTree method is:
235 % void *BalanceSplayTree(SplayTreeInfo *splay_tree,const void *key)
237 % A description of each parameter follows:
239 % o splay_tree: the splay-tree info.
245 static inline NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const size_t low,
254 bisect=low+(high-low)/2;
256 if ((low+1) > bisect)
257 node->left=(NodeInfo *) NULL;
259 node->left=LinkSplayTreeNodes(nodes,low,bisect-1);
260 if ((bisect+1) > high)
261 node->right=(NodeInfo *) NULL;
263 node->right=LinkSplayTreeNodes(nodes,bisect+1,high);
267 static inline int SplayTreeToNodeArray(NodeInfo *node,const void *nodes)
269 register const NodeInfo
272 p=(const NodeInfo ***) nodes;
278 static void BalanceSplayTree(SplayTreeInfo *splay_tree)
284 if (splay_tree->nodes <= 2)
286 splay_tree->balance=MagickFalse;
289 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
291 if (nodes == (NodeInfo **) NULL)
292 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
294 (void) IterateOverSplayTree(splay_tree,SplayTreeToNodeArray,(const void *)
296 splay_tree->root=LinkSplayTreeNodes(nodes,0,splay_tree->nodes-1);
297 splay_tree->balance=MagickFalse;
298 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
302 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
306 % C l o n e S p l a y T r e e %
310 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
312 % CloneSplayTree() clones the splay tree.
314 % The format of the CloneSplayTree method is:
316 % SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
317 % void *(*clone_key)(void *),void *(*cline_value)(void *))
319 % A description of each parameter follows:
321 % o splay_tree: the splay tree.
323 % o clone_key: the key clone method, typically ConstantString(), called
324 % whenever a key is added to the splay-tree.
326 % o clone_value: the value clone method; typically ConstantString(), called
327 % whenever a value object is added to the splay-tree.
331 static inline void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree)
336 node=splay_tree->root;
337 if (splay_tree->root == (NodeInfo *) NULL)
338 return((NodeInfo *) NULL);
339 while (node->left != (NodeInfo *) NULL)
344 MagickExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
345 void *(*clone_key)(void *),void *(*clone_value)(void *))
354 assert(splay_tree != (SplayTreeInfo *) NULL);
355 assert(splay_tree->signature == MagickSignature);
356 if (splay_tree->debug != MagickFalse)
357 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
358 clone_tree=NewSplayTree(splay_tree->compare,splay_tree->relinquish_key,
359 splay_tree->relinquish_value);
360 LockSemaphoreInfo(splay_tree->semaphore);
361 if (splay_tree->root == (NodeInfo *) NULL)
363 UnlockSemaphoreInfo(splay_tree->semaphore);
366 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
367 while (next != (NodeInfo *) NULL)
369 SplaySplayTree(splay_tree,next);
370 (void) AddValueToSplayTree(clone_tree,clone_key(splay_tree->root->key),
371 clone_value(splay_tree->root->value));
372 next=(NodeInfo *) NULL;
373 node=splay_tree->root->right;
374 if (node != (NodeInfo *) NULL)
376 while (node->left != (NodeInfo *) NULL)
378 next=(NodeInfo *) node->key;
381 UnlockSemaphoreInfo(splay_tree->semaphore);
386 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
390 % C o m p a r e S p l a y T r e e S t r i n g %
394 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
396 % CompareSplayTreeString() method finds a node in a splay-tree based on the
397 % contents of a string.
399 % The format of the CompareSplayTreeString method is:
401 % int CompareSplayTreeString(const void *target,const void *source)
403 % A description of each parameter follows:
405 % o target: the target string.
407 % o source: the source string.
410 MagickExport int CompareSplayTreeString(const void *target,const void *source)
416 p=(const char *) target;
417 q=(const char *) source;
418 return(LocaleCompare(p,q));
422 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
426 % 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 %
430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
432 % CompareSplayTreeStringInfo() finds a node in a splay-tree based on the
433 % contents of a string.
435 % The format of the CompareSplayTreeStringInfo method is:
437 % int CompareSplayTreeStringInfo(const void *target,const void *source)
439 % A description of each parameter follows:
441 % o target: the target string.
443 % o source: the source string.
446 MagickExport int CompareSplayTreeStringInfo(const void *target,
453 p=(const StringInfo *) target;
454 q=(const StringInfo *) source;
455 return(CompareStringInfo(p,q));
459 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
463 % 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 %
467 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
469 % DeleteNodeByValueFromSplayTree() deletes a node by value from the
472 % The format of the DeleteNodeByValueFromSplayTree method is:
474 % MagickBooleanType DeleteNodeByValueFromSplayTree(
475 % SplayTreeInfo *splay_tree,const void *value)
477 % A description of each parameter follows:
479 % o splay_tree: the splay-tree info.
481 % o value: the value.
484 MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree(
485 SplayTreeInfo *splay_tree,const void *value)
491 assert(splay_tree != (SplayTreeInfo *) NULL);
492 assert(splay_tree->signature == MagickSignature);
493 if (splay_tree->debug != MagickFalse)
494 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
495 LockSemaphoreInfo(splay_tree->semaphore);
496 if (splay_tree->root == (NodeInfo *) NULL)
498 UnlockSemaphoreInfo(splay_tree->semaphore);
501 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
502 while (next != (NodeInfo *) NULL)
504 SplaySplayTree(splay_tree,next);
505 next=(NodeInfo *) NULL;
506 node=splay_tree->root->right;
507 if (node != (NodeInfo *) NULL)
509 while (node->left != (NodeInfo *) NULL)
511 next=(NodeInfo *) node->key;
513 if (splay_tree->root->value == value)
526 We found the node that matches the value; now delete it.
528 key=splay_tree->root->key;
529 SplaySplayTree(splay_tree,key);
530 splay_tree->key=(void *) NULL;
531 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
532 compare=splay_tree->compare(splay_tree->root->key,key);
534 compare=(splay_tree->root->key > key) ? 1 :
535 ((splay_tree->root->key < key) ? -1 : 0);
538 UnlockSemaphoreInfo(splay_tree->semaphore);
541 left=splay_tree->root->left;
542 right=splay_tree->root->right;
543 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
544 (splay_tree->root->value != (void *) NULL))
545 splay_tree->root->value=splay_tree->relinquish_value(
546 splay_tree->root->value);
547 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
548 (splay_tree->root->key != (void *) NULL))
549 splay_tree->root->key=splay_tree->relinquish_key(
550 splay_tree->root->key);
551 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
553 if (left == (NodeInfo *) NULL)
555 splay_tree->root=right;
556 UnlockSemaphoreInfo(splay_tree->semaphore);
559 splay_tree->root=left;
560 if (right != (NodeInfo *) NULL)
562 while (left->right != (NodeInfo *) NULL)
566 UnlockSemaphoreInfo(splay_tree->semaphore);
570 UnlockSemaphoreInfo(splay_tree->semaphore);
575 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
579 % D e l e t e N o d e F r o m S p l a y T r e e %
583 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
585 % DeleteNodeFromSplayTree() deletes a node from the splay-tree. It returns
586 % MagickTrue if the option is found and successfully deleted from the
589 % The format of the DeleteNodeFromSplayTree method is:
591 % MagickBooleanType DeleteNodeFromSplayTree(SplayTreeInfo *splay_tree,
594 % A description of each parameter follows:
596 % o splay_tree: the splay-tree info.
601 MagickExport MagickBooleanType DeleteNodeFromSplayTree(
602 SplayTreeInfo *splay_tree,const void *key)
611 assert(splay_tree != (SplayTreeInfo *) NULL);
612 assert(splay_tree->signature == MagickSignature);
613 if (splay_tree->debug != MagickFalse)
614 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
615 if (splay_tree->root == (NodeInfo *) NULL)
617 LockSemaphoreInfo(splay_tree->semaphore);
618 SplaySplayTree(splay_tree,key);
619 splay_tree->key=(void *) NULL;
620 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
621 compare=splay_tree->compare(splay_tree->root->key,key);
623 compare=(splay_tree->root->key > key) ? 1 :
624 ((splay_tree->root->key < key) ? -1 : 0);
627 UnlockSemaphoreInfo(splay_tree->semaphore);
630 left=splay_tree->root->left;
631 right=splay_tree->root->right;
632 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
633 (splay_tree->root->value != (void *) NULL))
634 splay_tree->root->value=splay_tree->relinquish_value(
635 splay_tree->root->value);
636 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
637 (splay_tree->root->key != (void *) NULL))
638 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
639 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
641 if (left == (NodeInfo *) NULL)
643 splay_tree->root=right;
644 UnlockSemaphoreInfo(splay_tree->semaphore);
647 splay_tree->root=left;
648 if (right != (NodeInfo *) NULL)
650 while (left->right != (NodeInfo *) NULL)
654 UnlockSemaphoreInfo(splay_tree->semaphore);
659 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
663 % D e s t r o y S p l a y T r e e %
667 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
669 % DestroySplayTree() destroys the splay-tree.
671 % The format of the DestroySplayTree method is:
673 % SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
675 % A description of each parameter follows:
677 % o splay_tree: the splay tree.
680 MagickExport SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
689 LockSemaphoreInfo(splay_tree->semaphore);
690 if (splay_tree->root != (NodeInfo *) 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 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
697 (splay_tree->root->key != (void *) NULL))
698 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
699 splay_tree->root->key=(void *) NULL;
700 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
703 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
705 if (active->left != (NodeInfo *) NULL)
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);
711 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
712 (active->left->key != (void *) NULL))
713 active->left->key=splay_tree->relinquish_key(active->left->key);
714 active->left->key=(void *) pend;
717 if (active->right != (NodeInfo *) NULL)
719 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
720 (active->right->value != (void *) NULL))
721 active->right->value=splay_tree->relinquish_value(
722 active->right->value);
723 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
724 (active->right->key != (void *) NULL))
725 active->right->key=splay_tree->relinquish_key(
727 active->right->key=(void *) pend;
731 active=(NodeInfo *) node->key;
732 node=(NodeInfo *) RelinquishMagickMemory(node);
736 splay_tree->signature=(~MagickSignature);
737 UnlockSemaphoreInfo(splay_tree->semaphore);
738 RelinquishSemaphoreInfo(&splay_tree->semaphore);
739 splay_tree=(SplayTreeInfo *) RelinquishMagickMemory(splay_tree);
744 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
748 % G e t N e x t K e y I n S p l a y T r e e %
752 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
754 % GetNextKeyInSplayTree() gets the next key in the splay-tree.
756 % The format of the GetNextKeyInSplayTree method is:
758 % const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
760 % A description of each parameter follows:
762 % o splay_tree: the splay tree.
767 MagickExport const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
775 assert(splay_tree != (SplayTreeInfo *) NULL);
776 assert(splay_tree->signature == MagickSignature);
777 if (splay_tree->debug != MagickFalse)
778 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
779 if ((splay_tree->root == (NodeInfo *) NULL) ||
780 (splay_tree->next == (void *) NULL))
781 return((void *) NULL);
782 LockSemaphoreInfo(splay_tree->semaphore);
783 SplaySplayTree(splay_tree,splay_tree->next);
784 splay_tree->next=(void *) NULL;
785 node=splay_tree->root->right;
786 if (node != (NodeInfo *) NULL)
788 while (node->left != (NodeInfo *) NULL)
790 splay_tree->next=node->key;
792 key=splay_tree->root->key;
793 UnlockSemaphoreInfo(splay_tree->semaphore);
798 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
802 % G e t N e x t V a l u e I n S p l a y T r e e %
806 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
808 % GetNextValueInSplayTree() gets the next value in the splay-tree.
810 % The format of the GetNextValueInSplayTree method is:
812 % const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
814 % A description of each parameter follows:
816 % o splay_tree: the splay tree.
821 MagickExport const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
829 assert(splay_tree != (SplayTreeInfo *) NULL);
830 assert(splay_tree->signature == MagickSignature);
831 if (splay_tree->debug != MagickFalse)
832 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
833 if ((splay_tree->root == (NodeInfo *) NULL) ||
834 (splay_tree->next == (void *) NULL))
835 return((void *) NULL);
836 LockSemaphoreInfo(splay_tree->semaphore);
837 SplaySplayTree(splay_tree,splay_tree->next);
838 splay_tree->next=(void *) NULL;
839 node=splay_tree->root->right;
840 if (node != (NodeInfo *) NULL)
842 while (node->left != (NodeInfo *) NULL)
844 splay_tree->next=node->key;
846 value=splay_tree->root->value;
847 UnlockSemaphoreInfo(splay_tree->semaphore);
852 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
856 % G e t V a l u e F r o m S p l a y T r e e %
860 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
862 % GetValueFromSplayTree() gets a value from the splay-tree by its key.
864 % Note, the value is a constant. Do not attempt to free it.
866 % The format of the GetValueFromSplayTree method is:
868 % const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
871 % A description of each parameter follows:
873 % o splay_tree: the splay tree.
878 MagickExport const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
887 assert(splay_tree != (SplayTreeInfo *) NULL);
888 assert(splay_tree->signature == MagickSignature);
889 if (splay_tree->debug != MagickFalse)
890 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
891 if (splay_tree->root == (NodeInfo *) NULL)
892 return((void *) NULL);
893 LockSemaphoreInfo(splay_tree->semaphore);
894 SplaySplayTree(splay_tree,key);
895 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
896 compare=splay_tree->compare(splay_tree->root->key,key);
898 compare=(splay_tree->root->key > key) ? 1 :
899 ((splay_tree->root->key < key) ? -1 : 0);
902 UnlockSemaphoreInfo(splay_tree->semaphore);
903 return((void *) NULL);
905 value=splay_tree->root->value;
906 UnlockSemaphoreInfo(splay_tree->semaphore);
911 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
915 % 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 %
919 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
921 % GetNumberOfNodesInSplayTree() returns the number of nodes in the splay-tree.
923 % The format of the GetNumberOfNodesInSplayTree method is:
925 % size_t GetNumberOfNodesInSplayTree(
926 % const SplayTreeInfo *splay_tree)
928 % A description of each parameter follows:
930 % o splay_tree: the splay tree.
933 MagickExport size_t GetNumberOfNodesInSplayTree(
934 const SplayTreeInfo *splay_tree)
936 assert(splay_tree != (SplayTreeInfo *) NULL);
937 assert(splay_tree->signature == MagickSignature);
938 if (splay_tree->debug != MagickFalse)
939 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
940 return(splay_tree->nodes);
944 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
948 % I t e r a t e O v e r S p l a y T r e e %
952 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
954 % IterateOverSplayTree() iterates over the splay-tree.
956 % The format of the IterateOverSplayTree method is:
958 % int IterateOverSplayTree(SplayTreeInfo *splay_tree,
959 % int (*method)(NodeInfo *,void *),const void *value)
961 % A description of each parameter follows:
963 % o splay_tree: the splay-tree info.
965 % o method: the method.
967 % o value: the value.
970 static int IterateOverSplayTree(SplayTreeInfo *splay_tree,
971 int (*method)(NodeInfo *,const void *),const void *value)
1002 if (splay_tree->root == (NodeInfo *) NULL)
1004 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
1006 transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes,
1007 sizeof(*transitions));
1008 if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL))
1009 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1011 final_transition=MagickFalse;
1012 nodes[0]=splay_tree->root;
1013 transitions[0]=(unsigned char) LeftTransition;
1014 for (i=0; final_transition == MagickFalse; )
1017 transition=(TransitionType) transitions[i];
1020 case LeftTransition:
1022 transitions[i]=(unsigned char) DownTransition;
1023 if (node->left == (NodeInfo *) NULL)
1026 nodes[i]=node->left;
1027 transitions[i]=(unsigned char) LeftTransition;
1030 case RightTransition:
1032 transitions[i]=(unsigned char) UpTransition;
1033 if (node->right == (NodeInfo *) NULL)
1036 nodes[i]=node->right;
1037 transitions[i]=(unsigned char) LeftTransition;
1040 case DownTransition:
1043 transitions[i]=(unsigned char) RightTransition;
1044 status=(*method)(node,value);
1046 final_transition=MagickTrue;
1053 final_transition=MagickTrue;
1061 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
1062 transitions=(unsigned char *) RelinquishMagickMemory(transitions);
1067 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1071 % N e w S p l a y T r e e %
1075 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1077 % NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized
1078 % to default values.
1080 % The format of the NewSplayTree method is:
1082 % SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *),
1083 % void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1085 % A description of each parameter follows:
1087 % o compare: the compare method.
1089 % o relinquish_key: the key deallocation method, typically
1090 % RelinquishMagickMemory(), called whenever a key is removed from the
1093 % o relinquish_value: the value deallocation method; typically
1094 % RelinquishMagickMemory(), called whenever a value object is removed from
1098 MagickExport SplayTreeInfo *NewSplayTree(
1099 int (*compare)(const void *,const void *),void *(*relinquish_key)(void *),
1100 void *(*relinquish_value)(void *))
1105 splay_tree=(SplayTreeInfo *) AcquireMagickMemory(sizeof(*splay_tree));
1106 if (splay_tree == (SplayTreeInfo *) NULL)
1107 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1108 (void) ResetMagickMemory(splay_tree,0,sizeof(*splay_tree));
1109 splay_tree->root=(NodeInfo *) NULL;
1110 splay_tree->compare=compare;
1111 splay_tree->relinquish_key=relinquish_key;
1112 splay_tree->relinquish_value=relinquish_value;
1113 splay_tree->balance=MagickFalse;
1114 splay_tree->key=(void *) NULL;
1115 splay_tree->next=(void *) NULL;
1116 splay_tree->nodes=0;
1117 splay_tree->debug=IsEventLogging();
1118 splay_tree->semaphore=AcquireSemaphoreInfo();
1119 splay_tree->signature=MagickSignature;
1124 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1128 % 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 %
1132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1134 % RemoveNodeByValueFromSplayTree() removes a node by value from the splay-tree
1135 % and returns its key.
1137 % The format of the RemoveNodeByValueFromSplayTree method is:
1139 % void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1140 % const void *value)
1142 % A description of each parameter follows:
1144 % o splay_tree: the splay-tree info.
1146 % o value: the value.
1149 MagickExport void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1159 assert(splay_tree != (SplayTreeInfo *) NULL);
1160 assert(splay_tree->signature == MagickSignature);
1161 if (splay_tree->debug != MagickFalse)
1162 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1164 if (splay_tree->root == (NodeInfo *) NULL)
1166 LockSemaphoreInfo(splay_tree->semaphore);
1167 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
1168 while (next != (NodeInfo *) NULL)
1170 SplaySplayTree(splay_tree,next);
1171 next=(NodeInfo *) NULL;
1172 node=splay_tree->root->right;
1173 if (node != (NodeInfo *) NULL)
1175 while (node->left != (NodeInfo *) NULL)
1177 next=(NodeInfo *) node->key;
1179 if (splay_tree->root->value == value)
1189 We found the node that matches the value; now remove it.
1191 key=splay_tree->root->key;
1192 SplaySplayTree(splay_tree,key);
1193 splay_tree->key=(void *) NULL;
1194 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1195 compare=splay_tree->compare(splay_tree->root->key,key);
1197 compare=(splay_tree->root->key > key) ? 1 :
1198 ((splay_tree->root->key < key) ? -1 : 0);
1201 UnlockSemaphoreInfo(splay_tree->semaphore);
1204 left=splay_tree->root->left;
1205 right=splay_tree->root->right;
1206 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1207 (splay_tree->root->value != (void *) NULL))
1208 splay_tree->root->value=splay_tree->relinquish_value(
1209 splay_tree->root->value);
1210 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1211 splay_tree->nodes--;
1212 if (left == (NodeInfo *) NULL)
1214 splay_tree->root=right;
1215 UnlockSemaphoreInfo(splay_tree->semaphore);
1218 splay_tree->root=left;
1219 if (right != (NodeInfo *) NULL)
1221 while (left->right != (NodeInfo *) NULL)
1225 UnlockSemaphoreInfo(splay_tree->semaphore);
1229 UnlockSemaphoreInfo(splay_tree->semaphore);
1234 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1238 % R e m o v e N o d e F r o m S p l a y T r e e %
1242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1244 % RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its
1247 % The format of the RemoveNodeFromSplayTree method is:
1249 % void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key)
1251 % A description of each parameter follows:
1253 % o splay_tree: the splay-tree info.
1258 MagickExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,
1271 assert(splay_tree != (SplayTreeInfo *) NULL);
1272 assert(splay_tree->signature == MagickSignature);
1273 if (splay_tree->debug != MagickFalse)
1274 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1275 value=(void *) NULL;
1276 if (splay_tree->root == (NodeInfo *) NULL)
1278 LockSemaphoreInfo(splay_tree->semaphore);
1279 SplaySplayTree(splay_tree,key);
1280 splay_tree->key=(void *) NULL;
1281 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1282 compare=splay_tree->compare(splay_tree->root->key,key);
1284 compare=(splay_tree->root->key > key) ? 1 :
1285 ((splay_tree->root->key < key) ? -1 : 0);
1288 UnlockSemaphoreInfo(splay_tree->semaphore);
1291 left=splay_tree->root->left;
1292 right=splay_tree->root->right;
1293 value=splay_tree->root->value;
1294 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1295 (splay_tree->root->key != (void *) NULL))
1296 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1297 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1298 splay_tree->nodes--;
1299 if (left == (NodeInfo *) NULL)
1301 splay_tree->root=right;
1302 UnlockSemaphoreInfo(splay_tree->semaphore);
1305 splay_tree->root=left;
1306 if (right != (NodeInfo *) NULL)
1308 while (left->right != (NodeInfo *) NULL)
1312 UnlockSemaphoreInfo(splay_tree->semaphore);
1317 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1321 % R e s e t S p l a y T r e e %
1325 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1327 % ResetSplayTree() resets the splay-tree. That is, it deletes all the nodes
1330 % The format of the ResetSplayTree method is:
1332 % ResetSplayTree(SplayTreeInfo *splay_tree)
1334 % A description of each parameter follows:
1336 % o splay_tree: the splay tree.
1339 MagickExport void ResetSplayTree(SplayTreeInfo *splay_tree)
1348 assert(splay_tree != (SplayTreeInfo *) NULL);
1349 assert(splay_tree->signature == MagickSignature);
1350 if (splay_tree->debug != MagickFalse)
1351 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1352 LockSemaphoreInfo(splay_tree->semaphore);
1353 if (splay_tree->root != (NodeInfo *) NULL)
1355 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1356 (splay_tree->root->value != (void *) NULL))
1357 splay_tree->root->value=splay_tree->relinquish_value(
1358 splay_tree->root->value);
1359 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1360 (splay_tree->root->key != (void *) NULL))
1361 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1362 splay_tree->root->key=(void *) NULL;
1363 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
1366 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
1368 if (active->left != (NodeInfo *) NULL)
1370 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1371 (active->left->value != (void *) NULL))
1372 active->left->value=splay_tree->relinquish_value(
1373 active->left->value);
1374 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1375 (active->left->key != (void *) NULL))
1376 active->left->key=splay_tree->relinquish_key(active->left->key);
1377 active->left->key=(void *) pend;
1380 if (active->right != (NodeInfo *) NULL)
1382 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1383 (active->right->value != (void *) NULL))
1384 active->right->value=splay_tree->relinquish_value(
1385 active->right->value);
1386 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1387 (active->right->key != (void *) NULL))
1388 active->right->key=splay_tree->relinquish_key(
1389 active->right->key);
1390 active->right->key=(void *) pend;
1394 active=(NodeInfo *) node->key;
1395 node=(NodeInfo *) RelinquishMagickMemory(node);
1399 splay_tree->root=(NodeInfo *) NULL;
1400 splay_tree->key=(void *) NULL;
1401 splay_tree->next=(void *) NULL;
1402 splay_tree->nodes=0;
1403 splay_tree->balance=MagickFalse;
1404 UnlockSemaphoreInfo(splay_tree->semaphore);
1408 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1412 % R e s e t S p l a y T r e e I t e r a t o r %
1416 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1418 % ResetSplayTreeIterator() resets the splay-tree iterator. Use it in
1419 % conjunction with GetNextValueInSplayTree() to iterate over all the nodes in
1422 % The format of the ResetSplayTreeIterator method is:
1424 % ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1426 % A description of each parameter follows:
1428 % o splay_tree: the splay tree.
1431 MagickExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1433 assert(splay_tree != (SplayTreeInfo *) NULL);
1434 assert(splay_tree->signature == MagickSignature);
1435 if (splay_tree->debug != MagickFalse)
1436 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1437 LockSemaphoreInfo(splay_tree->semaphore);
1438 splay_tree->next=GetFirstSplayTreeNode(splay_tree);
1439 UnlockSemaphoreInfo(splay_tree->semaphore);
1443 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1447 % S p l a y S p l a y T r e e %
1451 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1453 % SplaySplayTree() splays the splay-tree.
1455 % The format of the SplaySplayTree method is:
1457 % void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key,
1458 % NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1460 % A description of each parameter follows:
1462 % o splay_tree: the splay-tree info.
1468 % o parent: the parent node.
1470 % o grandparent: the grandparent node.
1474 static inline NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth,
1475 const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1488 if (n == (NodeInfo *) NULL)
1490 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1491 compare=splay_tree->compare(n->key,key);
1493 compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
1494 next=(NodeInfo **) NULL;
1500 if (next != (NodeInfo **) NULL)
1502 if (depth >= MaxSplayTreeDepth)
1504 splay_tree->balance=MagickTrue;
1507 n=Splay(splay_tree,depth+1,key,next,node,parent);
1508 if ((n != *node) || (splay_tree->balance != MagickFalse))
1511 if (parent == (NodeInfo **) NULL)
1513 if (grandparent == (NodeInfo **) NULL)
1515 if (n == (*parent)->left)
1528 if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
1531 (*grandparent)->left=p->right;
1532 p->right=(*grandparent);
1538 if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
1541 (*grandparent)->right=p->left;
1542 p->left=(*grandparent);
1548 if (n == (*parent)->left)
1550 (*parent)->left=n->right;
1552 (*grandparent)->right=n->left;
1553 n->left=(*grandparent);
1557 (*parent)->right=n->left;
1559 (*grandparent)->left=n->right;
1560 n->right=(*grandparent);
1565 static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key)
1567 if (splay_tree->root == (NodeInfo *) NULL)
1569 if (splay_tree->key != (void *) NULL)
1574 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1575 compare=splay_tree->compare(splay_tree->root->key,key);
1577 compare=(splay_tree->key > key) ? 1 :
1578 ((splay_tree->key < key) ? -1 : 0);
1582 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1583 (NodeInfo **) NULL);
1584 if (splay_tree->balance != MagickFalse)
1586 BalanceSplayTree(splay_tree);
1587 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1588 (NodeInfo **) NULL);
1589 if (splay_tree->balance != MagickFalse)
1590 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1592 splay_tree->key=(void *) key;