MagickCore 6.9.13
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
82struct _SplayTreeInfo
83{
84 NodeInfo
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
107 SemaphoreInfo
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
159 NodeInfo
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{
249 NodeInfo
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{
281 NodeInfo
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{
334 NodeInfo
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{
348 NodeInfo
349 *next,
350 *node;
351
352 SplayTreeInfo
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{
488 NodeInfo
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
519 NodeInfo
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
608 NodeInfo
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{
683 NodeInfo
684 *active,
685 *node,
686 *pend;
687
688 LockSemaphoreInfo(splay_tree->semaphore);
689 if (splay_tree->root != (NodeInfo *) NULL)
690 {
691 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
692 (splay_tree->root->value != (void *) NULL))
693 splay_tree->root->value=splay_tree->relinquish_value(
694 splay_tree->root->value);
695 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
696 (splay_tree->root->key != (void *) NULL))
697 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
698 splay_tree->root->key=(void *) NULL;
699 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
700 {
701 active=pend;
702 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
703 {
704 if (active->left != (NodeInfo *) NULL)
705 {
706 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
707 (active->left->value != (void *) NULL))
708 active->left->value=splay_tree->relinquish_value(
709 active->left->value);
710 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
711 (active->left->key != (void *) NULL))
712 active->left->key=splay_tree->relinquish_key(active->left->key);
713 active->left->key=(void *) pend;
714 pend=active->left;
715 }
716 if (active->right != (NodeInfo *) NULL)
717 {
718 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
719 (active->right->value != (void *) NULL))
720 active->right->value=splay_tree->relinquish_value(
721 active->right->value);
722 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
723 (active->right->key != (void *) NULL))
724 active->right->key=splay_tree->relinquish_key(
725 active->right->key);
726 active->right->key=(void *) pend;
727 pend=active->right;
728 }
729 node=active;
730 active=(NodeInfo *) node->key;
731 node=(NodeInfo *) RelinquishMagickMemory(node);
732 }
733 }
734 }
735 splay_tree->signature=(~MagickCoreSignature);
736 UnlockSemaphoreInfo(splay_tree->semaphore);
737 DestroySemaphoreInfo(&splay_tree->semaphore);
738 splay_tree=(SplayTreeInfo *) RelinquishMagickMemory(splay_tree);
739 return(splay_tree);
740}
741␌
742/*
743%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
744% %
745% %
746% %
747% G e t N e x t K e y I n S p l a y T r e e %
748% %
749% %
750% %
751%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
752%
753% GetNextKeyInSplayTree() gets the next key in the splay-tree.
754%
755% The format of the GetNextKeyInSplayTree method is:
756%
757% const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
758%
759% A description of each parameter follows:
760%
761% o splay_tree: the splay tree.
762%
763% o key: the key.
764%
765*/
766MagickExport const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
767{
768 NodeInfo
769 *node;
770
771 void
772 *key;
773
774 assert(splay_tree != (SplayTreeInfo *) NULL);
775 assert(splay_tree->signature == MagickCoreSignature);
776 if (IsEventLogging() != MagickFalse)
777 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
778 if ((splay_tree->root == (NodeInfo *) NULL) ||
779 (splay_tree->next == (void *) NULL))
780 return((void *) NULL);
781 LockSemaphoreInfo(splay_tree->semaphore);
782 SplaySplayTree(splay_tree,splay_tree->next);
783 splay_tree->next=(void *) NULL;
784 node=splay_tree->root->right;
785 if (node != (NodeInfo *) NULL)
786 {
787 while (node->left != (NodeInfo *) NULL)
788 node=node->left;
789 splay_tree->next=node->key;
790 }
791 key=splay_tree->root->key;
792 UnlockSemaphoreInfo(splay_tree->semaphore);
793 return(key);
794}
795␌
796/*
797%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
798% %
799% %
800% %
801% G e t N e x t V a l u e I n S p l a y T r e e %
802% %
803% %
804% %
805%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
806%
807% GetNextValueInSplayTree() gets the next value in the splay-tree.
808%
809% The format of the GetNextValueInSplayTree method is:
810%
811% const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
812%
813% A description of each parameter follows:
814%
815% o splay_tree: the splay tree.
816%
817% o key: the key.
818%
819*/
820MagickExport const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
821{
822 NodeInfo
823 *node;
824
825 void
826 *value;
827
828 assert(splay_tree != (SplayTreeInfo *) NULL);
829 assert(splay_tree->signature == MagickCoreSignature);
830 if (IsEventLogging() != MagickFalse)
831 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
832 if ((splay_tree->root == (NodeInfo *) NULL) ||
833 (splay_tree->next == (void *) NULL))
834 return((void *) NULL);
835 LockSemaphoreInfo(splay_tree->semaphore);
836 SplaySplayTree(splay_tree,splay_tree->next);
837 splay_tree->next=(void *) NULL;
838 node=splay_tree->root->right;
839 if (node != (NodeInfo *) NULL)
840 {
841 while (node->left != (NodeInfo *) NULL)
842 node=node->left;
843 splay_tree->next=node->key;
844 }
845 value=splay_tree->root->value;
846 UnlockSemaphoreInfo(splay_tree->semaphore);
847 return(value);
848}
849␌
850/*
851%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
852% %
853% %
854% %
855% 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 %
856% %
857% %
858% %
859%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
860%
861% GetRootValueFromSplayTree() gets the root value from the splay-tree.
862%
863% The format of the GetRootValueFromSplayTree method is:
864%
865% const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
866%
867% A description of each parameter follows:
868%
869% o splay_tree: the splay tree.
870%
871% o key: the key.
872%
873*/
874MagickExport const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
875{
876 const void
877 *value;
878
879 assert(splay_tree != (SplayTreeInfo *) NULL);
880 assert(splay_tree->signature == MagickCoreSignature);
881 if (IsEventLogging() != MagickFalse)
882 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
883 value=(const void *) NULL;
884 LockSemaphoreInfo(splay_tree->semaphore);
885 if (splay_tree->root != (NodeInfo *) NULL)
886 value=splay_tree->root->value;
887 UnlockSemaphoreInfo(splay_tree->semaphore);
888 return(value);
889}
890␌
891/*
892%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
893% %
894% %
895% %
896% G e t V a l u e F r o m S p l a y T r e e %
897% %
898% %
899% %
900%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
901%
902% GetValueFromSplayTree() gets a value from the splay-tree by its key.
903%
904% Note, the value is a constant. Do not attempt to free it.
905%
906% The format of the GetValueFromSplayTree method is:
907%
908% const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
909% const void *key)
910%
911% A description of each parameter follows:
912%
913% o splay_tree: the splay tree.
914%
915% o key: the key.
916%
917*/
918MagickExport const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
919 const void *key)
920{
921 int
922 compare;
923
924 void
925 *value;
926
927 assert(splay_tree != (SplayTreeInfo *) NULL);
928 assert(splay_tree->signature == MagickCoreSignature);
929 if (IsEventLogging() != MagickFalse)
930 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
931 if (splay_tree->root == (NodeInfo *) NULL)
932 return((void *) NULL);
933 LockSemaphoreInfo(splay_tree->semaphore);
934 SplaySplayTree(splay_tree,key);
935 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
936 compare=splay_tree->compare(splay_tree->root->key,key);
937 else
938 compare=(splay_tree->root->key > key) ? 1 :
939 ((splay_tree->root->key < key) ? -1 : 0);
940 if (compare != 0)
941 {
942 UnlockSemaphoreInfo(splay_tree->semaphore);
943 return((void *) NULL);
944 }
945 value=splay_tree->root->value;
946 UnlockSemaphoreInfo(splay_tree->semaphore);
947 return(value);
948}
949␌
950/*
951%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
952% %
953% %
954% %
955% 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 %
956% %
957% %
958% %
959%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
960%
961% GetNumberOfNodesInSplayTree() returns the number of nodes in the splay-tree.
962%
963% The format of the GetNumberOfNodesInSplayTree method is:
964%
965% size_t GetNumberOfNodesInSplayTree(
966% const SplayTreeInfo *splay_tree)
967%
968% A description of each parameter follows:
969%
970% o splay_tree: the splay tree.
971%
972*/
973MagickExport size_t GetNumberOfNodesInSplayTree(
974 const SplayTreeInfo *splay_tree)
975{
976 assert(splay_tree != (SplayTreeInfo *) NULL);
977 assert(splay_tree->signature == MagickCoreSignature);
978 if (IsEventLogging() != MagickFalse)
979 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
980 return(splay_tree->nodes);
981}
982␌
983/*
984%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
985% %
986% %
987% %
988% I t e r a t e O v e r S p l a y T r e e %
989% %
990% %
991% %
992%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
993%
994% IterateOverSplayTree() iterates over the splay-tree.
995%
996% The format of the IterateOverSplayTree method is:
997%
998% int IterateOverSplayTree(SplayTreeInfo *splay_tree,
999% int (*method)(NodeInfo *,void *),const void *value)
1000%
1001% A description of each parameter follows:
1002%
1003% o splay_tree: the splay-tree info.
1004%
1005% o method: the method.
1006%
1007% o value: the value.
1008%
1009*/
1010static int IterateOverSplayTree(SplayTreeInfo *splay_tree,
1011 int (*method)(NodeInfo *,const void *),const void *value)
1012{
1013 typedef enum
1014 {
1015 LeftTransition,
1016 RightTransition,
1017 DownTransition,
1018 UpTransition
1019 } TransitionType;
1020
1021 int
1022 status;
1023
1024 MagickBooleanType
1025 final_transition;
1026
1027 NodeInfo
1028 *node,
1029 **nodes;
1030
1031 ssize_t
1032 i;
1033
1034 TransitionType
1035 transition;
1036
1037 unsigned char
1038 *transitions;
1039
1040 if (splay_tree->root == (NodeInfo *) NULL)
1041 return(0);
1042 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
1043 sizeof(*nodes));
1044 transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes,
1045 sizeof(*transitions));
1046 if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL))
1047 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1048 status=0;
1049 final_transition=MagickFalse;
1050 nodes[0]=splay_tree->root;
1051 transitions[0]=(unsigned char) LeftTransition;
1052 for (i=0; final_transition == MagickFalse; )
1053 {
1054 node=nodes[i];
1055 transition=(TransitionType) transitions[i];
1056 switch (transition)
1057 {
1058 case LeftTransition:
1059 {
1060 transitions[i]=(unsigned char) DownTransition;
1061 if (node->left == (NodeInfo *) NULL)
1062 break;
1063 i++;
1064 nodes[i]=node->left;
1065 transitions[i]=(unsigned char) LeftTransition;
1066 break;
1067 }
1068 case RightTransition:
1069 {
1070 transitions[i]=(unsigned char) UpTransition;
1071 if (node->right == (NodeInfo *) NULL)
1072 break;
1073 i++;
1074 nodes[i]=node->right;
1075 transitions[i]=(unsigned char) LeftTransition;
1076 break;
1077 }
1078 case DownTransition:
1079 default:
1080 {
1081 transitions[i]=(unsigned char) RightTransition;
1082 status=(*method)(node,value);
1083 if (status != 0)
1084 final_transition=MagickTrue;
1085 break;
1086 }
1087 case UpTransition:
1088 {
1089 if (i == 0)
1090 {
1091 final_transition=MagickTrue;
1092 break;
1093 }
1094 i--;
1095 break;
1096 }
1097 }
1098 }
1099 nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
1100 transitions=(unsigned char *) RelinquishMagickMemory(transitions);
1101 return(status);
1102}
1103␌
1104/*
1105%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1106% %
1107% %
1108% %
1109% N e w S p l a y T r e e %
1110% %
1111% %
1112% %
1113%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1114%
1115% NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized
1116% to default values.
1117%
1118% The format of the NewSplayTree method is:
1119%
1120% SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *),
1121% void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1122%
1123% A description of each parameter follows:
1124%
1125% o compare: the compare method.
1126%
1127% o relinquish_key: the key deallocation method, typically
1128% RelinquishMagickMemory(), called whenever a key is removed from the
1129% splay-tree.
1130%
1131% o relinquish_value: the value deallocation method; typically
1132% RelinquishMagickMemory(), called whenever a value object is removed from
1133% the splay-tree.
1134%
1135*/
1136MagickExport SplayTreeInfo *NewSplayTree(
1137 int (*compare)(const void *,const void *),void *(*relinquish_key)(void *),
1138 void *(*relinquish_value)(void *))
1139{
1140 SplayTreeInfo
1141 *splay_tree;
1142
1143 splay_tree=(SplayTreeInfo *) AcquireMagickMemory(sizeof(*splay_tree));
1144 if (splay_tree == (SplayTreeInfo *) NULL)
1145 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1146 (void) memset(splay_tree,0,sizeof(*splay_tree));
1147 splay_tree->root=(NodeInfo *) NULL;
1148 splay_tree->compare=compare;
1149 splay_tree->relinquish_key=relinquish_key;
1150 splay_tree->relinquish_value=relinquish_value;
1151 splay_tree->balance=MagickFalse;
1152 splay_tree->key=(void *) NULL;
1153 splay_tree->next=(void *) NULL;
1154 splay_tree->nodes=0;
1155 splay_tree->debug=IsEventLogging();
1156 splay_tree->semaphore=AllocateSemaphoreInfo();
1157 splay_tree->signature=MagickCoreSignature;
1158 return(splay_tree);
1159}
1160␌
1161/*
1162%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1163% %
1164% %
1165% %
1166% 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 %
1167% %
1168% %
1169% %
1170%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1171%
1172% RemoveNodeByValueFromSplayTree() removes a node by value from the splay-tree
1173% and returns its key.
1174%
1175% The format of the RemoveNodeByValueFromSplayTree method is:
1176%
1177% void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1178% const void *value)
1179%
1180% A description of each parameter follows:
1181%
1182% o splay_tree: the splay-tree info.
1183%
1184% o value: the value.
1185%
1186*/
1187MagickExport void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1188 const void *value)
1189{
1190 NodeInfo
1191 *next,
1192 *node;
1193
1194 void
1195 *key;
1196
1197 assert(splay_tree != (SplayTreeInfo *) NULL);
1198 assert(splay_tree->signature == MagickCoreSignature);
1199 if (IsEventLogging() != MagickFalse)
1200 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1201 key=(void *) NULL;
1202 if (splay_tree->root == (NodeInfo *) NULL)
1203 return(key);
1204 LockSemaphoreInfo(splay_tree->semaphore);
1205 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
1206 while (next != (NodeInfo *) NULL)
1207 {
1208 SplaySplayTree(splay_tree,next);
1209 next=(NodeInfo *) NULL;
1210 node=splay_tree->root->right;
1211 if (node != (NodeInfo *) NULL)
1212 {
1213 while (node->left != (NodeInfo *) NULL)
1214 node=node->left;
1215 next=(NodeInfo *) node->key;
1216 }
1217 if (splay_tree->root->value == value)
1218 {
1219 int
1220 compare;
1221
1222 NodeInfo
1223 *left,
1224 *right;
1225
1226 /*
1227 We found the node that matches the value; now remove it.
1228 */
1229 key=splay_tree->root->key;
1230 SplaySplayTree(splay_tree,key);
1231 splay_tree->key=(void *) NULL;
1232 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1233 compare=splay_tree->compare(splay_tree->root->key,key);
1234 else
1235 compare=(splay_tree->root->key > key) ? 1 :
1236 ((splay_tree->root->key < key) ? -1 : 0);
1237 if (compare != 0)
1238 {
1239 UnlockSemaphoreInfo(splay_tree->semaphore);
1240 return(key);
1241 }
1242 left=splay_tree->root->left;
1243 right=splay_tree->root->right;
1244 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1245 (splay_tree->root->value != (void *) NULL))
1246 splay_tree->root->value=splay_tree->relinquish_value(
1247 splay_tree->root->value);
1248 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1249 splay_tree->nodes--;
1250 if (left == (NodeInfo *) NULL)
1251 {
1252 splay_tree->root=right;
1253 UnlockSemaphoreInfo(splay_tree->semaphore);
1254 return(key);
1255 }
1256 splay_tree->root=left;
1257 if (right != (NodeInfo *) NULL)
1258 {
1259 while (left->right != (NodeInfo *) NULL)
1260 left=left->right;
1261 left->right=right;
1262 }
1263 UnlockSemaphoreInfo(splay_tree->semaphore);
1264 return(key);
1265 }
1266 }
1267 UnlockSemaphoreInfo(splay_tree->semaphore);
1268 return(key);
1269}
1270␌
1271/*
1272%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1273% %
1274% %
1275% %
1276% R e m o v e N o d e F r o m S p l a y T r e e %
1277% %
1278% %
1279% %
1280%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1281%
1282% RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its
1283% value.
1284%
1285% The format of the RemoveNodeFromSplayTree method is:
1286%
1287% void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key)
1288%
1289% A description of each parameter follows:
1290%
1291% o splay_tree: the splay-tree info.
1292%
1293% o key: the key.
1294%
1295*/
1296MagickExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,
1297 const void *key)
1298{
1299 int
1300 compare;
1301
1302 NodeInfo
1303 *left,
1304 *right;
1305
1306 void
1307 *value;
1308
1309 assert(splay_tree != (SplayTreeInfo *) NULL);
1310 assert(splay_tree->signature == MagickCoreSignature);
1311 if (IsEventLogging() != MagickFalse)
1312 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1313 value=(void *) NULL;
1314 if (splay_tree->root == (NodeInfo *) NULL)
1315 return(value);
1316 LockSemaphoreInfo(splay_tree->semaphore);
1317 SplaySplayTree(splay_tree,key);
1318 splay_tree->key=(void *) NULL;
1319 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1320 compare=splay_tree->compare(splay_tree->root->key,key);
1321 else
1322 compare=(splay_tree->root->key > key) ? 1 :
1323 ((splay_tree->root->key < key) ? -1 : 0);
1324 if (compare != 0)
1325 {
1326 UnlockSemaphoreInfo(splay_tree->semaphore);
1327 return(value);
1328 }
1329 left=splay_tree->root->left;
1330 right=splay_tree->root->right;
1331 value=splay_tree->root->value;
1332 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1333 (splay_tree->root->key != (void *) NULL))
1334 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1335 splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1336 splay_tree->nodes--;
1337 if (left == (NodeInfo *) NULL)
1338 {
1339 splay_tree->root=right;
1340 UnlockSemaphoreInfo(splay_tree->semaphore);
1341 return(value);
1342 }
1343 splay_tree->root=left;
1344 if (right != (NodeInfo *) NULL)
1345 {
1346 while (left->right != (NodeInfo *) NULL)
1347 left=left->right;
1348 left->right=right;
1349 }
1350 UnlockSemaphoreInfo(splay_tree->semaphore);
1351 return(value);
1352}
1353␌
1354/*
1355%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1356% %
1357% %
1358% %
1359% R e s e t S p l a y T r e e %
1360% %
1361% %
1362% %
1363%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1364%
1365% ResetSplayTree() resets the splay-tree. That is, it deletes all the nodes
1366% from the tree.
1367%
1368% The format of the ResetSplayTree method is:
1369%
1370% ResetSplayTree(SplayTreeInfo *splay_tree)
1371%
1372% A description of each parameter follows:
1373%
1374% o splay_tree: the splay tree.
1375%
1376*/
1377MagickExport void ResetSplayTree(SplayTreeInfo *splay_tree)
1378{
1379 NodeInfo
1380 *active,
1381 *node,
1382 *pend;
1383
1384 assert(splay_tree != (SplayTreeInfo *) NULL);
1385 assert(splay_tree->signature == MagickCoreSignature);
1386 if (IsEventLogging() != MagickFalse)
1387 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1388 LockSemaphoreInfo(splay_tree->semaphore);
1389 if (splay_tree->root != (NodeInfo *) NULL)
1390 {
1391 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1392 (splay_tree->root->value != (void *) NULL))
1393 splay_tree->root->value=splay_tree->relinquish_value(
1394 splay_tree->root->value);
1395 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1396 (splay_tree->root->key != (void *) NULL))
1397 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1398 splay_tree->root->key=(void *) NULL;
1399 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
1400 {
1401 active=pend;
1402 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
1403 {
1404 if (active->left != (NodeInfo *) NULL)
1405 {
1406 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1407 (active->left->value != (void *) NULL))
1408 active->left->value=splay_tree->relinquish_value(
1409 active->left->value);
1410 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1411 (active->left->key != (void *) NULL))
1412 active->left->key=splay_tree->relinquish_key(active->left->key);
1413 active->left->key=(void *) pend;
1414 pend=active->left;
1415 }
1416 if (active->right != (NodeInfo *) NULL)
1417 {
1418 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1419 (active->right->value != (void *) NULL))
1420 active->right->value=splay_tree->relinquish_value(
1421 active->right->value);
1422 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1423 (active->right->key != (void *) NULL))
1424 active->right->key=splay_tree->relinquish_key(
1425 active->right->key);
1426 active->right->key=(void *) pend;
1427 pend=active->right;
1428 }
1429 node=active;
1430 active=(NodeInfo *) node->key;
1431 node=(NodeInfo *) RelinquishMagickMemory(node);
1432 }
1433 }
1434 }
1435 splay_tree->root=(NodeInfo *) NULL;
1436 splay_tree->key=(void *) NULL;
1437 splay_tree->next=(void *) NULL;
1438 splay_tree->nodes=0;
1439 splay_tree->balance=MagickFalse;
1440 UnlockSemaphoreInfo(splay_tree->semaphore);
1441}
1442␌
1443/*
1444%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1445% %
1446% %
1447% %
1448% R e s e t S p l a y T r e e I t e r a t o r %
1449% %
1450% %
1451% %
1452%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1453%
1454% ResetSplayTreeIterator() resets the splay-tree iterator. Use it in
1455% conjunction with GetNextValueInSplayTree() to iterate over all the nodes in
1456% the splay-tree.
1457%
1458% The format of the ResetSplayTreeIterator method is:
1459%
1460% ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1461%
1462% A description of each parameter follows:
1463%
1464% o splay_tree: the splay tree.
1465%
1466*/
1467MagickExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1468{
1469 assert(splay_tree != (SplayTreeInfo *) NULL);
1470 assert(splay_tree->signature == MagickCoreSignature);
1471 if (IsEventLogging() != MagickFalse)
1472 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1473 LockSemaphoreInfo(splay_tree->semaphore);
1474 splay_tree->next=GetFirstSplayTreeNode(splay_tree);
1475 UnlockSemaphoreInfo(splay_tree->semaphore);
1476}
1477␌
1478/*
1479%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1480% %
1481% %
1482% %
1483% S p l a y S p l a y T r e e %
1484% %
1485% %
1486% %
1487%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1488%
1489% SplaySplayTree() splays the splay-tree.
1490%
1491% The format of the SplaySplayTree method is:
1492%
1493% void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key,
1494% NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1495%
1496% A description of each parameter follows:
1497%
1498% o splay_tree: the splay-tree info.
1499%
1500% o key: the key.
1501%
1502% o node: the node.
1503%
1504% o parent: the parent node.
1505%
1506% o grandparent: the grandparent node.
1507%
1508*/
1509
1510static NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth,
1511 const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1512{
1513 int
1514 compare;
1515
1516 NodeInfo
1517 *n,
1518 **next,
1519 *p;
1520
1521 n=(*node);
1522 if (n == (NodeInfo *) NULL)
1523 {
1524 if (parent != (NodeInfo **) NULL)
1525 return(*parent);
1526 else
1527 return((NodeInfo *) NULL);
1528 }
1529 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1530 compare=splay_tree->compare(n->key,key);
1531 else
1532 compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
1533 next=(NodeInfo **) NULL;
1534 if (compare > 0)
1535 next=(&n->left);
1536 else
1537 if (compare < 0)
1538 next=(&n->right);
1539 if (next != (NodeInfo **) NULL)
1540 {
1541 if (depth >= MaxSplayTreeDepth)
1542 {
1543 splay_tree->balance=MagickTrue;
1544 return(n);
1545 }
1546 n=Splay(splay_tree,depth+1,key,next,node,parent);
1547 if ((n != *node) || (splay_tree->balance != MagickFalse))
1548 return(n);
1549 }
1550 if (parent == (NodeInfo **) NULL)
1551 return(n);
1552 if (grandparent == (NodeInfo **) NULL)
1553 {
1554 if (n == (*parent)->left)
1555 {
1556 *node=n->right;
1557 n->right=(*parent);
1558 }
1559 else
1560 {
1561 *node=n->left;
1562 n->left=(*parent);
1563 }
1564 *parent=n;
1565 return(n);
1566 }
1567 if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
1568 {
1569 p=(*parent);
1570 (*grandparent)->left=p->right;
1571 p->right=(*grandparent);
1572 p->left=n->right;
1573 n->right=p;
1574 *grandparent=n;
1575 return(n);
1576 }
1577 if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
1578 {
1579 p=(*parent);
1580 (*grandparent)->right=p->left;
1581 p->left=(*grandparent);
1582 p->right=n->left;
1583 n->left=p;
1584 *grandparent=n;
1585 return(n);
1586 }
1587 if (n == (*parent)->left)
1588 {
1589 (*parent)->left=n->right;
1590 n->right=(*parent);
1591 (*grandparent)->right=n->left;
1592 n->left=(*grandparent);
1593 *grandparent=n;
1594 return(n);
1595 }
1596 (*parent)->right=n->left;
1597 n->left=(*parent);
1598 (*grandparent)->left=n->right;
1599 n->right=(*grandparent);
1600 *grandparent=n;
1601 return(n);
1602}
1603
1604static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key)
1605{
1606 if (splay_tree->root == (NodeInfo *) NULL)
1607 return;
1608 if (splay_tree->key != (void *) NULL)
1609 {
1610 int
1611 compare;
1612
1613 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1614 compare=splay_tree->compare(splay_tree->root->key,key);
1615 else
1616 compare=(splay_tree->key > key) ? 1 :
1617 ((splay_tree->key < key) ? -1 : 0);
1618 if (compare == 0)
1619 return;
1620 }
1621 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1622 (NodeInfo **) NULL);
1623 if (splay_tree->balance != MagickFalse)
1624 {
1625 BalanceSplayTree(splay_tree);
1626 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1627 (NodeInfo **) NULL);
1628 if (splay_tree->balance != MagickFalse)
1629 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1630 }
1631 splay_tree->key=(void *) key;
1632}
_NodeInfo
Definition splay-tree.c:70
_SplayTreeInfo
Definition splay-tree.c:83