Changeset 7 in kStuff for trunk/include/k/kAvlTmpl/kAvlRemove2.h

Timestamp:

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

Author:

bird

Message:

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

File:

• trunk/include/k/kAvlTmpl/kAvlRemove2.h (modified) (7 diffs)

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