Changeset 7 in kStuff

Timestamp:

Feb 4, 2008 2:08:02 AM (17 years ago)

Author:

bird

Message:

kAVL: Implemented locking, root node and a direct cache.

Location:

trunk

Files:

• include/k/kAvlTmpl/kAvlBase.h (modified) (16 diffs)
• include/k/kAvlTmpl/kAvlDestroy.h (modified) (4 diffs)
• include/k/kAvlTmpl/kAvlDoWithAll.h (modified) (7 diffs)
• include/k/kAvlTmpl/kAvlEnum.h (modified) (4 diffs)
• include/k/kAvlTmpl/kAvlGet.h (modified) (1 diff)
• include/k/kAvlTmpl/kAvlGetBestFit.h (modified) (6 diffs)
• include/k/kAvlTmpl/kAvlGetWithParent.h (modified) (2 diffs)
• include/k/kAvlTmpl/kAvlRemove2.h (modified) (7 diffs)
• include/k/kAvlTmpl/kAvlRemoveBestFit.h (modified) (3 diffs)
• include/k/kAvlTmpl/kAvlUndef.h (modified) (2 diffs)
• kProfiler2/prfreader.cpp.h (modified) (7 diffs)

trunk/include/k/kAvlTmpl/kAvlBase.h

@@ -48 +48 @@
  *
  *  \#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(<max nodes>) + 3
  *  Must be defined.
@@ -62 +62 @@
  *  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 +96 @@
  *  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 +111 @@
  *  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 +195 @@
 #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 +285 @@
 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 +421 @@
 
 /**
+ * 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 +457 @@
  *            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 +470 @@
         return false;
 #endif
+
+    KAVL_WRITE_LOCK(pRoot);
 
     AVLStack.cEntries = 0;
@@ -391 +490 @@
             KAVL_SET_POINTER_NULL(&pNode->mpList, &pCurNode->mpList);
             KAVL_SET_POINTER(&pCurNode->mpList, pNode);
+            KAVL_WRITE_UNLOCK(pRoot);
             return K_TRUE;
         }
@@ -396 +496 @@
 #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 +515 @@
 
     KAVL_FN(Rebalance)(&AVLStack);
+
+    KAVL_WRITE_UNLOCK(pRoot);
     return K_TRUE;
 }
@@ -419 +524 @@
  * 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 +560 @@
  *            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 +572 @@
     {
         if (*ppDeleteNode == KAVL_NULL)
+        {
+            KAVL_WRITE_UNLOCK(pRoot);
             return NULL;
+        }
         pDeleteNode = KAVL_GET_POINTER(ppDeleteNode);
 
@@ -511 +621 @@
 
     KAVL_FN(Rebalance)(&AVLStack);
+
+    KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pDeleteNode, Key);
+
+    KAVL_WRITE_UNLOCK(pRoot);
     return pDeleteNode;
 }

trunk/include/k/kAvlTmpl/kAvlDestroy.h

@@ -41 +41 @@
  *          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 +95 @@
                 rc = pfnCallBack(pEqual, pvUser);
                 if (rc)
+                {
+                    KAVL_WRITE_UNLOCK(pRoot);
                     return rc;
+                }
             }
 #endif
@@ -96 +114 @@
             }
             else
-                *ppTree = KAVL_NULL;
+                pRoot->mpRoot = KAVL_NULL;
 
             kHlpAssert(pNode->mpLeft == KAVL_NULL);
@@ -102 +120 @@
             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;
 }

trunk/include/k/kAvlTmpl/kAvlDoWithAll.h

@@ -43 +43 @@
     KAVLNODE       *aEntries[KAVL_MAX_STACK];
     char            achFlags[KAVL_MAX_STACK];
+    KAVLROOT        pRoot;
 } KAVL_INT(STACK2);
 
@@ -50 +51 @@
  *
  * @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 +57 @@
  * @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 +66 @@
     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 +104 @@
                     rc = pfnCallBack(pEqual, pvUser);
                     if (rc)
+                    {
+                        KAVL_READ_UNLOCK(pRoot);
                         return rc;
+                    }
                 }
 #endif
@@ -139 +147 @@
                     rc = pfnCallBack(pEqual, pvUser);
                     if (rc)
+                    {
+                        KAVL_READ_UNLOCK(pRoot);
                         return rc;
+                    }
                 }
 #endif
@@ -153 +164 @@
     }
 
+    KAVL_READ_UNLOCK(pRoot);
     return 0;
 }

trunk/include/k/kAvlTmpl/kAvlEnum.h

@@ -51 +51 @@
 
 /**
+ * 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 +74 @@
  * 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 +150 @@
     }
 
+    /* 
+     * Call EndEnum.
+     */
+    KAVL_FN(EndEnum)(pEnumData);
     return NULL;
 }
