MagickCore 6.9.13-14
Convert, Edit, Or Compose Bitmap Images
Loading...
Searching...
No Matches
splay-tree.c
1/*
2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3% %
4% %
5% %
6% SSSSS PPPP L AAA Y Y %
7% SS P P L A A Y Y %
8% SSS PPPP L AAAAA Y %
9% SS P L A A Y %
10% SSSSS P LLLLL A A Y %
11% %
12% TTTTT RRRR EEEEE EEEEE %
13% T R R E E %
14% T RRRR EEE EEE %
15% T R R E E %
16% T R R EEEEE EEEEE %
17% %
18% %
19% MagickCore Self-adjusting Binary Search Tree Methods %
20% %
21% Software Design %
22% Cristy %
23% December 2002 %
24% %
25% %
26% Copyright 1999 ImageMagick Studio LLC, a non-profit organization %
27% dedicated to making software imaging solutions freely available. %
28% %
29% You may not use this file except in compliance with the License. You may %
30% obtain a copy of the License at %
31% %
32% https://imagemagick.org/script/license.php %
33% %
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. %
39% %
40%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
41%
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.
45%
46*/
47
48/*
49 Include declarations.
50*/
51#include "magick/studio.h"
52#include "magick/exception.h"
53#include "magick/exception-private.h"
54#include "magick/locale_.h"
55#include "magick/log.h"
56#include "magick/memory_.h"
57#include "magick/splay-tree.h"
58#include "magick/semaphore.h"
59#include "magick/string_.h"
60
61/*
62 Define declarations.
63*/
64#define MaxSplayTreeDepth 1024
65
66/*
67 Typedef declarations.
68*/
69typedef struct _NodeInfo
70{
71 void
72 *key;
73
74 void
75 *value;
76
77 struct _NodeInfo
78 *left,
79 *right;
80} NodeInfo;
81
83{
85 *root;
86
87 int
88 (*compare)(const void *,const void *);
89
90 void
91 *(*relinquish_key)(void *),
92 *(*relinquish_value)(void *);
93
94 MagickBooleanType
95 balance;
96
97 void
98 *key,
99 *next;
100
101 size_t
102 nodes;
103
104 MagickBooleanType
105 debug;
106
108 *semaphore;
109
110 size_t
111 signature;
112};
113
114/*
115 Forward declarations.
116*/
117static int
118 IterateOverSplayTree(SplayTreeInfo *,int (*)(NodeInfo *,const void *),
119 const void *);
120
121static void
122 SplaySplayTree(SplayTreeInfo *,const void *);
123
124/*
125%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
126% %
127% %
128% %
129% A d d V a l u e T o S p l a y T r e e %
130% %
131% %
132% %
133%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
134%
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.
138%
139% The format of the AddValueToSplayTree method is:
140%
141% MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
142% const void *key,const void *value)
143%
144% A description of each parameter follows:
145%
146% o splay_tree: the splay-tree info.
147%
148% o key: the key.
149%
150% o value: the value.
151%
152*/
153MagickExport MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
154 const void *key,const void *value)
155{
156 int
157 compare;
158
160 *node;
161
162 LockSemaphoreInfo(splay_tree->semaphore);
163 SplaySplayTree(splay_tree,key);
164 compare=0;
165 if (splay_tree->root != (NodeInfo *) NULL)
166 {
167 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
168 compare=splay_tree->compare(splay_tree->root->key,key);
169 else
170 compare=(splay_tree->root->key > key) ? 1 :
171 ((splay_tree->root->key < key) ? -1 : 0);
172 if (compare == 0)
173 {
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);
185 return(MagickTrue);
186 }
187 }
188 node=(NodeInfo *) AcquireMagickMemory(sizeof(*node));
189 if (node == (NodeInfo *) NULL)
190 {
191 UnlockSemaphoreInfo(splay_tree->semaphore);
192 return(MagickFalse);
193 }
194 node->key=(void *) key;
195 node->value=(void *) value;
196 if (splay_tree->root == (NodeInfo *) NULL)
197 {
198 node->left=(NodeInfo *) NULL;
199 node->right=(NodeInfo *) NULL;
200 }
201 else
202 if (compare < 0)
203 {
204 node->left=splay_tree->root;
205 node->right=node->left->right;
206 node->left->right=(NodeInfo *) NULL;
207 }
208 else
209 {
210 node->right=splay_tree->root;
211 node->left=node->right->left;
212 node->right->left=(NodeInfo *) NULL;
213 }
214 splay_tree->root=node;
215 splay_tree->key=(void *) NULL;
216 splay_tree->nodes++;
217 UnlockSemaphoreInfo(splay_tree->semaphore);
218 return(MagickTrue);
219}
220
221/*
222%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
223% %
224% %
225% %
226% B a l a n c e S p l a y T r e e %
227% %
228% %
229% %
230%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
231%
232% BalanceSplayTree() balances the splay-tree.
233%
234% The format of the BalanceSplayTree method is:
235%
236% void *BalanceSplayTree(SplayTreeInfo *splay_tree,const void *key)
237%
238% A description of each parameter follows:
239%
240% o splay_tree: the splay-tree info.
241%
242% o key: the key.
243%
244*/
245
246static NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const size_t low,
247 const size_t high)
248{
250 *node;
251
252 size_t
253 bisect;
254
255 bisect=low+(high-low)/2;
256 node=nodes[bisect];
257 if ((low+1) > bisect)
258 node->left=(NodeInfo *) NULL;
259 else
260 node->left=LinkSplayTreeNodes(nodes,low,bisect-1);
261 if ((bisect+1) > high)
262 node->right=(NodeInfo *) NULL;
263 else
264 node->right=LinkSplayTreeNodes(nodes,bisect+1,high);
265 return(node);
266}
267
268static inline int SplayTreeToNodeArray(NodeInfo *node,const void *nodes)
269{
270 const NodeInfo
271 ***p;
272
273 p=(const NodeInfo ***) nodes;
274 *(*p)=node;
275 (*p)++;
276 return(0);
277}
278
279static void BalanceSplayTree(SplayTreeInfo *splay_tree)
280{
282 **node,
283 **nodes;
284
285 if (splay_tree->nodes <= 2)
286 {
287 splay_tree->balance=MagickFalse;
288 return;
289 }
290 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
291 sizeof(*nodes));
292 if (nodes == (NodeInfo **) NULL)
293 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
294 node=nodes;
295 (void) IterateOverSplayTree(splay_tree,SplayTreeToNodeArray,(const void *)
296 &node);
297 splay_tree->root=LinkSplayTreeNodes(nodes,0,splay_tree->nodes-1);
298 splay_tree->balance=MagickFalse;
299 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
300}
301
302/*
303%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
304% %
305% %
306% %
307% C l o n e S p l a y T r e e %
308% %
309% %
310% %
311%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
312%
313% CloneSplayTree() clones the splay tree.
314%
315% The format of the CloneSplayTree method is:
316%
317% SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
318% void *(*clone_key)(void *),void *(*clone_value)(void *))
319%
320% A description of each parameter follows:
321%
322% o splay_tree: the splay tree.
323%
324% o clone_key: the key clone method, typically ConstantString(), called
325% whenever a key is added to the splay-tree.
326%
327% o clone_value: the value clone method; typically ConstantString(), called
328% whenever a value object is added to the splay-tree.
329%
330*/
331
332static inline void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree)
333{
335 *node;
336
337 node=splay_tree->root;
338 if (splay_tree->root == (NodeInfo *) NULL)
339 return((NodeInfo *) NULL);
340 while (node->left != (NodeInfo *) NULL)
341 node=node->left;
342 return(node->key);
343}
344
345MagickExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
346 void *(*clone_key)(void *),void *(*clone_value)(void *))
347{
349 *next,
350 *node;
351
353 *clone_tree;
354
355 assert(splay_tree != (SplayTreeInfo *) NULL);
356 assert(splay_tree->signature == MagickCoreSignature);
357 if (IsEventLogging() != 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)
363 {
364 UnlockSemaphoreInfo(splay_tree->semaphore);
365 return(clone_tree);
366 }
367 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
368 while (next != (NodeInfo *) NULL)
369 {
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)
376 {
377 while (node->left != (NodeInfo *) NULL)
378 node=node->left;
379 next=(NodeInfo *) node->key;
380 }
381 }
382 UnlockSemaphoreInfo(splay_tree->semaphore);
383 return(clone_tree);
384}
385
386/*
387%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
388% %
389% %
390% %
391% C o m p a r e S p l a y T r e e S t r i n g %
392% %
393% %
394% %
395%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
396%
397% CompareSplayTreeString() method finds a node in a splay-tree based on the
398% contents of a string.
399%
400% The format of the CompareSplayTreeString method is:
401%
402% int CompareSplayTreeString(const void *target,const void *source)
403%
404% A description of each parameter follows:
405%
406% o target: the target string.
407%
408% o source: the source string.
409%
410*/
411MagickExport int CompareSplayTreeString(const void *target,const void *source)
412{
413 const char
414 *p,
415 *q;
416
417 p=(const char *) target;
418 q=(const char *) source;
419 return(LocaleCompare(p,q));
420}
421
422/*
423%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
424% %
425% %
426% %
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 %
428% %
429% %
430% %
431%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
432%
433% CompareSplayTreeStringInfo() finds a node in a splay-tree based on the
434% contents of a string.
435%
436% The format of the CompareSplayTreeStringInfo method is:
437%
438% int CompareSplayTreeStringInfo(const void *target,const void *source)
439%
440% A description of each parameter follows:
441%
442% o target: the target string.
443%
444% o source: the source string.
445%
446*/
447MagickExport int CompareSplayTreeStringInfo(const void *target,
448 const void *source)
449{
450 const StringInfo
451 *p,
452 *q;
453
454 p=(const StringInfo *) target;
455 q=(const StringInfo *) source;
456 return(CompareStringInfo(p,q));
457}
458
459/*
460%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
461% %
462% %
463% %
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 %
465% %
466% %
467% %
468%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
469%
470% DeleteNodeByValueFromSplayTree() deletes a node by value from the
471% splay-tree.
472%
473% The format of the DeleteNodeByValueFromSplayTree method is:
474%
475% MagickBooleanType DeleteNodeByValueFromSplayTree(
476% SplayTreeInfo *splay_tree,const void *value)
477%
478% A description of each parameter follows:
479%
480% o splay_tree: the splay-tree info.
481%
482% o value: the value.
483%
484*/
485MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree(
486 SplayTreeInfo *splay_tree,const void *value)
487{
489 *next,
490 *node;
491
492 assert(splay_tree != (SplayTreeInfo *) NULL);
493 assert(splay_tree->signature == MagickCoreSignature);
494 if (IsEventLogging() != MagickFalse)
495 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
496 LockSemaphoreInfo(splay_tree->semaphore);
497 if (splay_tree->root == (NodeInfo *) NULL)
498 {
499 UnlockSemaphoreInfo(splay_tree->semaphore);
500 return(MagickFalse);
501 }
502 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
503 while (next != (NodeInfo *) NULL)
504 {
505 SplaySplayTree(splay_tree,next);
506 next=(NodeInfo *) NULL;
507 node=splay_tree->root->right;
508 if (node != (NodeInfo *) NULL)
509 {
510 while (node->left != (NodeInfo *) NULL)
511 node=node->left;
512 next=(NodeInfo *) node->key;
513 }
514 if (splay_tree->root->value == value)
515 {
516 int
517 compare;
518
520 *left,
521 *right;
522
523 void
524 *key;
525
526 /*
527 We found the node that matches the value; now delete it.
528 */
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);
534 else
535 compare=(splay_tree->root->key > key) ? 1 :
536 ((splay_tree->root->key < key) ? -1 : 0);
537 if (compare != 0)
538 {
539 UnlockSemaphoreInfo(splay_tree->semaphore);
540 return(MagickFalse);
541 }
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);
553 splay_tree->nodes--;
554 if (left == (NodeInfo *) NULL)
555 {
556 splay_tree->root=right;
557 UnlockSemaphoreInfo(splay_tree->semaphore);
558 return(MagickTrue);
559 }
560 splay_tree->root=left;
561 if (right != (NodeInfo *) NULL)
562 {
563 while (left->right != (NodeInfo *) NULL)
564 left=left->right;
565 left->right=right;
566 }
567 UnlockSemaphoreInfo(splay_tree->semaphore);
568 return(MagickTrue);
569 }
570 }
571 UnlockSemaphoreInfo(splay_tree->semaphore);
572 return(MagickFalse);
573}
574
575/*
576%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
577% %
578% %
579% %
580% D e l e t e N o d e F r o m S p l a y T r e e %
581% %
582% %
583% %
584%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
585%
586% DeleteNodeFromSplayTree() deletes a node from the splay-tree. It returns
587% MagickTrue if the option is found and successfully deleted from the
588% splay-tree.
589%
590% The format of the DeleteNodeFromSplayTree method is:
591%
592% MagickBooleanType DeleteNodeFromSplayTree(SplayTreeInfo *splay_tree,
593% const void *key)
594%
595% A description of each parameter follows:
596%
597% o splay_tree: the splay-tree info.
598%
599% o key: the key.
600%
601*/
602MagickExport MagickBooleanType DeleteNodeFromSplayTree(
603 SplayTreeInfo *splay_tree,const void *key)
604{
605 int
606 compare;
607
609 *left,
610 *right;
611
612 assert(splay_tree != (SplayTreeInfo *) NULL);
613 assert(splay_tree->signature == MagickCoreSignature);
614 if (IsEventLogging() != MagickFalse)
615 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
616 if (splay_tree->root == (NodeInfo *) NULL)
617 return(MagickFalse);
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);
623 else
624 compare=(splay_tree->root->key > key) ? 1 :
625 ((splay_tree->root->key < key) ? -1 : 0);
626 if (compare != 0)
627 {
628 UnlockSemaphoreInfo(splay_tree->semaphore);
629 return(MagickFalse);
630 }
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);
641 splay_tree->nodes--;
642 if (left == (NodeInfo *) NULL)
643 {
644 splay_tree->root=right;
645 UnlockSemaphoreInfo(splay_tree->semaphore);
646 return(MagickTrue);
647 }
648 splay_tree->root=left;
649 if (right != (NodeInfo *) NULL)
650 {
651 while (left->right != (NodeInfo *) NULL)
652 left=left->right;
653 left->right=right;
654 }
655 UnlockSemaphoreInfo(splay_tree->semaphore);
656 return(MagickTrue);
657}
658
659/*
660%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
661% %
662% %
663% %
664% D e s t r o y S p l a y T r e e %
665% %
666% %
667% %
668%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
669%
670% DestroySplayTree() destroys the splay-tree.
671%
672% The format of the DestroySplayTree method is:
673%
674% SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
675%
676% A description of each parameter follows:
677%
678% o splay_tree: the splay tree.
679%
680*/
681MagickExport SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
682{
684 *node;
685
687 *active,
688 *pend;
689
690 LockSemaphoreInfo(splay_tree->semaphore);
691 if (splay_tree->root != (NodeInfo *) NULL)
692 {
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; )
702 {
703 active=pend;
704 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
705 {
706 if (active->left != (NodeInfo *) NULL)
707 {
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;
716 pend=active->left;
717 }
718 if (active->right != (NodeInfo *) NULL)
719 {
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(
727 active->right->key);
728 active->right->key=(void *) pend;
729 pend=active->right;
730 }
731 node=active;
732 active=(NodeInfo *) node->key;
733 node=(NodeInfo *) RelinquishMagickMemory(node);
734 }
735 }
736 }
737 splay_tree->signature=(~MagickCoreSignature);
738 UnlockSemaphoreInfo(splay_tree->semaphore);
739 DestroySemaphoreInfo(&splay_tree->semaphore);
740 splay_tree=(SplayTreeInfo *) RelinquishMagickMemory(splay_tree);
741 return(splay_tree);
742}
743
744/*
745%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
746% %
747% %
748% %
749% G e t N e x t K e y I n S p l a y T r e e %
750% %
751% %
752% %
753%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
754%
755% GetNextKeyInSplayTree() gets the next key in the splay-tree.
756%
757% The format of the GetNextKeyInSplayTree method is:
758%
759% const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
760%
761% A description of each parameter follows:
762%
763% o splay_tree: the splay tree.
764%
765% o key: the key.
766%
767*/
768MagickExport const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
769{
771 *node;
772
773 void
774 *key;
775
776 assert(splay_tree != (SplayTreeInfo *) NULL);
777 assert(splay_tree->signature == MagickCoreSignature);
778 if (IsEventLogging() != 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)
788 {
789 while (node->left != (NodeInfo *) NULL)
790 node=node->left;
791 splay_tree->next=node->key;
792 }
793 key=splay_tree->root->key;
794 UnlockSemaphoreInfo(splay_tree->semaphore);
795 return(key);
796}
797
798/*
799%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
800% %
801% %
802% %
803% G e t N e x t V a l u e I n S p l a y T r e e %
804% %
805% %
806% %
807%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
808%
809% GetNextValueInSplayTree() gets the next value in the splay-tree.
810%
811% The format of the GetNextValueInSplayTree method is:
812%
813% const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
814%
815% A description of each parameter follows:
816%
817% o splay_tree: the splay tree.
818%
819% o key: the key.
820%
821*/
822MagickExport const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
823{
825 *node;
826
827 void
828 *value;
829
830 assert(splay_tree != (SplayTreeInfo *) NULL);
831 assert(splay_tree->signature == MagickCoreSignature);
832 if (IsEventLogging() != 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)
842 {
843 while (node->left != (NodeInfo *) NULL)
844 node=node->left;
845 splay_tree->next=node->key;
846 }
847 value=splay_tree->root->value;
848 UnlockSemaphoreInfo(splay_tree->semaphore);
849 return(value);
850}
851
852/*
853%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
854% %
855% %
856% %
857% 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 %
858% %
859% %
860% %
861%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
862%
863% GetRootValueFromSplayTree() gets the root value from the splay-tree.
864%
865% The format of the GetRootValueFromSplayTree method is:
866%
867% const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
868%
869% A description of each parameter follows:
870%
871% o splay_tree: the splay tree.
872%
873% o key: the key.
874%
875*/
876MagickExport const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
877{
878 const void
879 *value;
880
881 assert(splay_tree != (SplayTreeInfo *) NULL);
882 assert(splay_tree->signature == MagickCoreSignature);
883 if (IsEventLogging() != MagickFalse)
884 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
885 value=(const void *) NULL;
886 LockSemaphoreInfo(splay_tree->semaphore);
887 if (splay_tree->root != (NodeInfo *) NULL)
888 value=splay_tree->root->value;
889 UnlockSemaphoreInfo(splay_tree->semaphore);
890 return(value);
891}
892
893/*
894%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
895% %
896% %
897% %
898% G e t V a l u e F r o m S p l a y T r e e %
899% %
900% %
901% %
902%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
903%
904% GetValueFromSplayTree() gets a value from the splay-tree by its key.
905%
906% Note, the value is a constant. Do not attempt to free it.
907%
908% The format of the GetValueFromSplayTree method is:
909%
910% const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
911% const void *key)
912%
913% A description of each parameter follows:
914%
915% o splay_tree: the splay tree.
916%
917% o key: the key.
918%
919*/
920MagickExport const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
921 const void *key)
922{
923 int
924 compare;
925
926 void
927 *value;
928
929 assert(splay_tree != (SplayTreeInfo *) NULL);
930 assert(splay_tree->signature == MagickCoreSignature);
931 if (IsEventLogging() != MagickFalse)
932 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
933 if (splay_tree->root == (NodeInfo *) NULL)
934 return((void *) NULL);
935 LockSemaphoreInfo(splay_tree->semaphore);
936 SplaySplayTree(splay_tree,key);
937 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
938 compare=splay_tree->compare(splay_tree->root->key,key);
939 else
940 compare=(splay_tree->root->key > key) ? 1 :
941 ((splay_tree->root->key < key) ? -1 : 0);
942 if (compare != 0)
943 {
944 UnlockSemaphoreInfo(splay_tree->semaphore);
945 return((void *) NULL);
946 }
947 value=splay_tree->root->value;
948 UnlockSemaphoreInfo(splay_tree->semaphore);
949 return(value);
950}
951
952/*
953%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
954% %
955% %
956% %
957% 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 %
958% %
959% %
960% %
961%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
962%
963% GetNumberOfNodesInSplayTree() returns the number of nodes in the splay-tree.
964%
965% The format of the GetNumberOfNodesInSplayTree method is:
966%
967% size_t GetNumberOfNodesInSplayTree(
968% const SplayTreeInfo *splay_tree)
969%
970% A description of each parameter follows:
971%
972% o splay_tree: the splay tree.
973%
974*/
975MagickExport size_t GetNumberOfNodesInSplayTree(
976 const SplayTreeInfo *splay_tree)
977{
978 assert(splay_tree != (SplayTreeInfo *) NULL);
979 assert(splay_tree->signature == MagickCoreSignature);
980 if (IsEventLogging() != MagickFalse)
981 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
982 return(splay_tree->nodes);
983}
984
985/*
986%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
987% %
988% %
989% %
990% I t e r a t e O v e r S p l a y T r e e %
991% %
992% %
993% %
994%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
995%
996% IterateOverSplayTree() iterates over the splay-tree.
997%
998% The format of the IterateOverSplayTree method is:
999%
1000% int IterateOverSplayTree(SplayTreeInfo *splay_tree,
1001% int (*method)(NodeInfo *,void *),const void *value)
1002%
1003% A description of each parameter follows:
1004%
1005% o splay_tree: the splay-tree info.
1006%
1007% o method: the method.
1008%
1009% o value: the value.
1010%
1011*/
1012static int IterateOverSplayTree(SplayTreeInfo *splay_tree,
1013 int (*method)(NodeInfo *,const void *),const void *value)
1014{
1015 typedef enum
1016 {
1017 LeftTransition,
1018 RightTransition,
1019 DownTransition,
1020 UpTransition
1021 } TransitionType;
1022
1023 int
1024 status;
1025
1026 MagickBooleanType
1027 final_transition;
1028
1029 NodeInfo
1030 **nodes;
1031
1032 ssize_t
1033 i;
1034
1035 NodeInfo
1036 *node;
1037
1038 TransitionType
1039 transition;
1040
1041 unsigned char
1042 *transitions;
1043
1044 if (splay_tree->root == (NodeInfo *) NULL)
1045 return(0);
1046 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
1047 sizeof(*nodes));
1048 transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes,
1049 sizeof(*transitions));
1050 if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL))
1051 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1052 status=0;
1053 final_transition=MagickFalse;
1054 nodes[0]=splay_tree->root;
1055 transitions[0]=(unsigned char) LeftTransition;
1056 for (i=0; final_transition == MagickFalse; )
1057 {
1058 node=nodes[i];
1059 transition=(TransitionType) transitions[i];
1060 switch (transition)
1061 {
1062 case LeftTransition:
1063 {
1064 transitions[i]=(unsigned char) DownTransition;
1065 if (node->left == (NodeInfo *) NULL)
1066 break;
1067 i++;
1068 nodes[i]=node->left;
1069 transitions[i]=(unsigned char) LeftTransition;
1070 break;
1071 }
1072 case RightTransition:
1073 {
1074 transitions[i]=(unsigned char) UpTransition;
1075 if (node->right == (NodeInfo *) NULL)
1076 break;
1077 i++;
1078 nodes[i]=node->right;
1079 transitions[i]=(unsigned char) LeftTransition;
1080 break;
1081 }
1082 case DownTransition:
1083 default:
1084 {
1085 transitions[i]=(unsigned char) RightTransition;
1086 status=(*method)(node,value);
1087 if (status != 0)
1088 final_transition=MagickTrue;
1089 break;
1090 }
1091 case UpTransition:
1092 {
1093 if (i == 0)
1094 {
1095 final_transition=MagickTrue;
1096 break;
1097 }
1098 i--;
1099 break;
1100 }
1101 }
1102 }
1103 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
1104 transitions=(unsigned char *) RelinquishMagickMemory(transitions);
1105 return(status);
1106}
1107
1108/*
1109%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1110% %
1111% %
1112% %
1113% N e w S p l a y T r e e %
1114% %
1115% %
1116% %
1117%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1118%
1119% NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized
1120% to default values.
1121%
1122% The format of the NewSplayTree method is:
1123%
1124% SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *),
1125% void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1126%
1127% A description of each parameter follows:
1128%
1129% o compare: the compare method.
1130%
1131% o relinquish_key: the key deallocation method, typically
1132% RelinquishMagickMemory(), called whenever a key is removed from the
1133% splay-tree.
1134%
1135% o relinquish_value: the value deallocation method; typically
1136% RelinquishMagickMemory(), called whenever a value object is removed from
1137% the splay-tree.
1138%
1139*/
1140MagickExport SplayTreeInfo *NewSplayTree(
1141 int (*compare)(const void *,const void *),void *(*relinquish_key)(void *),
1142 void *(*relinquish_value)(void *))
1143{
1145 *splay_tree;
1146
1147 splay_tree=(SplayTreeInfo *) AcquireMagickMemory(sizeof(*splay_tree));
1148 if (splay_tree == (SplayTreeInfo *) NULL)
1149 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1150 (void) memset(splay_tree,0,sizeof(*splay_tree));
1151 splay_tree->root=(NodeInfo *) NULL;
1152 splay_tree->compare=compare;
1153 splay_tree->relinquish_key=relinquish_key;
1154 splay_tree->relinquish_value=relinquish_value;
1155 splay_tree->balance=MagickFalse;
1156 splay_tree->key=(void *) NULL;
1157 splay_tree->next=(void *) NULL;
1158 splay_tree->nodes=0;
1159 splay_tree->debug=IsEventLogging();
1160 splay_tree->semaphore=AllocateSemaphoreInfo();
1161 splay_tree->signature=MagickCoreSignature;
1162 return(splay_tree);
1163}
1164
1165/*
1166%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1167% %
1168% %
1169% %
1170% 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 %
1171% %
1172% %
1173% %
1174%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1175%
1176% RemoveNodeByValueFromSplayTree() removes a node by value from the splay-tree
1177% and returns its key.
1178%
1179% The format of the RemoveNodeByValueFromSplayTree method is:
1180%
1181% void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1182% const void *value)
1183%
1184% A description of each parameter follows:
1185%
1186% o splay_tree: the splay-tree info.
1187%
1188% o value: the value.
1189%
1190*/
1191MagickExport void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1192 const void *value)
1193{
1194 NodeInfo
1195 *next,
1196 *node;
1197
1198 void
1199 *key;
1200
1201 assert(splay_tree != (SplayTreeInfo *) NULL);
1202 assert(splay_tree->signature == MagickCoreSignature);
1203 if (IsEventLogging() != MagickFalse)
1204 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1205 key=(void *) NULL;
1206 if (splay_tree->root == (NodeInfo *) NULL)
1207 return(key);
1208 LockSemaphoreInfo(splay_tree->semaphore);
1209 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
1210 while (next != (NodeInfo *) NULL)
1211 {
1212 SplaySplayTree(splay_tree,next);
1213 next=(NodeInfo *) NULL;
1214 node=splay_tree->root->right;
1215 if (node != (NodeInfo *) NULL)
1216 {
1217 while (node->left != (NodeInfo *) NULL)
1218 node=node->left;
1219 next=(NodeInfo *) node->key;
1220 }
1221 if (splay_tree->root->value == value)
1222 {
1223 int
1224 compare;
1225
1226 NodeInfo
1227 *left,
1228 *right;
1229
1230 /*
1231 We found the node that matches the value; now remove it.
1232 */
1233 key=splay_tree->root->key;
1234 SplaySplayTree(splay_tree,key);
1235 splay_tree->key=(void *) NULL;
1236 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1237 compare=splay_tree->compare(splay_tree->root->key,key);
1238 else
1239 compare=(splay_tree->root->key > key) ? 1 :
1240 ((splay_tree->root->key < key) ? -1 : 0);
1241 if (compare != 0)
1242 {
1243 UnlockSemaphoreInfo(splay_tree->semaphore);
1244 return(key);
1245 }
1246 left=splay_tree->root->left;
1247 right=splay_tree->root->right;
1248 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1249 (splay_tree->root->value != (void *) NULL))
1250 splay_tree->root->value=splay_tree->relinquish_value(
1251 splay_tree->root->value);
1252 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1253 splay_tree->nodes--;
1254 if (left == (NodeInfo *) NULL)
1255 {
1256 splay_tree->root=right;
1257 UnlockSemaphoreInfo(splay_tree->semaphore);
1258 return(key);
1259 }
1260 splay_tree->root=left;
1261 if (right != (NodeInfo *) NULL)
1262 {
1263 while (left->right != (NodeInfo *) NULL)
1264 left=left->right;
1265 left->right=right;
1266 }
1267 UnlockSemaphoreInfo(splay_tree->semaphore);
1268 return(key);
1269 }
1270 }
1271 UnlockSemaphoreInfo(splay_tree->semaphore);
1272 return(key);
1273}
1274
1275/*
1276%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1277% %
1278% %
1279% %
1280% R e m o v e N o d e F r o m S p l a y T r e e %
1281% %
1282% %
1283% %
1284%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1285%
1286% RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its
1287% value.
1288%
1289% The format of the RemoveNodeFromSplayTree method is:
1290%
1291% void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key)
1292%
1293% A description of each parameter follows:
1294%
1295% o splay_tree: the splay-tree info.
1296%
1297% o key: the key.
1298%
1299*/
1300MagickExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,
1301 const void *key)
1302{
1303 int
1304 compare;
1305
1306 NodeInfo
1307 *left,
1308 *right;
1309
1310 void
1311 *value;
1312
1313 assert(splay_tree != (SplayTreeInfo *) NULL);
1314 assert(splay_tree->signature == MagickCoreSignature);
1315 if (IsEventLogging() != MagickFalse)
1316 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1317 value=(void *) NULL;
1318 if (splay_tree->root == (NodeInfo *) NULL)
1319 return(value);
1320 LockSemaphoreInfo(splay_tree->semaphore);
1321 SplaySplayTree(splay_tree,key);
1322 splay_tree->key=(void *) NULL;
1323 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1324 compare=splay_tree->compare(splay_tree->root->key,key);
1325 else
1326 compare=(splay_tree->root->key > key) ? 1 :
1327 ((splay_tree->root->key < key) ? -1 : 0);
1328 if (compare != 0)
1329 {
1330 UnlockSemaphoreInfo(splay_tree->semaphore);
1331 return(value);
1332 }
1333 left=splay_tree->root->left;
1334 right=splay_tree->root->right;
1335 value=splay_tree->root->value;
1336 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1337 (splay_tree->root->key != (void *) NULL))
1338 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1339 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1340 splay_tree->nodes--;
1341 if (left == (NodeInfo *) NULL)
1342 {
1343 splay_tree->root=right;
1344 UnlockSemaphoreInfo(splay_tree->semaphore);
1345 return(value);
1346 }
1347 splay_tree->root=left;
1348 if (right != (NodeInfo *) NULL)
1349 {
1350 while (left->right != (NodeInfo *) NULL)
1351 left=left->right;
1352 left->right=right;
1353 }
1354 UnlockSemaphoreInfo(splay_tree->semaphore);
1355 return(value);
1356}
1357
1358/*
1359%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1360% %
1361% %
1362% %
1363% R e s e t S p l a y T r e e %
1364% %
1365% %
1366% %
1367%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1368%
1369% ResetSplayTree() resets the splay-tree. That is, it deletes all the nodes
1370% from the tree.
1371%
1372% The format of the ResetSplayTree method is:
1373%
1374% ResetSplayTree(SplayTreeInfo *splay_tree)
1375%
1376% A description of each parameter follows:
1377%
1378% o splay_tree: the splay tree.
1379%
1380*/
1381MagickExport void ResetSplayTree(SplayTreeInfo *splay_tree)
1382{
1383 NodeInfo
1384 *node;
1385
1386 NodeInfo
1387 *active,
1388 *pend;
1389
1390 assert(splay_tree != (SplayTreeInfo *) NULL);
1391 assert(splay_tree->signature == MagickCoreSignature);
1392 if (IsEventLogging() != MagickFalse)
1393 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1394 LockSemaphoreInfo(splay_tree->semaphore);
1395 if (splay_tree->root != (NodeInfo *) NULL)
1396 {
1397 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1398 (splay_tree->root->value != (void *) NULL))
1399 splay_tree->root->value=splay_tree->relinquish_value(
1400 splay_tree->root->value);
1401 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1402 (splay_tree->root->key != (void *) NULL))
1403 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1404 splay_tree->root->key=(void *) NULL;
1405 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
1406 {
1407 active=pend;
1408 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
1409 {
1410 if (active->left != (NodeInfo *) NULL)
1411 {
1412 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1413 (active->left->value != (void *) NULL))
1414 active->left->value=splay_tree->relinquish_value(
1415 active->left->value);
1416 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1417 (active->left->key != (void *) NULL))
1418 active->left->key=splay_tree->relinquish_key(active->left->key);
1419 active->left->key=(void *) pend;
1420 pend=active->left;
1421 }
1422 if (active->right != (NodeInfo *) NULL)
1423 {
1424 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1425 (active->right->value != (void *) NULL))
1426 active->right->value=splay_tree->relinquish_value(
1427 active->right->value);
1428 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1429 (active->right->key != (void *) NULL))
1430 active->right->key=splay_tree->relinquish_key(
1431 active->right->key);
1432 active->right->key=(void *) pend;
1433 pend=active->right;
1434 }
1435 node=active;
1436 active=(NodeInfo *) node->key;
1437 node=(NodeInfo *) RelinquishMagickMemory(node);
1438 }
1439 }
1440 }
1441 splay_tree->root=(NodeInfo *) NULL;
1442 splay_tree->key=(void *) NULL;
1443 splay_tree->next=(void *) NULL;
1444 splay_tree->nodes=0;
1445 splay_tree->balance=MagickFalse;
1446 UnlockSemaphoreInfo(splay_tree->semaphore);
1447}
1448
1449/*
1450%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1451% %
1452% %
1453% %
1454% R e s e t S p l a y T r e e I t e r a t o r %
1455% %
1456% %
1457% %
1458%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1459%
1460% ResetSplayTreeIterator() resets the splay-tree iterator. Use it in
1461% conjunction with GetNextValueInSplayTree() to iterate over all the nodes in
1462% the splay-tree.
1463%
1464% The format of the ResetSplayTreeIterator method is:
1465%
1466% ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1467%
1468% A description of each parameter follows:
1469%
1470% o splay_tree: the splay tree.
1471%
1472*/
1473MagickExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1474{
1475 assert(splay_tree != (SplayTreeInfo *) NULL);
1476 assert(splay_tree->signature == MagickCoreSignature);
1477 if (IsEventLogging() != MagickFalse)
1478 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1479 LockSemaphoreInfo(splay_tree->semaphore);
1480 splay_tree->next=GetFirstSplayTreeNode(splay_tree);
1481 UnlockSemaphoreInfo(splay_tree->semaphore);
1482}
1483
1484/*
1485%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1486% %
1487% %
1488% %
1489% S p l a y S p l a y T r e e %
1490% %
1491% %
1492% %
1493%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1494%
1495% SplaySplayTree() splays the splay-tree.
1496%
1497% The format of the SplaySplayTree method is:
1498%
1499% void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key,
1500% NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1501%
1502% A description of each parameter follows:
1503%
1504% o splay_tree: the splay-tree info.
1505%
1506% o key: the key.
1507%
1508% o node: the node.
1509%
1510% o parent: the parent node.
1511%
1512% o grandparent: the grandparent node.
1513%
1514*/
1515
1516static NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth,
1517 const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1518{
1519 int
1520 compare;
1521
1522 NodeInfo
1523 **next;
1524
1525 NodeInfo
1526 *n,
1527 *p;
1528
1529 n=(*node);
1530 if (n == (NodeInfo *) NULL)
1531 {
1532 if (parent != (NodeInfo **) NULL)
1533 return(*parent);
1534 else
1535 return((NodeInfo *) NULL);
1536 }
1537 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1538 compare=splay_tree->compare(n->key,key);
1539 else
1540 compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
1541 next=(NodeInfo **) NULL;
1542 if (compare > 0)
1543 next=(&n->left);
1544 else
1545 if (compare < 0)
1546 next=(&n->right);
1547 if (next != (NodeInfo **) NULL)
1548 {
1549 if (depth >= MaxSplayTreeDepth)
1550 {
1551 splay_tree->balance=MagickTrue;
1552 return(n);
1553 }
1554 n=Splay(splay_tree,depth+1,key,next,node,parent);
1555 if ((n != *node) || (splay_tree->balance != MagickFalse))
1556 return(n);
1557 }
1558 if (parent == (NodeInfo **) NULL)
1559 return(n);
1560 if (grandparent == (NodeInfo **) NULL)
1561 {
1562 if (n == (*parent)->left)
1563 {
1564 *node=n->right;
1565 n->right=(*parent);
1566 }
1567 else
1568 {
1569 *node=n->left;
1570 n->left=(*parent);
1571 }
1572 *parent=n;
1573 return(n);
1574 }
1575 if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
1576 {
1577 p=(*parent);
1578 (*grandparent)->left=p->right;
1579 p->right=(*grandparent);
1580 p->left=n->right;
1581 n->right=p;
1582 *grandparent=n;
1583 return(n);
1584 }
1585 if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
1586 {
1587 p=(*parent);
1588 (*grandparent)->right=p->left;
1589 p->left=(*grandparent);
1590 p->right=n->left;
1591 n->left=p;
1592 *grandparent=n;
1593 return(n);
1594 }
1595 if (n == (*parent)->left)
1596 {
1597 (*parent)->left=n->right;
1598 n->right=(*parent);
1599 (*grandparent)->right=n->left;
1600 n->left=(*grandparent);
1601 *grandparent=n;
1602 return(n);
1603 }
1604 (*parent)->right=n->left;
1605 n->left=(*parent);
1606 (*grandparent)->left=n->right;
1607 n->right=(*grandparent);
1608 *grandparent=n;
1609 return(n);
1610}
1611
1612static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key)
1613{
1614 if (splay_tree->root == (NodeInfo *) NULL)
1615 return;
1616 if (splay_tree->key != (void *) NULL)
1617 {
1618 int
1619 compare;
1620
1621 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1622 compare=splay_tree->compare(splay_tree->root->key,key);
1623 else
1624 compare=(splay_tree->key > key) ? 1 :
1625 ((splay_tree->key < key) ? -1 : 0);
1626 if (compare == 0)
1627 return;
1628 }
1629 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1630 (NodeInfo **) NULL);
1631 if (splay_tree->balance != MagickFalse)
1632 {
1633 BalanceSplayTree(splay_tree);
1634 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1635 (NodeInfo **) NULL);
1636 if (splay_tree->balance != MagickFalse)
1637 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1638 }
1639 splay_tree->key=(void *) key;
1640}