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