- Generated by
1.7.5
|
WizardsToolkit
1.0.7
|
00001 /* 00002 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00003 % % 00004 % % 00005 % % 00006 % SSSSS PPPP L AAA Y Y % 00007 % SS P P L A A Y Y % 00008 % SSS PPPP L AAAAA Y % 00009 % SS P L A A Y % 00010 % SSSSS P LLLLL A A Y % 00011 % % 00012 % TTTTT RRRR EEEEE EEEEE % 00013 % T R R E E % 00014 % T RRRR EEE EEE % 00015 % T R R E E % 00016 % T R R EEEEE EEEEE % 00017 % % 00018 % % 00019 % Wizard's Toolkit Self-adjusting Binary Search Tree Methods % 00020 % % 00021 % Software Design % 00022 % John Cristy % 00023 % December 2002 % 00024 % % 00025 % % 00026 % Copyright 1999-2011 ImageMagick Studio LLC, a non-profit organization % 00027 % dedicated to making software imaging solutions freely available. % 00028 % % 00029 % You may not use this file except in compliance with the License. You may % 00030 % obtain a copy of the License at % 00031 % % 00032 % http://www.wizards-toolkit.org/script/license.php % 00033 % % 00034 % Unless required by applicable law or agreed to in writing, software % 00035 % distributed under the License is distributed on an "AS IS" BASIS, % 00036 % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. % 00037 % See the License for the specific language governing permissions and % 00038 % limitations under the License. % 00039 % % 00040 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00041 % 00042 % This module implements the standard handy splay-tree methods for storing and 00043 % retrieving large numbers of data elements. It is loosely based on the Java 00044 % implementation of these algorithms. 00045 % 00046 */ 00047 00048 /* 00049 Include declarations. 00050 */ 00051 #include "wizard/studio.h" 00052 #include "wizard/exception.h" 00053 #include "wizard/exception-private.h" 00054 #include "wizard/log.h" 00055 #include "wizard/memory_.h" 00056 #include "wizard/splay-tree.h" 00057 #include "wizard/semaphore.h" 00058 #include "wizard/string_.h" 00059 00060 /* 00061 Define declarations. 00062 */ 00063 #define MaxSplayTreeDepth 1024 00064 00065 /* 00066 Typedef declarations. 00067 */ 00068 typedef struct _NodeInfo 00069 { 00070 void 00071 *key; 00072 00073 void 00074 *value; 00075 00076 struct _NodeInfo 00077 *left, 00078 *right; 00079 } NodeInfo; 00080 00081 struct _SplayTreeInfo 00082 { 00083 NodeInfo 00084 *root; 00085 00086 int 00087 (*compare)(const void *,const void *); 00088 00089 void 00090 *(*relinquish_key)(void *), 00091 *(*relinquish_value)(void *); 00092 00093 WizardBooleanType 00094 balance; 00095 00096 void 00097 *key, 00098 *next; 00099 00100 size_t 00101 nodes; 00102 00103 WizardBooleanType 00104 debug; 00105 00106 SemaphoreInfo 00107 *semaphore; 00108 00109 size_t 00110 signature; 00111 }; 00112 00113 /* 00114 Forward declarations. 00115 */ 00116 static int 00117 IterateOverSplayTree(SplayTreeInfo *,int (*)(NodeInfo *,const void *), 00118 const void *); 00119 00120 static void 00121 SplaySplayTree(SplayTreeInfo *,const void *); 00122 00123 /* 00124 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00125 % % 00126 % % 00127 % % 00128 % A d d V a l u e T o S p l a y T r e e % 00129 % % 00130 % % 00131 % % 00132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00133 % 00134 % AddValueToSplayTree() adds a value to the splay-tree. 00135 % 00136 % The format of the AddValueToSplayTree method is: 00137 % 00138 % WizardBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree, 00139 % const void *key,const void *value) 00140 % 00141 % A description of each parameter follows: 00142 % 00143 % o splay_tree: The splay-tree info. 00144 % 00145 % o key: The key. 00146 % 00147 % o value: The value. 00148 % 00149 */ 00150 WizardExport WizardBooleanType AddValueToSplayTree(SplayTreeInfo *splay_tree, 00151 const void *key,const void *value) 00152 { 00153 int 00154 compare; 00155 00156 register NodeInfo 00157 *node; 00158 00159 LockSemaphoreInfo(splay_tree->semaphore); 00160 SplaySplayTree(splay_tree,key); 00161 compare=0; 00162 if (splay_tree->root != (NodeInfo *) NULL) 00163 { 00164 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 00165 compare=splay_tree->compare(splay_tree->root->key,key); 00166 else 00167 compare=(splay_tree->root->key > key) ? 1 : 00168 ((splay_tree->root->key < key) ? -1 : 0); 00169 if (compare == 0) 00170 { 00171 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 00172 (splay_tree->root->value != (void *) NULL)) 00173 splay_tree->root->value=splay_tree->relinquish_value( 00174 splay_tree->root->value); 00175 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 00176 (splay_tree->root->key != (void *) NULL)) 00177 splay_tree->root->key=splay_tree->relinquish_key( 00178 splay_tree->root->key); 00179 splay_tree->root->key=(void *) key; 00180 splay_tree->root->value=(void *) value; 00181 UnlockSemaphoreInfo(splay_tree->semaphore); 00182 return(WizardTrue); 00183 } 00184 } 00185 node=(NodeInfo *) AcquireWizardMemory(sizeof(*node)); 00186 if (node == (NodeInfo *) NULL) 00187 { 00188 UnlockSemaphoreInfo(splay_tree->semaphore); 00189 return(WizardFalse); 00190 } 00191 node->key=(void *) key; 00192 node->value=(void *) value; 00193 if (splay_tree->root == (NodeInfo *) NULL) 00194 { 00195 node->left=(NodeInfo *) NULL; 00196 node->right=(NodeInfo *) NULL; 00197 } 00198 else 00199 if (compare < 0) 00200 { 00201 node->left=splay_tree->root; 00202 node->right=node->left->right; 00203 node->left->right=(NodeInfo *) NULL; 00204 } 00205 else 00206 { 00207 node->right=splay_tree->root; 00208 node->left=node->right->left; 00209 node->right->left=(NodeInfo *) NULL; 00210 } 00211 splay_tree->root=node; 00212 splay_tree->key=(void *) NULL; 00213 splay_tree->nodes++; 00214 UnlockSemaphoreInfo(splay_tree->semaphore); 00215 return(WizardTrue); 00216 } 00217 00218 /* 00219 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00220 % % 00221 % % 00222 % % 00223 % B a l a n c e S p l a y T r e e % 00224 % % 00225 % % 00226 % % 00227 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00228 % 00229 % BalanceSplayTree() balances the splay-tree. 00230 % 00231 % The format of the BalanceSplayTree method is: 00232 % 00233 % void *BalanceSplayTree(SplayTreeInfo *splay_tree,const void *key) 00234 % 00235 % A description of each parameter follows: 00236 % 00237 % o splay_tree: The splay-tree info. 00238 % 00239 % o key: The key. 00240 % 00241 */ 00242 00243 static NodeInfo *LinkSplayTreeNodes(NodeInfo **nodes,const size_t low, 00244 const size_t high) 00245 { 00246 register NodeInfo 00247 *node; 00248 00249 size_t 00250 bisect; 00251 00252 bisect=low+(high-low)/2; 00253 node=nodes[bisect]; 00254 if ((low+1) > bisect) 00255 node->left=(NodeInfo *) NULL; 00256 else 00257 node->left=LinkSplayTreeNodes(nodes,low,bisect-1); 00258 if ((bisect+1) > high) 00259 node->right=(NodeInfo *) NULL; 00260 else 00261 node->right=LinkSplayTreeNodes(nodes,bisect+1,high); 00262 return(node); 00263 } 00264 00265 static int SplayTreeToNodeArray(NodeInfo *node,const void *nodes) 00266 { 00267 register const NodeInfo 00268 ***p; 00269 00270 p=(const NodeInfo ***) nodes; 00271 *(*p)=node; 00272 (*p)++; 00273 return(0); 00274 } 00275 00276 static void BalanceSplayTree(SplayTreeInfo *splay_tree) 00277 { 00278 NodeInfo 00279 **node, 00280 **nodes; 00281 00282 if (splay_tree->nodes <= 2) 00283 { 00284 splay_tree->balance=WizardFalse; 00285 return; 00286 } 00287 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes, 00288 sizeof(*nodes)); 00289 if (nodes == (NodeInfo **) NULL) 00290 ThrowWizardFatalError(CacheDomain,MemoryError); 00291 node=nodes; 00292 (void) IterateOverSplayTree(splay_tree,SplayTreeToNodeArray, 00293 (const void *) &node); 00294 splay_tree->root=LinkSplayTreeNodes(nodes,0,splay_tree->nodes-1); 00295 splay_tree->balance=WizardFalse; 00296 nodes=(NodeInfo **) RelinquishWizardMemory(nodes); 00297 } 00298 00299 /* 00300 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00301 % % 00302 % % 00303 % % 00304 % C l o n e S p l a y T r e e % 00305 % % 00306 % % 00307 % % 00308 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00309 % 00310 % CloneSplayTree() clones the splay tree. 00311 % 00312 % The format of the CloneSplayTree method is: 00313 % 00314 % SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree, 00315 % void *(*clone_key)(void *),void *(*cline_value)(void *)) 00316 % 00317 % A description of each parameter follows: 00318 % 00319 % o splay_tree: The splay tree. 00320 % 00321 % o clone_key: The key clone method, typically ConstantString(), called 00322 % whenever a key is added to the splay-tree. 00323 % 00324 % o clone_value: The value clone method; typically ConstantString(), called 00325 % whenever a value object is added to the splay-tree. 00326 % 00327 */ 00328 00329 static void *GetFirstSplayTreeNode(SplayTreeInfo *splay_tree) 00330 { 00331 register NodeInfo 00332 *node; 00333 00334 node=splay_tree->root; 00335 if (splay_tree->root == (NodeInfo *) NULL) 00336 return((NodeInfo *) NULL); 00337 while (node->left != (NodeInfo *) NULL) 00338 node=node->left; 00339 return(node->key); 00340 } 00341 00342 WizardExport SplayTreeInfo *CloneSplayTree(SplayTreeInfo *splay_tree, 00343 void *(*clone_key)(void *),void *(*clone_value)(void *)) 00344 { 00345 register NodeInfo 00346 *next, 00347 *node; 00348 00349 SplayTreeInfo 00350 *clone_tree; 00351 00352 WizardAssert(ResourceDomain,splay_tree != (SplayTreeInfo *) NULL); 00353 WizardAssert(ResourceDomain,splay_tree->signature == WizardSignature); 00354 if (splay_tree->debug != WizardFalse) 00355 (void) LogWizardEvent(TraceEvent,GetWizardModule(),"..."); 00356 clone_tree=NewSplayTree(splay_tree->compare,splay_tree->relinquish_key, 00357 splay_tree->relinquish_value); 00358 LockSemaphoreInfo(splay_tree->semaphore); 00359 if (splay_tree->root == (NodeInfo *) NULL) 00360 { 00361 UnlockSemaphoreInfo(splay_tree->semaphore); 00362 return(clone_tree); 00363 } 00364 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree); 00365 while (next != (NodeInfo *) NULL) 00366 { 00367 SplaySplayTree(splay_tree,next); 00368 (void) AddValueToSplayTree(clone_tree,clone_key(splay_tree->root->key), 00369 clone_value(splay_tree->root->value)); 00370 next=(NodeInfo *) NULL; 00371 node=splay_tree->root->right; 00372 if (node != (NodeInfo *) NULL) 00373 { 00374 while (node->left != (NodeInfo *) NULL) 00375 node=node->left; 00376 next=(NodeInfo *) node->key; 00377 } 00378 } 00379 UnlockSemaphoreInfo(splay_tree->semaphore); 00380 return(clone_tree); 00381 } 00382 00383 /* 00384 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00385 % % 00386 % % 00387 % % 00388 % C o m p a r e S p l a y T r e e S t r i n g % 00389 % % 00390 % % 00391 % % 00392 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00393 % 00394 % CompareSplayTreeString() method finds a node in a splay-tree based on the 00395 % contents of a string. 00396 % 00397 % The format of the CompareSplayTreeString method is: 00398 % 00399 % int CompareSplayTreeString(const void *target,const void *source) 00400 % 00401 % A description of each parameter follows: 00402 % 00403 % o target: The target string. 00404 % 00405 % o source: The source string. 00406 % 00407 */ 00408 WizardExport int CompareSplayTreeString(const void *target,const void *source) 00409 { 00410 const char 00411 *p, 00412 *q; 00413 00414 p=(const char *) target; 00415 q=(const char *) source; 00416 return(LocaleCompare(p,q)); 00417 } 00418 00419 /* 00420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00421 % % 00422 % % 00423 % % 00424 % 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 % 00425 % % 00426 % % 00427 % % 00428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00429 % 00430 % CompareSplayTreeStringInfo() finds a node in a splay-tree based on the 00431 % contents of a string. 00432 % 00433 % The format of the CompareSplayTreeStringInfo method is: 00434 % 00435 % int CompareSplayTreeStringInfo(const void *target,const void *source) 00436 % 00437 % A description of each parameter follows: 00438 % 00439 % o target: The target string. 00440 % 00441 % o source: The source string. 00442 % 00443 */ 00444 WizardExport int CompareSplayTreeStringInfo(const void *target, 00445 const void *source) 00446 { 00447 const StringInfo 00448 *p, 00449 *q; 00450 00451 p=(const StringInfo *) target; 00452 q=(const StringInfo *) source; 00453 return(CompareStringInfo(p,q)); 00454 } 00455 00456 /* 00457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00458 % % 00459 % % 00460 % % 00461 % 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 % 00462 % % 00463 % % 00464 % % 00465 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00466 % 00467 % DeleteNodeByValueFromSplayTree() deletes a node by value from the 00468 % splay-tree. 00469 % 00470 % The format of the DeleteNodeByValueFromSplayTree method is: 00471 % 00472 % WizardBooleanType DeleteNodeByValueFromSplayTree( 00473 % SplayTreeInfo *splay_tree,const void *value) 00474 % 00475 % A description of each parameter follows: 00476 % 00477 % o splay_tree: The splay-tree info. 00478 % 00479 % o value: The value. 00480 % 00481 */ 00482 WizardExport WizardBooleanType DeleteNodeByValueFromSplayTree( 00483 SplayTreeInfo *splay_tree,const void *value) 00484 { 00485 register NodeInfo 00486 *next, 00487 *node; 00488 00489 WizardAssert(ResourceDomain,splay_tree != (SplayTreeInfo *) NULL); 00490 WizardAssert(ResourceDomain,splay_tree->signature == WizardSignature); 00491 if (splay_tree->debug != WizardFalse) 00492 (void) LogWizardEvent(TraceEvent,GetWizardModule(),"..."); 00493 LockSemaphoreInfo(splay_tree->semaphore); 00494 if (splay_tree->root == (NodeInfo *) NULL) 00495 { 00496 UnlockSemaphoreInfo(splay_tree->semaphore); 00497 return(WizardFalse); 00498 } 00499 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree); 00500 while (next != (NodeInfo *) NULL) 00501 { 00502 SplaySplayTree(splay_tree,next); 00503 next=(NodeInfo *) NULL; 00504 node=splay_tree->root->right; 00505 if (node != (NodeInfo *) NULL) 00506 { 00507 while (node->left != (NodeInfo *) NULL) 00508 node=node->left; 00509 next=(NodeInfo *) node->key; 00510 } 00511 if (splay_tree->root->value == value) 00512 { 00513 int 00514 compare; 00515 00516 register NodeInfo 00517 *left, 00518 *right; 00519 00520 void 00521 *key; 00522 00523 /* 00524 We found the node that matches the value; now delete it. 00525 */ 00526 key=splay_tree->root->key; 00527 SplaySplayTree(splay_tree,key); 00528 splay_tree->key=(void *) NULL; 00529 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 00530 compare=splay_tree->compare(splay_tree->root->key,key); 00531 else 00532 compare=(splay_tree->root->key > key) ? 1 : 00533 ((splay_tree->root->key < key) ? -1 : 0); 00534 if (compare != 0) 00535 { 00536 UnlockSemaphoreInfo(splay_tree->semaphore); 00537 return(WizardFalse); 00538 } 00539 left=splay_tree->root->left; 00540 right=splay_tree->root->right; 00541 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 00542 (splay_tree->root->value != (void *) NULL)) 00543 splay_tree->root->value=splay_tree->relinquish_value( 00544 splay_tree->root->value); 00545 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 00546 (splay_tree->root->key != (void *) NULL)) 00547 splay_tree->root->key=splay_tree->relinquish_key( 00548 splay_tree->root->key); 00549 splay_tree->root=(NodeInfo *) RelinquishWizardMemory(splay_tree->root); 00550 splay_tree->nodes--; 00551 if (left == (NodeInfo *) NULL) 00552 { 00553 splay_tree->root=right; 00554 UnlockSemaphoreInfo(splay_tree->semaphore); 00555 return(WizardTrue); 00556 } 00557 splay_tree->root=left; 00558 if (right != (NodeInfo *) NULL) 00559 { 00560 while (left->right != (NodeInfo *) NULL) 00561 left=left->right; 00562 left->right=right; 00563 } 00564 UnlockSemaphoreInfo(splay_tree->semaphore); 00565 return(WizardTrue); 00566 } 00567 } 00568 UnlockSemaphoreInfo(splay_tree->semaphore); 00569 return(WizardFalse); 00570 } 00571 00572 /* 00573 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00574 % % 00575 % % 00576 % % 00577 % D e l e t e N o d e F r o m S p l a y T r e e % 00578 % % 00579 % % 00580 % % 00581 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00582 % 00583 % DeleteNodeFromSplayTree() deletes a node from the splay-tree. 00584 % 00585 % The format of the DeleteNodeFromSplayTree method is: 00586 % 00587 % WizardBooleanType DeleteNodeFromSplayTree(SplayTreeInfo *splay_tree, 00588 % const void *key) 00589 % 00590 % A description of each parameter follows: 00591 % 00592 % o splay_tree: The splay-tree info. 00593 % 00594 % o key: The key. 00595 % 00596 */ 00597 WizardExport WizardBooleanType DeleteNodeFromSplayTree( 00598 SplayTreeInfo *splay_tree,const void *key) 00599 { 00600 int 00601 compare; 00602 00603 register NodeInfo 00604 *left, 00605 *right; 00606 00607 WizardAssert(ResourceDomain,splay_tree != (SplayTreeInfo *) NULL); 00608 WizardAssert(ResourceDomain,splay_tree->signature == WizardSignature); 00609 if (splay_tree->debug != WizardFalse) 00610 (void) LogWizardEvent(TraceEvent,GetWizardModule(),"..."); 00611 if (splay_tree->root == (NodeInfo *) NULL) 00612 return(WizardFalse); 00613 LockSemaphoreInfo(splay_tree->semaphore); 00614 SplaySplayTree(splay_tree,key); 00615 splay_tree->key=(void *) NULL; 00616 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 00617 compare=splay_tree->compare(splay_tree->root->key,key); 00618 else 00619 compare=(splay_tree->root->key > key) ? 1 : 00620 ((splay_tree->root->key < key) ? -1 : 0); 00621 if (compare != 0) 00622 { 00623 UnlockSemaphoreInfo(splay_tree->semaphore); 00624 return(WizardFalse); 00625 } 00626 left=splay_tree->root->left; 00627 right=splay_tree->root->right; 00628 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 00629 (splay_tree->root->value != (void *) NULL)) 00630 splay_tree->root->value=splay_tree->relinquish_value( 00631 splay_tree->root->value); 00632 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 00633 (splay_tree->root->key != (void *) NULL)) 00634 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key); 00635 splay_tree->root=(NodeInfo *) RelinquishWizardMemory(splay_tree->root); 00636 splay_tree->nodes--; 00637 if (left == (NodeInfo *) NULL) 00638 { 00639 splay_tree->root=right; 00640 UnlockSemaphoreInfo(splay_tree->semaphore); 00641 return(WizardTrue); 00642 } 00643 splay_tree->root=left; 00644 if (right != (NodeInfo *) NULL) 00645 { 00646 while (left->right != (NodeInfo *) NULL) 00647 left=left->right; 00648 left->right=right; 00649 } 00650 UnlockSemaphoreInfo(splay_tree->semaphore); 00651 return(WizardTrue); 00652 } 00653 00654 /* 00655 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00656 % % 00657 % % 00658 % % 00659 % D e s t r o y S p l a y T r e e % 00660 % % 00661 % % 00662 % % 00663 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00664 % 00665 % DestroySplayTree() destroys the splay-tree. 00666 % 00667 % The format of the DestroySplayTree method is: 00668 % 00669 % SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree) 00670 % 00671 % A description of each parameter follows: 00672 % 00673 % o splay_tree: The splay tree. 00674 % 00675 */ 00676 WizardExport SplayTreeInfo *DestroySplayTree(SplayTreeInfo *splay_tree) 00677 { 00678 NodeInfo 00679 *node; 00680 00681 register NodeInfo 00682 *active, 00683 *pend; 00684 00685 LockSemaphoreInfo(splay_tree->semaphore); 00686 if (splay_tree->root != (NodeInfo *) NULL) 00687 { 00688 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 00689 (splay_tree->root->value != (void *) NULL)) 00690 splay_tree->root->value=splay_tree->relinquish_value( 00691 splay_tree->root->value); 00692 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 00693 (splay_tree->root->key != (void *) NULL)) 00694 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key); 00695 splay_tree->root->key=(void *) NULL; 00696 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; ) 00697 { 00698 active=pend; 00699 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; ) 00700 { 00701 if (active->left != (NodeInfo *) NULL) 00702 { 00703 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 00704 (active->left->value != (void *) NULL)) 00705 active->left->value=splay_tree->relinquish_value( 00706 active->left->value); 00707 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 00708 (active->left->key != (void *) NULL)) 00709 active->left->key=splay_tree->relinquish_key(active->left->key); 00710 active->left->key=(void *) pend; 00711 pend=active->left; 00712 } 00713 if (active->right != (NodeInfo *) NULL) 00714 { 00715 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 00716 (active->right->value != (void *) NULL)) 00717 active->right->value=splay_tree->relinquish_value( 00718 active->right->value); 00719 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 00720 (active->right->key != (void *) NULL)) 00721 active->right->key=splay_tree->relinquish_key( 00722 active->right->key); 00723 active->right->key=(void *) pend; 00724 pend=active->right; 00725 } 00726 node=active; 00727 active=(NodeInfo *) node->key; 00728 node=(NodeInfo *) RelinquishWizardMemory(node); 00729 } 00730 } 00731 } 00732 splay_tree->signature=(~WizardSignature); 00733 UnlockSemaphoreInfo(splay_tree->semaphore); 00734 DestroySemaphoreInfo(&splay_tree->semaphore); 00735 splay_tree=(SplayTreeInfo *) RelinquishWizardMemory(splay_tree); 00736 return(splay_tree); 00737 } 00738 00739 /* 00740 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00741 % % 00742 % % 00743 % % 00744 % G e t N e x t K e y I n S p l a y T r e e % 00745 % % 00746 % % 00747 % % 00748 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00749 % 00750 % GetNextKeyInSplayTree() gets the next key in the splay-tree. 00751 % 00752 % The format of the GetNextKeyInSplayTree method is: 00753 % 00754 % const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree) 00755 % 00756 % A description of each parameter follows: 00757 % 00758 % o splay_tree: The splay tree. 00759 % 00760 % o key: The key. 00761 % 00762 */ 00763 WizardExport const void *GetNextKeyInSplayTree(SplayTreeInfo *splay_tree) 00764 { 00765 register NodeInfo 00766 *node; 00767 00768 void 00769 *key; 00770 00771 WizardAssert(ResourceDomain,splay_tree != (SplayTreeInfo *) NULL); 00772 WizardAssert(ResourceDomain,splay_tree->signature == WizardSignature); 00773 if (splay_tree->debug != WizardFalse) 00774 (void) LogWizardEvent(TraceEvent,GetWizardModule(),"..."); 00775 if ((splay_tree->root == (NodeInfo *) NULL) || 00776 (splay_tree->next == (void *) NULL)) 00777 return((void *) NULL); 00778 LockSemaphoreInfo(splay_tree->semaphore); 00779 SplaySplayTree(splay_tree,splay_tree->next); 00780 splay_tree->next=(void *) NULL; 00781 node=splay_tree->root->right; 00782 if (node != (NodeInfo *) NULL) 00783 { 00784 while (node->left != (NodeInfo *) NULL) 00785 node=node->left; 00786 splay_tree->next=node->key; 00787 } 00788 key=splay_tree->root->key; 00789 UnlockSemaphoreInfo(splay_tree->semaphore); 00790 return(key); 00791 } 00792 00793 /* 00794 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00795 % % 00796 % % 00797 % % 00798 % G e t N e x t V a l u e I n S p l a y T r e e % 00799 % % 00800 % % 00801 % % 00802 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00803 % 00804 % GetNextValueInSplayTree() gets the next value in the splay-tree. 00805 % 00806 % The format of the GetNextValueInSplayTree method is: 00807 % 00808 % const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree) 00809 % 00810 % A description of each parameter follows: 00811 % 00812 % o splay_tree: The splay tree. 00813 % 00814 % o key: The key. 00815 % 00816 */ 00817 WizardExport const void *GetNextValueInSplayTree(SplayTreeInfo *splay_tree) 00818 { 00819 register NodeInfo 00820 *node; 00821 00822 void 00823 *value; 00824 00825 WizardAssert(ResourceDomain,splay_tree != (SplayTreeInfo *) NULL); 00826 WizardAssert(ResourceDomain,splay_tree->signature == WizardSignature); 00827 if (splay_tree->debug != WizardFalse) 00828 (void) LogWizardEvent(TraceEvent,GetWizardModule(),"..."); 00829 if ((splay_tree->root == (NodeInfo *) NULL) || 00830 (splay_tree->next == (void *) NULL)) 00831 return((void *) NULL); 00832 LockSemaphoreInfo(splay_tree->semaphore); 00833 SplaySplayTree(splay_tree,splay_tree->next); 00834 splay_tree->next=(void *) NULL; 00835 node=splay_tree->root->right; 00836 if (node != (NodeInfo *) NULL) 00837 { 00838 while (node->left != (NodeInfo *) NULL) 00839 node=node->left; 00840 splay_tree->next=node->key; 00841 } 00842 value=splay_tree->root->value; 00843 UnlockSemaphoreInfo(splay_tree->semaphore); 00844 return(value); 00845 } 00846 00847 /* 00848 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00849 % % 00850 % % 00851 % % 00852 % G e t V a l u e F r o m S p l a y T r e e % 00853 % % 00854 % % 00855 % % 00856 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00857 % 00858 % GetValueFromSplayTree() gets a value from the splay-tree by its key. 00859 % 00860 % The format of the GetValueFromSplayTree method is: 00861 % 00862 % const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree, 00863 % const void *key) 00864 % 00865 % A description of each parameter follows: 00866 % 00867 % o splay_tree: The splay tree. 00868 % 00869 % o key: The key. 00870 % 00871 */ 00872 WizardExport const void *GetValueFromSplayTree(SplayTreeInfo *splay_tree, 00873 const void *key) 00874 { 00875 int 00876 compare; 00877 00878 void 00879 *value; 00880 00881 WizardAssert(ResourceDomain,splay_tree != (SplayTreeInfo *) NULL); 00882 WizardAssert(ResourceDomain,splay_tree->signature == WizardSignature); 00883 if (splay_tree->debug != WizardFalse) 00884 (void) LogWizardEvent(TraceEvent,GetWizardModule(),"..."); 00885 if (splay_tree->root == (NodeInfo *) NULL) 00886 return((void *) NULL); 00887 LockSemaphoreInfo(splay_tree->semaphore); 00888 SplaySplayTree(splay_tree,key); 00889 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 00890 compare=splay_tree->compare(splay_tree->root->key,key); 00891 else 00892 compare=(splay_tree->root->key > key) ? 1 : 00893 ((splay_tree->root->key < key) ? -1 : 0); 00894 if (compare != 0) 00895 { 00896 UnlockSemaphoreInfo(splay_tree->semaphore); 00897 return((void *) NULL); 00898 } 00899 value=splay_tree->root->value; 00900 UnlockSemaphoreInfo(splay_tree->semaphore); 00901 return(value); 00902 } 00903 00904 /* 00905 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00906 % % 00907 % % 00908 % % 00909 % 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 % 00910 % % 00911 % % 00912 % % 00913 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00914 % 00915 % GetNumberOfNodesInSplayTree() returns the number of nodes in the splay-tree. 00916 % 00917 % The format of the GetNumberOfNodesInSplayTree method is: 00918 % 00919 % size_t GetNumberOfNodesInSplayTree( 00920 % const SplayTreeInfo *splay_tree) 00921 % 00922 % A description of each parameter follows: 00923 % 00924 % o splay_tree: The splay tree. 00925 % 00926 */ 00927 WizardExport size_t GetNumberOfNodesInSplayTree( 00928 const SplayTreeInfo *splay_tree) 00929 { 00930 WizardAssert(ResourceDomain,splay_tree != (SplayTreeInfo *) NULL); 00931 WizardAssert(ResourceDomain,splay_tree->signature == WizardSignature); 00932 if (splay_tree->debug != WizardFalse) 00933 (void) LogWizardEvent(TraceEvent,GetWizardModule(),"..."); 00934 return(splay_tree->nodes); 00935 } 00936 00937 /* 00938 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00939 % % 00940 % % 00941 % % 00942 % I t e r a t e O v e r S p l a y T r e e % 00943 % % 00944 % % 00945 % % 00946 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00947 % 00948 % IterateOverSplayTree() iterates over the splay-tree. 00949 % 00950 % The format of the IterateOverSplayTree method is: 00951 % 00952 % int IterateOverSplayTree(SplayTreeInfo *splay_tree, 00953 % int (*method)(NodeInfo *,void *),const void *value) 00954 % 00955 % A description of each parameter follows: 00956 % 00957 % o splay_tree: The splay-tree info. 00958 % 00959 % o method: The method. 00960 % 00961 % o value: The value. 00962 % 00963 */ 00964 static int IterateOverSplayTree(SplayTreeInfo *splay_tree, 00965 int (*method)(NodeInfo *,const void *),const void *value) 00966 { 00967 typedef enum 00968 { 00969 LeftTransition, 00970 RightTransition, 00971 DownTransition, 00972 UpTransition 00973 } TransitionType; 00974 00975 int 00976 status; 00977 00978 WizardBooleanType 00979 final_transition; 00980 00981 NodeInfo 00982 **nodes; 00983 00984 register ssize_t 00985 i; 00986 00987 register NodeInfo 00988 *node; 00989 00990 TransitionType 00991 transition; 00992 00993 unsigned char 00994 *transitions; 00995 00996 if (splay_tree->root == (NodeInfo *) NULL) 00997 return(0); 00998 nodes=(NodeInfo **) AcquireQuantumMemory((size_t) splay_tree->nodes, 00999 sizeof(*nodes)); 01000 transitions=(unsigned char *) AcquireQuantumMemory((size_t) splay_tree->nodes, 01001 sizeof(*transitions)); 01002 if ((nodes == (NodeInfo **) NULL) || (transitions == (unsigned char *) NULL)) 01003 ThrowWizardFatalError(CacheDomain,MemoryError); 01004 status=0; 01005 final_transition=WizardFalse; 01006 nodes[0]=splay_tree->root; 01007 transitions[0]=(unsigned char) LeftTransition; 01008 for (i=0; final_transition == WizardFalse; ) 01009 { 01010 node=nodes[i]; 01011 transition=(TransitionType) transitions[i]; 01012 switch (transition) 01013 { 01014 case LeftTransition: 01015 { 01016 transitions[i]=(unsigned char) DownTransition; 01017 if (node->left == (NodeInfo *) NULL) 01018 break; 01019 i++; 01020 nodes[i]=node->left; 01021 transitions[i]=(unsigned char) LeftTransition; 01022 break; 01023 } 01024 case RightTransition: 01025 { 01026 transitions[i]=(unsigned char) UpTransition; 01027 if (node->right == (NodeInfo *) NULL) 01028 break; 01029 i++; 01030 nodes[i]=node->right; 01031 transitions[i]=(unsigned char) LeftTransition; 01032 break; 01033 } 01034 case DownTransition: 01035 default: 01036 { 01037 transitions[i]=(unsigned char) RightTransition; 01038 status=(*method)(node,value); 01039 if (status != 0) 01040 final_transition=WizardTrue; 01041 break; 01042 } 01043 case UpTransition: 01044 { 01045 if (i == 0) 01046 { 01047 final_transition=WizardTrue; 01048 break; 01049 } 01050 i--; 01051 break; 01052 } 01053 } 01054 } 01055 nodes=(NodeInfo **) RelinquishWizardMemory(nodes); 01056 transitions=(unsigned char *) RelinquishWizardMemory(transitions); 01057 return(status); 01058 } 01059 01060 /* 01061 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 01062 % % 01063 % % 01064 % % 01065 % N e w S p l a y T r e e % 01066 % % 01067 % % 01068 % % 01069 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 01070 % 01071 % NewSplayTree() returns a pointer to a SplayTreeInfo structure initialized 01072 % to default values. 01073 % 01074 % The format of the NewSplayTree method is: 01075 % 01076 % SplayTreeInfo *NewSplayTree(int (*compare)(const void *,const void *), 01077 % void *(*relinquish_key)(void *),void *(*relinquish_value)(void *)) 01078 % 01079 % A description of each parameter follows: 01080 % 01081 % o compare: The compare method. 01082 % 01083 % o relinquish_key: The key deallocation method, typically 01084 % RelinquishWizardMemory(), called whenever a key is removed from the 01085 % splay-tree. 01086 % 01087 % o relinquish_value: The value deallocation method; typically 01088 % RelinquishWizardMemory(), called whenever a value object is removed from 01089 % the splay-tree. 01090 % 01091 */ 01092 WizardExport SplayTreeInfo *NewSplayTree( 01093 int (*compare)(const void *,const void *),void *(*relinquish_key)(void *), 01094 void *(*relinquish_value)(void *)) 01095 { 01096 SplayTreeInfo 01097 *splay_tree; 01098 01099 splay_tree=(SplayTreeInfo *) AcquireWizardMemory(sizeof(*splay_tree)); 01100 if (splay_tree == (SplayTreeInfo *) NULL) 01101 ThrowWizardFatalError(CacheDomain,MemoryError); 01102 (void) ResetWizardMemory(splay_tree,0,sizeof(*splay_tree)); 01103 splay_tree->root=(NodeInfo *) NULL; 01104 splay_tree->compare=compare; 01105 splay_tree->relinquish_key=relinquish_key; 01106 splay_tree->relinquish_value=relinquish_value; 01107 splay_tree->balance=WizardFalse; 01108 splay_tree->key=(void *) NULL; 01109 splay_tree->next=(void *) NULL; 01110 splay_tree->nodes=0; 01111 splay_tree->debug=IsEventLogging(); 01112 splay_tree->semaphore=AllocateSemaphoreInfo(); 01113 splay_tree->signature=WizardSignature; 01114 return(splay_tree); 01115 } 01116 01117 /* 01118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 01119 % % 01120 % % 01121 % % 01122 % 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 % 01123 % % 01124 % % 01125 % % 01126 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 01127 % 01128 % RemoveNodeByValueFromSplayTree() removes a node by value from the splay-tree 01129 % and returns its key. 01130 % 01131 % The format of the RemoveNodeByValueFromSplayTree method is: 01132 % 01133 % void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree, 01134 % const void *value) 01135 % 01136 % A description of each parameter follows: 01137 % 01138 % o splay_tree: The splay-tree info. 01139 % 01140 % o value: The value. 01141 % 01142 */ 01143 WizardExport void *RemoveNodeByValueFromSplayTree(SplayTreeInfo *splay_tree, 01144 const void *value) 01145 { 01146 register NodeInfo 01147 *next, 01148 *node; 01149 01150 void 01151 *key; 01152 01153 WizardAssert(ResourceDomain,splay_tree != (SplayTreeInfo *) NULL); 01154 WizardAssert(ResourceDomain,splay_tree->signature == WizardSignature); 01155 if (splay_tree->debug != WizardFalse) 01156 (void) LogWizardEvent(TraceEvent,GetWizardModule(),"..."); 01157 key=(void *) NULL; 01158 if (splay_tree->root == (NodeInfo *) NULL) 01159 return(key); 01160 LockSemaphoreInfo(splay_tree->semaphore); 01161 next=(NodeInfo *) GetFirstSplayTreeNode(splay_tree); 01162 while (next != (NodeInfo *) NULL) 01163 { 01164 SplaySplayTree(splay_tree,next); 01165 next=(NodeInfo *) NULL; 01166 node=splay_tree->root->right; 01167 if (node != (NodeInfo *) NULL) 01168 { 01169 while (node->left != (NodeInfo *) NULL) 01170 node=node->left; 01171 next=(NodeInfo *) node->key; 01172 } 01173 if (splay_tree->root->value == value) 01174 { 01175 int 01176 compare; 01177 01178 register NodeInfo 01179 *left, 01180 *right; 01181 01182 /* 01183 We found the node that matches the value; now remove it. 01184 */ 01185 key=splay_tree->root->key; 01186 SplaySplayTree(splay_tree,key); 01187 splay_tree->key=(void *) NULL; 01188 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 01189 compare=splay_tree->compare(splay_tree->root->key,key); 01190 else 01191 compare=(splay_tree->root->key > key) ? 1 : 01192 ((splay_tree->root->key < key) ? -1 : 0); 01193 if (compare != 0) 01194 { 01195 UnlockSemaphoreInfo(splay_tree->semaphore); 01196 return(key); 01197 } 01198 left=splay_tree->root->left; 01199 right=splay_tree->root->right; 01200 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 01201 (splay_tree->root->value != (void *) NULL)) 01202 splay_tree->root->value=splay_tree->relinquish_value( 01203 splay_tree->root->value); 01204 splay_tree->root=(NodeInfo *) RelinquishWizardMemory(splay_tree->root); 01205 splay_tree->nodes--; 01206 if (left == (NodeInfo *) NULL) 01207 { 01208 splay_tree->root=right; 01209 UnlockSemaphoreInfo(splay_tree->semaphore); 01210 return(key); 01211 } 01212 splay_tree->root=left; 01213 if (right != (NodeInfo *) NULL) 01214 { 01215 while (left->right != (NodeInfo *) NULL) 01216 left=left->right; 01217 left->right=right; 01218 } 01219 UnlockSemaphoreInfo(splay_tree->semaphore); 01220 return(key); 01221 } 01222 } 01223 UnlockSemaphoreInfo(splay_tree->semaphore); 01224 return(key); 01225 } 01226 01227 /* 01228 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 01229 % % 01230 % % 01231 % % 01232 % R e m o v e N o d e F r o m S p l a y T r e e % 01233 % % 01234 % % 01235 % % 01236 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 01237 % 01238 % RemoveNodeFromSplayTree() removes a node from the splay-tree and returns its 01239 % value. 01240 % 01241 % The format of the RemoveNodeFromSplayTree method is: 01242 % 01243 % void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree,const void *key) 01244 % 01245 % A description of each parameter follows: 01246 % 01247 % o splay_tree: The splay-tree info. 01248 % 01249 % o key: The key. 01250 % 01251 */ 01252 WizardExport void *RemoveNodeFromSplayTree(SplayTreeInfo *splay_tree, 01253 const void *key) 01254 { 01255 int 01256 compare; 01257 01258 register NodeInfo 01259 *left, 01260 *right; 01261 01262 void 01263 *value; 01264 01265 WizardAssert(ResourceDomain,splay_tree != (SplayTreeInfo *) NULL); 01266 WizardAssert(ResourceDomain,splay_tree->signature == WizardSignature); 01267 if (splay_tree->debug != WizardFalse) 01268 (void) LogWizardEvent(TraceEvent,GetWizardModule(),"..."); 01269 value=(void *) NULL; 01270 if (splay_tree->root == (NodeInfo *) NULL) 01271 return(value); 01272 LockSemaphoreInfo(splay_tree->semaphore); 01273 SplaySplayTree(splay_tree,key); 01274 splay_tree->key=(void *) NULL; 01275 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 01276 compare=splay_tree->compare(splay_tree->root->key,key); 01277 else 01278 compare=(splay_tree->root->key > key) ? 1 : 01279 ((splay_tree->root->key < key) ? -1 : 0); 01280 if (compare != 0) 01281 { 01282 UnlockSemaphoreInfo(splay_tree->semaphore); 01283 return(value); 01284 } 01285 left=splay_tree->root->left; 01286 right=splay_tree->root->right; 01287 value=splay_tree->root->value; 01288 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 01289 (splay_tree->root->key != (void *) NULL)) 01290 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key); 01291 splay_tree->root=(NodeInfo *) RelinquishWizardMemory(splay_tree->root); 01292 splay_tree->nodes--; 01293 if (left == (NodeInfo *) NULL) 01294 { 01295 splay_tree->root=right; 01296 UnlockSemaphoreInfo(splay_tree->semaphore); 01297 return(value); 01298 } 01299 splay_tree->root=left; 01300 if (right != (NodeInfo *) NULL) 01301 { 01302 while (left->right != (NodeInfo *) NULL) 01303 left=left->right; 01304 left->right=right; 01305 } 01306 UnlockSemaphoreInfo(splay_tree->semaphore); 01307 return(value); 01308 } 01309 01310 /* 01311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 01312 % % 01313 % % 01314 % % 01315 % R e s e t S p l a y T r e e % 01316 % % 01317 % % 01318 % % 01319 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 01320 % 01321 % ResetSplayTree() resets the splay-tree. That is, it deletes all the nodes 01322 % from the tree. 01323 % 01324 % The format of the ResetSplayTree method is: 01325 % 01326 % ResetSplayTree(SplayTreeInfo *splay_tree) 01327 % 01328 % A description of each parameter follows: 01329 % 01330 % o splay_tree: the splay tree. 01331 % 01332 */ 01333 WizardExport void ResetSplayTree(SplayTreeInfo *splay_tree) 01334 { 01335 NodeInfo 01336 *node; 01337 01338 register NodeInfo 01339 *active, 01340 *pend; 01341 01342 WizardAssert(ResourceDomain,splay_tree != (SplayTreeInfo *) NULL); 01343 WizardAssert(ResourceDomain,splay_tree->signature == WizardSignature); 01344 if (splay_tree->debug != WizardFalse) 01345 (void) LogWizardEvent(TraceEvent,GetWizardModule(),"..."); 01346 LockSemaphoreInfo(splay_tree->semaphore); 01347 if (splay_tree->root != (NodeInfo *) NULL) 01348 { 01349 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 01350 (splay_tree->root->value != (void *) NULL)) 01351 splay_tree->root->value=splay_tree->relinquish_value( 01352 splay_tree->root->value); 01353 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 01354 (splay_tree->root->key != (void *) NULL)) 01355 splay_tree->root->key=splay_tree->relinquish_key(splay_tree->root->key); 01356 splay_tree->root->key=(void *) NULL; 01357 for (pend=splay_tree->root; pend != (NodeInfo *) NULL; ) 01358 { 01359 active=pend; 01360 for (pend=(NodeInfo *) NULL; active != (NodeInfo *) NULL; ) 01361 { 01362 if (active->left != (NodeInfo *) NULL) 01363 { 01364 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 01365 (active->left->value != (void *) NULL)) 01366 active->left->value=splay_tree->relinquish_value( 01367 active->left->value); 01368 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 01369 (active->left->key != (void *) NULL)) 01370 active->left->key=splay_tree->relinquish_key(active->left->key); 01371 active->left->key=(void *) pend; 01372 pend=active->left; 01373 } 01374 if (active->right != (NodeInfo *) NULL) 01375 { 01376 if ((splay_tree->relinquish_value != (void *(*)(void *)) NULL) && 01377 (active->right->value != (void *) NULL)) 01378 active->right->value=splay_tree->relinquish_value( 01379 active->right->value); 01380 if ((splay_tree->relinquish_key != (void *(*)(void *)) NULL) && 01381 (active->right->key != (void *) NULL)) 01382 active->right->key=splay_tree->relinquish_key( 01383 active->right->key); 01384 active->right->key=(void *) pend; 01385 pend=active->right; 01386 } 01387 node=active; 01388 active=(NodeInfo *) node->key; 01389 node=(NodeInfo *) RelinquishWizardMemory(node); 01390 } 01391 } 01392 } 01393 splay_tree->root=(NodeInfo *) NULL; 01394 splay_tree->key=(void *) NULL; 01395 splay_tree->next=(void *) NULL; 01396 splay_tree->nodes=0; 01397 splay_tree->balance=WizardFalse; 01398 UnlockSemaphoreInfo(splay_tree->semaphore); 01399 } 01400 01401 /* 01402 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 01403 % % 01404 % % 01405 % % 01406 % R e s e t S p l a y T r e e I t e r a t o r % 01407 % % 01408 % % 01409 % % 01410 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 01411 % 01412 % ResetSplayTreeIterator() resets the splay-tree iterator. Use it in 01413 % conjunction with GetNextValueInSplayTree() to iterate over all the nodes in 01414 % the splay-tree. 01415 % 01416 % The format of the ResetSplayTreeIterator method is: 01417 % 01418 % ResetSplayTreeIterator(SplayTreeInfo *splay_tree) 01419 % 01420 % A description of each parameter follows: 01421 % 01422 % o splay_tree: The splay tree. 01423 % 01424 */ 01425 WizardExport void ResetSplayTreeIterator(SplayTreeInfo *splay_tree) 01426 { 01427 WizardAssert(ResourceDomain,splay_tree != (SplayTreeInfo *) NULL); 01428 WizardAssert(ResourceDomain,splay_tree->signature == WizardSignature); 01429 if (splay_tree->debug != WizardFalse) 01430 (void) LogWizardEvent(TraceEvent,GetWizardModule(),"..."); 01431 LockSemaphoreInfo(splay_tree->semaphore); 01432 splay_tree->next=GetFirstSplayTreeNode(splay_tree); 01433 UnlockSemaphoreInfo(splay_tree->semaphore); 01434 } 01435 01436 /* 01437 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 01438 % % 01439 % % 01440 % % 01441 % S p l a y S p l a y T r e e % 01442 % % 01443 % % 01444 % % 01445 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 01446 % 01447 % SplaySplayTree() splays the splay-tree. 01448 % 01449 % The format of the SplaySplayTree method is: 01450 % 01451 % void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key, 01452 % NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent) 01453 % 01454 % A description of each parameter follows: 01455 % 01456 % o splay_tree: The splay-tree info. 01457 % 01458 % o key: The key. 01459 % 01460 % o node: The node. 01461 % 01462 % o parent: The parent node. 01463 % 01464 % o grandparent: The grandparent node. 01465 % 01466 */ 01467 01468 static NodeInfo *Splay(SplayTreeInfo *splay_tree,const size_t depth, 01469 const void *key,NodeInfo **node,NodeInfo **parent,NodeInfo **grandparent) 01470 { 01471 int 01472 compare; 01473 01474 NodeInfo 01475 **next; 01476 01477 register NodeInfo 01478 *n, 01479 *p; 01480 01481 n=(*node); 01482 if (n == (NodeInfo *) NULL) 01483 return(*parent); 01484 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 01485 compare=splay_tree->compare(n->key,key); 01486 else 01487 compare=(n->key > key) ? 1 : ((n->key < key) ? -1 : 0); 01488 next=(NodeInfo **) NULL; 01489 if (compare > 0) 01490 next=(&n->left); 01491 else 01492 if (compare < 0) 01493 next=(&n->right); 01494 if (next != (NodeInfo **) NULL) 01495 { 01496 if (depth >= MaxSplayTreeDepth) 01497 { 01498 splay_tree->balance=WizardTrue; 01499 return(n); 01500 } 01501 n=Splay(splay_tree,depth+1,key,next,node,parent); 01502 if ((n != *node) || (splay_tree->balance != WizardFalse)) 01503 return(n); 01504 } 01505 if (parent == (NodeInfo **) NULL) 01506 return(n); 01507 if (grandparent == (NodeInfo **) NULL) 01508 { 01509 if (n == (*parent)->left) 01510 { 01511 *node=n->right; 01512 n->right=(*parent); 01513 } 01514 else 01515 { 01516 *node=n->left; 01517 n->left=(*parent); 01518 } 01519 *parent=n; 01520 return(n); 01521 } 01522 if ((n == (*parent)->left) && (*parent == (*grandparent)->left)) 01523 { 01524 p=(*parent); 01525 (*grandparent)->left=p->right; 01526 p->right=(*grandparent); 01527 p->left=n->right; 01528 n->right=p; 01529 *grandparent=n; 01530 return(n); 01531 } 01532 if ((n == (*parent)->right) && (*parent == (*grandparent)->right)) 01533 { 01534 p=(*parent); 01535 (*grandparent)->right=p->left; 01536 p->left=(*grandparent); 01537 p->right=n->left; 01538 n->left=p; 01539 *grandparent=n; 01540 return(n); 01541 } 01542 if (n == (*parent)->left) 01543 { 01544 (*parent)->left=n->right; 01545 n->right=(*parent); 01546 (*grandparent)->right=n->left; 01547 n->left=(*grandparent); 01548 *grandparent=n; 01549 return(n); 01550 } 01551 (*parent)->right=n->left; 01552 n->left=(*parent); 01553 (*grandparent)->left=n->right; 01554 n->right=(*grandparent); 01555 *grandparent=n; 01556 return(n); 01557 } 01558 01559 static void SplaySplayTree(SplayTreeInfo *splay_tree,const void *key) 01560 { 01561 if (splay_tree->root == (NodeInfo *) NULL) 01562 return; 01563 if (splay_tree->key != (void *) NULL) 01564 { 01565 int 01566 compare; 01567 01568 if (splay_tree->compare != (int (*)(const void *,const void *)) NULL) 01569 compare=splay_tree->compare(splay_tree->root->key,key); 01570 else 01571 compare=(splay_tree->key > key) ? 1 : 01572 ((splay_tree->key < key) ? -1 : 0); 01573 if (compare == 0) 01574 return; 01575 } 01576 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL, 01577 (NodeInfo **) NULL); 01578 if (splay_tree->balance != WizardFalse) 01579 { 01580 BalanceSplayTree(splay_tree); 01581 (void) Splay(splay_tree,0UL,key,&splay_tree->root,(NodeInfo **) NULL, 01582 (NodeInfo **) NULL); 01583 if (splay_tree->balance != WizardFalse) 01584 ThrowWizardFatalError(CacheDomain,MemoryError); 01585 } 01586 splay_tree->key=(void *) key; 01587 }
1.7.5