Changeset 5b04fc7 in mainline for generic/src

Timestamp:

2006-04-01T18:39:25Z (19 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

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

Children:

b9b14a83

Parents:

0cb56f5d

Message:

Completed B+-tree support.
Enable btree_remove().
Reorder some static functions and group them together.
Fix order of nodes in the leaf_head list.

Location:

generic/src

Files:

• adt/btree.c (modified) (8 diffs)
• mm/slab.c (modified) (1 diff)

generic/src/adt/btree.c

@@ -50 +50 @@
 static void _btree_remove(btree_t *t, __native key, btree_node_t *node);
 static void node_initialize(btree_node_t *node);
-static void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
+static void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree);
 static void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
+static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);
+static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);
 static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
 static btree_node_t *node_combine(btree_node_t *node);
-static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);
-static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);
 static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
 static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
@@ -155 +155 @@
 
                 if (LEAF_NODE(node)) {
-                        list_append(&rnode->leaf_link, &node->leaf_link);
+                        list_prepend(&rnode->leaf_link, &node->leaf_link);
                 }
                 
@@ -190 +190 @@
         btree_node_t *lnode;
         
-        panic("%s needs testing and is disabled in revision %s\n", __FUNCTION__, REVISION);
         lnode = leaf_node;
         if (!lnode) {
@@ -437 +436 @@
 }
 
