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