Changeset 296cc1b in mainline

Timestamp:

2006-03-30T18:39:21Z (19 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

ca687ad

Parents:

ff75d34

Message:

Change B+-tree from 2-3-4 tree to 2-3-4-5 tree by adding space for the fourth key.
This should make key removal easier.

Location:

generic

Files:

• include/adt/btree.h (modified) (3 diffs)
• src/adt/btree.c (modified) (3 diffs)

generic/include/adt/btree.h

@@ -34 +34 @@
 #include <adt/list.h>
 
-#define BTREE_M         4
+#define BTREE_M         5
 #define BTREE_MAX_KEYS  (BTREE_M - 1)
 
@@ -53 +53 @@
         /**
          * Pointers to descendants of this node sorted according to the key array.
-         * subtree[0] points to subtree with keys lesser than or equal to key[0].
-         * subtree[1] points to subtree with keys greater than key[0] and lesser than or equal to key[1].
+         * subtree[0] points to subtree with keys lesser than to key[0].
+         * subtree[1] points to subtree with keys greater than or equal to key[0] and lesser than key[1].
          * ...
          * There is room for storing a subtree pointer for the extra key.
@@ -81 +81 @@
 
 extern void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node);
-extern void btree_remove(btree_t *t, __native key);
+extern void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node);
 extern void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node);
 

generic/src/adt/btree.c

@@ -29 +29 @@
 /*
  * This B-tree has the following properties:
- * - it is a ballanced 2-3-4 tree (i.e. BTREE_M = 4)
+ * - it is a ballanced 2-3-4-5 tree (i.e. BTREE_M = 5)
  * - values (i.e. pointers to values) are stored only in leaves
  * - leaves are linked in a list
@@ -61 +61 @@
 #define INDEX_NODE(n)           ((n)->subtree[0] != NULL)
 #define LEAF_NODE(n)            ((n)->subtree[0] == NULL)
+
+#define FILL_FACTOR             ((BTREE_M-1)/2)
 
 #define MEDIAN_LOW_INDEX(n)     (((n)->keys-1)/2)
@@ -172 +174 @@
 }
 
-/* TODO */
-void btree_remove(btree_t *t, __native key)
-{
+/** Remove B-tree node.
+ *
+ * @param B-tree.
+ * @param key Key to be removed from the B-tree along with its associated value.
+ * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
+ */
+void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node)
+{
+        btree_node_t *lnode;
+        
+        lnode = leaf_node;
+        if (!lnode) {
+                if (!btree_search(t, key, &lnode)) {
+                        panic("B-tree %P does not contain key %d\n", t, key);
+                }
+        }
+        
+        /* TODO */
+
 }