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-2019 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 % https://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/locale_.h"
55 #include "MagickCore/log.h"
56 #include "MagickCore/memory_.h"
57 #include "MagickCore/memory-private.h"
58 #include "MagickCore/splay-tree.h"
59 #include "MagickCore/semaphore.h"
60 #include "MagickCore/string_.h"
65 #define MaxSplayTreeDepth 1024
70 typedef struct _NodeInfo
89 (*compare)(const void *,const void *);
92 *(*relinquish_key)(void *),
93 *(*relinquish_value)(void *);
116 Forward declarations.
119 IterateOverSplayTree(SplayTreeInfo *,int (*)(NodeInfo *,const void *),
123 SplaySplayTree(SplayTreeInfo *,const void *);
126 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
130 % A d d V a l u e T o S p l a y T r e e %
134 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
136 % AddValueToSplayTree() adds the given key and value to the splay-tree. Both
137 % key and value are used as is, without coping or cloning. It returns
138 % MagickTrue on success, otherwise MagickFalse.
140 % The format of the AddValueToSplayTree method is:
142 % MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
143 % const void *key,const void *value)
145 % A description of each parameter follows:
147 % o splay_tree: the splay-tree info.
151 % o value: the value.
154 MagickExport MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
155 const void *key,const void *value)
163 LockSemaphoreInfo(splay_tree->semaphore);
164 SplaySplayTree(splay_tree,key);
166 if (splay_tree->root != (NodeInfo *) NULL)
168 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
169 compare=splay_tree->compare(splay_tree->root->key,key);
171 compare=(splay_tree->root->key > key) ? 1 :
172 ((splay_tree->root->key < key) ? -1 : 0);
175 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
176 (splay_tree->root->value != (void *) NULL))
177 splay_tree->root->value=splay_tree->relinquish_value(
178 splay_tree->root->value);
179 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
180 (splay_tree->root->key != (void *) NULL))
181 splay_tree->root->key=splay_tree->relinquish_key(
182 splay_tree->root->key);
183 splay_tree->root->key=(void *) key;
184 splay_tree->root->value=(void *) value;
185 UnlockSemaphoreInfo(splay_tree->semaphore);
189 node=(NodeInfo *) AcquireMagickMemory(sizeof(*node));
190 if (node == (NodeInfo *) NULL)
192 UnlockSemaphoreInfo(splay_tree->semaphore);
195 node->key=(void *) key;
196 node->value=(void *) value;
197 if (splay_tree->root == (NodeInfo *) NULL)
199 node->left=(NodeInfo *) NULL;
200 node->right=(NodeInfo *) NULL;
205 node->left=splay_tree->root;
206 node->right=node->left->right;
207 node->left->right=(NodeInfo *) NULL;
211 node->right=splay_tree->root;
212 node->left=node->right->left;
213 node->right->left=(NodeInfo *) NULL;
215 splay_tree->root=node;
216 splay_tree->key=(void *) NULL;
218 UnlockSemaphoreInfo(splay_tree->semaphore);
223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
227 % B a l a n c e S p l a y T r e e %
231 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
233 % BalanceSplayTree() balances the splay-tree.
235 % The format of the BalanceSplayTree method is:
237 % void *BalanceSplayTree(SplayTreeInfo *splay_tree,const void *key)
239 % A description of each parameter follows:
241 % o splay_tree: the splay-tree info.
247 static NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const size_t low,
256 bisect=low+(high-low)/2;
258 if ((low+1) > bisect)
259 node->left=(NodeInfo *) NULL;
261 node->left=LinkSplayTreeNodes(nodes,low,bisect-1);
262 if ((bisect+1) > high)
263 node->right=(NodeInfo *) NULL;
265 node->right=LinkSplayTreeNodes(nodes,bisect+1,high);
269 static inline int SplayTreeToNodeArray(NodeInfo *node,const void *nodes)
271 register const NodeInfo
274 p=(const NodeInfo ***) nodes;
280 static void BalanceSplayTree(SplayTreeInfo *splay_tree)
286 if (splay_tree->nodes <= 2)
288 splay_tree->balance=MagickFalse;
291 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
293 if (nodes == (NodeInfo **) NULL)
294 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
296 (void) IterateOverSplayTree(splay_tree,SplayTreeToNodeArray,(const void *)
298 splay_tree->root=LinkSplayTreeNodes(nodes,0,splay_tree->nodes-1);
299 splay_tree->balance=MagickFalse;
300 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
304 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
308 % C l o n e S p l a y T r e e %
312 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
314 % CloneSplayTree() clones the splay tree.
316 % The format of the CloneSplayTree method is:
318 % SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
319 % void *(*clone_key)(void *),void *(*cline_value)(void *))
321 % A description of each parameter follows:
323 % o splay_tree: the splay tree.
325 % o clone_key: the key clone method, typically ConstantString(), called
326 % whenever a key is added to the splay-tree.
328 % o clone_value: the value clone method; typically ConstantString(), called
329 % whenever a value object is added to the splay-tree.
333 static inline void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree)
338 node=splay_tree->root;
339 if (splay_tree->root == (NodeInfo *) NULL)
340 return((NodeInfo *) NULL);
341 while (node->left != (NodeInfo *) NULL)
346 MagickExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
347 void *(*clone_key)(void *),void *(*clone_value)(void *))
356 assert(splay_tree != (SplayTreeInfo *) NULL);
357 assert(splay_tree->signature == MagickCoreSignature);
358 if (splay_tree->debug != MagickFalse)
359 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
360 clone_tree=NewSplayTree(splay_tree->compare,splay_tree->relinquish_key,
361 splay_tree->relinquish_value);
362 LockSemaphoreInfo(splay_tree->semaphore);
363 if (splay_tree->root == (NodeInfo *) NULL)
365 UnlockSemaphoreInfo(splay_tree->semaphore);
368 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
369 while (next != (NodeInfo *) NULL)
371 SplaySplayTree(splay_tree,next);
372 (void) AddValueToSplayTree(clone_tree,clone_key(splay_tree->root->key),
373 clone_value(splay_tree->root->value));
374 next=(NodeInfo *) NULL;
375 node=splay_tree->root->right;
376 if (node != (NodeInfo *) NULL)
378 while (node->left != (NodeInfo *) NULL)
380 next=(NodeInfo *) node->key;
383 UnlockSemaphoreInfo(splay_tree->semaphore);
388 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
392 % C o m p a r e S p l a y T r e e S t r i n g %
396 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
398 % CompareSplayTreeString() method finds a node in a splay-tree based on the
399 % contents of a string.
401 % The format of the CompareSplayTreeString method is:
403 % int CompareSplayTreeString(const void *target,const void *source)
405 % A description of each parameter follows:
407 % o target: the target string.
409 % o source: the source string.
412 MagickExport int CompareSplayTreeString(const void *target,const void *source)
418 p=(const char *) target;
419 q=(const char *) source;
420 return(LocaleCompare(p,q));
424 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
428 % 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 %
432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
434 % CompareSplayTreeStringInfo() finds a node in a splay-tree based on the
435 % contents of a string.
437 % The format of the CompareSplayTreeStringInfo method is:
439 % int CompareSplayTreeStringInfo(const void *target,const void *source)
441 % A description of each parameter follows:
443 % o target: the target string.
445 % o source: the source string.
448 MagickExport int CompareSplayTreeStringInfo(const void *target,
455 p=(const StringInfo *) target;
456 q=(const StringInfo *) source;
457 return(CompareStringInfo(p,q));
461 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
465 % 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 %
469 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
471 % DeleteNodeByValueFromSplayTree() deletes a node by value from the
474 % The format of the DeleteNodeByValueFromSplayTree method is:
476 % MagickBooleanType DeleteNodeByValueFromSplayTree(
477 % SplayTreeInfo *splay_tree,const void *value)
479 % A description of each parameter follows:
481 % o splay_tree: the splay-tree info.
483 % o value: the value.
486 MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree(
487 SplayTreeInfo *splay_tree,const void *value)
493 assert(splay_tree != (SplayTreeInfo *) NULL);
494 assert(splay_tree->signature == MagickCoreSignature);
495 if (splay_tree->debug != MagickFalse)
496 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
497 LockSemaphoreInfo(splay_tree->semaphore);
498 if (splay_tree->root == (NodeInfo *) NULL)
500 UnlockSemaphoreInfo(splay_tree->semaphore);
503 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
504 while (next != (NodeInfo *) NULL)
506 SplaySplayTree(splay_tree,next);
507 next=(NodeInfo *) NULL;
508 node=splay_tree->root->right;
509 if (node != (NodeInfo *) NULL)
511 while (node->left != (NodeInfo *) NULL)
513 next=(NodeInfo *) node->key;
515 if (splay_tree->root->value == value)
528 We found the node that matches the value; now delete it.
530 key=splay_tree->root->key;
531 SplaySplayTree(splay_tree,key);
532 splay_tree->key=(void *) NULL;
533 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
534 compare=splay_tree->compare(splay_tree->root->key,key);
536 compare=(splay_tree->root->key > key) ? 1 :
537 ((splay_tree->root->key < key) ? -1 : 0);
540 UnlockSemaphoreInfo(splay_tree->semaphore);
543 left=splay_tree->root->left;
544 right=splay_tree->root->right;
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 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
550 (splay_tree->root->key != (void *) NULL))
551 splay_tree->root->key=splay_tree->relinquish_key(
552 splay_tree->root->key);
553 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
555 if (left == (NodeInfo *) NULL)
557 splay_tree->root=right;
558 UnlockSemaphoreInfo(splay_tree->semaphore);
561 splay_tree->root=left;
562 if (right != (NodeInfo *) NULL)
564 while (left->right != (NodeInfo *) NULL)
568 UnlockSemaphoreInfo(splay_tree->semaphore);
572 UnlockSemaphoreInfo(splay_tree->semaphore);
577 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
581 % D e l e t e N o d e F r o m S p l a y T r e e %
585 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
587 % DeleteNodeFromSplayTree() deletes a node from the splay-tree. It returns
588 % MagickTrue if the option is found and successfully deleted from the
591 % The format of the DeleteNodeFromSplayTree method is:
593 % MagickBooleanType DeleteNodeFromSplayTree(SplayTreeInfo *splay_tree,
596 % A description of each parameter follows:
598 % o splay_tree: the splay-tree info.
603 MagickExport MagickBooleanType DeleteNodeFromSplayTree(
604 SplayTreeInfo *splay_tree,const void *key)
613 assert(splay_tree != (SplayTreeInfo *) NULL);
614 assert(splay_tree->signature == MagickCoreSignature);
615 if (splay_tree->debug != MagickFalse)
616 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
617 if (splay_tree->root == (NodeInfo *) NULL)
619 LockSemaphoreInfo(splay_tree->semaphore);
620 SplaySplayTree(splay_tree,key);
621 splay_tree->key=(void *) NULL;
622 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
623 compare=splay_tree->compare(splay_tree->root->key,key);
625 compare=(splay_tree->root->key > key) ? 1 :
626 ((splay_tree->root->key < key) ? -1 : 0);
629 UnlockSemaphoreInfo(splay_tree->semaphore);
632 left=splay_tree->root->left;
633 right=splay_tree->root->right;
634 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
635 (splay_tree->root->value != (void *) NULL))
636 splay_tree->root->value=splay_tree->relinquish_value(
637 splay_tree->root->value);
638 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
639 (splay_tree->root->key != (void *) NULL))
640 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
641 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
643 if (left == (NodeInfo *) NULL)
645 splay_tree->root=right;
646 UnlockSemaphoreInfo(splay_tree->semaphore);
649 splay_tree->root=left;
650 if (right != (NodeInfo *) NULL)
652 while (left->right != (NodeInfo *) NULL)
656 UnlockSemaphoreInfo(splay_tree->semaphore);
661 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
665 % D e s t r o y S p l a y T r e e %
669 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
671 % DestroySplayTree() destroys the splay-tree.
673 % The format of the DestroySplayTree method is:
675 % SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
677 % A description of each parameter follows:
679 % o splay_tree: the splay tree.
682 MagickExport SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
691 LockSemaphoreInfo(splay_tree->semaphore);
692 if (splay_tree->root != (NodeInfo *) NULL)
694 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
695 (splay_tree->root->value != (void *) NULL))
696 splay_tree->root->value=splay_tree->relinquish_value(
697 splay_tree->root->value);
698 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
699 (splay_tree->root->key != (void *) NULL))
700 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
701 splay_tree->root->key=(void *) NULL;
702 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
705 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
707 if (active->left != (NodeInfo *) NULL)
709 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
710 (active->left->value != (void *) NULL))
711 active->left->value=splay_tree->relinquish_value(
712 active->left->value);
713 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
714 (active->left->key != (void *) NULL))
715 active->left->key=splay_tree->relinquish_key(active->left->key);
716 active->left->key=(void *) pend;
719 if (active->right != (NodeInfo *) NULL)
721 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
722 (active->right->value != (void *) NULL))
723 active->right->value=splay_tree->relinquish_value(
724 active->right->value);
725 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
726 (active->right->key != (void *) NULL))
727 active->right->key=splay_tree->relinquish_key(
729 active->right->key=(void *) pend;
733 active=(NodeInfo *) node->key;
734 node=(NodeInfo *) RelinquishMagickMemory(node);
738 splay_tree->signature=(~MagickCoreSignature);
739 UnlockSemaphoreInfo(splay_tree->semaphore);
740 RelinquishSemaphoreInfo(&splay_tree->semaphore);
741 splay_tree=(SplayTreeInfo *) RelinquishMagickMemory(splay_tree);
746 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
750 % G e t N e x t K e y I n S p l a y T r e e %
754 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
756 % GetNextKeyInSplayTree() gets the next key in the splay-tree.
758 % The format of the GetNextKeyInSplayTree method is:
760 % const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
762 % A description of each parameter follows:
764 % o splay_tree: the splay tree.
769 MagickExport const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
777 assert(splay_tree != (SplayTreeInfo *) NULL);
778 assert(splay_tree->signature == MagickCoreSignature);
779 if (splay_tree->debug != MagickFalse)
780 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
781 if ((splay_tree->root == (NodeInfo *) NULL) ||
782 (splay_tree->next == (void *) NULL))
783 return((void *) NULL);
784 LockSemaphoreInfo(splay_tree->semaphore);
785 SplaySplayTree(splay_tree,splay_tree->next);
786 splay_tree->next=(void *) NULL;
787 node=splay_tree->root->right;
788 if (node != (NodeInfo *) NULL)
790 while (node->left != (NodeInfo *) NULL)
792 splay_tree->next=node->key;
794 key=splay_tree->root->key;
795 UnlockSemaphoreInfo(splay_tree->semaphore);
800 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
804 % G e t N e x t V a l u e I n S p l a y T r e e %
808 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
810 % GetNextValueInSplayTree() gets the next value in the splay-tree.
812 % The format of the GetNextValueInSplayTree method is:
814 % const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
816 % A description of each parameter follows:
818 % o splay_tree: the splay tree.
823 MagickExport const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
831 assert(splay_tree != (SplayTreeInfo *) NULL);
832 assert(splay_tree->signature == MagickCoreSignature);
833 if (splay_tree->debug != MagickFalse)
834 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
835 if ((splay_tree->root == (NodeInfo *) NULL) ||
836 (splay_tree->next == (void *) NULL))
837 return((void *) NULL);
838 LockSemaphoreInfo(splay_tree->semaphore);
839 SplaySplayTree(splay_tree,splay_tree->next);
840 splay_tree->next=(void *) NULL;
841 node=splay_tree->root->right;
842 if (node != (NodeInfo *) NULL)
844 while (node->left != (NodeInfo *) NULL)
846 splay_tree->next=node->key;
848 value=splay_tree->root->value;
849 UnlockSemaphoreInfo(splay_tree->semaphore);
854 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
858 % G e t R o o t V a l u e F r o m S p l a y T r e e %
862 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
864 % GetRootValueFromSplayTree() gets the root value from the splay-tree.
866 % The format of the GetRootValueFromSplayTree method is:
868 % const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
870 % A description of each parameter follows:
872 % o splay_tree: the splay tree.
877 MagickExport const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
882 assert(splay_tree != (SplayTreeInfo *) NULL);
883 assert(splay_tree->signature == MagickCoreSignature);
884 if (splay_tree->debug != MagickFalse)
885 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
886 value=(const void *) NULL;
887 LockSemaphoreInfo(splay_tree->semaphore);
888 if (splay_tree->root != (NodeInfo *) NULL)
889 value=splay_tree->root->value;
890 UnlockSemaphoreInfo(splay_tree->semaphore);
895 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
899 % G e t V a l u e F r o m S p l a y T r e e %
903 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
905 % GetValueFromSplayTree() gets a value from the splay-tree by its key.
907 % Note, the value is a constant. Do not attempt to free it.
909 % The format of the GetValueFromSplayTree method is:
911 % const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
914 % A description of each parameter follows:
916 % o splay_tree: the splay tree.
921 MagickExport const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
930 assert(splay_tree != (SplayTreeInfo *) NULL);
931 assert(splay_tree->signature == MagickCoreSignature);
932 if (splay_tree->debug != MagickFalse)
933 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
934 if (splay_tree->root == (NodeInfo *) NULL)
935 return((void *) NULL);
936 LockSemaphoreInfo(splay_tree->semaphore);
937 SplaySplayTree(splay_tree,key);
938 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
939 compare=splay_tree->compare(splay_tree->root->key,key);
941 compare=(splay_tree->root->key > key) ? 1 :
942 ((splay_tree->root->key < key) ? -1 : 0);
945 UnlockSemaphoreInfo(splay_tree->semaphore);
946 return((void *) NULL);
948 value=splay_tree->root->value;
949 UnlockSemaphoreInfo(splay_tree->semaphore);
954 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
958 % 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 %
962 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
964 % GetNumberOfNodesInSplayTree() returns the number of nodes in the splay-tree.
966 % The format of the GetNumberOfNodesInSplayTree method is:
968 % size_t GetNumberOfNodesInSplayTree(
969 % const SplayTreeInfo *splay_tree)
971 % A description of each parameter follows:
973 % o splay_tree: the splay tree.
976 MagickExport size_t GetNumberOfNodesInSplayTree(
977 const SplayTreeInfo *splay_tree)
979 assert(splay_tree != (SplayTreeInfo *) NULL);
980 assert(splay_tree->signature == MagickCoreSignature);
981 if (splay_tree->debug != MagickFalse)
982 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
983 return(splay_tree->nodes);
987 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
991 % I t e r a t e O v e r S p l a y T r e e %
995 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
997 % IterateOverSplayTree() iterates over the splay-tree.
999 % The format of the IterateOverSplayTree method is:
1001 % int IterateOverSplayTree(SplayTreeInfo *splay_tree,
1002 % int (*method)(NodeInfo *,void *),const void *value)
1004 % A description of each parameter follows:
1006 % o splay_tree: the splay-tree info.
1008 % o method: the method.
1010 % o value: the value.
1013 static int IterateOverSplayTree(SplayTreeInfo *splay_tree,
1014 int (*method)(NodeInfo *,const void *),const void *value)
1045 if (splay_tree->root == (NodeInfo *) NULL)
1047 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
1049 transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes,
1050 sizeof(*transitions));
1051 if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL))
1052 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1054 final_transition=MagickFalse;
1055 nodes[0]=splay_tree->root;
1056 transitions[0]=(unsigned char) LeftTransition;
1057 for (i=0; final_transition == MagickFalse; )
1060 transition=(TransitionType) transitions[i];
1063 case LeftTransition:
1065 transitions[i]=(unsigned char) DownTransition;
1066 if (node->left == (NodeInfo *) NULL)
1069 nodes[i]=node->left;
1070 transitions[i]=(unsigned char) LeftTransition;
1073 case RightTransition:
1075 transitions[i]=(unsigned char) UpTransition;
1076 if (node->right == (NodeInfo *) NULL)
1079 nodes[i]=node->right;
1080 transitions[i]=(unsigned char) LeftTransition;
1083 case DownTransition:
1086 transitions[i]=(unsigned char) RightTransition;
1087 status=(*method)(node,value);
1089 final_transition=MagickTrue;
1096 final_transition=MagickTrue;
1104 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
1105 transitions=(unsigned char *) RelinquishMagickMemory(transitions);
1110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1114 % N e w S p l a y T r e e %
1118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1120 % NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized
1121 % to default values.
1123 % The format of the NewSplayTree method is:
1125 % SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *),
1126 % void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1128 % A description of each parameter follows:
1130 % o compare: the compare method.
1132 % o relinquish_key: the key deallocation method, typically
1133 % RelinquishMagickMemory(), called whenever a key is removed from the
1136 % o relinquish_value: the value deallocation method; typically
1137 % RelinquishMagickMemory(), called whenever a value object is removed from
1141 MagickExport SplayTreeInfo *NewSplayTree(
1142 int (*compare)(const void *,const void *),void *(*relinquish_key)(void *),
1143 void *(*relinquish_value)(void *))
1148 splay_tree=(SplayTreeInfo *) AcquireCriticalMemory(sizeof(*splay_tree));
1149 (void) memset(splay_tree,0,sizeof(*splay_tree));
1150 splay_tree->root=(NodeInfo *) NULL;
1151 splay_tree->compare=compare;
1152 splay_tree->relinquish_key=relinquish_key;
1153 splay_tree->relinquish_value=relinquish_value;
1154 splay_tree->balance=MagickFalse;
1155 splay_tree->key=(void *) NULL;
1156 splay_tree->next=(void *) NULL;
1157 splay_tree->nodes=0;
1158 splay_tree->debug=IsEventLogging();
1159 splay_tree->semaphore=AcquireSemaphoreInfo();
1160 splay_tree->signature=MagickCoreSignature;
1165 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1169 % 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 %
1173 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1175 % RemoveNodeByValueFromSplayTree() removes a node by value from the splay-tree
1176 % and returns its key.
1178 % The format of the RemoveNodeByValueFromSplayTree method is:
1180 % void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1181 % const void *value)
1183 % A description of each parameter follows:
1185 % o splay_tree: the splay-tree info.
1187 % o value: the value.
1190 MagickExport void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1200 assert(splay_tree != (SplayTreeInfo *) NULL);
1201 assert(splay_tree->signature == MagickCoreSignature);
1202 if (splay_tree->debug != MagickFalse)
1203 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1205 if (splay_tree->root == (NodeInfo *) NULL)
1207 LockSemaphoreInfo(splay_tree->semaphore);
1208 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
1209 while (next != (NodeInfo *) NULL)
1211 SplaySplayTree(splay_tree,next);
1212 next=(NodeInfo *) NULL;
1213 node=splay_tree->root->right;
1214 if (node != (NodeInfo *) NULL)
1216 while (node->left != (NodeInfo *) NULL)
1218 next=(NodeInfo *) node->key;
1220 if (splay_tree->root->value == value)
1230 We found the node that matches the value; now remove it.
1232 key=splay_tree->root->key;
1233 SplaySplayTree(splay_tree,key);
1234 splay_tree->key=(void *) NULL;
1235 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1236 compare=splay_tree->compare(splay_tree->root->key,key);
1238 compare=(splay_tree->root->key > key) ? 1 :
1239 ((splay_tree->root->key < key) ? -1 : 0);
1242 UnlockSemaphoreInfo(splay_tree->semaphore);
1245 left=splay_tree->root->left;
1246 right=splay_tree->root->right;
1247 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1248 (splay_tree->root->value != (void *) NULL))
1249 splay_tree->root->value=splay_tree->relinquish_value(
1250 splay_tree->root->value);
1251 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1252 splay_tree->nodes--;
1253 if (left == (NodeInfo *) NULL)
1255 splay_tree->root=right;
1256 UnlockSemaphoreInfo(splay_tree->semaphore);
1259 splay_tree->root=left;
1260 if (right != (NodeInfo *) NULL)
1262 while (left->right != (NodeInfo *) NULL)
1266 UnlockSemaphoreInfo(splay_tree->semaphore);
1270 UnlockSemaphoreInfo(splay_tree->semaphore);
1275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1279 % R e m o v e N o d e F r o m S p l a y T r e e %
1283 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1285 % RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its
1288 % The format of the RemoveNodeFromSplayTree method is:
1290 % void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key)
1292 % A description of each parameter follows:
1294 % o splay_tree: the splay-tree info.
1299 MagickExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,
1312 assert(splay_tree != (SplayTreeInfo *) NULL);
1313 assert(splay_tree->signature == MagickCoreSignature);
1314 if (splay_tree->debug != MagickFalse)
1315 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1316 value=(void *) NULL;
1317 if (splay_tree->root == (NodeInfo *) NULL)
1319 LockSemaphoreInfo(splay_tree->semaphore);
1320 SplaySplayTree(splay_tree,key);
1321 splay_tree->key=(void *) NULL;
1322 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1323 compare=splay_tree->compare(splay_tree->root->key,key);
1325 compare=(splay_tree->root->key > key) ? 1 :
1326 ((splay_tree->root->key < key) ? -1 : 0);
1329 UnlockSemaphoreInfo(splay_tree->semaphore);
1332 left=splay_tree->root->left;
1333 right=splay_tree->root->right;
1334 value=splay_tree->root->value;
1335 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1336 (splay_tree->root->key != (void *) NULL))
1337 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1338 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1339 splay_tree->nodes--;
1340 if (left == (NodeInfo *) NULL)
1342 splay_tree->root=right;
1343 UnlockSemaphoreInfo(splay_tree->semaphore);
1346 splay_tree->root=left;
1347 if (right != (NodeInfo *) NULL)
1349 while (left->right != (NodeInfo *) NULL)
1353 UnlockSemaphoreInfo(splay_tree->semaphore);
1358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1362 % R e s e t S p l a y T r e e %
1366 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1368 % ResetSplayTree() resets the splay-tree. That is, it deletes all the nodes
1371 % The format of the ResetSplayTree method is:
1373 % ResetSplayTree(SplayTreeInfo *splay_tree)
1375 % A description of each parameter follows:
1377 % o splay_tree: the splay tree.
1380 MagickExport void ResetSplayTree(SplayTreeInfo *splay_tree)
1389 assert(splay_tree != (SplayTreeInfo *) NULL);
1390 assert(splay_tree->signature == MagickCoreSignature);
1391 if (splay_tree->debug != MagickFalse)
1392 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1393 LockSemaphoreInfo(splay_tree->semaphore);
1394 if (splay_tree->root != (NodeInfo *) NULL)
1396 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1397 (splay_tree->root->value != (void *) NULL))
1398 splay_tree->root->value=splay_tree->relinquish_value(
1399 splay_tree->root->value);
1400 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1401 (splay_tree->root->key != (void *) NULL))
1402 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1403 splay_tree->root->key=(void *) NULL;
1404 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
1407 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
1409 if (active->left != (NodeInfo *) NULL)
1411 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1412 (active->left->value != (void *) NULL))
1413 active->left->value=splay_tree->relinquish_value(
1414 active->left->value);
1415 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1416 (active->left->key != (void *) NULL))
1417 active->left->key=splay_tree->relinquish_key(active->left->key);
1418 active->left->key=(void *) pend;
1421 if (active->right != (NodeInfo *) NULL)
1423 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1424 (active->right->value != (void *) NULL))
1425 active->right->value=splay_tree->relinquish_value(
1426 active->right->value);
1427 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1428 (active->right->key != (void *) NULL))
1429 active->right->key=splay_tree->relinquish_key(
1430 active->right->key);
1431 active->right->key=(void *) pend;
1435 active=(NodeInfo *) node->key;
1436 node=(NodeInfo *) RelinquishMagickMemory(node);
1440 splay_tree->root=(NodeInfo *) NULL;
1441 splay_tree->key=(void *) NULL;
1442 splay_tree->next=(void *) NULL;
1443 splay_tree->nodes=0;
1444 splay_tree->balance=MagickFalse;
1445 UnlockSemaphoreInfo(splay_tree->semaphore);
1449 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1453 % R e s e t S p l a y T r e e I t e r a t o r %
1457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1459 % ResetSplayTreeIterator() resets the splay-tree iterator. Use it in
1460 % conjunction with GetNextValueInSplayTree() to iterate over all the nodes in
1463 % The format of the ResetSplayTreeIterator method is:
1465 % ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1467 % A description of each parameter follows:
1469 % o splay_tree: the splay tree.
1472 MagickExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1474 assert(splay_tree != (SplayTreeInfo *) NULL);
1475 assert(splay_tree->signature == MagickCoreSignature);
1476 if (splay_tree->debug != MagickFalse)
1477 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1478 LockSemaphoreInfo(splay_tree->semaphore);
1479 splay_tree->next=GetFirstSplayTreeNode(splay_tree);
1480 UnlockSemaphoreInfo(splay_tree->semaphore);
1484 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1488 % S p l a y S p l a y T r e e %
1492 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1494 % SplaySplayTree() splays the splay-tree.
1496 % The format of the SplaySplayTree method is:
1498 % void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key,
1499 % NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1501 % A description of each parameter follows:
1503 % o splay_tree: the splay-tree info.
1509 % o parent: the parent node.
1511 % o grandparent: the grandparent node.
1515 static NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth,
1516 const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1529 if (n == (NodeInfo *) NULL)
1531 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1532 compare=splay_tree->compare(n->key,key);
1534 compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
1535 next=(NodeInfo **) NULL;
1541 if (next != (NodeInfo **) NULL)
1543 if (depth >= MaxSplayTreeDepth)
1545 splay_tree->balance=MagickTrue;
1548 n=Splay(splay_tree,depth+1,key,next,node,parent);
1549 if ((n != *node) || (splay_tree->balance != MagickFalse))
1552 if (parent == (NodeInfo **) NULL)
1554 if (grandparent == (NodeInfo **) NULL)
1556 if (n == (*parent)->left)
1569 if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
1572 (*grandparent)->left=p->right;
1573 p->right=(*grandparent);
1579 if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
1582 (*grandparent)->right=p->left;
1583 p->left=(*grandparent);
1589 if (n == (*parent)->left)
1591 (*parent)->left=n->right;
1593 (*grandparent)->right=n->left;
1594 n->left=(*grandparent);
1598 (*parent)->right=n->left;
1600 (*grandparent)->left=n->right;
1601 n->right=(*grandparent);
1606 static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key)
1608 if (splay_tree->root == (NodeInfo *) NULL)
1610 if (splay_tree->key != (void *) NULL)
1615 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1616 compare=splay_tree->compare(splay_tree->root->key,key);
1618 compare=(splay_tree->key > key) ? 1 :
1619 ((splay_tree->key < key) ? -1 : 0);
1623 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1624 (NodeInfo **) NULL);
1625 if (splay_tree->balance != MagickFalse)
1627 BalanceSplayTree(splay_tree);
1628 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1629 (NodeInfo **) NULL);
1630 if (splay_tree->balance != MagickFalse)
1631 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1633 splay_tree->key=(void *) key;