Changeset 4687 in vbox for trunk/src/VBox

Timestamp:

Sep 11, 2007 9:13:32 AM (17 years ago)

Author:

vboxsync

Message:

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

Location:

trunk/src/VBox/Runtime

Files:

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

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 @@
 
 /*
- * Copyright (C) 1999-2004 knut st. osmundsen ([email protected])
+ * Copyright (C) 1999-2007 knut st. osmundsen ([email protected])
  *
  * This file is part of VirtualBox Open Source Edition (OSE), as
@@ -21 +21 @@
 
 /**
- * Iterates thru all nodes in the given tree so the caller can free resources
- * associated with each node.
+ * Destroys the specified tree, starting with the root node and working our way down.
  *
- * @returns     0 on success.
- * @returns     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.
- *
- * @param       ppTree          Pointer to the AVL-tree root node pointer.
- * @param       pfnCallBack     Pointer to callback function.
- * @param       pvParam         User parameter passed on to the callback function.
+ * @returns 0 on success.
+ * @returns 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.
+ * @param   ppTree          Pointer to the AVL-tree root node pointer.
+ * @param   pfnCallBack     Pointer to callback function.
+ * @param   pvUser          User parameter passed on to the callback function.
  */
-RTDECL(int) KAVL_FN(Destroy)(PPKAVLNODECORE ppTree, PKAVLCALLBACK pfnCallBack, void *pvParam)
+RTDECL(int) KAVL_FN(Destroy)(PPKAVLNODECORE ppTree, PKAVLCALLBACK pfnCallBack, void *pvUser)
 {
-    KAVLSTACK2      AVLStack;
+    unsigned        cEntries;
+    PKAVLNODECORE   apEntries[KAVL_MAX_STACK];
+    int             rc;
+
     if (*ppTree == KAVL_NULL)
         return 0;
 
-    AVLStack.cEntries = 1;
-    AVLStack.achFlags[0] = 0;
-    AVLStack.aEntries[0] = KAVL_GET_POINTER(ppTree);
-    while (AVLStack.cEntries > 0)
+    cEntries = 1;
+    apEntries[0] = KAVL_GET_POINTER(ppTree);
+    while (cEntries > 0)
     {
-        int             rc;
-        PKAVLNODECORE   pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
+        /*
+         * Process the subtrees first.
+         */
+        PKAVLNODECORE pNode = apEntries[cEntries - 1];
+        if (pNode->pLeft != KAVL_NULL)
+            apEntries[cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
+        else if (pNode->pRight != KAVL_NULL)
+            apEntries[cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
+        else
+        {
+#ifdef KAVL_EQUAL_ALLOWED
+            /*
+             * Process nodes with the same key.
+             */
+            while (pNode->pList != KAVL_NULL)
+            {
+                PKAVLNODECORE pEqual = KAVL_GET_POINTER(&pNode->pList);
+                KAVL_SET_POINTER(&pNode->pList, KAVL_GET_POINTER_NULL(&pEqual->pList));
+                pEqual->pList = KAVL_NULL;
 
-        if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
-        {
-            /* push left and recurse */
-            if (pNode->pLeft != KAVL_NULL)
+                rc = pfnCallBack(pEqual, pvUser);
+                if (rc)
+                    return rc;
+            }
+#endif
+
+            /*
+             * Unlink the node.
+             */
+            if (--cEntries > 0)
             {
-                AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
-                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
-                continue;
+                PKAVLNODECORE pParent = apEntries[cEntries - 1];
+                if (KAVL_GET_POINTER(&pParent->pLeft) == pNode)
+                    pParent->pLeft = KAVL_NULL;
+                else
+                    pParent->pRight = KAVL_NULL;
             }
+            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 */
 
-    *ppTree = KAVL_NULL;
+    kASSERT(*ppTree == KAVL_NULL);
+
     return 0;
 }
-
 
 #endif

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

@@ -5 +5 @@
 
 /*
- * Copyright (C) 1999-2002 knut st. osmundsen ([email protected])
+ * Copyright (C) 1999-2007 knut st. osmundsen ([email protected])
  *
  * This file is part of VirtualBox Open Source Edition (OSE), as
@@ -21 +21 @@
 
 /**
- * Iterates tru all nodes in the given tree.
+ * Iterates thru all nodes in the given tree.
  * @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)
     {
-        #ifdef KAVL_EQUAL_ALLOWED
+#ifdef KAVL_EQUAL_ALLOWED
         if (pNode->pList != KAVL_NULL)
         {
-            PKAVLANODECORE pRet = KAVL_GET_POINTER(&pNode->pList);
+            PKAVLNODECORE pRet = KAVL_GET_POINTER(&pNode->pList);
             KAVL_SET_POINTER_NULL(&pNode->pList, &pRet->pList);
             return pRet;
         }
-        #endif
+#endif
         pNode = KAVL_FN(Remove)(ppTree, pNode->Key);
     }

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

@@ -26 +26 @@
  * AVL configuration.
  */
-#define KAVL_FN(a)                  RTAvlU32##a
+#define KAVL_FN(a)                  RTAvllU32##a
 #define KAVL_MAX_STACK              27  /* Up to 2^24 nodes. */
-#define KAVL_CHECK_FOR_EQUAL_INSERT 1   /* No duplicate keys! */
-#define KAVLNODECORE                AVLU32NODECORE
-#define PKAVLNODECORE               PAVLU32NODECORE
-#define PPKAVLNODECORE              PPAVLU32NODECORE
-#define KAVLKEY                     AVLU32KEY
-#define PKAVLKEY                    PAVLU32KEY
-#define KAVLENUMDATA                AVLU32ENUMDATA
-#define PKAVLENUMDATA               PAVLU32ENUMDATA
-#define PKAVLCALLBACK               PAVLU32CALLBACK
+#define KAVL_EQUAL_ALLOWED          1   /* List duplicate keys! */
+#define KAVLNODECORE                AVLLU32NODECORE
+#define PKAVLNODECORE               PAVLLU32NODECORE
+#define PPKAVLNODECORE              PPAVLLU32NODECORE
+#define KAVLKEY                     AVLLU32KEY
+#define PKAVLKEY                    PAVLLU32KEY
+#define KAVLENUMDATA                AVLLU32ENUMDATA
+#define PKAVLENUMDATA               PAVLLU32ENUMDATA
+#define PKAVLCALLBACK               PAVLLU32CALLBACK