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