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