Changeset 113 for trunk/src/helpers/tree.c

Timestamp:

Oct 23, 2001, 11:25:46 PM (24 years ago)

Author:

umoeller

Message:

Misc updates.

File:

• trunk/src/helpers/tree.c (modified) (9 diffs)

trunk/src/helpers/tree.c

@@ -285 +285 @@
  *      initializes the root of a tree.
  *
- */
-
-void treeInit(TREE **root)
+ *@@changed V0.9.16 (2001-10-19) [umoeller]: added plCount
+ */
+
+void treeInit(TREE **root,
+              PLONG plCount)            // out: tree item count, set to 0 (ptr can be NULL)
 {
     *root = LEAF;
+
+    if (plCount)
+        *plCount = 0;       // V0.9.16 (2001-10-19) [umoeller]
 }
 
@@ -511 +516 @@
  *      STATUS_DUPLICATE_KEY if a node with the
  *      same ulKey already exists.
+ *
+ *@@changed V0.9.16 (2001-10-19) [umoeller]: added plCount
  */
 
 int treeInsert(TREE **root,                     // in: root of the tree
+               PLONG plCount,                 // in/out: item count (ptr can be NULL)
                TREE *x,                         // in: new node to insert
                FNTREE_COMPARE *pfnCompare)      // in: comparison func
@@ -531 +539 @@
         if (0 == (iResult = pfnCompare(key, current->ulKey))) // if (compEQ(key, current->key))
             return STATUS_DUPLICATE_KEY;
+
         parent = current;
         current = (iResult < 0)    // compLT(key, current->key)
@@ -561 +570 @@
                 x);
     // lastFind = NULL;
+
+    if (plCount)
+        (*plCount)++;       // V0.9.16 (2001-10-19) [umoeller]
 
     return STATUS_OK;
@@ -740 +752 @@
  *      Returns 0 if the node was deleted or
  *      STATUS_INVALID_NODE if not.
+ *
+ *@@changed V0.9.16 (2001-10-19) [umoeller]: added plCount
  */
 
 int treeDelete(TREE **root,         // in: root of the tree
+               PLONG plCount,     // in/out: item count (ptr can be NULL)
                TREE *tree)          // in: tree node to delete
 {
@@ -820 +835 @@
                     y);
 
+    if (plCount)
+        (*plCount)--;       // V0.9.16 (2001-10-19) [umoeller]
+
     return (STATUS_OK);
-
-    /* TREE    *x,
-            *y; */
-            // *z;
-
-   /*****************************
-    *  delete node z from tree  *
-    *****************************/
-
-    // find node in tree
-    /* if (lastFind && compEQ(lastFind->key, key))
-        // if we just found node, use pointer
-        z = lastFind;
-    else {
-        z = *root;
-        while(z != LEAF)
-        {
-            int iResult = pfnCompare(key, z->key);
-            if (iResult == 0)
-            // if(compEQ(key, z->key))
-                break;
-            else
-                z = (iResult < 0) // compLT(key, z->key)
-                    ? z->left
-                    : z->right;
-        }
-        if (z == LEAF)
-            return STATUS_KEY_NOT_FOUND;
-    }
-
-    if (    z->left == LEAF
-         || z->right == LEAF
-       )
-    {
-        // y has a LEAF node as a child
-        y = z;
-    }
-    else
-    {
-        // find tree successor with a LEAF node as a child
-        y = z->right;
-        while (y->left != LEAF)
-            y = y->left;
-    }
-
-    // x is y's only child
-    if (y->left != LEAF)
-        x = y->left;
-    else
-        x = y->right;
-
-    // remove y from the parent chain
-    x->parent = y->parent;
-    if (y->parent)
-        if (y == y->parent->left)
-            y->parent->left = x;
-        else
-            y->parent->right = x;
-    else
-        *root = x;
-
-    // y is about to be deleted...
-
-    if (y != z)
-    {
-        // now, the original code simply copied the data
-        // from y to z... we can't safely do that since
-        // we don't know about the real data in the
-        // caller's TREE structure
-        z->ulKey = y->ulKey;
-        // z->rec = y->rec;         // hope this works...
-                                    // the original implementation used rec
-                                    // for the node's data
-
-        if (cbStruct > sizeof(TREE))
-        {
-            memcpy(((char*)&z) + sizeof(TREE),
-                   ((char*)&y) + sizeof(TREE),
-                   cbStruct - sizeof(TREE));
-        }
-    }
-
-    if (y->color == BLACK)
-        deleteFixup(root,
-                    x);
-
-    // free(y);
-    // lastFind = NULL;
-
-    return STATUS_OK; */
 }
 
@@ -1120 +1048 @@
 
 TREE** treeBuildArray(TREE* pRoot,
-                      unsigned long *pulCount)  // in: item count, out: array item count
+                      PLONG plCount)  // in: item count, out: array item count
 {
     TREE            **papNodes = NULL,
                     **papThis = NULL;
-    unsigned long   cb = (sizeof(TREE*) * (*pulCount)),
+    long            cb = (sizeof(TREE*) * (*plCount)),
                     cNodes = 0;
 
@@ -1140 +1068 @@
             // copy nodes to array
             while (    pNode
-                    && cNodes < (*pulCount)     // just to make sure
+                    && cNodes < (*plCount)     // just to make sure
                   )
             {
@@ -1151 +1079 @@
 
             // output count
-            *pulCount = cNodes;
+            *plCount = cNodes;
         }
     }