Index: /trunk/include/k/kAvlTmpl/kAvlBase.h =================================================================== --- /trunk/include/k/kAvlTmpl/kAvlBase.h (revision 6) +++ /trunk/include/k/kAvlTmpl/kAvlBase.h (revision 7) @@ -48,6 +48,6 @@ * * \#define KAVL_MAX_STACK - * Use this to specify the max number of stack entries the stack will use when inserting - * and removing nodes from the tree. The size should be something like + * Use this to specify the max number of stack entries the stack will use when + * inserting and removing nodes from the tree. The size should be something like * log2() + 3 * Must be defined. @@ -62,4 +62,32 @@ * the exact same distance. * + * \#define KAVL_LOOKTHRU + * Define this to employ a lookthru cache (direct) to speed up lookup for + * some usage patterns. The value should be the number of members of the + * array. + * + * \#define KAVL_LOOKTHRU_HASH(Key) + * Define this to specify a more efficient translation of the key into + * a lookthru array index. The default is key % size. + * For some key types this is required as the default will not compile. + * + * \#define KAVL_LOCKED + * Define this if you wish for the tree to be locked via the + * KAVL_WRITE_LOCK, KAVL_WRITE_UNLOCK, KAVL_READ_LOCK and + * KAVL_READ_UNLOCK macros. If not defined the tree will not be subject + * do any kind of locking and the problem of concurrency is left the user. + * + * \#define KAVL_WRITE_LOCK(pRoot) + * Lock the tree for writing. + * + * \#define KAVL_WRITE_UNLOCK(pRoot) + * Counteracts KAVL_WRITE_LOCK. + * + * \#define KAVL_READ_LOCK(pRoot) + * Lock the tree for reading. + * + * \#define KAVL_READ_UNLOCK(pRoot) + * Counteracts KAVL_READ_LOCK. + * * \#define KAVLKEY * Define this to the name of the AVL key type. @@ -68,6 +96,6 @@ * Define this to use the standard key compare macros. If not set all the * compare operations for KAVLKEY have to be defined: KAVL_G, KAVL_E, KAVL_NE, - * KAVL_R_IS_IDENTICAL, KAVL_R_IS_INTERSECTING and KAVL_R_IS_IN_RANGE. The latter - * three are only required when KAVL_RANGE is defined. + * KAVL_R_IS_IDENTICAL, KAVL_R_IS_INTERSECTING and KAVL_R_IS_IN_RANGE. The + * latter three are only required when KAVL_RANGE is defined. * * \#define KAVLNODE @@ -83,4 +111,11 @@ * to KAVLNODE *. * + * \#define KAVLROOT + * Define this to the name (typedef) of the AVL root structure. This + * is optional. However, if specified it must at least have a mpRoot + * member of KAVLTREEPTR type. If KAVL_LOOKTHRU is non-zero a + * maLookthru[KAVL_LOOKTHRU] member of the KAVLTREEPTR type is also + * required. + * * \#define KAVL_FN * Use this to alter the names of the AVL functions. @@ -160,4 +195,35 @@ #ifndef KAVLTREEPTR # define KAVLTREEPTR KAVLNODE * +#endif + +#ifndef KAVLROOT +# define KAVLROOT KAVL_TYPE(,ROOT) +# define KAVL_NEED_KAVLROOT +#endif + +#ifdef KAVL_LOOKTHRU +# ifndef KAVL_LOOKTHRU_HASH +# define KAVL_LOOKTHRU_HASH(Key) ( (Key) % (KAVL_LOOKTHRU) ) +# endif +#elif defined(KAVL_LOOKTHRU_HASH) +# error "KAVL_LOOKTHRU_HASH without KAVL_LOOKTHRU!" +#endif + +#ifdef KAVL_LOOKTHRU +# define KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pNode, Key) \ + do { \ + KAVLTREEPTR **ppEntry = &pRoot->maLookthru[KAVL_LOOKTHRU_HASH(Key)]; \ + if ((pNode) == KAVL_GET_POINTER_NULL(ppEntry)) \ + *ppEntry = KAVL_NULL; \ + } while (0) +#else +# define KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pNode, Key) do { } while (0) +#endif + +#ifndef KAVL_LOCKED +# define KAVL_WRITE_LOCK(pRoot) do { } while (0) +# define KAVL_WRITE_UNLOCK(pRoot) do { } while (0) +# define KAVL_READ_LOCK(pRoot) do { } while (0) +# define KAVL_READ_UNLOCK(pRoot) do { } while (0) #endif @@ -219,4 +285,16 @@ typedef int (* KAVL_TYPE(PFN,CALLBACK))(KAVLNODE *, void *); +#ifdef KAVL_NEED_KAVLROOT +/** + * The AVL root structure. + */ +typedef struct +{ + KAVLTREEPTR mpRoot; +# ifdef KAVL_LOOKTHRU + KAVLTREEPTR maLookthru[KAVL_LOOKTHRU]; +# endif +} KAVLROOT; +#endif @@ -343,9 +421,28 @@ /** + * Initializes the root of the AVL-tree. + * + * @param pTree Pointer to the root structure. + */ +KAVL_DECL(void) KAVL_FN(Init)(KAVLROOT *pRoot) +{ +#ifdef KAVL_LOOKTHRU + unsigned i; +#endif + + pRoot->mpRoot = KAVL_NULL; +#ifdef KAVL_LOOKTHRU + for (i = 0; i < (KAVL_LOOKTHRU); i++) + pRoot->maLookthru[i] = KAVL_NULL; +#endif +} + + +/** * Inserts a node into the AVL-tree. - * @returns TRUE if inserted. - * FALSE if node exists in tree. - * @param ppTree Pointer to the AVL-tree root node pointer. - * @param pNode Pointer to the node which is to be added. + * @returns K_TRUE if inserted. + * K_FALSE if node exists in tree. + * @param pRoot Pointer to the AVL-tree root structure. + * @param pNode Pointer to the node which is to be added. * @sketch Find the location of the node (using binary tree algorithm.): * LOOP until NULL leaf pointer @@ -360,8 +457,8 @@ * Rebalance the tree. */ -KAVL_DECL(KBOOL) KAVL_FN(Insert)(KAVLTREEPTR *ppTree, KAVLNODE *pNode) +KAVL_DECL(KBOOL) KAVL_FN(Insert)(KAVLROOT *pRoot, KAVLNODE *pNode) { KAVL_INT(STACK) AVLStack; - KAVLTREEPTR *ppCurNode = ppTree; + KAVLTREEPTR *ppCurNode = &pRoot->mpRoot; register KAVLKEY Key = pNode->mKey; #ifdef KAVL_RANGE @@ -373,4 +470,6 @@ return false; #endif + + KAVL_WRITE_LOCK(pRoot); AVLStack.cEntries = 0; @@ -391,4 +490,5 @@ KAVL_SET_POINTER_NULL(&pNode->mpList, &pCurNode->mpList); KAVL_SET_POINTER(&pCurNode->mpList, pNode); + KAVL_WRITE_UNLOCK(pRoot); return K_TRUE; } @@ -396,5 +496,8 @@ #ifdef KAVL_CHECK_FOR_EQUAL_INSERT if (KAVL_R_IS_INTERSECTING(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast)) + { + KAVL_WRITE_UNLOCK(pRoot); return K_FALSE; + } #endif if (KAVL_G(pCurNode->mKey, Key)) @@ -412,4 +515,6 @@ KAVL_FN(Rebalance)(&AVLStack); + + KAVL_WRITE_UNLOCK(pRoot); return K_TRUE; } @@ -419,6 +524,6 @@ * Removes a node from the AVL-tree. * @returns Pointer to the node. - * @param ppTree Pointer to the AVL-tree root node pointer. - * @param Key Key value of the node which is to be removed. + * @param pRoot Pointer to the AVL-tree root structure. + * @param Key Key value of the node which is to be removed. * @sketch Find the node which is to be removed: * LOOP until not found @@ -455,9 +560,11 @@ * return pointer to the removed node (if found). */ -KAVL_DECL(KAVLNODE *) KAVL_FN(Remove)(KAVLTREEPTR *ppTree, KAVLKEY Key) +KAVL_DECL(KAVLNODE *) KAVL_FN(Remove)(KAVLROOT *pRoot, KAVLKEY Key) { KAVL_INT(STACK) AVLStack; - KAVLTREEPTR *ppDeleteNode = ppTree; + KAVLTREEPTR *ppDeleteNode = &pRoot->mpRoot; register KAVLNODE *pDeleteNode; + + KAVL_WRITE_LOCK(pRoot); AVLStack.cEntries = 0; @@ -465,5 +572,8 @@ { if (*ppDeleteNode == KAVL_NULL) + { + KAVL_WRITE_UNLOCK(pRoot); return NULL; + } pDeleteNode = KAVL_GET_POINTER(ppDeleteNode); @@ -511,4 +621,8 @@ KAVL_FN(Rebalance)(&AVLStack); + + KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pDeleteNode, Key); + + KAVL_WRITE_UNLOCK(pRoot); return pDeleteNode; } Index: /trunk/include/k/kAvlTmpl/kAvlDestroy.h =================================================================== --- /trunk/include/k/kAvlTmpl/kAvlDestroy.h (revision 6) +++ /trunk/include/k/kAvlTmpl/kAvlDestroy.h (revision 7) @@ -41,19 +41,34 @@ * made on it. Note that the node we fail on will be considered dead and * no action is taken to link it back into the tree. - * @param ppTree Pointer to the AVL-tree root node pointer. + * @param pRoot Pointer to the AVL-tree root structure. * @param pfnCallBack Pointer to callback function. * @param pvUser User parameter passed on to the callback function. */ -KAVL_DECL(int) KAVL_FN(Destroy)(KAVLTREEPTR *ppTree, KAVL_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser) +KAVL_DECL(int) KAVL_FN(Destroy)(KAVLROOT *pRoot, KAVL_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser) { +#ifdef KAVL_LOOKTHRU + unsigned i; +#endif unsigned cEntries; KAVLNODE *apEntries[KAVL_MAX_STACK]; int rc; - if (*ppTree == KAVL_NULL) + KAVL_WRITE_LOCK(pRoot); + if (pRoot->mpRoot == KAVL_NULL) + { + KAVL_WRITE_UNLOCK(pRoot); return 0; + } + +#ifdef KAVL_LOOKTHRU + /* + * Kill the lookthru cache. + */ + for (i = 0; i < (KAVL_LOOKTHRU); i++) + pRoot->maLookthru[i] = KAVL_NULL; +#endif cEntries = 1; - apEntries[0] = KAVL_GET_POINTER(ppTree); + apEntries[0] = KAVL_GET_POINTER(&pRoot->mpRoot); while (cEntries > 0) { @@ -80,5 +95,8 @@ rc = pfnCallBack(pEqual, pvUser); if (rc) + { + KAVL_WRITE_UNLOCK(pRoot); return rc; + } } #endif @@ -96,5 +114,5 @@ } else - *ppTree = KAVL_NULL; + pRoot->mpRoot = KAVL_NULL; kHlpAssert(pNode->mpLeft == KAVL_NULL); @@ -102,9 +120,13 @@ rc = pfnCallBack(pNode, pvUser); if (rc) + { + KAVL_WRITE_UNLOCK(pRoot); return rc; + } } } /* while */ - kHlpAssert(*ppTree == KAVL_NULL); + kHlpAssert(pRoot->mpRoot == KAVL_NULL); + KAVL_WRITE_UNLOCK(pRoot); return 0; } Index: /trunk/include/k/kAvlTmpl/kAvlDoWithAll.h =================================================================== --- /trunk/include/k/kAvlTmpl/kAvlDoWithAll.h (revision 6) +++ /trunk/include/k/kAvlTmpl/kAvlDoWithAll.h (revision 7) @@ -43,4 +43,5 @@ KAVLNODE *aEntries[KAVL_MAX_STACK]; char achFlags[KAVL_MAX_STACK]; + KAVLROOT pRoot; } KAVL_INT(STACK2); @@ -50,5 +51,5 @@ * * @returns 0 on success. Return from callback on failure. - * @param ppTree Pointer to the AVL-tree root node pointer. + * @param pRoot Pointer to the AVL-tree root structure. * @param fFromLeft K_TRUE: Left to right. * K_FALSE: Right to left. @@ -56,5 +57,5 @@ * @param pvUser User parameter passed on to the callback function. */ -KAVL_DECL(int) KAVL_FN(DoWithAll)(KAVLTREEPTR *ppTree, KBOOL fFromLeft, KAVL_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser) +KAVL_DECL(int) KAVL_FN(DoWithAll)(KAVLROOT *pRoot, KBOOL fFromLeft, KAVL_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser) { KAVL_INT(STACK2) AVLStack; @@ -65,10 +66,14 @@ int rc; - if (*ppTree == KAVL_NULL) + KAVL_READ_LOCK(pRoot); + if (pRoot->mpRoot == KAVL_NULL) + { + KAVL_READ_UNLOCK(pRoot); return 0; + } AVLStack.cEntries = 1; AVLStack.achFlags[0] = 0; - AVLStack.aEntries[0] = KAVL_GET_POINTER(ppTree); + AVLStack.aEntries[0] = KAVL_GET_POINTER(&pRoot->mpRoot); if (fFromLeft) @@ -99,5 +104,8 @@ rc = pfnCallBack(pEqual, pvUser); if (rc) + { + KAVL_READ_UNLOCK(pRoot); return rc; + } } #endif @@ -139,5 +147,8 @@ rc = pfnCallBack(pEqual, pvUser); if (rc) + { + KAVL_READ_UNLOCK(pRoot); return rc; + } } #endif @@ -153,4 +164,5 @@ } + KAVL_READ_UNLOCK(pRoot); return 0; } Index: /trunk/include/k/kAvlTmpl/kAvlEnum.h =================================================================== --- /trunk/include/k/kAvlTmpl/kAvlEnum.h (revision 6) +++ /trunk/include/k/kAvlTmpl/kAvlEnum.h (revision 7) @@ -51,4 +51,22 @@ /** + * Ends an enumeration. + * + * The purpose of this function is to unlock the tree should the + * AVL implementation include locking. It's good practice to call + * it anyway even if the tree doesn't do any locking. + * + * @param pEnumData Pointer to enumeration control data. + */ +KAVL_DECL(void) KAVL_FN(EndEnum)(KAVL_TYPE(,ENUMDATA) *pEnumData) +{ + KAVLROOT pRoot = pEnumData->pRoot; + pEnumData->pRoot = NULL; + if (pRoot) + KAVL_READ_UNLOCK(pEnumData->pRoot); +} + + +/** * Get the next node in the tree enumeration. * @@ -56,5 +74,7 @@ * chain like the DoWithAll function does. This may be changed later. * - * @returns Pointer to the first node in the tree. + * @returns Pointer to the next node in the tree. + * NULL is returned when the end of the tree has been reached, + * it is not necessary to call EndEnum in this case. * @param pEnumData Pointer to enumeration control data. */ @@ -130,4 +150,8 @@ } + /* + * Call EndEnum. + */ + KAVL_FN(EndEnum)(pEnumData); return NULL; } @@ -137,20 +161,24 @@ * Starts an enumeration of all nodes in the given AVL tree. * - * The current implementation of this function willl not walk the mpList + * The current implementation of this function will not walk the mpList * chain like the DoWithAll function does. This may be changed later. * * @returns Pointer to the first node in the enumeration. - * @param ppTree Pointer to the AVL-tree root node pointer. - * @param pEnumData Pointer to enumeration control data. - * @param fFromLeft K_TRUE: Left to right. - * K_FALSE: Right to left. + * If NULL is returned the tree is empty calling EndEnum isn't + * strictly necessary (although it will do no harm). + * @param pRoot Pointer to the AVL-tree root structure. + * @param pEnumData Pointer to enumeration control data. + * @param fFromLeft K_TRUE: Left to right. + * K_FALSE: Right to left. */ -KAVL_DECL(KAVLNODE *) KAVL_FN(BeginEnum)(KAVLTREEPTR *ppTree, KAVL_TYPE(,ENUMDATA) *pEnumData, KBOOL fFromLeft) +KAVL_DECL(KAVLNODE *) KAVL_FN(BeginEnum)(KAVLROOT *pRoot, KAVL_TYPE(,ENUMDATA) *pEnumData, KBOOL fFromLeft) { - if (*ppTree != KAVL_NULL) + KAVL_READ_LOCK(pRoot); + pEnumData->pRoot = pRoot; + if (pRoot->mpRoot != KAVL_NULL) { pEnumData->fFromLeft = fFromLeft; pEnumData->cEntries = 1; - pEnumData->aEntries[0] = KAVL_GET_POINTER(ppTree); + pEnumData->aEntries[0] = KAVL_GET_POINTER(pRoot->mpRoot); pEnumData->achFlags[0] = 0; } Index: /trunk/include/k/kAvlTmpl/kAvlGet.h =================================================================== --- /trunk/include/k/kAvlTmpl/kAvlGet.h (revision 6) +++ /trunk/include/k/kAvlTmpl/kAvlGet.h (revision 7) @@ -36,30 +36,57 @@ * Gets a node from the tree (does not remove it!) * - * @returns Pointer to the node holding the given key. - * @param ppTree Pointer to the AVL-tree root node pointer. - * @param Key Key value of the node which is to be found. + * @returns Pointer to the node holding the given key. + * @param pRoot Pointer to the AVL-tree root structure. + * @param Key Key value of the node which is to be found. */ -KAVL_DECL(KAVLNODE *) KAVL_FN(Get)(KAVLTREEPTR *ppTree, KAVLKEY Key) +KAVL_DECL(KAVLNODE *) KAVL_FN(Get)(KAVLROOT *pRoot, KAVLKEY Key) { KAVLNODE *pNode; - if (*ppTree == KAVL_NULL) +#ifdef KAVL_LOOKTHRU_CACHE + KAVLTREEPTR *ppEntry; +#endif + + KAVL_READ_LOCK(pRoot); + if (pRoot->mpRoot == KAVL_NULL) + { + KAVL_READ_UNLOCK(pRoot); return NULL; + } - pNode = KAVL_GET_POINTER(ppTree); - while (KAVL_NE(pNode->mKey, Key)) +#ifdef KAVL_LOOKTHRU_CACHE + ppEntry = &pRoot->maLookthru[KAVL_LOOKTHRU_HASH(Key)]; + pNode = KAVL_GET_POINTER_NULL(ppEntry); + if (!pNode || KAVL_NE(pNode->mKey, Key)) +#endif { - if (KAVL_G(pNode->mKey, Key)) + pNode = KAVL_GET_POINTER(&pRoot->mpRoot); + while (KAVL_NE(pNode->mKey, Key)) { - if (pNode->mpLeft == KAVL_NULL) - return NULL; - pNode = KAVL_GET_POINTER(&pNode->mpLeft); + if (KAVL_G(pNode->mKey, Key)) + { + if (pNode->mpLeft == KAVL_NULL) + { + KAVL_READ_UNLOCK(pRoot); + return NULL; + } + pNode = KAVL_GET_POINTER(&pNode->mpLeft); + } + else + { + if (pNode->mpRight == KAVL_NULL) + { + KAVL_READ_UNLOCK(pRoot); + return NULL; + } + pNode = KAVL_GET_POINTER(&pNode->mpRight); + } } - else - { - if (pNode->mpRight == KAVL_NULL) - return NULL; - pNode = KAVL_GET_POINTER(&pNode->mpRight); - } + +#ifdef KAVL_LOOKTHRU_CACHE + KAVL_SET_POINTER(ppEntry, pNode); +#endif } + + KAVL_READ_UNLOCK(pRoot); return pNode; } Index: /trunk/include/k/kAvlTmpl/kAvlGetBestFit.h =================================================================== --- /trunk/include/k/kAvlTmpl/kAvlGetBestFit.h (revision 6) +++ /trunk/include/k/kAvlTmpl/kAvlGetBestFit.h (revision 7) @@ -37,21 +37,25 @@ * * @returns Pointer to the best fitting node found. - * @param ppTree Pointer to Pointer to the tree root node. - * @param Key The Key of which is to be found a best fitting match for.. - * @param fAbove K_TRUE: Returned node is have the closest key to Key from above. - * K_FALSE: Returned node is have the closest key to Key from below. + * @param pRoot Pointer to the AVL-tree root structure. + * @param Key The Key of which is to be found a best fitting match for.. + * @param fAbove K_TRUE: Returned node is have the closest key to Key from above. + * K_FALSE: Returned node is have the closest key to Key from below. * @sketch The best fitting node is always located in the searchpath above you. * >= (above): The node where you last turned left. * <= (below): the node where you last turned right. */ -KAVL_DECL(KAVLNODE *) KAVL_FN(GetBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove) +KAVL_DECL(KAVLNODE *) KAVL_FN(GetBestFit)(KAVLROOT *pRoot, KAVLKEY Key, KBOOL fAbove) { register KAVLNODE *pNode; KAVLNODE *pNodeLast; - if (*ppTree == KAVL_NULL) + KAVL_READ_LOCK(pLook); + if (pRoot->mpRoot == KAVL_NULL) + { + KAVL_READ_UNLOCK(pLook); return NULL; + } - pNode = KAVL_GET_POINTER(ppTree); + pNode = KAVL_GET_POINTER(&pRoot->mpRoot); pNodeLast = NULL; if (fAbove) @@ -62,5 +66,8 @@ { if (pNode->mpLeft == KAVL_NULL) + { + KAVL_READ_UNLOCK(pLook); return pNode; + } pNodeLast = pNode; pNode = KAVL_GET_POINTER(&pNode->mpLeft); @@ -69,5 +76,8 @@ { if (pNode->mpRight == KAVL_NULL) + { + KAVL_READ_UNLOCK(pLook); return pNodeLast; + } pNode = KAVL_GET_POINTER(&pNode->mpRight); } @@ -81,5 +91,8 @@ { if (pNode->mpLeft == KAVL_NULL) + { + KAVL_READ_UNLOCK(pLook); return pNodeLast; + } pNode = KAVL_GET_POINTER(&pNode->mpLeft); } @@ -87,5 +100,8 @@ { if (pNode->mpRight == KAVL_NULL) + { + KAVL_READ_UNLOCK(pLook); return pNode; + } pNodeLast = pNode; pNode = KAVL_GET_POINTER(&pNode->mpRight); @@ -95,4 +111,5 @@ /* perfect match or nothing. */ + KAVL_READ_UNLOCK(pLook); return pNode; } Index: /trunk/include/k/kAvlTmpl/kAvlGetWithParent.h =================================================================== --- /trunk/include/k/kAvlTmpl/kAvlGetWithParent.h (revision 6) +++ /trunk/include/k/kAvlTmpl/kAvlGetWithParent.h (revision 7) @@ -37,15 +37,19 @@ * The tree remains unchanged. * - * @returns Pointer to the node holding the given key. - * @param ppTree Pointer to the AVL-tree root node pointer. - * @param ppParent Pointer to a variable which will hold the pointer to the partent node on + * @returns Pointer to the node holding the given key. + * @param pRoot Pointer to the AVL-tree root structure. + * @param ppParent Pointer to a variable which will hold the pointer to the partent node on * return. When no node is found, this will hold the last searched node. - * @param Key Key value of the node which is to be found. + * @param Key Key value of the node which is to be found. */ -KAVL_DECL(KAVLNODE *) KAVL_FN(GetWithParent)(KAVLTREEPTR *ppTree, KAVLNODE **ppParent, KAVLKEY Key) +KAVL_DECL(KAVLNODE *) KAVL_FN(GetWithParent)(KAVLROOT *pRoot, KAVLNODE **ppParent, KAVLKEY Key) { - register KAVLNODE *pNode = KAVL_GET_POINTER_NULL(ppTree); - register KAVLNODE *pParent = NULL; + register KAVLNODE *pNode; + register KAVLNODE *pParent; + KAVL_READ_LOCK(pRoot); + + pParent = NULL; + pNode = KAVL_GET_POINTER_NULL(&pRoot->mpRoot); while ( pNode != NULL && KAVL_NE(pNode->mKey, Key)) @@ -58,4 +62,6 @@ } + KAVL_UNLOCK(pRoot); + *ppParent = pParent; return pNode; Index: /trunk/include/k/kAvlTmpl/kAvlRemove2.h =================================================================== --- /trunk/include/k/kAvlTmpl/kAvlRemove2.h (revision 6) +++ /trunk/include/k/kAvlTmpl/kAvlRemove2.h (revision 7) @@ -37,5 +37,5 @@ * * @returns Pointer to the removed node (NULL if not in the tree) - * @param ppTree Pointer to Pointer to the tree root node. + * @param pRoot Pointer to the AVL-tree root structure. * @param Key The Key of which is to be found a best fitting match for.. * @@ -43,5 +43,5 @@ * easier to manage. */ -KAVL_DECL(KAVLNODE *) KAVL_FN(Remove2)(KAVLTREEPTR *ppTree, KAVLNODE *pNode) +KAVL_DECL(KAVLNODE *) KAVL_FN(Remove2)(KAVLTROOT *pRoot, KAVLNODE *pNode) { #ifdef KAVL_EQUAL_ALLOWED @@ -50,7 +50,8 @@ */ KAVLNODE *pParent; - KAVLNODE *pCurNode = KAVL_FN(GetWithParent)(ppTree, pNode->mKey, &pParent); + KAVLNODE *pCurNode = KAVL_FN(GetWithParent)(pRoot, pNode->mKey, &pParent); if (!pCurNode) return NULL; + KAVL_WRITE_LOCK(pRoot); /** @todo the locking here isn't 100% sane. The only way to archive that is by no calling worker functions. */ if (pCurNode != pNode) { @@ -65,8 +66,11 @@ KAVL_SET_POINTER_NULL(&pCurNode->mpList, KAVL_GET_POINTER_NULL(&pNode->mpList)); pNode->mpList = KAVL_NULL; + KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pNode, pNode->mKey); + KAVL_WRITE_UNLOCK(pRoot); return pNode; } pCurNode = pNext; } + KAVL_WRITE_UNLOCK(pRoot); return NULL; } @@ -80,5 +84,8 @@ */ if (pNode->mpList == KAVL_NODE) - KAVL_FN(Remove)(ppTree, pNode->mKey); + { + KAVL_WRITE_UNLOCK(pRoot); + KAVL_FN(Remove)(pRoot, pNode->mKey); + } else { @@ -105,6 +112,10 @@ } else - KAVL_SET_POINTER(ppTree, pNewUs); + KAVL_SET_POINTER(&pRoot->mpRoot, pNewUs); + + KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pNode, pNode->mKey); + KAVL_WRITE_UNLOCK(pRoot); } + return pNode; @@ -116,9 +127,9 @@ * of wrong nodes but just uses this API for his convenience. */ - KAVLNODE *pRemovedNode = KAVL_FN(Remove)(ppTree, pNode->mKey); + KAVLNODE *pRemovedNode = KAVL_FN(Remove)(pRoot, pNode->mKey); if (pRemovedNode == pNode) return pRemovedNode; - KAVL_FN(Insert)(ppTree, pRemovedNode); + KAVL_FN(Insert)(pRoot, pRemovedNode); return NULL; #endif Index: /trunk/include/k/kAvlTmpl/kAvlRemoveBestFit.h =================================================================== --- /trunk/include/k/kAvlTmpl/kAvlRemoveBestFit.h (revision 6) +++ /trunk/include/k/kAvlTmpl/kAvlRemoveBestFit.h (revision 7) @@ -37,5 +37,5 @@ * * @returns Pointer to the removed node. - * @param ppTree Pointer to Pointer to the tree root node. + * @param pRoot Pointer to the AVL-tree root structure. * @param Key The Key of which is to be found a best fitting match for.. * @param fAbove K_TRUE: Returned node is have the closest key to Key from above. @@ -46,5 +46,5 @@ * code size, and the likelyhood for bugs. */ -KAVL_DECL(KAVLNODE *) KAVL_FN(RemoveBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove) +KAVL_DECL(KAVLNODE *) KAVL_FN(RemoveBestFit)(KAVLROOT *pRoot, KAVLKEY Key, KBOOL fAbove) { /* @@ -53,16 +53,20 @@ * removing the in-tree node as this is way cheaper. */ - KAVLNODE *pNode = KAVL_FN(GetBestFit)(ppTree, Key, fAbove); + KAVLNODE *pNode = KAVL_FN(GetBestFit)(pRoot, Key, fAbove); if (pNode != NULL) { #ifdef KAVL_EQUAL_ALLOWED + KAVL_WRITE_LOCK(pRoot); /** @todo the locking isn't quite sane here. :-/ */ if (pNode->mpList != KAVL_NULL) { KAVLNODE *pRet = KAVL_GET_POINTER(&pNode->mpList); KAVL_SET_POINTER_NULL(&pNode->mpList, &pRet->mpList); + KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pNode, pNode->mKey); + KAVL_WRITE_UNLOCK(pRoot); return pRet; } + KAVL_WRITE_UNLOCK(pRoot); #endif - pNode = KAVL_FN(Remove)(ppTree, pNode->mKey); + pNode = KAVL_FN(Remove)(pRoot, pNode->mKey); } return pNode; Index: /trunk/include/k/kAvlTmpl/kAvlUndef.h =================================================================== --- /trunk/include/k/kAvlTmpl/kAvlUndef.h (revision 6) +++ /trunk/include/k/kAvlTmpl/kAvlUndef.h (revision 7) @@ -41,7 +41,15 @@ #undef KAVL_OFFSET #undef KAVL_STD_KEY_COMP +#undef KAVL_LOOKTHRU +#undef KAVL_LOOKTHRU_HASH +#undef KAVL_LOCKED +#undef KAVL_WRITE_LOCK +#undef KAVL_WRITE_UNLOCK +#undef KAVL_READ_LOCK +#undef KAVL_READ_UNLOCK #undef KAVLKEY #undef KAVLNODE #undef KAVLTREEPTR +#undef KAVLROOT #undef KAVL_FN #undef KAVL_TYPE @@ -54,4 +62,6 @@ #undef mpRight #undef mpList +#undef mpRoot +#undef maLookthru /* Index: /trunk/kProfiler2/prfreader.cpp.h =================================================================== --- /trunk/kProfiler2/prfreader.cpp.h (revision 6) +++ /trunk/kProfiler2/prfreader.cpp.h (revision 7) @@ -266,20 +266,4 @@ } KPRF_TYPE(,REPORTMODSEG), *KPRF_TYPE(P,REPORTMODSEG); -/* Instantiate the AVL tree code. */ -#define KAVL_CHECK_FOR_EQUAL_INSERT -#define KAVL_MAX_STACK 32 -#define KAVL_STD_KEY_COMP -#define mKey offSegment -#define KAVLKEY KDBGADDR -#define KAVLNODE KPRF_TYPE(,REPORTMODSEG) -#define KAVL_FN(name) KPRF_NAME(ReportTree ## name) -#define KAVL_TYPE(prefix,name) KPRF_TYPE(prefix, REPORTMODESEG ## name) -#define KAVL_INT(name) KPRF_NAME(REPORTMODESEGINT ## name) -#define KAVL_DECL(type) K_DECL_INLINE(type) -#include -#include -#include -#include - /** @@ -530,5 +514,5 @@ /** The number of modules in the list. */ KU32 cMods; - /** The module segment tree. */ + /** The module segment tree. (Only kAvl cares about this.) */ KPRF_TYPE(P,REPORTMODSEG) pModSegTree; /** The number of module segments in the tree. */ @@ -557,4 +541,23 @@ } KPRF_TYPE(,REPORT), *KPRF_TYPE(P,REPORT), **KPRF_TYPE(PP,REPORT); + + +/* Instantiate the AVL tree code. */ +#define KAVL_CHECK_FOR_EQUAL_INSERT +#define KAVL_MAX_STACK 32 +#define KAVL_STD_KEY_COMP +#define mKey offSegment +#define KAVLKEY KDBGADDR +#define KAVLNODE KPRF_TYPE(,REPORTMODSEG) +#define mpRoot pModSegTree +#define KAVLROOT KPRF_TYPE(,REPORT) +#define KAVL_FN(name) KPRF_NAME(ReportTree ## name) +#define KAVL_TYPE(prefix,name) KPRF_TYPE(prefix, REPORTMODESEG ## name) +#define KAVL_INT(name) KPRF_NAME(REPORTMODESEGINT ## name) +#define KAVL_DECL(type) K_DECL_INLINE(type) +#include +#include +#include +#include @@ -592,5 +595,5 @@ pReport->pFirstMod = NULL; pReport->cMods = 0; - pReport->pModSegTree = NULL; + KPRF_NAME(ReportTreeInit)(pReport); pReport->cModSegs = 0; pReport->papSortedThreads = (KPRF_TYPE(P,REPORTTHREAD) *)((KU8 *)pReport + offSortedThreads); @@ -637,5 +640,5 @@ } - KPRF_NAME(ReportTreeDestroy)(&pReport->pModSegTree, KPRF_NAME(DeleteModSeg), NULL); + KPRF_NAME(ReportTreeDestroy)(pReport, KPRF_NAME(DeleteModSeg), NULL); /* @@ -688,5 +691,5 @@ pSeg->cFunctions = 0; - if (!KPRF_NAME(ReportTreeInsert)(&pReport->pModSegTree, pSeg)) + if (!KPRF_NAME(ReportTreeInsert)(pReport, pSeg)) { free(pSeg); @@ -758,5 +761,5 @@ pReport->papSortedFunctions[iFunc] = pReportFunc; pReportFunc->pFunc = pFunc; - pReportFunc->pModSeg = KPRF_NAME(ReportTreeGet)(&pReport->pModSegTree, pFunc->offModSeg); + pReportFunc->pModSeg = KPRF_NAME(ReportTreeGet)(pReport, pFunc->offModSeg); pReportFunc->pSym = NULL; pReportFunc->pLine = NULL;