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