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