-/** Split full B-tree node and insert new key-value-right-subtree triplet.
- *
- * This function will split a node and return pointer to a newly created
- * node containing keys greater than or equal to the greater of medians
- * (or median) of the old keys and the newly added key. It will also write
- * the median key to a memory address supplied by the caller.
- *
- * If the node being split is an index node, the median will not be
- * included in the new node. If the node is a leaf node,
- * the median will be copied there.
- *
- * @param node B-tree node wich is going to be split.
- * @param key The key to be inserted.
- * @param value Pointer to the value to be inserted.
- * @param rsubtree Pointer to the right subtree of the key being added.
- * @param median Address in memory, where the median key will be stored.
- *
- * @return Newly created right sibling of node.
- */ 
-btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median)
-{
-        btree_node_t *rnode;
-        int i, j;
-
-        ASSERT(median);
-        ASSERT(node->keys == BTREE_MAX_KEYS);
-
-        /*
-         * Use the extra space to store the extra node.
-         */
-        node_insert_key_and_rsubtree(node, key, value, rsubtree);
-
-        /*
-         * Compute median of keys.
-         */
-        *median = MEDIAN_HIGH(node);
-                
-        /*
-         * Allocate and initialize new right sibling.
-         */
-        rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
-        node_initialize(rnode);
-        rnode->parent = node->parent;
-        rnode->depth = node->depth;
-        
-        /*
-         * Copy big keys, values and subtree pointers to the new right sibling.
-         * If this is an index node, do not copy the median.
-         */
-        i = (int) INDEX_NODE(node);
-        for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
-                rnode->key[j] = node->key[i];
-                rnode->value[j] = node->value[i];
-                rnode->subtree[j] = node->subtree[i];
-                
-                /*
-                 * Fix parent links in subtrees.
-                 */
-                if (rnode->subtree[j])
-                        rnode->subtree[j]->parent = rnode;
-                        
-        }
-        rnode->subtree[j] = node->subtree[i];
-        if (rnode->subtree[j])
-                rnode->subtree[j]->parent = rnode;
-
-        rnode->keys = j;        /* Set number of keys of the new node. */
-        node->keys /= 2;        /* Shrink the old node. */
-                
-        return rnode;
-}
-
-/** Combine node with any of its siblings.
- *
- * The siblings are required to be below the fill factor.
- *
- * @param node Node to combine with one of its siblings.
- *
- * @return Pointer to the rightmost of the two nodes.
- */
-btree_node_t *node_combine(btree_node_t *node)
-{
-        index_t idx;
-        btree_node_t *rnode;
-        int i;
-
-        ASSERT(!ROOT_NODE(node));
-        
-        idx = find_key_by_subtree(node->parent, node, false);
-        if (idx == node->parent->keys) {
-                /*
-                 * Rightmost subtree of its parent, combine with the left sibling.
-                 */
-                idx--;
-                rnode = node;
-                node = node->parent->subtree[idx];
-        } else {
-                rnode = node->parent->subtree[idx + 1];
-        }
-
-        /* Index nodes need to insert parent node key in between left and right node. */
-        if (INDEX_NODE(node))
-                node->key[node->keys++] = node->parent->key[idx];
-        
-        /* Copy the key-value-subtree triplets from the right node. */
-        for (i = 0; i < rnode->keys; i++) {
-                node->key[node->keys + i] = rnode->key[i];
-                node->value[node->keys + i] = rnode->value[i];
-                if (INDEX_NODE(node)) {
-                        node->subtree[node->keys + i] = rnode->subtree[i];
-                        rnode->subtree[i]->parent = node;
-                }
-        }
-        if (INDEX_NODE(node)) {
-                node->subtree[node->keys + i] = rnode->subtree[i];
-                rnode->subtree[i]->parent = node;
-        }
-
-        node->keys += rnode->keys;
-
-        return rnode;
-}
-
 /** Remove key and its left subtree pointer from B-tree node.
  *
@@ -615 +491 @@
 }
 
+/** Split full B-tree node and insert new key-value-right-subtree triplet.
+ *
+ * This function will split a node and return pointer to a newly created
+ * node containing keys greater than or equal to the greater of medians
+ * (or median) of the old keys and the newly added key. It will also write
+ * the median key to a memory address supplied by the caller.
+ *
+ * If the node being split is an index node, the median will not be
+ * included in the new node. If the node is a leaf node,
+ * the median will be copied there.
+ *
+ * @param node B-tree node wich is going to be split.
+ * @param key The key to be inserted.
+ * @param value Pointer to the value to be inserted.
+ * @param rsubtree Pointer to the right subtree of the key being added.
+ * @param median Address in memory, where the median key will be stored.
+ *
+ * @return Newly created right sibling of node.
+ */ 
+btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median)
+{
+        btree_node_t *rnode;
+        int i, j;
+
+        ASSERT(median);
+        ASSERT(node->keys == BTREE_MAX_KEYS);
+
+        /*
+         * Use the extra space to store the extra node.
+         */
+        node_insert_key_and_rsubtree(node, key, value, rsubtree);
+
+        /*
+         * Compute median of keys.
+         */
+        *median = MEDIAN_HIGH(node);
+                
+        /*
+         * Allocate and initialize new right sibling.
+         */
+        rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
+        node_initialize(rnode);
+        rnode->parent = node->parent;
+        rnode->depth = node->depth;
+        
+        /*
+         * Copy big keys, values and subtree pointers to the new right sibling.
+         * If this is an index node, do not copy the median.
+         */
+        i = (int) INDEX_NODE(node);
+        for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
+                rnode->key[j] = node->key[i];
+                rnode->value[j] = node->value[i];
+                rnode->subtree[j] = node->subtree[i];
+                
+                /*
+                 * Fix parent links in subtrees.
+                 */
+                if (rnode->subtree[j])
+                        rnode->subtree[j]->parent = rnode;
+                        
+        }
+        rnode->subtree[j] = node->subtree[i];
+        if (rnode->subtree[j])
+                rnode->subtree[j]->parent = rnode;
+
+        rnode->keys = j;        /* Set number of keys of the new node. */
+        node->keys /= 2;        /* Shrink the old node. */
+                
+        return rnode;
+}
+
+/** Combine node with any of its siblings.
+ *
+ * The siblings are required to be below the fill factor.
+ *
+ * @param node Node to combine with one of its siblings.
+ *
+ * @return Pointer to the rightmost of the two nodes.
+ */
+btree_node_t *node_combine(btree_node_t *node)
+{
+        index_t idx;
+        btree_node_t *rnode;
+        int i;
+
+        ASSERT(!ROOT_NODE(node));
+        
+        idx = find_key_by_subtree(node->parent, node, false);
+        if (idx == node->parent->keys) {
+                /*
+                 * Rightmost subtree of its parent, combine with the left sibling.
+                 */
+                idx--;
+                rnode = node;
+                node = node->parent->subtree[idx];
+        } else {
+                rnode = node->parent->subtree[idx + 1];
+        }
+
+        /* Index nodes need to insert parent node key in between left and right node. */
+        if (INDEX_NODE(node))
+                node->key[node->keys++] = node->parent->key[idx];
+        
+        /* Copy the key-value-subtree triplets from the right node. */
+        for (i = 0; i < rnode->keys; i++) {
+                node->key[node->keys + i] = rnode->key[i];
+                node->value[node->keys + i] = rnode->value[i];
+                if (INDEX_NODE(node)) {
+                        node->subtree[node->keys + i] = rnode->subtree[i];
+                        rnode->subtree[i]->parent = node;
+                }
+        }
+        if (INDEX_NODE(node)) {
+                node->subtree[node->keys + i] = rnode->subtree[i];
+                rnode->subtree[i]->parent = node;
+        }
+
+        node->keys += rnode->keys;
+
+        return rnode;
+}
+
 /** Find key by its left or right subtree.
  *
@@ -879 +878 @@
 {
         int i, depth = t->root->depth;
-        link_t head;
-        
+        link_t head, *cur;
+
+        printf("Printing B-tree:\n");
         list_initialize(&head);
         list_append(&t->root->bfs_link, &head);
@@ -906 +906 @@
                 printf("(");
                 for (i = 0; i < node->keys; i++) {
-                        printf("%d,", node->key[i]);
+                        printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
                         if (node->depth && node->subtree[i]) {
                                 list_append(&node->subtree[i]->bfs_link, &head);
@@ -917 +917 @@
         }
         printf("\n");
-}
+        
+        printf("Printing list of leaves:\n");
+        for (cur = t->leaf_head.next; cur != &t->leaf_head; cur = cur->next) {
+                btree_node_t *node;
+                
+                node = list_get_instance(cur, btree_node_t, leaf_link);
+                
+                ASSERT(node);
+
+                printf("(");
+                for (i = 0; i < node->keys; i++)
+                        printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
+                printf(")");
+        }
+        printf("\n");
+}

generic/src/mm/slab.c

@@ -40 +40 @@
  *   - cache coloring
  *   - dynamic magazine growing (different magazine sizes are already
- *     supported, but we would need to adjust allocating strategy)
+ *     supported, but we would need to adjust allocation strategy)
  *
  * The SLAB allocator supports per-CPU caches ('magazines') to facilitate