Changeset 296cc1b in mainline for generic/include/adt/btree.h

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.

File:

• generic/include/adt/btree.h (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);