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