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