@@ -137 +161 @@
  * 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;
     }

trunk/include/k/kAvlTmpl/kAvlGet.h

@@ -36 +36 @@
  * 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;
 }

trunk/include/k/kAvlTmpl/kAvlGetBestFit.h

@@ -37 +37 @@
  *
  * @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 +66 @@
             {
                 if (pNode->mpLeft == KAVL_NULL)
+                {
+                    KAVL_READ_UNLOCK(pLook);
                     return pNode;
+                }
                 pNodeLast = pNode;
                 pNode = KAVL_GET_POINTER(&pNode->mpLeft);
@@ -69 +76 @@
             {
                 if (pNode->mpRight == KAVL_NULL)
+                {
+                    KAVL_READ_UNLOCK(pLook);
                     return pNodeLast;
+                }
                 pNode = KAVL_GET_POINTER(&pNode->mpRight);
             }
@@ -81 +91 @@
             {
                 if (pNode->mpLeft == KAVL_NULL)
+                {
+                    KAVL_READ_UNLOCK(pLook);
                     return pNodeLast;
+                }
                 pNode = KAVL_GET_POINTER(&pNode->mpLeft);
             }
@@ -87 +100 @@
             {
                 if (pNode->mpRight == KAVL_NULL)
+                {
+                    KAVL_READ_UNLOCK(pLook);
                     return pNode;
+                }
                 pNodeLast = pNode;
                 pNode = KAVL_GET_POINTER(&pNode->mpRight);
@@ -95 +111 @@
 
     /* perfect match or nothing. */
+    KAVL_READ_UNLOCK(pLook);
     return pNode;
 }

trunk/include/k/kAvlTmpl/kAvlGetWithParent.h

@@ -37 +37 @@
  * 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 +62 @@
     }
 
+    KAVL_UNLOCK(pRoot);
+
     *ppParent = pParent;
     return pNode;

trunk/include/k/kAvlTmpl/kAvlRemove2.h

@@ -37 +37 @@
  *
  * @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 +43 @@
  *          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 +50 @@
      */
     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 +66 @@
                 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 +84 @@
      */
     if (pNode->mpList == KAVL_NODE)
-        KAVL_FN(Remove)(ppTree, pNode->mKey);
+    {
+        KAVL_WRITE_UNLOCK(pRoot);
+        KAVL_FN(Remove)(pRoot, pNode->mKey);
+    }
     else
     {
@@ -105 +112 @@
         }
         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 +127 @@
      * 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

trunk/include/k/kAvlTmpl/kAvlRemoveBestFit.h

@@ -37 +37 @@
  *
  * @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 +46 @@
  *          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 +53 @@
      * 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;

trunk/include/k/kAvlTmpl/kAvlUndef.h

@@ -41 +41 @@
 #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 +62 @@
 #undef mpRight
 #undef mpList
+#undef mpRoot
+#undef maLookthru
 
 /*

trunk/kProfiler2/prfreader.cpp.h

@@ -266 +266 @@
 } 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 <k/kAvlTmpl/kAvlBase.h>
-#include <k/kAvlTmpl/kAvlDestroy.h>
-#include <k/kAvlTmpl/kAvlGet.h>
-#include <k/kAvlTmpl/kAvlUndef.h>
-
 
 /**
@@ -530 +514 @@
     /** 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 +541 @@
 
 } 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 <k/kAvlTmpl/kAvlBase.h>
+#include <k/kAvlTmpl/kAvlDestroy.h>
+#include <k/kAvlTmpl/kAvlGet.h>
+#include <k/kAvlTmpl/kAvlUndef.h>
 
 
@@ -592 +595 @@
     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 +640 @@
     }
 
-    KPRF_NAME(ReportTreeDestroy)(&pReport->pModSegTree, KPRF_NAME(DeleteModSeg), NULL);
+    KPRF_NAME(ReportTreeDestroy)(pReport, KPRF_NAME(DeleteModSeg), NULL);
 
     /*
@@ -688 +691 @@
         pSeg->cFunctions = 0;
 
-        if (!KPRF_NAME(ReportTreeInsert)(&pReport->pModSegTree, pSeg))
+        if (!KPRF_NAME(ReportTreeInsert)(pReport, pSeg))
         {
             free(pSeg);
@@ -758 +761 @@
         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;