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