WebSVN – HelenOS-historic – Diff – /kernel/trunk/generic/src/adt/btree.c

 #include <print.h>
 static void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node);
 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 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 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 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);
 static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
 static bool try_insert_by_rotation_to_left(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
 static bool try_insert_by_rotation_to_right(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
          */
         rnode = node_split(node, key, value, rsubtree, &median);
         if (LEAF_NODE(node)) {
-            list_append(&rnode->leaf_link, &node->leaf_link);
+            list_prepend(&rnode->leaf_link, &node->leaf_link);
+        }
         if (ROOT_NODE(node)) {
             /*
              * We split the root node. Create new root.
  */
 void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node)
+{
     btree_node_t *lnode;
-    panic("%s needs testing and is disabled in revision %s\n", __FUNCTION__, REVISION);
     lnode = leaf_node;
     if (!lnode) {
         if (!btree_search(t, key, &lnode)) {
             panic("B-tree %P does not contain key %d\n", t, key);
+        }
     node->subtree[i + 1] = rsubtree;
     node->keys++;
+}
+/** Remove key and its left subtree pointer from B-tree node.
+ *
+ * Remove the key and eliminate gaps in node->key array.
+ * Note that the value pointer and the left subtree pointer
+ * is removed from the node as well.
+ *
+ * @param node B-tree node.
+ * @param key Key to be removed.
+ */
+void node_remove_key_and_lsubtree(btree_node_t *node, __native key)
+{
+    int i, j;
+    for (i = 0; i < node->keys; i++) {
+        if (key == node->key[i]) {
+            for (j = i + 1; j < node->keys; j++) {
+                node->key[j - 1] = node->key[j];
+                node->value[j - 1] = node->value[j];
+                node->subtree[j - 1] = node->subtree[j];
+            }
+            node->subtree[j - 1] = node->subtree[j];
+            node->keys--;
+            return;
+        }
+    }
+    panic("node %P does not contain key %d\n", node, key);
+}
+/** Remove key and its right subtree pointer from B-tree node.
+ *
+ * Remove the key and eliminate gaps in node->key array.
+ * Note that the value pointer and the right subtree pointer
+ * is removed from the node as well.
+ *
+ * @param node B-tree node.
+ * @param key Key to be removed.
+ */
+void node_remove_key_and_rsubtree(btree_node_t *node, __native key)
+{
+    int i, j;
+    for (i = 0; i < node->keys; i++) {
+        if (key == node->key[i]) {
+            for (j = i + 1; j < node->keys; j++) {
+                node->key[j - 1] = node->key[j];
+                node->value[j - 1] = node->value[j];
+                node->subtree[j] = node->subtree[j + 1];
+            }
+            node->keys--;
+            return;
+        }
+    }
+    panic("node %P does not contain key %d\n", node, key);
+}
 /** 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
     node->keys += rnode->keys;
     return rnode;
+}
-/** Remove key and its left subtree pointer from B-tree node.
- *
- * Remove the key and eliminate gaps in node->key array.
- * Note that the value pointer and the left subtree pointer
- * is removed from the node as well.
- *
- * @param node B-tree node.
- * @param key Key to be removed.
- */
-void node_remove_key_and_lsubtree(btree_node_t *node, __native key)
-{
-    int i, j;
-    for (i = 0; i < node->keys; i++) {
-        if (key == node->key[i]) {
-            for (j = i + 1; j < node->keys; j++) {
-                node->key[j - 1] = node->key[j];
-                node->value[j - 1] = node->value[j];
-                node->subtree[j - 1] = node->subtree[j];
-            }
-            node->subtree[j - 1] = node->subtree[j];
-            node->keys--;
-            return;
-        }
-    }
-    panic("node %P does not contain key %d\n", node, key);
-}
-/** Remove key and its right subtree pointer from B-tree node.
- *
- * Remove the key and eliminate gaps in node->key array.
- * Note that the value pointer and the right subtree pointer
- * is removed from the node as well.
- *
- * @param node B-tree node.
- * @param key Key to be removed.
- */
-void node_remove_key_and_rsubtree(btree_node_t *node, __native key)
-{
-    int i, j;
-    for (i = 0; i < node->keys; i++) {
-        if (key == node->key[i]) {
-            for (j = i + 1; j < node->keys; j++) {
-                node->key[j - 1] = node->key[j];
-                node->value[j - 1] = node->value[j];
-                node->subtree[j] = node->subtree[j + 1];
-            }
-            node->keys--;
-            return;
-        }
-    }
-    panic("node %P does not contain key %d\n", node, key);
-}
 /** Find key by its left or right subtree.
+ *
  * @param node B-tree node.
  * @param subtree Left or right subtree of a key found in node.
  * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
  * @param t Print out B-tree.
  */
 void btree_print(btree_t *t)
+{
     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);
     /*
      * Use BFS search to print out the tree.
             depth = node->depth;
+        }
         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);
+            }
+        }
         if (node->depth && node->subtree[i]) {
             list_append(&node->subtree[i]->bfs_link, &head);
+        }
         printf(")");
+    }
     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");
+}

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/adt/btree.c – Rev 1142 → 1144