Changeset 3564
- Timestamp:
- Aug 27, 2007, 5:43:09 AM (18 years ago)
- Location:
- trunk/kStuff/include/k/kAvlTmpl
- Files:
-
- 3 edited
- 1 copied
-
kAvlBase.h (modified) (1 diff)
-
kAvlDestroy.h (copied) (copied from trunk/kStuff/include/k/kAvlTmpl/kAvlDoWithAll.h ) (2 diffs)
-
kAvlDoWithAll.h (modified) (5 diffs)
-
kAvlEnum.h (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/kStuff/include/k/kAvlTmpl/kAvlBase.h
r3563 r3564 213 213 KAVLTREEPTR *aEntries[KAVL_MAX_STACK]; 214 214 } KAVL_INT(STACK); 215 216 /** 217 * The callback used by the Destroy and DoWithAll functions. 218 */ 219 typedef int (* KAVL_TYPE(PFN,CALLBACK))(KAVLNODE *, void *); 220 215 221 216 222 -
trunk/kStuff/include/k/kAvlTmpl/kAvlDestroy.h
r3563 r3564 1 1 /* $Id$ */ 2 2 /** @file 3 * kAvlTmpl - Templated AVL Trees, The Callback Iterator.3 * kAvlTmpl - Templated AVL Trees, Destroy the tree. 4 4 */ 5 5 … … 32 32 */ 33 33 34 /*******************************************************************************35 * Structures and Typedefs *36 *******************************************************************************/37 /** The callback typedef. */38 typedef int (* KAVL_TYPE(PFN,CALLBACK))(KAVLNODE *, void *);39 34 40 35 /** 41 * Stack used by DoWithAll to avoid recusive function calls. 36 * Destroys the specified tree, starting with the root node and working our way down. 37 * 38 * @returns 0 on success. 39 * @returns Return value from callback on failure. On failure, the tree will be in 40 * an unbalanced condition and only further calls to the Destroy should be 41 * made on it. Note that the node we fail on will be considered dead and 42 * no action is taken to link it back into the tree. 43 * @param ppTree Pointer to the AVL-tree root node pointer. 44 * @param pfnCallBack Pointer to callback function. 45 * @param pvUser User parameter passed on to the callback function. 42 46 */ 43 typedef struct 47 KAVL_DECL(int) KAVL_FN(Destroy)(KAVLTREEPTR *ppTree, KAVL_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser) 44 48 { 45 unsigned cEntries; 46 KAVLNODE *aEntries[KAVL_MAX_STACK]; 47 char achFlags[KAVL_MAX_STACK]; 48 } KAVL_INT(STACK2); 49 50 51 /** 52 * Iterates tru all nodes in the given tree. 53 * 54 * @returns 0 on success. Return from callback on failure. 55 * @param ppTree Pointer to the AVL-tree root node pointer. 56 * @param fFromLeft K_TRUE: Left to right. 57 * K_FALSE: Right to left. 58 * @param pfnCallBack Pointer to callback function. 59 * @param pvUser User parameter passed on to the callback function. 60 */ 61 KAVL_DECL(int) KAVL_FN(DoWithAll)(KAVLTREEPTR *ppTree, KBOOL fFromLeft, KAVL_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser) 62 { 63 KAVL_INT(STACK2) AVLStack; 64 KAVLNODE *pNode; 65 int rc; 49 unsigned cEntries; 50 KAVLNODE *apEntries[KAVL_MAX_STACK]; 51 int rc; 66 52 67 53 if (*ppTree == KAVL_NULL) 68 54 return 0; 69 55 70 AVLStack.cEntries = 1; 71 AVLStack.achFlags[0] = 0; 72 AVLStack.aEntries[0] = KAVL_GET_POINTER(ppTree); 56 cEntries = 1; 57 apEntries[0] = KAVL_GET_POINTER(ppTree); 58 while (cEntries > 0) 59 { 60 /* 61 * Process the subtrees first. 62 */ 63 KAVLNODE *pNode = apEntries[cEntries - 1]; 64 if (pNode->mpLeft != KAVL_NULL) 65 apEntries[cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft); 66 else if (pNode->mpRight != KAVL_NULL) 67 apEntries[cEntries++] = KAVL_GET_POINTER(&pNode->mpRight); 68 else 69 { 70 #ifdef KAVL_EQUAL_ALLOWED 71 /* 72 * Process nodes with the same key. 73 */ 74 while (pNode->pList != KAVL_NULL) 75 { 76 KAVLNODE *pEqual = KAVL_GET_POINTER(&pNode->pList); 77 KAVL_SET_POINTER(&pNode->pList) = KAVL_GET_POINTER_NULL(&pEqual->pList); 78 pEqual->pList = KAVL_NULL; 73 79 74 if (fFromLeft)75 { /* from left */76 while (AVLStack.cEntries > 0)77 {78 pNode = AVLStack.aEntries[AVLStack.cEntries - 1]; 80 rc = pfnCallBack(pEqual, pvUser); 81 if (rc) 82 return rc; 83 } 84 #endif 79 85 80 /* left */ 81 if (!AVLStack.achFlags[AVLStack.cEntries - 1]++) 86 /* 87 * Unlink the node. 88 */ 89 if (--cEntries > 0) 82 90 { 83 if (pNode->mpLeft != KAVL_NULL) 84 { 85 AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */ 86 AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft); 87 continue; 88 } 91 KAVLNODE *pParent = apEntries[cEntries - 1]; 92 if (KAVL_GET_POINTER(&pParent->mpLeft) == pNode) 93 pParent->mpLeft = KAVL_NULL; 94 else 95 pParent->mpRight = KAVL_NULL; 89 96 } 97 else 98 *ppTree = KAVL_NULL; 90 99 91 /* center */ 100 kHlpAssert(pNode->mLeft == KAVL_NULL); 101 kHlpAssert(pNode->mRight == KAVL_NULL); 92 102 rc = pfnCallBack(pNode, pvUser); 93 103 if (rc) 94 104 return rc; 95 96 /* right */ 97 AVLStack.cEntries--; 98 if (pNode->mpRight != KAVL_NULL) 99 { 100 AVLStack.achFlags[AVLStack.cEntries] = 0; 101 AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpRight); 102 } 103 } /* while */ 104 } 105 else 106 { /* from right */ 107 while (AVLStack.cEntries > 0) 108 { 109 pNode = AVLStack.aEntries[AVLStack.cEntries - 1]; 110 111 /* right */ 112 if (!AVLStack.achFlags[AVLStack.cEntries - 1]++) 113 { 114 if (pNode->mpRight != KAVL_NULL) 115 { 116 AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */ 117 AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpRight); 118 continue; 119 } 120 } 121 122 /* center */ 123 rc = pfnCallBack(pNode, pvUser); 124 if (rc) 125 return rc; 126 127 /* left */ 128 AVLStack.cEntries--; 129 if (pNode->mpLeft != KAVL_NULL) 130 { 131 AVLStack.achFlags[AVLStack.cEntries] = 0; 132 AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft); 133 } 134 } /* while */ 135 } 105 } 106 } /* while */ 107 kHlpAssert(*ppTree == KAVL_NULL); 136 108 137 109 return 0; -
trunk/kStuff/include/k/kAvlTmpl/kAvlDoWithAll.h
r3563 r3564 35 35 * Structures and Typedefs * 36 36 *******************************************************************************/ 37 /** The callback typedef. */38 typedef int (* KAVL_TYPE(PFN,CALLBACK))(KAVLNODE *, void *);39 40 37 /** 41 38 * Stack used by DoWithAll to avoid recusive function calls. … … 50 47 51 48 /** 52 * Iterates t ru all nodes in the given tree.49 * Iterates thru all nodes in the given tree. 53 50 * 54 51 * @returns 0 on success. Return from callback on failure. … … 63 60 KAVL_INT(STACK2) AVLStack; 64 61 KAVLNODE *pNode; 62 #ifdef KAVL_EQUAL_ALLOWED 63 KAVLNODE *pEqual; 64 #endif 65 65 int rc; 66 66 … … 93 93 if (rc) 94 94 return rc; 95 #ifdef KAVL_EQUAL_ALLOWED 96 if (pNode->pList != KAVL_NULL) 97 for (pEqual = KAVL_GET_POINTER(&pNode->pList); pEqual; pEqual = KAVL_GET_POINTER_NULL(&pEqual->pNext)) 98 { 99 rc = pfnCallBack(pEqual, pvUser); 100 if (rc) 101 return rc; 102 } 103 #endif 95 104 96 105 /* right */ … … 124 133 if (rc) 125 134 return rc; 135 #ifdef KAVL_EQUAL_ALLOWED 136 if (pNode->pList != KAVL_NULL) 137 for (pEqual = KAVL_GET_POINTER(&pNode->pList); pEqual; pEqual = KAVL_GET_POINTER_NULL(&pEqual->pNext)) 138 { 139 rc = pfnCallBack(pEqual, pvUser); 140 if (rc) 141 return rc; 142 } 143 #endif 126 144 127 145 /* left */ -
trunk/kStuff/include/k/kAvlTmpl/kAvlEnum.h
r3563 r3564 52 52 /** 53 53 * Get the next node in the tree enumeration. 54 * 55 * The current implementation of this function willl not walk the mpList 56 * chain like the DoWithAll function does. This may be changed later. 54 57 * 55 58 * @returns Pointer to the first node in the tree. … … 134 137 * Starts an enumeration of all nodes in the given AVL tree. 135 138 * 139 * The current implementation of this function willl not walk the mpList 140 * chain like the DoWithAll function does. This may be changed later. 141 * 136 142 * @returns Pointer to the first node in the enumeration. 137 143 * @param ppTree Pointer to the AVL-tree root node pointer.
Note:
See TracChangeset
for help on using the changeset viewer.
