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