Changeset 7 in kStuff for trunk/include/k/kAvlTmpl/kAvlGet.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/kAvlGet.h (modified) (1 diff)

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;
 }