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-2016 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/locale_.h"
55 #include "MagickCore/log.h"
56 #include "MagickCore/memory_.h"
57 #include "MagickCore/splay-tree.h"
58 #include "MagickCore/semaphore.h"
59 #include "MagickCore/string_.h"
64 #define MaxSplayTreeDepth 1024
69 typedef struct _NodeInfo
88 (*compare)(const void *,const void *);
91 *(*relinquish_key)(void *),
92 *(*relinquish_value)(void *);
115 Forward declarations.
118 IterateOverSplayTree(SplayTreeInfo *,int (*)(NodeInfo *,const void *),
122 SplaySplayTree(SplayTreeInfo *,const void *);
125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
129 % A d d V a l u e T o S p l a y T r e e %
133 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
135 % AddValueToSplayTree() adds the given key and value to the splay-tree. Both
136 % key and value are used as is, without coping or cloning. It returns
137 % MagickTrue on success, otherwise MagickFalse.
139 % The format of the AddValueToSplayTree method is:
141 % MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
142 % const void *key,const void *value)
144 % A description of each parameter follows:
146 % o splay_tree: the splay-tree info.
150 % o value: the value.
153 MagickExport MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
154 const void *key,const void *value)
162 LockSemaphoreInfo(splay_tree->semaphore);
163 SplaySplayTree(splay_tree,key);
165 if (splay_tree->root != (NodeInfo *) NULL)
167 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
168 compare=splay_tree->compare(splay_tree->root->key,key);
170 compare=(splay_tree->root->key > key) ? 1 :
171 ((splay_tree->root->key < key) ? -1 : 0);
174 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
175 (splay_tree->root->value != (void *) NULL))
176 splay_tree->root->value=splay_tree->relinquish_value(
177 splay_tree->root->value);
178 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
179 (splay_tree->root->key != (void *) NULL))
180 splay_tree->root->key=splay_tree->relinquish_key(
181 splay_tree->root->key);
182 splay_tree->root->key=(void *) key;
183 splay_tree->root->value=(void *) value;
184 UnlockSemaphoreInfo(splay_tree->semaphore);
188 node=(NodeInfo *) AcquireMagickMemory(sizeof(*node));
189 if (node == (NodeInfo *) NULL)
191 UnlockSemaphoreInfo(splay_tree->semaphore);
194 node->key=(void *) key;
195 node->value=(void *) value;
196 if (splay_tree->root == (NodeInfo *) NULL)
198 node->left=(NodeInfo *) NULL;
199 node->right=(NodeInfo *) NULL;
204 node->left=splay_tree->root;
205 node->right=node->left->right;
206 node->left->right=(NodeInfo *) NULL;
210 node->right=splay_tree->root;
211 node->left=node->right->left;
212 node->right->left=(NodeInfo *) NULL;
214 splay_tree->root=node;
215 splay_tree->key=(void *) NULL;
217 UnlockSemaphoreInfo(splay_tree->semaphore);
222 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
226 % B a l a n c e S p l a y T r e e %
230 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
232 % BalanceSplayTree() balances the splay-tree.
234 % The format of the BalanceSplayTree method is:
236 % void *BalanceSplayTree(SplayTreeInfo *splay_tree,const void *key)
238 % A description of each parameter follows:
240 % o splay_tree: the splay-tree info.
246 static NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const size_t low,
255 bisect=low+(high-low)/2;
257 if ((low+1) > bisect)
258 node->left=(NodeInfo *) NULL;
260 node->left=LinkSplayTreeNodes(nodes,low,bisect-1);
261 if ((bisect+1) > high)
262 node->right=(NodeInfo *) NULL;
264 node->right=LinkSplayTreeNodes(nodes,bisect+1,high);
268 static inline int SplayTreeToNodeArray(NodeInfo *node,const void *nodes)
270 register const NodeInfo
273 p=(const NodeInfo ***) nodes;
279 static void BalanceSplayTree(SplayTreeInfo *splay_tree)
285 if (splay_tree->nodes <= 2)
287 splay_tree->balance=MagickFalse;
290 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
292 if (nodes == (NodeInfo **) NULL)
293 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
295 (void) IterateOverSplayTree(splay_tree,SplayTreeToNodeArray,(const void *)
297 splay_tree->root=LinkSplayTreeNodes(nodes,0,splay_tree->nodes-1);
298 splay_tree->balance=MagickFalse;
299 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
303 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
307 % C l o n e S p l a y T r e e %
311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
313 % CloneSplayTree() clones the splay tree.
315 % The format of the CloneSplayTree method is:
317 % SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
318 % void *(*clone_key)(void *),void *(*clone_value)(void *))
320 % A description of each parameter follows:
322 % o splay_tree: the splay tree.
324 % o clone_key: the key clone method, typically ConstantString(), called
325 % whenever a key is added to the splay-tree.
327 % o clone_value: the value clone method; typically ConstantString(), called
328 % whenever a value object is added to the splay-tree.
332 static inline void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree)
337 node=splay_tree->root;
338 if (splay_tree->root == (NodeInfo *) NULL)
339 return((NodeInfo *) NULL);
340 while (node->left != (NodeInfo *) NULL)
345 MagickExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
346 void *(*clone_key)(void *),void *(*clone_value)(void *))
355 assert(splay_tree != (SplayTreeInfo *) NULL);
356 assert(splay_tree->signature == MagickCoreSignature);
357 if (splay_tree->debug != MagickFalse)
358 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
359 clone_tree=NewSplayTree(splay_tree->compare,splay_tree->relinquish_key,
360 splay_tree->relinquish_value);
361 LockSemaphoreInfo(splay_tree->semaphore);
362 if (splay_tree->root == (NodeInfo *) NULL)
364 UnlockSemaphoreInfo(splay_tree->semaphore);
367 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
368 while (next != (NodeInfo *) NULL)
370 SplaySplayTree(splay_tree,next);
371 (void) AddValueToSplayTree(clone_tree,clone_key(splay_tree->root->key),
372 clone_value(splay_tree->root->value));
373 next=(NodeInfo *) NULL;
374 node=splay_tree->root->right;
375 if (node != (NodeInfo *) NULL)
377 while (node->left != (NodeInfo *) NULL)
379 next=(NodeInfo *) node->key;
382 UnlockSemaphoreInfo(splay_tree->semaphore);
387 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
391 % C o m p a r e S p l a y T r e e S t r i n g %
395 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
397 % CompareSplayTreeString() method finds a node in a splay-tree based on the
398 % contents of a string.
400 % The format of the CompareSplayTreeString method is:
402 % int CompareSplayTreeString(const void *target,const void *source)
404 % A description of each parameter follows:
406 % o target: the target string.
408 % o source: the source string.
411 MagickExport int CompareSplayTreeString(const void *target,const void *source)
417 p=(const char *) target;
418 q=(const char *) source;
419 return(LocaleCompare(p,q));
423 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
427 % 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 %
431 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
433 % CompareSplayTreeStringInfo() finds a node in a splay-tree based on the
434 % contents of a string.
436 % The format of the CompareSplayTreeStringInfo method is:
438 % int CompareSplayTreeStringInfo(const void *target,const void *source)
440 % A description of each parameter follows:
442 % o target: the target string.
444 % o source: the source string.
447 MagickExport int CompareSplayTreeStringInfo(const void *target,
454 p=(const StringInfo *) target;
455 q=(const StringInfo *) source;
456 return(CompareStringInfo(p,q));
460 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
464 % 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 %
468 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
470 % DeleteNodeByValueFromSplayTree() deletes a node by value from the
473 % The format of the DeleteNodeByValueFromSplayTree method is:
475 % MagickBooleanType DeleteNodeByValueFromSplayTree(
476 % SplayTreeInfo *splay_tree,const void *value)
478 % A description of each parameter follows:
480 % o splay_tree: the splay-tree info.
482 % o value: the value.
485 MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree(
486 SplayTreeInfo *splay_tree,const void *value)
492 assert(splay_tree != (SplayTreeInfo *) NULL);
493 assert(splay_tree->signature == MagickCoreSignature);
494 if (splay_tree->debug != MagickFalse)
495 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
496 LockSemaphoreInfo(splay_tree->semaphore);
497 if (splay_tree->root == (NodeInfo *) NULL)
499 UnlockSemaphoreInfo(splay_tree->semaphore);
502 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
503 while (next != (NodeInfo *) NULL)
505 SplaySplayTree(splay_tree,next);
506 next=(NodeInfo *) NULL;
507 node=splay_tree->root->right;
508 if (node != (NodeInfo *) NULL)
510 while (node->left != (NodeInfo *) NULL)
512 next=(NodeInfo *) node->key;
514 if (splay_tree->root->value == value)
527 We found the node that matches the value; now delete it.
529 key=splay_tree->root->key;
530 SplaySplayTree(splay_tree,key);
531 splay_tree->key=(void *) NULL;
532 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
533 compare=splay_tree->compare(splay_tree->root->key,key);
535 compare=(splay_tree->root->key > key) ? 1 :
536 ((splay_tree->root->key < key) ? -1 : 0);
539 UnlockSemaphoreInfo(splay_tree->semaphore);
542 left=splay_tree->root->left;
543 right=splay_tree->root->right;
544 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
545 (splay_tree->root->value != (void *) NULL))
546 splay_tree->root->value=splay_tree->relinquish_value(
547 splay_tree->root->value);
548 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
549 (splay_tree->root->key != (void *) NULL))
550 splay_tree->root->key=splay_tree->relinquish_key(
551 splay_tree->root->key);
552 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
554 if (left == (NodeInfo *) NULL)
556 splay_tree->root=right;
557 UnlockSemaphoreInfo(splay_tree->semaphore);
560 splay_tree->root=left;
561 if (right != (NodeInfo *) NULL)
563 while (left->right != (NodeInfo *) NULL)
567 UnlockSemaphoreInfo(splay_tree->semaphore);
571 UnlockSemaphoreInfo(splay_tree->semaphore);
576 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
580 % D e l e t e N o d e F r o m S p l a y T r e e %
584 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
586 % DeleteNodeFromSplayTree() deletes a node from the splay-tree. It returns
587 % MagickTrue if the option is found and successfully deleted from the
590 % The format of the DeleteNodeFromSplayTree method is:
592 % MagickBooleanType DeleteNodeFromSplayTree(SplayTreeInfo *splay_tree,
595 % A description of each parameter follows:
597 % o splay_tree: the splay-tree info.
602 MagickExport MagickBooleanType DeleteNodeFromSplayTree(
603 SplayTreeInfo *splay_tree,const void *key)
612 assert(splay_tree != (SplayTreeInfo *) NULL);
613 assert(splay_tree->signature == MagickCoreSignature);
614 if (splay_tree->debug != MagickFalse)
615 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
616 if (splay_tree->root == (NodeInfo *) NULL)
618 LockSemaphoreInfo(splay_tree->semaphore);
619 SplaySplayTree(splay_tree,key);
620 splay_tree->key=(void *) NULL;
621 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
622 compare=splay_tree->compare(splay_tree->root->key,key);
624 compare=(splay_tree->root->key > key) ? 1 :
625 ((splay_tree->root->key < key) ? -1 : 0);
628 UnlockSemaphoreInfo(splay_tree->semaphore);
631 left=splay_tree->root->left;
632 right=splay_tree->root->right;
633 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
634 (splay_tree->root->value != (void *) NULL))
635 splay_tree->root->value=splay_tree->relinquish_value(
636 splay_tree->root->value);
637 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
638 (splay_tree->root->key != (void *) NULL))
639 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
640 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
642 if (left == (NodeInfo *) NULL)
644 splay_tree->root=right;
645 UnlockSemaphoreInfo(splay_tree->semaphore);
648 splay_tree->root=left;
649 if (right != (NodeInfo *) NULL)
651 while (left->right != (NodeInfo *) NULL)
655 UnlockSemaphoreInfo(splay_tree->semaphore);
660 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
664 % D e s t r o y S p l a y T r e e %
668 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
670 % DestroySplayTree() destroys the splay-tree.
672 % The format of the DestroySplayTree method is:
674 % SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
676 % A description of each parameter follows:
678 % o splay_tree: the splay tree.
681 MagickExport SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
690 LockSemaphoreInfo(splay_tree->semaphore);
691 if (splay_tree->root != (NodeInfo *) NULL)
693 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
694 (splay_tree->root->value != (void *) NULL))
695 splay_tree->root->value=splay_tree->relinquish_value(
696 splay_tree->root->value);
697 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
698 (splay_tree->root->key != (void *) NULL))
699 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
700 splay_tree->root->key=(void *) NULL;
701 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
704 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
706 if (active->left != (NodeInfo *) NULL)
708 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
709 (active->left->value != (void *) NULL))
710 active->left->value=splay_tree->relinquish_value(
711 active->left->value);
712 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
713 (active->left->key != (void *) NULL))
714 active->left->key=splay_tree->relinquish_key(active->left->key);
715 active->left->key=(void *) pend;
718 if (active->right != (NodeInfo *) NULL)
720 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
721 (active->right->value != (void *) NULL))
722 active->right->value=splay_tree->relinquish_value(
723 active->right->value);
724 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
725 (active->right->key != (void *) NULL))
726 active->right->key=splay_tree->relinquish_key(
728 active->right->key=(void *) pend;
732 active=(NodeInfo *) node->key;
733 node=(NodeInfo *) RelinquishMagickMemory(node);
737 splay_tree->signature=(~MagickCoreSignature);
738 UnlockSemaphoreInfo(splay_tree->semaphore);
739 RelinquishSemaphoreInfo(&splay_tree->semaphore);
740 splay_tree=(SplayTreeInfo *) RelinquishMagickMemory(splay_tree);
745 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
749 % G e t N e x t K e y I n S p l a y T r e e %
753 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
755 % GetNextKeyInSplayTree() gets the next key in the splay-tree.
757 % The format of the GetNextKeyInSplayTree method is:
759 % const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
761 % A description of each parameter follows:
763 % o splay_tree: the splay tree.
768 MagickExport const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
776 assert(splay_tree != (SplayTreeInfo *) NULL);
777 assert(splay_tree->signature == MagickCoreSignature);
778 if (splay_tree->debug != MagickFalse)
779 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
780 if ((splay_tree->root == (NodeInfo *) NULL) ||
781 (splay_tree->next == (void *) NULL))
782 return((void *) NULL);
783 LockSemaphoreInfo(splay_tree->semaphore);
784 SplaySplayTree(splay_tree,splay_tree->next);
785 splay_tree->next=(void *) NULL;
786 node=splay_tree->root->right;
787 if (node != (NodeInfo *) NULL)
789 while (node->left != (NodeInfo *) NULL)
791 splay_tree->next=node->key;
793 key=splay_tree->root->key;
794 UnlockSemaphoreInfo(splay_tree->semaphore);
799 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
803 % G e t N e x t V a l u e I n S p l a y T r e e %
807 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
809 % GetNextValueInSplayTree() gets the next value in the splay-tree.
811 % The format of the GetNextValueInSplayTree method is:
813 % const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
815 % A description of each parameter follows:
817 % o splay_tree: the splay tree.
822 MagickExport const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
830 assert(splay_tree != (SplayTreeInfo *) NULL);
831 assert(splay_tree->signature == MagickCoreSignature);
832 if (splay_tree->debug != MagickFalse)
833 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
834 if ((splay_tree->root == (NodeInfo *) NULL) ||
835 (splay_tree->next == (void *) NULL))
836 return((void *) NULL);
837 LockSemaphoreInfo(splay_tree->semaphore);
838 SplaySplayTree(splay_tree,splay_tree->next);
839 splay_tree->next=(void *) NULL;
840 node=splay_tree->root->right;
841 if (node != (NodeInfo *) NULL)
843 while (node->left != (NodeInfo *) NULL)
845 splay_tree->next=node->key;
847 value=splay_tree->root->value;
848 UnlockSemaphoreInfo(splay_tree->semaphore);
853 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
857 % G e t V a l u e F r o m S p l a y T r e e %
861 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
863 % GetValueFromSplayTree() gets a value from the splay-tree by its key.
865 % Note, the value is a constant. Do not attempt to free it.
867 % The format of the GetValueFromSplayTree method is:
869 % const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
872 % A description of each parameter follows:
874 % o splay_tree: the splay tree.
879 MagickExport const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
888 assert(splay_tree != (SplayTreeInfo *) NULL);
889 assert(splay_tree->signature == MagickCoreSignature);
890 if (splay_tree->debug != MagickFalse)
891 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
892 if (splay_tree->root == (NodeInfo *) NULL)
893 return((void *) NULL);
894 LockSemaphoreInfo(splay_tree->semaphore);
895 SplaySplayTree(splay_tree,key);
896 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
897 compare=splay_tree->compare(splay_tree->root->key,key);
899 compare=(splay_tree->root->key > key) ? 1 :
900 ((splay_tree->root->key < key) ? -1 : 0);
903 UnlockSemaphoreInfo(splay_tree->semaphore);
904 return((void *) NULL);
906 value=splay_tree->root->value;
907 UnlockSemaphoreInfo(splay_tree->semaphore);
912 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
916 % 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 %
920 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
922 % GetNumberOfNodesInSplayTree() returns the number of nodes in the splay-tree.
924 % The format of the GetNumberOfNodesInSplayTree method is:
926 % size_t GetNumberOfNodesInSplayTree(
927 % const SplayTreeInfo *splay_tree)
929 % A description of each parameter follows:
931 % o splay_tree: the splay tree.
934 MagickExport size_t GetNumberOfNodesInSplayTree(
935 const SplayTreeInfo *splay_tree)
937 assert(splay_tree != (SplayTreeInfo *) NULL);
938 assert(splay_tree->signature == MagickCoreSignature);
939 if (splay_tree->debug != MagickFalse)
940 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
941 return(splay_tree->nodes);
945 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
949 % I t e r a t e O v e r S p l a y T r e e %
953 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
955 % IterateOverSplayTree() iterates over the splay-tree.
957 % The format of the IterateOverSplayTree method is:
959 % int IterateOverSplayTree(SplayTreeInfo *splay_tree,
960 % int (*method)(NodeInfo *,void *),const void *value)
962 % A description of each parameter follows:
964 % o splay_tree: the splay-tree info.
966 % o method: the method.
968 % o value: the value.
971 static int IterateOverSplayTree(SplayTreeInfo *splay_tree,
972 int (*method)(NodeInfo *,const void *),const void *value)
1003 if (splay_tree->root == (NodeInfo *) NULL)
1005 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
1007 transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes,
1008 sizeof(*transitions));
1009 if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL))
1010 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1012 final_transition=MagickFalse;
1013 nodes[0]=splay_tree->root;
1014 transitions[0]=(unsigned char) LeftTransition;
1015 for (i=0; final_transition == MagickFalse; )
1018 transition=(TransitionType) transitions[i];
1021 case LeftTransition:
1023 transitions[i]=(unsigned char) DownTransition;
1024 if (node->left == (NodeInfo *) NULL)
1027 nodes[i]=node->left;
1028 transitions[i]=(unsigned char) LeftTransition;
1031 case RightTransition:
1033 transitions[i]=(unsigned char) UpTransition;
1034 if (node->right == (NodeInfo *) NULL)
1037 nodes[i]=node->right;
1038 transitions[i]=(unsigned char) LeftTransition;
1041 case DownTransition:
1044 transitions[i]=(unsigned char) RightTransition;
1045 status=(*method)(node,value);
1047 final_transition=MagickTrue;
1054 final_transition=MagickTrue;
1062 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
1063 transitions=(unsigned char *) RelinquishMagickMemory(transitions);
1068 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1072 % N e w S p l a y T r e e %
1076 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1078 % NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized
1079 % to default values.
1081 % The format of the NewSplayTree method is:
1083 % SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *),
1084 % void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1086 % A description of each parameter follows:
1088 % o compare: the compare method.
1090 % o relinquish_key: the key deallocation method, typically
1091 % RelinquishMagickMemory(), called whenever a key is removed from the
1094 % o relinquish_value: the value deallocation method; typically
1095 % RelinquishMagickMemory(), called whenever a value object is removed from
1099 MagickExport SplayTreeInfo *NewSplayTree(
1100 int (*compare)(const void *,const void *),void *(*relinquish_key)(void *),
1101 void *(*relinquish_value)(void *))
1106 splay_tree=(SplayTreeInfo *) AcquireMagickMemory(sizeof(*splay_tree));
1107 if (splay_tree == (SplayTreeInfo *) NULL)
1108 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1109 (void) ResetMagickMemory(splay_tree,0,sizeof(*splay_tree));
1110 splay_tree->root=(NodeInfo *) NULL;
1111 splay_tree->compare=compare;
1112 splay_tree->relinquish_key=relinquish_key;
1113 splay_tree->relinquish_value=relinquish_value;
1114 splay_tree->balance=MagickFalse;
1115 splay_tree->key=(void *) NULL;
1116 splay_tree->next=(void *) NULL;
1117 splay_tree->nodes=0;
1118 splay_tree->debug=IsEventLogging();
1119 splay_tree->semaphore=AcquireSemaphoreInfo();
1120 splay_tree->signature=MagickCoreSignature;
1125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1129 % 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 %
1133 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1135 % RemoveNodeByValueFromSplayTree() removes a node by value from the splay-tree
1136 % and returns its key.
1138 % The format of the RemoveNodeByValueFromSplayTree method is:
1140 % void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1141 % const void *value)
1143 % A description of each parameter follows:
1145 % o splay_tree: the splay-tree info.
1147 % o value: the value.
1150 MagickExport void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1160 assert(splay_tree != (SplayTreeInfo *) NULL);
1161 assert(splay_tree->signature == MagickCoreSignature);
1162 if (splay_tree->debug != MagickFalse)
1163 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1165 if (splay_tree->root == (NodeInfo *) NULL)
1167 LockSemaphoreInfo(splay_tree->semaphore);
1168 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
1169 while (next != (NodeInfo *) NULL)
1171 SplaySplayTree(splay_tree,next);
1172 next=(NodeInfo *) NULL;
1173 node=splay_tree->root->right;
1174 if (node != (NodeInfo *) NULL)
1176 while (node->left != (NodeInfo *) NULL)
1178 next=(NodeInfo *) node->key;
1180 if (splay_tree->root->value == value)
1190 We found the node that matches the value; now remove it.
1192 key=splay_tree->root->key;
1193 SplaySplayTree(splay_tree,key);
1194 splay_tree->key=(void *) NULL;
1195 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1196 compare=splay_tree->compare(splay_tree->root->key,key);
1198 compare=(splay_tree->root->key > key) ? 1 :
1199 ((splay_tree->root->key < key) ? -1 : 0);
1202 UnlockSemaphoreInfo(splay_tree->semaphore);
1205 left=splay_tree->root->left;
1206 right=splay_tree->root->right;
1207 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1208 (splay_tree->root->value != (void *) NULL))
1209 splay_tree->root->value=splay_tree->relinquish_value(
1210 splay_tree->root->value);
1211 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1212 splay_tree->nodes--;
1213 if (left == (NodeInfo *) NULL)
1215 splay_tree->root=right;
1216 UnlockSemaphoreInfo(splay_tree->semaphore);
1219 splay_tree->root=left;
1220 if (right != (NodeInfo *) NULL)
1222 while (left->right != (NodeInfo *) NULL)
1226 UnlockSemaphoreInfo(splay_tree->semaphore);
1230 UnlockSemaphoreInfo(splay_tree->semaphore);
1235 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1239 % R e m o v e N o d e F r o m S p l a y T r e e %
1243 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1245 % RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its
1248 % The format of the RemoveNodeFromSplayTree method is:
1250 % void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key)
1252 % A description of each parameter follows:
1254 % o splay_tree: the splay-tree info.
1259 MagickExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,
1272 assert(splay_tree != (SplayTreeInfo *) NULL);
1273 assert(splay_tree->signature == MagickCoreSignature);
1274 if (splay_tree->debug != MagickFalse)
1275 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1276 value=(void *) NULL;
1277 if (splay_tree->root == (NodeInfo *) NULL)
1279 LockSemaphoreInfo(splay_tree->semaphore);
1280 SplaySplayTree(splay_tree,key);
1281 splay_tree->key=(void *) NULL;
1282 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1283 compare=splay_tree->compare(splay_tree->root->key,key);
1285 compare=(splay_tree->root->key > key) ? 1 :
1286 ((splay_tree->root->key < key) ? -1 : 0);
1289 UnlockSemaphoreInfo(splay_tree->semaphore);
1292 left=splay_tree->root->left;
1293 right=splay_tree->root->right;
1294 value=splay_tree->root->value;
1295 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1296 (splay_tree->root->key != (void *) NULL))
1297 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1298 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1299 splay_tree->nodes--;
1300 if (left == (NodeInfo *) NULL)
1302 splay_tree->root=right;
1303 UnlockSemaphoreInfo(splay_tree->semaphore);
1306 splay_tree->root=left;
1307 if (right != (NodeInfo *) NULL)
1309 while (left->right != (NodeInfo *) NULL)
1313 UnlockSemaphoreInfo(splay_tree->semaphore);
1318 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1322 % R e s e t S p l a y T r e e %
1326 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1328 % ResetSplayTree() resets the splay-tree. That is, it deletes all the nodes
1331 % The format of the ResetSplayTree method is:
1333 % ResetSplayTree(SplayTreeInfo *splay_tree)
1335 % A description of each parameter follows:
1337 % o splay_tree: the splay tree.
1340 MagickExport void ResetSplayTree(SplayTreeInfo *splay_tree)
1349 assert(splay_tree != (SplayTreeInfo *) NULL);
1350 assert(splay_tree->signature == MagickCoreSignature);
1351 if (splay_tree->debug != MagickFalse)
1352 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1353 LockSemaphoreInfo(splay_tree->semaphore);
1354 if (splay_tree->root != (NodeInfo *) NULL)
1356 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1357 (splay_tree->root->value != (void *) NULL))
1358 splay_tree->root->value=splay_tree->relinquish_value(
1359 splay_tree->root->value);
1360 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1361 (splay_tree->root->key != (void *) NULL))
1362 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1363 splay_tree->root->key=(void *) NULL;
1364 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
1367 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
1369 if (active->left != (NodeInfo *) NULL)
1371 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1372 (active->left->value != (void *) NULL))
1373 active->left->value=splay_tree->relinquish_value(
1374 active->left->value);
1375 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1376 (active->left->key != (void *) NULL))
1377 active->left->key=splay_tree->relinquish_key(active->left->key);
1378 active->left->key=(void *) pend;
1381 if (active->right != (NodeInfo *) NULL)
1383 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1384 (active->right->value != (void *) NULL))
1385 active->right->value=splay_tree->relinquish_value(
1386 active->right->value);
1387 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1388 (active->right->key != (void *) NULL))
1389 active->right->key=splay_tree->relinquish_key(
1390 active->right->key);
1391 active->right->key=(void *) pend;
1395 active=(NodeInfo *) node->key;
1396 node=(NodeInfo *) RelinquishMagickMemory(node);
1400 splay_tree->root=(NodeInfo *) NULL;
1401 splay_tree->key=(void *) NULL;
1402 splay_tree->next=(void *) NULL;
1403 splay_tree->nodes=0;
1404 splay_tree->balance=MagickFalse;
1405 UnlockSemaphoreInfo(splay_tree->semaphore);
1409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1413 % R e s e t S p l a y T r e e I t e r a t o r %
1417 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1419 % ResetSplayTreeIterator() resets the splay-tree iterator. Use it in
1420 % conjunction with GetNextValueInSplayTree() to iterate over all the nodes in
1423 % The format of the ResetSplayTreeIterator method is:
1425 % ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1427 % A description of each parameter follows:
1429 % o splay_tree: the splay tree.
1432 MagickExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1434 assert(splay_tree != (SplayTreeInfo *) NULL);
1435 assert(splay_tree->signature == MagickCoreSignature);
1436 if (splay_tree->debug != MagickFalse)
1437 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1438 LockSemaphoreInfo(splay_tree->semaphore);
1439 splay_tree->next=GetFirstSplayTreeNode(splay_tree);
1440 UnlockSemaphoreInfo(splay_tree->semaphore);
1444 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1448 % S p l a y S p l a y T r e e %
1452 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1454 % SplaySplayTree() splays the splay-tree.
1456 % The format of the SplaySplayTree method is:
1458 % void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key,
1459 % NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1461 % A description of each parameter follows:
1463 % o splay_tree: the splay-tree info.
1469 % o parent: the parent node.
1471 % o grandparent: the grandparent node.
1475 static NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth,
1476 const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1489 if (n == (NodeInfo *) NULL)
1491 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1492 compare=splay_tree->compare(n->key,key);
1494 compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
1495 next=(NodeInfo **) NULL;
1501 if (next != (NodeInfo **) NULL)
1503 if (depth >= MaxSplayTreeDepth)
1505 splay_tree->balance=MagickTrue;
1508 n=Splay(splay_tree,depth+1,key,next,node,parent);
1509 if ((n != *node) || (splay_tree->balance != MagickFalse))
1512 if (parent == (NodeInfo **) NULL)
1514 if (grandparent == (NodeInfo **) NULL)
1516 if (n == (*parent)->left)
1529 if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
1532 (*grandparent)->left=p->right;
1533 p->right=(*grandparent);
1539 if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
1542 (*grandparent)->right=p->left;
1543 p->left=(*grandparent);
1549 if (n == (*parent)->left)
1551 (*parent)->left=n->right;
1553 (*grandparent)->right=n->left;
1554 n->left=(*grandparent);
1558 (*parent)->right=n->left;
1560 (*grandparent)->left=n->right;
1561 n->right=(*grandparent);
1566 static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key)
1568 if (splay_tree->root == (NodeInfo *) NULL)
1570 if (splay_tree->key != (void *) NULL)
1575 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1576 compare=splay_tree->compare(splay_tree->root->key,key);
1578 compare=(splay_tree->key > key) ? 1 :
1579 ((splay_tree->key < key) ? -1 : 0);
1583 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1584 (NodeInfo **) NULL);
1585 if (splay_tree->balance != MagickFalse)
1587 BalanceSplayTree(splay_tree);
1588 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1589 (NodeInfo **) NULL);
1590 if (splay_tree->balance != MagickFalse)
1591 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1593 splay_tree->key=(void *) key;