Changeset 4687

Timestamp:

09/11/07 11:13:32 (1 year ago)

Author:

vboxsync

Message:

Added RTAvllU32*. Applied enumeration fixes for non-unique tree. Applied Destroy fixes.

Files:

• trunk/include/iprt/avl.h (modified) (1 diff)
• trunk/src/VBox/Runtime/Makefile.kmk (modified) (1 diff)
• trunk/src/VBox/Runtime/table/avl_Destroy.cpp.h (modified) (2 diffs)
• trunk/src/VBox/Runtime/table/avl_DoWithAll.cpp.h (modified) (6 diffs)
• trunk/src/VBox/Runtime/table/avl_RemoveBestFit.cpp.h (modified) (1 diff)
• trunk/src/VBox/Runtime/table/avllu32.cpp (copied) (copied from trunk/src/VBox/Runtime/table/avlu32.cpp) (1 diff)

trunk/include/iprt/avl.h

@@ -146 +146 @@
-RTDECL(int)             RTAvlU32DoWithAll(PPAVLU32NODECORE ppTree, int fFromLeft, PAVLU32CALLBACK pfnCallBack, void *pvParam);
-RTDECL(int)             RTAvlU32Destroy(PPAVLU32NODECORE pTree, PAVLU32CALLBACK pfnCallBack, void *pvParam);
+
+/** @} */
+
+
+
+/** AVL tree of uint32_t, list duplicates.
+ * @{
+ */
+
+/** AVL key type. */
+typedef uint32_t    AVLLU32KEY;
+
+/** AVL Core node. */
+typedef struct _AVLLU32NodeCore
+{
+    AVLLU32KEY                  Key;        /**< Key value. */
+    unsigned char               uchHeight;  /**< Height of this tree: max(height(left), height(right)) + 1 */
+    struct _AVLLU32NodeCore    *pLeft;      /**< Pointer to left leaf node. */
+    struct _AVLLU32NodeCore    *pRight;     /**< Pointer to right leaf node. */
+    struct _AVLLU32NodeCore    *pList;      /**< Pointer to next node with the same key. */
+} AVLLU32NODECORE, *PAVLLU32NODECORE, **PPAVLLU32NODECORE;
+
+/** Callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
+typedef DECLCALLBACK(int) AVLLU32CALLBACK(PAVLLU32NODECORE, void*);
+/** Pointer to callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
+typedef AVLLU32CALLBACK *PAVLLU32CALLBACK;
+
+
+/*
+ * Functions.
+ */
+RTDECL(bool)                RTAvllU32Insert(PPAVLLU32NODECORE ppTree, PAVLLU32NODECORE pNode);
+RTDECL(PAVLLU32NODECORE)    RTAvllU32Remove(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
+RTDECL(PAVLLU32NODECORE)    RTAvllU32Get(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
+RTDECL(PAVLLU32NODECORE)    RTAvllU32GetBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
+RTDECL(PAVLLU32NODECORE)    RTAvllU32RemoveBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
+RTDECL(int)                 RTAvllU32DoWithAll(PPAVLLU32NODECORE ppTree, int fFromLeft, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
+RTDECL(int)                 RTAvllU32Destroy(PPAVLLU32NODECORE pTree, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
-
-/** @} */

trunk/src/VBox/Runtime/Makefile.kmk

@@ -153 +153 @@
-        table/avlroioport.cpp \
-        table/avlu32.cpp \
+        table/avllu32.cpp \
-        table/avlul.cpp \
-        table/table.cpp \

trunk/src/VBox/Runtime/table/avl_Destroy.cpp.h

@@ -5 +5 @@
-
-/*
-4
+7
- *
- * This file is part of VirtualBox Open Source Edition (OSE), as
@@ -21 +21 @@
-
-/**
-
-
+
- *
-    
-    Return code from the callback on failure. The tree might be half
-    destroyed at this point and will not behave correctly when any
-    insert or remove operation is attempted.
-
-    
-    
-    pvParam
+
+Return value from callback on failure. On failure, the tree will be in
+an unbalanced condition and only further calls to the Destroy should be
+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.
+
+
+pvUser 
- */
-Param
+User
-{
-
+
+
+
+
-    if (*ppTree == KAVL_NULL)
-        return 0;
-
-
-
-
-
+
+
+
-    {
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
-            {
-
-
-
+
+
+
+
+
-            }
+            else
+                *ppTree = KAVL_NULL;
+
+            kASSERT(pNode->pLeft == KAVL_NULL);
+            kASSERT(pNode->pRight == KAVL_NULL);
+            rc = pfnCallBack(pNode, pvUser);
+            if (rc)
+                return rc;
-        }
-
-        /* pop pNode */
-        AVLStack.cEntries--;
-
-        /* push right */
-        if (pNode->pRight != KAVL_NULL)
-        {
-            AVLStack.achFlags[AVLStack.cEntries] = 0;
-            AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
-        }
-
-        /* call destructor */
-        pNode->pRight = pNode->pLeft = KAVL_NULL;
-        rc = pfnCallBack(pNode, pvParam);
-        if (rc)
-            return rc;
-
-    } /* while */
-
-
+
+
-    return 0;
-}
-
-
-#endif

trunk/src/VBox/Runtime/table/avl_DoWithAll.cpp.h

@@ -5 +5 @@
-
-/*
-2
+7
- *
- * This file is part of VirtualBox Open Source Edition (OSE), as
@@ -21 +21 @@
-
-/**
-
+h
- * @returns   0 on success. Return from callback on failure.
- * @param     ppTree   Pointer to the AVL-tree root node pointer.
@@ -33 +33 @@
-    KAVLSTACK2      AVLStack;
-    PKAVLNODECORE   pNode;
+#ifdef KAVL_EQUAL_ALLOWED
+    PKAVLNODECORE   pEqual;
+#endif
-    int             rc;
-
@@ -63 +66 @@
-            if (rc)
-                return rc;
+#ifdef KAVL_EQUAL_ALLOWED
+            if (pNode->pList != KAVL_NULL)
+                for (pEqual = KAVL_GET_POINTER(&pNode->pList); pEqual; pEqual = KAVL_GET_POINTER_NULL(&pEqual->pList))
+                {
+                    rc = pfnCallBack(pEqual, pvParam);
+                    if (rc)
+                        return rc;
+                }
+#endif
-
-            /* right */
@@ -79 +91 @@
-            pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
-
-
-            /* right */
-            if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
@@ -95 +106 @@
-            if (rc)
-                return rc;
+#ifdef KAVL_EQUAL_ALLOWED
+            if (pNode->pList != KAVL_NULL)
+                for (pEqual = KAVL_GET_POINTER(&pNode->pList); pEqual; pEqual = KAVL_GET_POINTER_NULL(&pEqual->pList))
+                {
+                    rc = pfnCallBack(pEqual, pvParam);
+                    if (rc)
+                        return rc;
+                }
+#endif
-
-            /* left */

trunk/src/VBox/Runtime/table/avl_RemoveBestFit.cpp.h

@@ -45 +45 @@
-    if (pNode != NULL)
-    {
-        
+
-        if (pNode->pList != KAVL_NULL)
-        {
-A
+
-            KAVL_SET_POINTER_NULL(&pNode->pList, &pRet->pList);
-            return pRet;
-        }
-        
+
-        pNode = KAVL_FN(Remove)(ppTree, pNode->Key);
-    }

trunk/src/VBox/Runtime/table/avllu32.cpp

@@ -26 +26 @@
- * AVL configuration.
- */
-
+l
-#define KAVL_MAX_STACK              27  /* Up to 2^24 nodes. */
-CHECK_FOR_EQUAL_INSERT 1   /* No
-
-
-
-
-
-
-
-
+EQUAL_ALLOWED          1   /* List
+L
+L
+L
+L
+L
+L
+L
+L
-
-