Changes in kernel/generic/src/adt/btree.c [1ab4aca:8b3bff5] in mainline

File:

• kernel/generic/src/adt/btree.c (modified) (15 diffs)

kernel/generic/src/adt/btree.c

@@ -38 +38 @@
  *
  * The B+tree has the following properties:
- * @li it is a balanced 3-4-5 tree (i.e. BTREE_M = 5)
+ * @li it is a ballanced 3-4-5 tree (i.e. BTREE_M = 5)
  * @li values (i.e. pointers to values) are stored only in leaves
  * @li leaves are linked in a list
  *
- * Be careful when using these trees. They need to allocate
+ * Be carefull when using these trees. They need to allocate
  * and deallocate memory for their index nodes and as such
  * can sleep.
@@ -108 +108 @@
 void btree_create(btree_t *t)
 {
-        list_initialize(&t->leaf_list);
+        list_initialize(&t->leaf_head);
         t->root = (btree_node_t *) slab_alloc(btree_node_slab, 0);
         node_initialize(t->root);
-        list_append(&t->root->leaf_link, &t->leaf_list);
+        list_append(&t->root->leaf_link, &t->leaf_head);
 }
 
@@ -146 +146 @@
  * also makes use of this feature.
  *
- * @param node     B-tree node into which the new key is to be inserted.
+ * @param node     B-tree node into wich the new key is to be inserted.
  * @param key      The key to be inserted.
  * @param value    Pointer to value to be inserted.
@@ -270 +270 @@
  * This feature is used during insert by right rotation.
  *
- * @param node     B-tree node into which the new key is to be inserted.
+ * @param node     B-tree node into wich the new key is to be inserted.
  * @param key      The key to be inserted.
  * @param value    Pointer to value to be inserted.
@@ -463 +463 @@
         if (rnode->keys < BTREE_MAX_KEYS) {
                 /*
-                 * The rotation can be done. The right sibling has free space.
+                 * The rotaion can be done. The right sibling has free space.
                  */
                 node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
@@ -484 +484 @@
  * the median will be copied there.
  *
- * @param node     B-tree node which is going to be split.
+ * @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.
@@ -562 +562 @@
         if (node->keys < BTREE_MAX_KEYS) {
                 /*
-                 * Node contains enough space, the key can be stored immediately.
+                 * Node conatins enough space, the key can be stored immediately.
                  */
                 node_insert_key_and_rsubtree(node, key, value, rsubtree);
@@ -588 +588 @@
                 
                 if (LEAF_NODE(node)) {
-                        list_insert_after(&rnode->leaf_link, &node->leaf_link);
+                        list_prepend(&rnode->leaf_link, &node->leaf_link);
                 }
                 
@@ -806 +806 @@
                 
                 /*
-                 * The key can be immediately removed.
+                 * The key can be immediatelly removed.
                  *
                  * Note that the right subtree is removed because when
@@ -953 +953 @@
         ASSERT(LEAF_NODE(node));
         
-        if (node->leaf_link.prev != &t->leaf_list.head)
+        if (node->leaf_link.prev != &t->leaf_head)
                 return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link);
         else
@@ -972 +972 @@
         ASSERT(LEAF_NODE(node));
         
-        if (node->leaf_link.next != &t->leaf_list.head)
+        if (node->leaf_link.next != &t->leaf_head)
                 return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link);
         else
@@ -987 +987 @@
         size_t i;
         int depth = t->root->depth;
-        list_t list;
+        link_t head, *cur;
         
         printf("Printing B-tree:\n");
-        list_initialize(&list);
-        list_append(&t->root->bfs_link, &list);
+        list_initialize(&head);
+        list_append(&t->root->bfs_link, &head);
         
         /*
@@ -997 +997 @@
          * Levels are distinguished from one another by node->depth.
          */
-        while (!list_empty(&list)) {
+        while (!list_empty(&head)) {
                 link_t *hlp;
                 btree_node_t *node;
                 
-                hlp = list_first(&list);
-                ASSERT(hlp != NULL);
+                hlp = head.next;
+                ASSERT(hlp != &head);
                 node = list_get_instance(hlp, btree_node_t, bfs_link);
                 list_remove(hlp);
@@ -1018 +1018 @@
                         printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
                         if (node->depth && node->subtree[i]) {
-                                list_append(&node->subtree[i]->bfs_link, &list);
+                                list_append(&node->subtree[i]->bfs_link, &head);
                         }
                 }
                 
                 if (node->depth && node->subtree[i])
-                        list_append(&node->subtree[i]->bfs_link, &list);
+                        list_append(&node->subtree[i]->bfs_link, &head);
                 
                 printf(")");
@@ -1031 +1031 @@
         
         printf("Printing list of leaves:\n");
-        list_foreach(t->leaf_list, cur) {
+        for (cur = t->leaf_head.next; cur != &t->leaf_head; cur = cur->next) {
                 btree_node_t *node;