MagickCore  6.9.12-67
Convert, Edit, Or Compose Bitmap Images
 All Data Structures
splay-tree.c
1 /*
2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3 % %
4 % %
5 % %
6 % SSSSS PPPP L AAA Y Y %
7 % SS P P L A A Y Y %
8 % SSS PPPP L AAAAA Y %
9 % SS P L A A Y %
10 % SSSSS P LLLLL A A Y %
11 % %
12 % TTTTT RRRR EEEEE EEEEE %
13 % T R R E E %
14 % T RRRR EEE EEE %
15 % T R R E E %
16 % T R R EEEEE EEEEE %
17 % %
18 % %
19 % MagickCore Self-adjusting Binary Search Tree Methods %
20 % %
21 % Software Design %
22 % Cristy %
23 % December 2002 %
24 % %
25 % %
26 % Copyright 1999-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 "magick/studio.h"
52 #include "magick/exception.h"
53 #include "magick/exception-private.h"
54 #include "magick/locale_.h"
55 #include "magick/log.h"
56 #include "magick/memory_.h"
57 #include "magick/splay-tree.h"
58 #include "magick/semaphore.h"
59 #include "magick/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 
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 
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 */
153 MagickExport MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree,
154  const void *key,const void *value)
155 {
156  int
157  compare;
158 
159  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 
246 static NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const size_t low,
247  const size_t high)
248 {
249  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 
268 static inline int SplayTreeToNodeArray(NodeInfo *node,const void *nodes)
269 {
270  const NodeInfo
271  ***p;
272 
273  p=(const NodeInfo ***) nodes;
274  *(*p)=node;
275  (*p)++;
276  return(0);
277 }
278 
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 *(*clone_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 
332 static inline void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree)
333 {
334  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 
345 MagickExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree,
346  void *(*clone_key)(void *),void *(*clone_value)(void *))
347 {
348  NodeInfo
349  *next,
350  *node;
351 
353  *clone_tree;
354 
355  assert(splay_tree != (SplayTreeInfo *) NULL);
356  assert(splay_tree->signature == MagickCoreSignature);
357  if (IsEventLogging() != 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 */
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 */
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 */
485 MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree(
486  SplayTreeInfo *splay_tree,const void *value)
487 {
488  NodeInfo
489  *next,
490  *node;
491 
492  assert(splay_tree != (SplayTreeInfo *) NULL);
493  assert(splay_tree->signature == MagickCoreSignature);
494  if (IsEventLogging() != 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  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 */
602 MagickExport MagickBooleanType DeleteNodeFromSplayTree(
603  SplayTreeInfo *splay_tree,const void *key)
604 {
605  int
606  compare;
607 
608  NodeInfo
609  *left,
610  *right;
611 
612  assert(splay_tree != (SplayTreeInfo *) NULL);
613  assert(splay_tree->signature == MagickCoreSignature);
614  if (IsEventLogging() != 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 */
681 MagickExport SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
682 {
683  NodeInfo
684  *node;
685 
686  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  DestroySemaphoreInfo(&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 */
768 MagickExport const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
769 {
770  NodeInfo
771  *node;
772 
773  void
774  *key;
775 
776  assert(splay_tree != (SplayTreeInfo *) NULL);
777  assert(splay_tree->signature == MagickCoreSignature);
778  if (IsEventLogging() != 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 */
822 MagickExport const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
823 {
824  NodeInfo
825  *node;
826 
827  void
828  *value;
829 
830  assert(splay_tree != (SplayTreeInfo *) NULL);
831  assert(splay_tree->signature == MagickCoreSignature);
832  if (IsEventLogging() != 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 R o o 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 % GetRootValueFromSplayTree() gets the root value from the splay-tree.
864 %
865 % The format of the GetRootValueFromSplayTree method is:
866 %
867 % const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
868 %
869 % A description of each parameter follows:
870 %
871 % o splay_tree: the splay tree.
872 %
873 % o key: the key.
874 %
875 */
876 MagickExport const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
877 {
878  const void
879  *value;
880 
881  assert(splay_tree != (SplayTreeInfo *) NULL);
882  assert(splay_tree->signature == MagickCoreSignature);
883  if (IsEventLogging() != MagickFalse)
884  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
885  value=(const void *) NULL;
886  LockSemaphoreInfo(splay_tree->semaphore);
887  if (splay_tree->root != (NodeInfo *) NULL)
888  value=splay_tree->root->value;
889  UnlockSemaphoreInfo(splay_tree->semaphore);
890  return(value);
891 }
892 
893 /*
894 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
895 % %
896 % %
897 % %
898 % G e t V a l u e F r o m S p l a y T r e e %
899 % %
900 % %
901 % %
902 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
903 %
904 % GetValueFromSplayTree() gets a value from the splay-tree by its key.
905 %
906 % Note, the value is a constant. Do not attempt to free it.
907 %
908 % The format of the GetValueFromSplayTree method is:
909 %
910 % const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
911 % const void *key)
912 %
913 % A description of each parameter follows:
914 %
915 % o splay_tree: the splay tree.
916 %
917 % o key: the key.
918 %
919 */
920 MagickExport const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
921  const void *key)
922 {
923  int
924  compare;
925 
926  void
927  *value;
928 
929  assert(splay_tree != (SplayTreeInfo *) NULL);
930  assert(splay_tree->signature == MagickCoreSignature);
931  if (IsEventLogging() != MagickFalse)
932  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
933  if (splay_tree->root == (NodeInfo *) NULL)
934  return((void *) NULL);
935  LockSemaphoreInfo(splay_tree->semaphore);
936  SplaySplayTree(splay_tree,key);
937  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
938  compare=splay_tree->compare(splay_tree->root->key,key);
939  else
940  compare=(splay_tree->root->key > key) ? 1 :
941  ((splay_tree->root->key < key) ? -1 : 0);
942  if (compare != 0)
943  {
944  UnlockSemaphoreInfo(splay_tree->semaphore);
945  return((void *) NULL);
946  }
947  value=splay_tree->root->value;
948  UnlockSemaphoreInfo(splay_tree->semaphore);
949  return(value);
950 }
951 
952 /*
953 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
954 % %
955 % %
956 % %
957 % 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 %
958 % %
959 % %
960 % %
961 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
962 %
963 % GetNumberOfNodesInSplayTree() returns the number of nodes in the splay-tree.
964 %
965 % The format of the GetNumberOfNodesInSplayTree method is:
966 %
967 % size_t GetNumberOfNodesInSplayTree(
968 % const SplayTreeInfo *splay_tree)
969 %
970 % A description of each parameter follows:
971 %
972 % o splay_tree: the splay tree.
973 %
974 */
975 MagickExport size_t GetNumberOfNodesInSplayTree(
976  const SplayTreeInfo *splay_tree)
977 {
978  assert(splay_tree != (SplayTreeInfo *) NULL);
979  assert(splay_tree->signature == MagickCoreSignature);
980  if (IsEventLogging() != MagickFalse)
981  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
982  return(splay_tree->nodes);
983 }
984 
985 /*
986 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
987 % %
988 % %
989 % %
990 % I t e r a t e O v e r S p l a y T r e e %
991 % %
992 % %
993 % %
994 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
995 %
996 % IterateOverSplayTree() iterates over the splay-tree.
997 %
998 % The format of the IterateOverSplayTree method is:
999 %
1000 % int IterateOverSplayTree(SplayTreeInfo *splay_tree,
1001 % int (*method)(NodeInfo *,void *),const void *value)
1002 %
1003 % A description of each parameter follows:
1004 %
1005 % o splay_tree: the splay-tree info.
1006 %
1007 % o method: the method.
1008 %
1009 % o value: the value.
1010 %
1011 */
1012 static int IterateOverSplayTree(SplayTreeInfo *splay_tree,
1013  int (*method)(NodeInfo *,const void *),const void *value)
1014 {
1015  typedef enum
1016  {
1017  LeftTransition,
1018  RightTransition,
1019  DownTransition,
1020  UpTransition
1021  } TransitionType;
1022 
1023  int
1024  status;
1025 
1026  MagickBooleanType
1027  final_transition;
1028 
1029  NodeInfo
1030  **nodes;
1031 
1032  ssize_t
1033  i;
1034 
1035  NodeInfo
1036  *node;
1037 
1038  TransitionType
1039  transition;
1040 
1041  unsigned char
1042  *transitions;
1043 
1044  if (splay_tree->root == (NodeInfo *) NULL)
1045  return(0);
1046  nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
1047  sizeof(*nodes));
1048  transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes,
1049  sizeof(*transitions));
1050  if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL))
1051  ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1052  status=0;
1053  final_transition=MagickFalse;
1054  nodes[0]=splay_tree->root;
1055  transitions[0]=(unsigned char) LeftTransition;
1056  for (i=0; final_transition == MagickFalse; )
1057  {
1058  node=nodes[i];
1059  transition=(TransitionType) transitions[i];
1060  switch (transition)
1061  {
1062  case LeftTransition:
1063  {
1064  transitions[i]=(unsigned char) DownTransition;
1065  if (node->left == (NodeInfo *) NULL)
1066  break;
1067  i++;
1068  nodes[i]=node->left;
1069  transitions[i]=(unsigned char) LeftTransition;
1070  break;
1071  }
1072  case RightTransition:
1073  {
1074  transitions[i]=(unsigned char) UpTransition;
1075  if (node->right == (NodeInfo *) NULL)
1076  break;
1077  i++;
1078  nodes[i]=node->right;
1079  transitions[i]=(unsigned char) LeftTransition;
1080  break;
1081  }
1082  case DownTransition:
1083  default:
1084  {
1085  transitions[i]=(unsigned char) RightTransition;
1086  status=(*method)(node,value);
1087  if (status != 0)
1088  final_transition=MagickTrue;
1089  break;
1090  }
1091  case UpTransition:
1092  {
1093  if (i == 0)
1094  {
1095  final_transition=MagickTrue;
1096  break;
1097  }
1098  i--;
1099  break;
1100  }
1101  }
1102  }
1103  nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
1104  transitions=(unsigned char *) RelinquishMagickMemory(transitions);
1105  return(status);
1106 }
1107 
1108 /*
1109 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1110 % %
1111 % %
1112 % %
1113 % N e w S p l a y T r e e %
1114 % %
1115 % %
1116 % %
1117 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1118 %
1119 % NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized
1120 % to default values.
1121 %
1122 % The format of the NewSplayTree method is:
1123 %
1124 % SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *),
1125 % void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1126 %
1127 % A description of each parameter follows:
1128 %
1129 % o compare: the compare method.
1130 %
1131 % o relinquish_key: the key deallocation method, typically
1132 % RelinquishMagickMemory(), called whenever a key is removed from the
1133 % splay-tree.
1134 %
1135 % o relinquish_value: the value deallocation method; typically
1136 % RelinquishMagickMemory(), called whenever a value object is removed from
1137 % the splay-tree.
1138 %
1139 */
1140 MagickExport SplayTreeInfo *NewSplayTree(
1141  int (*compare)(const void *,const void *),void *(*relinquish_key)(void *),
1142  void *(*relinquish_value)(void *))
1143 {
1145  *splay_tree;
1146 
1147  splay_tree=(SplayTreeInfo *) AcquireMagickMemory(sizeof(*splay_tree));
1148  if (splay_tree == (SplayTreeInfo *) NULL)
1149  ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1150  (void) memset(splay_tree,0,sizeof(*splay_tree));
1151  splay_tree->root=(NodeInfo *) NULL;
1152  splay_tree->compare=compare;
1153  splay_tree->relinquish_key=relinquish_key;
1154  splay_tree->relinquish_value=relinquish_value;
1155  splay_tree->balance=MagickFalse;
1156  splay_tree->key=(void *) NULL;
1157  splay_tree->next=(void *) NULL;
1158  splay_tree->nodes=0;
1159  splay_tree->debug=IsEventLogging();
1160  splay_tree->semaphore=AllocateSemaphoreInfo();
1161  splay_tree->signature=MagickCoreSignature;
1162  return(splay_tree);
1163 }
1164 
1165 /*
1166 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1167 % %
1168 % %
1169 % %
1170 % 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 %
1171 % %
1172 % %
1173 % %
1174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1175 %
1176 % RemoveNodeByValueFromSplayTree() removes a node by value from the splay-tree
1177 % and returns its key.
1178 %
1179 % The format of the RemoveNodeByValueFromSplayTree method is:
1180 %
1181 % void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1182 % const void *value)
1183 %
1184 % A description of each parameter follows:
1185 %
1186 % o splay_tree: the splay-tree info.
1187 %
1188 % o value: the value.
1189 %
1190 */
1191 MagickExport void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1192  const void *value)
1193 {
1194  NodeInfo
1195  *next,
1196  *node;
1197 
1198  void
1199  *key;
1200 
1201  assert(splay_tree != (SplayTreeInfo *) NULL);
1202  assert(splay_tree->signature == MagickCoreSignature);
1203  if (IsEventLogging() != MagickFalse)
1204  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1205  key=(void *) NULL;
1206  if (splay_tree->root == (NodeInfo *) NULL)
1207  return(key);
1208  LockSemaphoreInfo(splay_tree->semaphore);
1209  next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
1210  while (next != (NodeInfo *) NULL)
1211  {
1212  SplaySplayTree(splay_tree,next);
1213  next=(NodeInfo *) NULL;
1214  node=splay_tree->root->right;
1215  if (node != (NodeInfo *) NULL)
1216  {
1217  while (node->left != (NodeInfo *) NULL)
1218  node=node->left;
1219  next=(NodeInfo *) node->key;
1220  }
1221  if (splay_tree->root->value == value)
1222  {
1223  int
1224  compare;
1225 
1226  NodeInfo
1227  *left,
1228  *right;
1229 
1230  /*
1231  We found the node that matches the value; now remove it.
1232  */
1233  key=splay_tree->root->key;
1234  SplaySplayTree(splay_tree,key);
1235  splay_tree->key=(void *) NULL;
1236  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1237  compare=splay_tree->compare(splay_tree->root->key,key);
1238  else
1239  compare=(splay_tree->root->key > key) ? 1 :
1240  ((splay_tree->root->key < key) ? -1 : 0);
1241  if (compare != 0)
1242  {
1243  UnlockSemaphoreInfo(splay_tree->semaphore);
1244  return(key);
1245  }
1246  left=splay_tree->root->left;
1247  right=splay_tree->root->right;
1248  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1249  (splay_tree->root->value != (void *) NULL))
1250  splay_tree->root->value=splay_tree->relinquish_value(
1251  splay_tree->root->value);
1252  splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1253  splay_tree->nodes--;
1254  if (left == (NodeInfo *) NULL)
1255  {
1256  splay_tree->root=right;
1257  UnlockSemaphoreInfo(splay_tree->semaphore);
1258  return(key);
1259  }
1260  splay_tree->root=left;
1261  if (right != (NodeInfo *) NULL)
1262  {
1263  while (left->right != (NodeInfo *) NULL)
1264  left=left->right;
1265  left->right=right;
1266  }
1267  UnlockSemaphoreInfo(splay_tree->semaphore);
1268  return(key);
1269  }
1270  }
1271  UnlockSemaphoreInfo(splay_tree->semaphore);
1272  return(key);
1273 }
1274 
1275 /*
1276 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1277 % %
1278 % %
1279 % %
1280 % R e m o v e N o d e F r o m S p l a y T r e e %
1281 % %
1282 % %
1283 % %
1284 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1285 %
1286 % RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its
1287 % value.
1288 %
1289 % The format of the RemoveNodeFromSplayTree method is:
1290 %
1291 % void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key)
1292 %
1293 % A description of each parameter follows:
1294 %
1295 % o splay_tree: the splay-tree info.
1296 %
1297 % o key: the key.
1298 %
1299 */
1300 MagickExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,
1301  const void *key)
1302 {
1303  int
1304  compare;
1305 
1306  NodeInfo
1307  *left,
1308  *right;
1309 
1310  void
1311  *value;
1312 
1313  assert(splay_tree != (SplayTreeInfo *) NULL);
1314  assert(splay_tree->signature == MagickCoreSignature);
1315  if (IsEventLogging() != MagickFalse)
1316  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1317  value=(void *) NULL;
1318  if (splay_tree->root == (NodeInfo *) NULL)
1319  return(value);
1320  LockSemaphoreInfo(splay_tree->semaphore);
1321  SplaySplayTree(splay_tree,key);
1322  splay_tree->key=(void *) NULL;
1323  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1324  compare=splay_tree->compare(splay_tree->root->key,key);
1325  else
1326  compare=(splay_tree->root->key > key) ? 1 :
1327  ((splay_tree->root->key < key) ? -1 : 0);
1328  if (compare != 0)
1329  {
1330  UnlockSemaphoreInfo(splay_tree->semaphore);
1331  return(value);
1332  }
1333  left=splay_tree->root->left;
1334  right=splay_tree->root->right;
1335  value=splay_tree->root->value;
1336  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1337  (splay_tree->root->key != (void *) NULL))
1338  splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1339  splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1340  splay_tree->nodes--;
1341  if (left == (NodeInfo *) NULL)
1342  {
1343  splay_tree->root=right;
1344  UnlockSemaphoreInfo(splay_tree->semaphore);
1345  return(value);
1346  }
1347  splay_tree->root=left;
1348  if (right != (NodeInfo *) NULL)
1349  {
1350  while (left->right != (NodeInfo *) NULL)
1351  left=left->right;
1352  left->right=right;
1353  }
1354  UnlockSemaphoreInfo(splay_tree->semaphore);
1355  return(value);
1356 }
1357 
1358 /*
1359 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1360 % %
1361 % %
1362 % %
1363 % R e s e t S p l a y T r e e %
1364 % %
1365 % %
1366 % %
1367 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1368 %
1369 % ResetSplayTree() resets the splay-tree. That is, it deletes all the nodes
1370 % from the tree.
1371 %
1372 % The format of the ResetSplayTree method is:
1373 %
1374 % ResetSplayTree(SplayTreeInfo *splay_tree)
1375 %
1376 % A description of each parameter follows:
1377 %
1378 % o splay_tree: the splay tree.
1379 %
1380 */
1381 MagickExport void ResetSplayTree(SplayTreeInfo *splay_tree)
1382 {
1383  NodeInfo
1384  *node;
1385 
1386  NodeInfo
1387  *active,
1388  *pend;
1389 
1390  assert(splay_tree != (SplayTreeInfo *) NULL);
1391  assert(splay_tree->signature == MagickCoreSignature);
1392  if (IsEventLogging() != MagickFalse)
1393  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1394  LockSemaphoreInfo(splay_tree->semaphore);
1395  if (splay_tree->root != (NodeInfo *) NULL)
1396  {
1397  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1398  (splay_tree->root->value != (void *) NULL))
1399  splay_tree->root->value=splay_tree->relinquish_value(
1400  splay_tree->root->value);
1401  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1402  (splay_tree->root->key != (void *) NULL))
1403  splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1404  splay_tree->root->key=(void *) NULL;
1405  for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
1406  {
1407  active=pend;
1408  for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
1409  {
1410  if (active->left != (NodeInfo *) NULL)
1411  {
1412  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1413  (active->left->value != (void *) NULL))
1414  active->left->value=splay_tree->relinquish_value(
1415  active->left->value);
1416  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1417  (active->left->key != (void *) NULL))
1418  active->left->key=splay_tree->relinquish_key(active->left->key);
1419  active->left->key=(void *) pend;
1420  pend=active->left;
1421  }
1422  if (active->right != (NodeInfo *) NULL)
1423  {
1424  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1425  (active->right->value != (void *) NULL))
1426  active->right->value=splay_tree->relinquish_value(
1427  active->right->value);
1428  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1429  (active->right->key != (void *) NULL))
1430  active->right->key=splay_tree->relinquish_key(
1431  active->right->key);
1432  active->right->key=(void *) pend;
1433  pend=active->right;
1434  }
1435  node=active;
1436  active=(NodeInfo *) node->key;
1437  node=(NodeInfo *) RelinquishMagickMemory(node);
1438  }
1439  }
1440  }
1441  splay_tree->root=(NodeInfo *) NULL;
1442  splay_tree->key=(void *) NULL;
1443  splay_tree->next=(void *) NULL;
1444  splay_tree->nodes=0;
1445  splay_tree->balance=MagickFalse;
1446  UnlockSemaphoreInfo(splay_tree->semaphore);
1447 }
1448 
1449 /*
1450 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1451 % %
1452 % %
1453 % %
1454 % R e s e t S p l a y T r e e I t e r a t o r %
1455 % %
1456 % %
1457 % %
1458 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1459 %
1460 % ResetSplayTreeIterator() resets the splay-tree iterator. Use it in
1461 % conjunction with GetNextValueInSplayTree() to iterate over all the nodes in
1462 % the splay-tree.
1463 %
1464 % The format of the ResetSplayTreeIterator method is:
1465 %
1466 % ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1467 %
1468 % A description of each parameter follows:
1469 %
1470 % o splay_tree: the splay tree.
1471 %
1472 */
1473 MagickExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1474 {
1475  assert(splay_tree != (SplayTreeInfo *) NULL);
1476  assert(splay_tree->signature == MagickCoreSignature);
1477  if (IsEventLogging() != MagickFalse)
1478  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1479  LockSemaphoreInfo(splay_tree->semaphore);
1480  splay_tree->next=GetFirstSplayTreeNode(splay_tree);
1481  UnlockSemaphoreInfo(splay_tree->semaphore);
1482 }
1483 
1484 /*
1485 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1486 % %
1487 % %
1488 % %
1489 % S p l a y S p l a y T r e e %
1490 % %
1491 % %
1492 % %
1493 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1494 %
1495 % SplaySplayTree() splays the splay-tree.
1496 %
1497 % The format of the SplaySplayTree method is:
1498 %
1499 % void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key,
1500 % NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1501 %
1502 % A description of each parameter follows:
1503 %
1504 % o splay_tree: the splay-tree info.
1505 %
1506 % o key: the key.
1507 %
1508 % o node: the node.
1509 %
1510 % o parent: the parent node.
1511 %
1512 % o grandparent: the grandparent node.
1513 %
1514 */
1515 
1516 static NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth,
1517  const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1518 {
1519  int
1520  compare;
1521 
1522  NodeInfo
1523  **next;
1524 
1525  NodeInfo
1526  *n,
1527  *p;
1528 
1529  n=(*node);
1530  if (n == (NodeInfo *) NULL)
1531  {
1532  if (parent != (NodeInfo **) NULL)
1533  return(*parent);
1534  else
1535  return((NodeInfo *) NULL);
1536  }
1537  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1538  compare=splay_tree->compare(n->key,key);
1539  else
1540  compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
1541  next=(NodeInfo **) NULL;
1542  if (compare > 0)
1543  next=(&n->left);
1544  else
1545  if (compare < 0)
1546  next=(&n->right);
1547  if (next != (NodeInfo **) NULL)
1548  {
1549  if (depth >= MaxSplayTreeDepth)
1550  {
1551  splay_tree->balance=MagickTrue;
1552  return(n);
1553  }
1554  n=Splay(splay_tree,depth+1,key,next,node,parent);
1555  if ((n != *node) || (splay_tree->balance != MagickFalse))
1556  return(n);
1557  }
1558  if (parent == (NodeInfo **) NULL)
1559  return(n);
1560  if (grandparent == (NodeInfo **) NULL)
1561  {
1562  if (n == (*parent)->left)
1563  {
1564  *node=n->right;
1565  n->right=(*parent);
1566  }
1567  else
1568  {
1569  *node=n->left;
1570  n->left=(*parent);
1571  }
1572  *parent=n;
1573  return(n);
1574  }
1575  if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
1576  {
1577  p=(*parent);
1578  (*grandparent)->left=p->right;
1579  p->right=(*grandparent);
1580  p->left=n->right;
1581  n->right=p;
1582  *grandparent=n;
1583  return(n);
1584  }
1585  if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
1586  {
1587  p=(*parent);
1588  (*grandparent)->right=p->left;
1589  p->left=(*grandparent);
1590  p->right=n->left;
1591  n->left=p;
1592  *grandparent=n;
1593  return(n);
1594  }
1595  if (n == (*parent)->left)
1596  {
1597  (*parent)->left=n->right;
1598  n->right=(*parent);
1599  (*grandparent)->right=n->left;
1600  n->left=(*grandparent);
1601  *grandparent=n;
1602  return(n);
1603  }
1604  (*parent)->right=n->left;
1605  n->left=(*parent);
1606  (*grandparent)->left=n->right;
1607  n->right=(*grandparent);
1608  *grandparent=n;
1609  return(n);
1610 }
1611 
1612 static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key)
1613 {
1614  if (splay_tree->root == (NodeInfo *) NULL)
1615  return;
1616  if (splay_tree->key != (void *) NULL)
1617  {
1618  int
1619  compare;
1620 
1621  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1622  compare=splay_tree->compare(splay_tree->root->key,key);
1623  else
1624  compare=(splay_tree->key > key) ? 1 :
1625  ((splay_tree->key < key) ? -1 : 0);
1626  if (compare == 0)
1627  return;
1628  }
1629  (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1630  (NodeInfo **) NULL);
1631  if (splay_tree->balance != MagickFalse)
1632  {
1633  BalanceSplayTree(splay_tree);
1634  (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1635  (NodeInfo **) NULL);
1636  if (splay_tree->balance != MagickFalse)
1637  ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1638  }
1639  splay_tree->key=(void *) key;
1640 }