MagickCore  7.0.7
Convert, Edit, Or Compose Bitmap Images
splay-tree.c
Go to the documentation of this file.
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-2018 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://www.imagemagick.org/script/license.php %
33 % %
34 % Unless required by applicable law or agreed to in writing, software %
35 % distributed under the License is distributed on an "AS IS" BASIS, %
36 % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %
37 % See the License for the specific language governing permissions and %
38 % limitations under the License. %
39 % %
40 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
41 %
42 % This module implements the standard handy splay-tree methods for storing and
43 % retrieving large numbers of data elements. It is loosely based on the Java
44 % implementation of these algorithms.
45 %
46 */
47 
48 /*
49  Include declarations.
50 */
51 #include "MagickCore/studio.h"
52 #include "MagickCore/exception.h"
54 #include "MagickCore/locale_.h"
55 #include "MagickCore/log.h"
56 #include "MagickCore/memory_.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
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 
97 
98  void
99  *key,
100  *next;
101 
102  size_t
104 
107 
110 
111  size_t
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 */
155  const void *key,const void *value)
156 {
157  int
158  compare;
159 
160  register 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  register 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  register 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 *(*cline_value)(void *))
320 %
321 % A description of each parameter follows:
322 %
323 % o splay_tree: the splay tree.
324 %
325 % o clone_key: the key clone method, typically ConstantString(), called
326 % whenever a key is added to the splay-tree.
327 %
328 % o clone_value: the value clone method; typically ConstantString(), called
329 % whenever a value object is added to the splay-tree.
330 %
331 */
332 
333 static inline void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree)
334 {
335  register 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 
347  void *(*clone_key)(void *),void *(*clone_value)(void *))
348 {
349  register NodeInfo
350  *next,
351  *node;
352 
354  *clone_tree;
355 
356  assert(splay_tree != (SplayTreeInfo *) NULL);
357  assert(splay_tree->signature == MagickCoreSignature);
358  if (splay_tree->debug != MagickFalse)
359  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
360  clone_tree=NewSplayTree(splay_tree->compare,splay_tree->relinquish_key,
361  splay_tree->relinquish_value);
362  LockSemaphoreInfo(splay_tree->semaphore);
363  if (splay_tree->root == (NodeInfo *) NULL)
364  {
365  UnlockSemaphoreInfo(splay_tree->semaphore);
366  return(clone_tree);
367  }
368  next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
369  while (next != (NodeInfo *) NULL)
370  {
371  SplaySplayTree(splay_tree,next);
372  (void) AddValueToSplayTree(clone_tree,clone_key(splay_tree->root->key),
373  clone_value(splay_tree->root->value));
374  next=(NodeInfo *) NULL;
375  node=splay_tree->root->right;
376  if (node != (NodeInfo *) NULL)
377  {
378  while (node->left != (NodeInfo *) NULL)
379  node=node->left;
380  next=(NodeInfo *) node->key;
381  }
382  }
383  UnlockSemaphoreInfo(splay_tree->semaphore);
384  return(clone_tree);
385 }
386 
387 /*
388 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
389 % %
390 % %
391 % %
392 % C o m p a r e S p l a y T r e e S t r i n g %
393 % %
394 % %
395 % %
396 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
397 %
398 % CompareSplayTreeString() method finds a node in a splay-tree based on the
399 % contents of a string.
400 %
401 % The format of the CompareSplayTreeString method is:
402 %
403 % int CompareSplayTreeString(const void *target,const void *source)
404 %
405 % A description of each parameter follows:
406 %
407 % o target: the target string.
408 %
409 % o source: the source string.
410 %
411 */
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 */
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 */
487  SplayTreeInfo *splay_tree,const void *value)
488 {
489  register NodeInfo
490  *next,
491  *node;
492 
493  assert(splay_tree != (SplayTreeInfo *) NULL);
494  assert(splay_tree->signature == MagickCoreSignature);
495  if (splay_tree->debug != MagickFalse)
496  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
497  LockSemaphoreInfo(splay_tree->semaphore);
498  if (splay_tree->root == (NodeInfo *) NULL)
499  {
500  UnlockSemaphoreInfo(splay_tree->semaphore);
501  return(MagickFalse);
502  }
503  next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
504  while (next != (NodeInfo *) NULL)
505  {
506  SplaySplayTree(splay_tree,next);
507  next=(NodeInfo *) NULL;
508  node=splay_tree->root->right;
509  if (node != (NodeInfo *) NULL)
510  {
511  while (node->left != (NodeInfo *) NULL)
512  node=node->left;
513  next=(NodeInfo *) node->key;
514  }
515  if (splay_tree->root->value == value)
516  {
517  int
518  compare;
519 
520  register 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 */
604  SplayTreeInfo *splay_tree,const void *key)
605 {
606  int
607  compare;
608 
609  register NodeInfo
610  *left,
611  *right;
612 
613  assert(splay_tree != (SplayTreeInfo *) NULL);
614  assert(splay_tree->signature == MagickCoreSignature);
615  if (splay_tree->debug != MagickFalse)
616  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
617  if (splay_tree->root == (NodeInfo *) NULL)
618  return(MagickFalse);
619  LockSemaphoreInfo(splay_tree->semaphore);
620  SplaySplayTree(splay_tree,key);
621  splay_tree->key=(void *) NULL;
622  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
623  compare=splay_tree->compare(splay_tree->root->key,key);
624  else
625  compare=(splay_tree->root->key > key) ? 1 :
626  ((splay_tree->root->key < key) ? -1 : 0);
627  if (compare != 0)
628  {
629  UnlockSemaphoreInfo(splay_tree->semaphore);
630  return(MagickFalse);
631  }
632  left=splay_tree->root->left;
633  right=splay_tree->root->right;
634  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
635  (splay_tree->root->value != (void *) NULL))
636  splay_tree->root->value=splay_tree->relinquish_value(
637  splay_tree->root->value);
638  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
639  (splay_tree->root->key != (void *) NULL))
640  splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
641  splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
642  splay_tree->nodes--;
643  if (left == (NodeInfo *) NULL)
644  {
645  splay_tree->root=right;
646  UnlockSemaphoreInfo(splay_tree->semaphore);
647  return(MagickTrue);
648  }
649  splay_tree->root=left;
650  if (right != (NodeInfo *) NULL)
651  {
652  while (left->right != (NodeInfo *) NULL)
653  left=left->right;
654  left->right=right;
655  }
656  UnlockSemaphoreInfo(splay_tree->semaphore);
657  return(MagickTrue);
658 }
659 
660 /*
661 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
662 % %
663 % %
664 % %
665 % D e s t r o y S p l a y T r e e %
666 % %
667 % %
668 % %
669 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
670 %
671 % DestroySplayTree() destroys the splay-tree.
672 %
673 % The format of the DestroySplayTree method is:
674 %
675 % SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree)
676 %
677 % A description of each parameter follows:
678 %
679 % o splay_tree: the splay tree.
680 %
681 */
683 {
684  NodeInfo
685  *node;
686 
687  register NodeInfo
688  *active,
689  *pend;
690 
691  LockSemaphoreInfo(splay_tree->semaphore);
692  if (splay_tree->root != (NodeInfo *) NULL)
693  {
694  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
695  (splay_tree->root->value != (void *) NULL))
696  splay_tree->root->value=splay_tree->relinquish_value(
697  splay_tree->root->value);
698  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
699  (splay_tree->root->key != (void *) NULL))
700  splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
701  splay_tree->root->key=(void *) NULL;
702  for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
703  {
704  active=pend;
705  for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
706  {
707  if (active->left != (NodeInfo *) NULL)
708  {
709  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
710  (active->left->value != (void *) NULL))
711  active->left->value=splay_tree->relinquish_value(
712  active->left->value);
713  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
714  (active->left->key != (void *) NULL))
715  active->left->key=splay_tree->relinquish_key(active->left->key);
716  active->left->key=(void *) pend;
717  pend=active->left;
718  }
719  if (active->right != (NodeInfo *) NULL)
720  {
721  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
722  (active->right->value != (void *) NULL))
723  active->right->value=splay_tree->relinquish_value(
724  active->right->value);
725  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
726  (active->right->key != (void *) NULL))
727  active->right->key=splay_tree->relinquish_key(
728  active->right->key);
729  active->right->key=(void *) pend;
730  pend=active->right;
731  }
732  node=active;
733  active=(NodeInfo *) node->key;
734  node=(NodeInfo *) RelinquishMagickMemory(node);
735  }
736  }
737  }
738  splay_tree->signature=(~MagickCoreSignature);
739  UnlockSemaphoreInfo(splay_tree->semaphore);
740  RelinquishSemaphoreInfo(&splay_tree->semaphore);
741  splay_tree=(SplayTreeInfo *) RelinquishMagickMemory(splay_tree);
742  return(splay_tree);
743 }
744 
745 /*
746 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
747 % %
748 % %
749 % %
750 % G e t N e x t K e y I n S p l a y T r e e %
751 % %
752 % %
753 % %
754 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
755 %
756 % GetNextKeyInSplayTree() gets the next key in the splay-tree.
757 %
758 % The format of the GetNextKeyInSplayTree method is:
759 %
760 % const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
761 %
762 % A description of each parameter follows:
763 %
764 % o splay_tree: the splay tree.
765 %
766 % o key: the key.
767 %
768 */
770 {
771  register NodeInfo
772  *node;
773 
774  void
775  *key;
776 
777  assert(splay_tree != (SplayTreeInfo *) NULL);
778  assert(splay_tree->signature == MagickCoreSignature);
779  if (splay_tree->debug != MagickFalse)
780  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
781  if ((splay_tree->root == (NodeInfo *) NULL) ||
782  (splay_tree->next == (void *) NULL))
783  return((void *) NULL);
784  LockSemaphoreInfo(splay_tree->semaphore);
785  SplaySplayTree(splay_tree,splay_tree->next);
786  splay_tree->next=(void *) NULL;
787  node=splay_tree->root->right;
788  if (node != (NodeInfo *) NULL)
789  {
790  while (node->left != (NodeInfo *) NULL)
791  node=node->left;
792  splay_tree->next=node->key;
793  }
794  key=splay_tree->root->key;
795  UnlockSemaphoreInfo(splay_tree->semaphore);
796  return(key);
797 }
798 
799 /*
800 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
801 % %
802 % %
803 % %
804 % G e t N e x t V a l u e I n S p l a y T r e e %
805 % %
806 % %
807 % %
808 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
809 %
810 % GetNextValueInSplayTree() gets the next value in the splay-tree.
811 %
812 % The format of the GetNextValueInSplayTree method is:
813 %
814 % const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
815 %
816 % A description of each parameter follows:
817 %
818 % o splay_tree: the splay tree.
819 %
820 % o key: the key.
821 %
822 */
824 {
825  register NodeInfo
826  *node;
827 
828  void
829  *value;
830 
831  assert(splay_tree != (SplayTreeInfo *) NULL);
832  assert(splay_tree->signature == MagickCoreSignature);
833  if (splay_tree->debug != MagickFalse)
834  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
835  if ((splay_tree->root == (NodeInfo *) NULL) ||
836  (splay_tree->next == (void *) NULL))
837  return((void *) NULL);
838  LockSemaphoreInfo(splay_tree->semaphore);
839  SplaySplayTree(splay_tree,splay_tree->next);
840  splay_tree->next=(void *) NULL;
841  node=splay_tree->root->right;
842  if (node != (NodeInfo *) NULL)
843  {
844  while (node->left != (NodeInfo *) NULL)
845  node=node->left;
846  splay_tree->next=node->key;
847  }
848  value=splay_tree->root->value;
849  UnlockSemaphoreInfo(splay_tree->semaphore);
850  return(value);
851 }
852 
853 /*
854 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
855 % %
856 % %
857 % %
858 % G e t R o o t V a l u e F r o m S p l a y T r e e %
859 % %
860 % %
861 % %
862 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
863 %
864 % GetRootValueFromSplayTree() gets the root value from the splay-tree.
865 %
866 % The format of the GetRootValueFromSplayTree method is:
867 %
868 % const void *GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
869 %
870 % A description of each parameter follows:
871 %
872 % o splay_tree: the splay tree.
873 %
874 % o key: the key.
875 %
876 */
878 {
879  const void
880  *value;
881 
882  assert(splay_tree != (SplayTreeInfo *) NULL);
883  assert(splay_tree->signature == MagickCoreSignature);
884  if (splay_tree->debug != MagickFalse)
885  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
886  value=(const void *) NULL;
887  LockSemaphoreInfo(splay_tree->semaphore);
888  if (splay_tree->root != (NodeInfo *) NULL)
889  value=splay_tree->root->value;
890  UnlockSemaphoreInfo(splay_tree->semaphore);
891  return(value);
892 }
893 
894 /*
895 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
896 % %
897 % %
898 % %
899 % G e t V a l u e F r o m S p l a y T r e e %
900 % %
901 % %
902 % %
903 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
904 %
905 % GetValueFromSplayTree() gets a value from the splay-tree by its key.
906 %
907 % Note, the value is a constant. Do not attempt to free it.
908 %
909 % The format of the GetValueFromSplayTree method is:
910 %
911 % const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree,
912 % const void *key)
913 %
914 % A description of each parameter follows:
915 %
916 % o splay_tree: the splay tree.
917 %
918 % o key: the key.
919 %
920 */
922  const void *key)
923 {
924  int
925  compare;
926 
927  void
928  *value;
929 
930  assert(splay_tree != (SplayTreeInfo *) NULL);
931  assert(splay_tree->signature == MagickCoreSignature);
932  if (splay_tree->debug != MagickFalse)
933  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
934  if (splay_tree->root == (NodeInfo *) NULL)
935  return((void *) NULL);
936  LockSemaphoreInfo(splay_tree->semaphore);
937  SplaySplayTree(splay_tree,key);
938  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
939  compare=splay_tree->compare(splay_tree->root->key,key);
940  else
941  compare=(splay_tree->root->key > key) ? 1 :
942  ((splay_tree->root->key < key) ? -1 : 0);
943  if (compare != 0)
944  {
945  UnlockSemaphoreInfo(splay_tree->semaphore);
946  return((void *) NULL);
947  }
948  value=splay_tree->root->value;
949  UnlockSemaphoreInfo(splay_tree->semaphore);
950  return(value);
951 }
952 
953 /*
954 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
955 % %
956 % %
957 % %
958 % G e t N u m b e r O f N o d e s I n S p l a y T r e e %
959 % %
960 % %
961 % %
962 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
963 %
964 % GetNumberOfNodesInSplayTree() returns the number of nodes in the splay-tree.
965 %
966 % The format of the GetNumberOfNodesInSplayTree method is:
967 %
968 % size_t GetNumberOfNodesInSplayTree(
969 % const SplayTreeInfo *splay_tree)
970 %
971 % A description of each parameter follows:
972 %
973 % o splay_tree: the splay tree.
974 %
975 */
977  const SplayTreeInfo *splay_tree)
978 {
979  assert(splay_tree != (SplayTreeInfo *) NULL);
980  assert(splay_tree->signature == MagickCoreSignature);
981  if (splay_tree->debug != MagickFalse)
982  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
983  return(splay_tree->nodes);
984 }
985 
986 /*
987 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
988 % %
989 % %
990 % %
991 % I t e r a t e O v e r S p l a y T r e e %
992 % %
993 % %
994 % %
995 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
996 %
997 % IterateOverSplayTree() iterates over the splay-tree.
998 %
999 % The format of the IterateOverSplayTree method is:
1000 %
1001 % int IterateOverSplayTree(SplayTreeInfo *splay_tree,
1002 % int (*method)(NodeInfo *,void *),const void *value)
1003 %
1004 % A description of each parameter follows:
1005 %
1006 % o splay_tree: the splay-tree info.
1007 %
1008 % o method: the method.
1009 %
1010 % o value: the value.
1011 %
1012 */
1013 static int IterateOverSplayTree(SplayTreeInfo *splay_tree,
1014  int (*method)(NodeInfo *,const void *),const void *value)
1015 {
1016  typedef enum
1017  {
1018  LeftTransition,
1019  RightTransition,
1020  DownTransition,
1021  UpTransition
1022  } TransitionType;
1023 
1024  int
1025  status;
1026 
1028  final_transition;
1029 
1030  NodeInfo
1031  **nodes;
1032 
1033  register ssize_t
1034  i;
1035 
1036  register NodeInfo
1037  *node;
1038 
1039  TransitionType
1040  transition;
1041 
1042  unsigned char
1043  *transitions;
1044 
1045  if (splay_tree->root == (NodeInfo *) NULL)
1046  return(0);
1047  nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes,
1048  sizeof(*nodes));
1049  transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes,
1050  sizeof(*transitions));
1051  if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL))
1052  ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1053  status=0;
1054  final_transition=MagickFalse;
1055  nodes[0]=splay_tree->root;
1056  transitions[0]=(unsigned char) LeftTransition;
1057  for (i=0; final_transition == MagickFalse; )
1058  {
1059  node=nodes[i];
1060  transition=(TransitionType) transitions[i];
1061  switch (transition)
1062  {
1063  case LeftTransition:
1064  {
1065  transitions[i]=(unsigned char) DownTransition;
1066  if (node->left == (NodeInfo *) NULL)
1067  break;
1068  i++;
1069  nodes[i]=node->left;
1070  transitions[i]=(unsigned char) LeftTransition;
1071  break;
1072  }
1073  case RightTransition:
1074  {
1075  transitions[i]=(unsigned char) UpTransition;
1076  if (node->right == (NodeInfo *) NULL)
1077  break;
1078  i++;
1079  nodes[i]=node->right;
1080  transitions[i]=(unsigned char) LeftTransition;
1081  break;
1082  }
1083  case DownTransition:
1084  default:
1085  {
1086  transitions[i]=(unsigned char) RightTransition;
1087  status=(*method)(node,value);
1088  if (status != 0)
1089  final_transition=MagickTrue;
1090  break;
1091  }
1092  case UpTransition:
1093  {
1094  if (i == 0)
1095  {
1096  final_transition=MagickTrue;
1097  break;
1098  }
1099  i--;
1100  break;
1101  }
1102  }
1103  }
1104  nodes=(NodeInfo **) RelinquishMagickMemory(nodes);
1105  transitions=(unsigned char *) RelinquishMagickMemory(transitions);
1106  return(status);
1107 }
1108 
1109 /*
1110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1111 % %
1112 % %
1113 % %
1114 % N e w S p l a y T r e e %
1115 % %
1116 % %
1117 % %
1118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1119 %
1120 % NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized
1121 % to default values.
1122 %
1123 % The format of the NewSplayTree method is:
1124 %
1125 % SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *),
1126 % void *(*relinquish_key)(void *),void *(*relinquish_value)(void *))
1127 %
1128 % A description of each parameter follows:
1129 %
1130 % o compare: the compare method.
1131 %
1132 % o relinquish_key: the key deallocation method, typically
1133 % RelinquishMagickMemory(), called whenever a key is removed from the
1134 % splay-tree.
1135 %
1136 % o relinquish_value: the value deallocation method; typically
1137 % RelinquishMagickMemory(), called whenever a value object is removed from
1138 % the splay-tree.
1139 %
1140 */
1142  int (*compare)(const void *,const void *),void *(*relinquish_key)(void *),
1143  void *(*relinquish_value)(void *))
1144 {
1146  *splay_tree;
1147 
1148  splay_tree=(SplayTreeInfo *) AcquireCriticalMemory(sizeof(*splay_tree));
1149  (void) ResetMagickMemory(splay_tree,0,sizeof(*splay_tree));
1150  splay_tree->root=(NodeInfo *) NULL;
1151  splay_tree->compare=compare;
1152  splay_tree->relinquish_key=relinquish_key;
1153  splay_tree->relinquish_value=relinquish_value;
1154  splay_tree->balance=MagickFalse;
1155  splay_tree->key=(void *) NULL;
1156  splay_tree->next=(void *) NULL;
1157  splay_tree->nodes=0;
1158  splay_tree->debug=IsEventLogging();
1159  splay_tree->semaphore=AcquireSemaphoreInfo();
1160  splay_tree->signature=MagickCoreSignature;
1161  return(splay_tree);
1162 }
1163 
1164 /*
1165 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1166 % %
1167 % %
1168 % %
1169 % R e m o v e N o d e B y V a l u e F r o m S p l a y T r e e %
1170 % %
1171 % %
1172 % %
1173 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1174 %
1175 % RemoveNodeByValueFromSplayTree() removes a node by value from the splay-tree
1176 % and returns its key.
1177 %
1178 % The format of the RemoveNodeByValueFromSplayTree method is:
1179 %
1180 % void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree,
1181 % const void *value)
1182 %
1183 % A description of each parameter follows:
1184 %
1185 % o splay_tree: the splay-tree info.
1186 %
1187 % o value: the value.
1188 %
1189 */
1191  const void *value)
1192 {
1193  register NodeInfo
1194  *next,
1195  *node;
1196 
1197  void
1198  *key;
1199 
1200  assert(splay_tree != (SplayTreeInfo *) NULL);
1201  assert(splay_tree->signature == MagickCoreSignature);
1202  if (splay_tree->debug != MagickFalse)
1203  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1204  key=(void *) NULL;
1205  if (splay_tree->root == (NodeInfo *) NULL)
1206  return(key);
1207  LockSemaphoreInfo(splay_tree->semaphore);
1208  next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree);
1209  while (next != (NodeInfo *) NULL)
1210  {
1211  SplaySplayTree(splay_tree,next);
1212  next=(NodeInfo *) NULL;
1213  node=splay_tree->root->right;
1214  if (node != (NodeInfo *) NULL)
1215  {
1216  while (node->left != (NodeInfo *) NULL)
1217  node=node->left;
1218  next=(NodeInfo *) node->key;
1219  }
1220  if (splay_tree->root->value == value)
1221  {
1222  int
1223  compare;
1224 
1225  register NodeInfo
1226  *left,
1227  *right;
1228 
1229  /*
1230  We found the node that matches the value; now remove it.
1231  */
1232  key=splay_tree->root->key;
1233  SplaySplayTree(splay_tree,key);
1234  splay_tree->key=(void *) NULL;
1235  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1236  compare=splay_tree->compare(splay_tree->root->key,key);
1237  else
1238  compare=(splay_tree->root->key > key) ? 1 :
1239  ((splay_tree->root->key < key) ? -1 : 0);
1240  if (compare != 0)
1241  {
1242  UnlockSemaphoreInfo(splay_tree->semaphore);
1243  return(key);
1244  }
1245  left=splay_tree->root->left;
1246  right=splay_tree->root->right;
1247  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1248  (splay_tree->root->value != (void *) NULL))
1249  splay_tree->root->value=splay_tree->relinquish_value(
1250  splay_tree->root->value);
1251  splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1252  splay_tree->nodes--;
1253  if (left == (NodeInfo *) NULL)
1254  {
1255  splay_tree->root=right;
1256  UnlockSemaphoreInfo(splay_tree->semaphore);
1257  return(key);
1258  }
1259  splay_tree->root=left;
1260  if (right != (NodeInfo *) NULL)
1261  {
1262  while (left->right != (NodeInfo *) NULL)
1263  left=left->right;
1264  left->right=right;
1265  }
1266  UnlockSemaphoreInfo(splay_tree->semaphore);
1267  return(key);
1268  }
1269  }
1270  UnlockSemaphoreInfo(splay_tree->semaphore);
1271  return(key);
1272 }
1273 
1274 /*
1275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1276 % %
1277 % %
1278 % %
1279 % R e m o v e N o d e F r o m S p l a y T r e e %
1280 % %
1281 % %
1282 % %
1283 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1284 %
1285 % RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its
1286 % value.
1287 %
1288 % The format of the RemoveNodeFromSplayTree method is:
1289 %
1290 % void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key)
1291 %
1292 % A description of each parameter follows:
1293 %
1294 % o splay_tree: the splay-tree info.
1295 %
1296 % o key: the key.
1297 %
1298 */
1300  const void *key)
1301 {
1302  int
1303  compare;
1304 
1305  register NodeInfo
1306  *left,
1307  *right;
1308 
1309  void
1310  *value;
1311 
1312  assert(splay_tree != (SplayTreeInfo *) NULL);
1313  assert(splay_tree->signature == MagickCoreSignature);
1314  if (splay_tree->debug != MagickFalse)
1315  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1316  value=(void *) NULL;
1317  if (splay_tree->root == (NodeInfo *) NULL)
1318  return(value);
1319  LockSemaphoreInfo(splay_tree->semaphore);
1320  SplaySplayTree(splay_tree,key);
1321  splay_tree->key=(void *) NULL;
1322  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1323  compare=splay_tree->compare(splay_tree->root->key,key);
1324  else
1325  compare=(splay_tree->root->key > key) ? 1 :
1326  ((splay_tree->root->key < key) ? -1 : 0);
1327  if (compare != 0)
1328  {
1329  UnlockSemaphoreInfo(splay_tree->semaphore);
1330  return(value);
1331  }
1332  left=splay_tree->root->left;
1333  right=splay_tree->root->right;
1334  value=splay_tree->root->value;
1335  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1336  (splay_tree->root->key != (void *) NULL))
1337  splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1338  splay_tree->root=(NodeInfo *) RelinquishMagickMemory(splay_tree->root);
1339  splay_tree->nodes--;
1340  if (left == (NodeInfo *) NULL)
1341  {
1342  splay_tree->root=right;
1343  UnlockSemaphoreInfo(splay_tree->semaphore);
1344  return(value);
1345  }
1346  splay_tree->root=left;
1347  if (right != (NodeInfo *) NULL)
1348  {
1349  while (left->right != (NodeInfo *) NULL)
1350  left=left->right;
1351  left->right=right;
1352  }
1353  UnlockSemaphoreInfo(splay_tree->semaphore);
1354  return(value);
1355 }
1356 
1357 /*
1358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1359 % %
1360 % %
1361 % %
1362 % R e s e t S p l a y T r e e %
1363 % %
1364 % %
1365 % %
1366 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1367 %
1368 % ResetSplayTree() resets the splay-tree. That is, it deletes all the nodes
1369 % from the tree.
1370 %
1371 % The format of the ResetSplayTree method is:
1372 %
1373 % ResetSplayTree(SplayTreeInfo *splay_tree)
1374 %
1375 % A description of each parameter follows:
1376 %
1377 % o splay_tree: the splay tree.
1378 %
1379 */
1381 {
1382  NodeInfo
1383  *node;
1384 
1385  register NodeInfo
1386  *active,
1387  *pend;
1388 
1389  assert(splay_tree != (SplayTreeInfo *) NULL);
1390  assert(splay_tree->signature == MagickCoreSignature);
1391  if (splay_tree->debug != MagickFalse)
1392  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1393  LockSemaphoreInfo(splay_tree->semaphore);
1394  if (splay_tree->root != (NodeInfo *) NULL)
1395  {
1396  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1397  (splay_tree->root->value != (void *) NULL))
1398  splay_tree->root->value=splay_tree->relinquish_value(
1399  splay_tree->root->value);
1400  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1401  (splay_tree->root->key != (void *) NULL))
1402  splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key);
1403  splay_tree->root->key=(void *) NULL;
1404  for (pend=splay_tree->root; pend != (NodeInfo *) NULL; )
1405  {
1406  active=pend;
1407  for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; )
1408  {
1409  if (active->left != (NodeInfo *) NULL)
1410  {
1411  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1412  (active->left->value != (void *) NULL))
1413  active->left->value=splay_tree->relinquish_value(
1414  active->left->value);
1415  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1416  (active->left->key != (void *) NULL))
1417  active->left->key=splay_tree->relinquish_key(active->left->key);
1418  active->left->key=(void *) pend;
1419  pend=active->left;
1420  }
1421  if (active->right != (NodeInfo *) NULL)
1422  {
1423  if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) &&
1424  (active->right->value != (void *) NULL))
1425  active->right->value=splay_tree->relinquish_value(
1426  active->right->value);
1427  if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) &&
1428  (active->right->key != (void *) NULL))
1429  active->right->key=splay_tree->relinquish_key(
1430  active->right->key);
1431  active->right->key=(void *) pend;
1432  pend=active->right;
1433  }
1434  node=active;
1435  active=(NodeInfo *) node->key;
1436  node=(NodeInfo *) RelinquishMagickMemory(node);
1437  }
1438  }
1439  }
1440  splay_tree->root=(NodeInfo *) NULL;
1441  splay_tree->key=(void *) NULL;
1442  splay_tree->next=(void *) NULL;
1443  splay_tree->nodes=0;
1444  splay_tree->balance=MagickFalse;
1445  UnlockSemaphoreInfo(splay_tree->semaphore);
1446 }
1447 
1448 /*
1449 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1450 % %
1451 % %
1452 % %
1453 % R e s e t S p l a y T r e e I t e r a t o r %
1454 % %
1455 % %
1456 % %
1457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1458 %
1459 % ResetSplayTreeIterator() resets the splay-tree iterator. Use it in
1460 % conjunction with GetNextValueInSplayTree() to iterate over all the nodes in
1461 % the splay-tree.
1462 %
1463 % The format of the ResetSplayTreeIterator method is:
1464 %
1465 % ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
1466 %
1467 % A description of each parameter follows:
1468 %
1469 % o splay_tree: the splay tree.
1470 %
1471 */
1473 {
1474  assert(splay_tree != (SplayTreeInfo *) NULL);
1475  assert(splay_tree->signature == MagickCoreSignature);
1476  if (splay_tree->debug != MagickFalse)
1477  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1478  LockSemaphoreInfo(splay_tree->semaphore);
1479  splay_tree->next=GetFirstSplayTreeNode(splay_tree);
1480  UnlockSemaphoreInfo(splay_tree->semaphore);
1481 }
1482 
1483 /*
1484 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1485 % %
1486 % %
1487 % %
1488 % S p l a y S p l a y T r e e %
1489 % %
1490 % %
1491 % %
1492 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1493 %
1494 % SplaySplayTree() splays the splay-tree.
1495 %
1496 % The format of the SplaySplayTree method is:
1497 %
1498 % void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key,
1499 % NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1500 %
1501 % A description of each parameter follows:
1502 %
1503 % o splay_tree: the splay-tree info.
1504 %
1505 % o key: the key.
1506 %
1507 % o node: the node.
1508 %
1509 % o parent: the parent node.
1510 %
1511 % o grandparent: the grandparent node.
1512 %
1513 */
1514 
1515 static NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth,
1516  const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent)
1517 {
1518  int
1519  compare;
1520 
1521  NodeInfo
1522  **next;
1523 
1524  register NodeInfo
1525  *n,
1526  *p;
1527 
1528  n=(*node);
1529  if (n == (NodeInfo *) NULL)
1530  return(*parent);
1531  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1532  compare=splay_tree->compare(n->key,key);
1533  else
1534  compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0);
1535  next=(NodeInfo **) NULL;
1536  if (compare > 0)
1537  next=(&n->left);
1538  else
1539  if (compare < 0)
1540  next=(&n->right);
1541  if (next != (NodeInfo **) NULL)
1542  {
1543  if (depth >= MaxSplayTreeDepth)
1544  {
1545  splay_tree->balance=MagickTrue;
1546  return(n);
1547  }
1548  n=Splay(splay_tree,depth+1,key,next,node,parent);
1549  if ((n != *node) || (splay_tree->balance != MagickFalse))
1550  return(n);
1551  }
1552  if (parent == (NodeInfo **) NULL)
1553  return(n);
1554  if (grandparent == (NodeInfo **) NULL)
1555  {
1556  if (n == (*parent)->left)
1557  {
1558  *node=n->right;
1559  n->right=(*parent);
1560  }
1561  else
1562  {
1563  *node=n->left;
1564  n->left=(*parent);
1565  }
1566  *parent=n;
1567  return(n);
1568  }
1569  if ((n == (*parent)->left) && (*parent == (*grandparent)->left))
1570  {
1571  p=(*parent);
1572  (*grandparent)->left=p->right;
1573  p->right=(*grandparent);
1574  p->left=n->right;
1575  n->right=p;
1576  *grandparent=n;
1577  return(n);
1578  }
1579  if ((n == (*parent)->right) && (*parent == (*grandparent)->right))
1580  {
1581  p=(*parent);
1582  (*grandparent)->right=p->left;
1583  p->left=(*grandparent);
1584  p->right=n->left;
1585  n->left=p;
1586  *grandparent=n;
1587  return(n);
1588  }
1589  if (n == (*parent)->left)
1590  {
1591  (*parent)->left=n->right;
1592  n->right=(*parent);
1593  (*grandparent)->right=n->left;
1594  n->left=(*grandparent);
1595  *grandparent=n;
1596  return(n);
1597  }
1598  (*parent)->right=n->left;
1599  n->left=(*parent);
1600  (*grandparent)->left=n->right;
1601  n->right=(*grandparent);
1602  *grandparent=n;
1603  return(n);
1604 }
1605 
1606 static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key)
1607 {
1608  if (splay_tree->root == (NodeInfo *) NULL)
1609  return;
1610  if (splay_tree->key != (void *) NULL)
1611  {
1612  int
1613  compare;
1614 
1615  if (splay_tree->compare != (int (*)(const void *,const void *)) NULL)
1616  compare=splay_tree->compare(splay_tree->root->key,key);
1617  else
1618  compare=(splay_tree->key > key) ? 1 :
1619  ((splay_tree->key < key) ? -1 : 0);
1620  if (compare == 0)
1621  return;
1622  }
1623  (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1624  (NodeInfo **) NULL);
1625  if (splay_tree->balance != MagickFalse)
1626  {
1627  BalanceSplayTree(splay_tree);
1628  (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL,
1629  (NodeInfo **) NULL);
1630  if (splay_tree->balance != MagickFalse)
1631  ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1632  }
1633  splay_tree->key=(void *) key;
1634 }
void *(* relinquish_key)(void *)
Definition: splay-tree.c:92
static NodeInfo * LinkSplayTreeNodes(NodeInfo **nodes, const size_t low, const size_t high)
Definition: splay-tree.c:247
MagickExport int CompareStringInfo(const StringInfo *target, const StringInfo *source)
Definition: string.c:362
MagickExport MagickBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree, const void *key, const void *value)
Definition: splay-tree.c:154
MagickExport void UnlockSemaphoreInfo(SemaphoreInfo *semaphore_info)
Definition: semaphore.c:450
void *(*) *(* relinquish_value)(void *)
Definition: splay-tree.c:93
#define ThrowFatalException(severity, tag)
static void * GetFirstSplayTreeNode(SplayTreeInfo *splay_tree)
Definition: splay-tree.c:333
MagickExport SemaphoreInfo * AcquireSemaphoreInfo(void)
Definition: semaphore.c:192
MagickExport void * RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree, const void *value)
Definition: splay-tree.c:1190
size_t signature
Definition: splay-tree.c:112
Definition: log.h:52
MagickExport const void * GetNextValueInSplayTree(SplayTreeInfo *splay_tree)
Definition: splay-tree.c:823
static void BalanceSplayTree(SplayTreeInfo *splay_tree)
Definition: splay-tree.c:280
MagickExport void ResetSplayTree(SplayTreeInfo *splay_tree)
Definition: splay-tree.c:1380
#define MagickCoreSignature
MagickBooleanType balance
Definition: splay-tree.c:96
MagickExport void LockSemaphoreInfo(SemaphoreInfo *semaphore_info)
Definition: semaphore.c:293
static NodeInfo * Splay(SplayTreeInfo *splay_tree, const size_t depth, const void *key, NodeInfo **node, NodeInfo **parent, NodeInfo **grandparent)
Definition: splay-tree.c:1515
MagickBooleanType
Definition: magick-type.h:156
int(* compare)(const void *, const void *)
Definition: splay-tree.c:89
MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree(SplayTreeInfo *splay_tree, const void *value)
Definition: splay-tree.c:486
MagickExport void * ResetMagickMemory(void *memory, int byte, const size_t size)
Definition: memory.c:1164
MagickExport int CompareSplayTreeStringInfo(const void *target, const void *source)
Definition: splay-tree.c:448
MagickExport void * AcquireQuantumMemory(const size_t count, const size_t quantum)
Definition: memory.c:529
MagickExport SplayTreeInfo * DestroySplayTree(SplayTreeInfo *splay_tree)
Definition: splay-tree.c:682
MagickExport MagickBooleanType IsEventLogging(void)
Definition: log.c:716
MagickExport MagickBooleanType static void * AcquireCriticalMemory(const size_t size)
struct _NodeInfo NodeInfo
MagickExport SplayTreeInfo * NewSplayTree(int(*compare)(const void *, const void *), void *(*relinquish_key)(void *), void *(*relinquish_value)(void *))
Definition: splay-tree.c:1141
MagickExport MagickBooleanType LogMagickEvent(const LogEventType type, const char *module, const char *function, const size_t line, const char *format,...)
Definition: log.c:1397
struct _NodeInfo * parent
Definition: quantize.c:232
MagickExport const void * GetValueFromSplayTree(SplayTreeInfo *splay_tree, const void *key)
Definition: splay-tree.c:921
MagickExport int LocaleCompare(const char *p, const char *q)
Definition: locale.c:1409
MagickExport SplayTreeInfo * CloneSplayTree(SplayTreeInfo *splay_tree, void *(*clone_key)(void *), void *(*clone_value)(void *))
Definition: splay-tree.c:346
#define GetMagickModule()
Definition: log.h:28
MagickExport int CompareSplayTreeString(const void *target, const void *source)
Definition: splay-tree.c:412
static int IterateOverSplayTree(SplayTreeInfo *, int(*)(NodeInfo *, const void *), const void *)
Definition: splay-tree.c:1013
NodeInfo * root
Definition: splay-tree.c:86
static void SplaySplayTree(SplayTreeInfo *, const void *)
Definition: splay-tree.c:1606
SemaphoreInfo * semaphore
Definition: splay-tree.c:109
void * value
Definition: splay-tree.c:76
MagickExport const void * GetNextKeyInSplayTree(SplayTreeInfo *splay_tree)
Definition: splay-tree.c:769
MagickExport void * AcquireMagickMemory(const size_t size)
Definition: memory.c:458
static int SplayTreeToNodeArray(NodeInfo *node, const void *nodes)
Definition: splay-tree.c:269
MagickExport const void * GetRootValueFromSplayTree(SplayTreeInfo *splay_tree)
Definition: splay-tree.c:877
MagickExport void * RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree, const void *key)
Definition: splay-tree.c:1299
MagickExport MagickBooleanType DeleteNodeFromSplayTree(SplayTreeInfo *splay_tree, const void *key)
Definition: splay-tree.c:603
MagickExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree)
Definition: splay-tree.c:1472
MagickExport void * RelinquishMagickMemory(void *memory)
Definition: memory.c:1038
MagickExport size_t GetNumberOfNodesInSplayTree(const SplayTreeInfo *splay_tree)
Definition: splay-tree.c:976
struct _NodeInfo * right
Definition: splay-tree.c:78
#define MagickExport
void * key
Definition: splay-tree.c:73
MagickExport void RelinquishSemaphoreInfo(SemaphoreInfo **semaphore_info)
Definition: semaphore.c:351
MagickBooleanType debug
Definition: splay-tree.c:106
#define MaxSplayTreeDepth
Definition: splay-tree.c:65
struct _NodeInfo * left
Definition: splay-tree.c:78