Changes in kernel/generic/src/adt/btree.c [a35b458:1b20da0] in mainline

File:

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

kernel/generic/src/adt/btree.c

@@ -83 +83 @@
 {
         unsigned int i;
-
+        
         node->keys = 0;
-
+        
         /* Clean also space for the extra key. */
         for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
@@ -92 +92 @@
                 node->subtree[i] = NULL;
         }
-
+        
         node->subtree[i] = NULL;
         node->parent = NULL;
-
+        
         link_initialize(&node->leaf_link);
         link_initialize(&node->bfs_link);
@@ -122 +122 @@
 {
         size_t i;
-
+        
         if (root->keys) {
                 for (i = 0; i < root->keys + 1; i++) {
@@ -129 +129 @@
                 }
         }
-
+        
         slab_free(btree_node_cache, root);
 }
@@ -156 +156 @@
 {
         size_t i;
-
+        
         for (i = 0; i < node->keys; i++) {
                 if (key < node->key[i]) {
                         size_t j;
-
+                        
                         for (j = node->keys; j > i; j--) {
                                 node->key[j] = node->key[j - 1];
@@ -166 +166 @@
                                 node->subtree[j + 1] = node->subtree[j];
                         }
-
+                        
                         break;
                 }
         }
-
+        
         node->key[i] = key;
         node->value[i] = value;
@@ -191 +191 @@
 {
         size_t i;
-
+        
         for (i = 0; i < node->keys + 1; i++) {
                 if (subtree == node->subtree[i])
                         return i - (int) (right != false);
         }
-
+        
         panic("Node %p does not contain subtree %p.", node, subtree);
 }
@@ -215 +215 @@
         size_t i;
         size_t j;
-
+        
         for (i = 0; i < node->keys; i++) {
                 if (key == node->key[i]) {
@@ -223 +223 @@
                                 node->subtree[j - 1] = node->subtree[j];
                         }
-
+                        
                         node->subtree[j - 1] = node->subtree[j];
                         node->keys--;
-
+                        
                         return;
                 }
         }
-
+        
         panic("Node %p does not contain key %" PRIu64 ".", node, key);
 }
@@ -248 +248 @@
 {
         size_t i, j;
-
+        
         for (i = 0; i < node->keys; i++) {
                 if (key == node->key[i]) {
@@ -256 +256 @@
                                 node->subtree[j] = node->subtree[j + 1];
                         }
-
+                        
                         node->keys--;
                         return;
                 }
         }
-
+        
         panic("Node %p does not contain key %" PRIu64 ".", node, key);
 }
@@ -280 +280 @@
 {
         size_t i;
-
+        
         for (i = 0; i < node->keys; i++) {
                 if (key < node->key[i]) {
                         size_t j;
-
+                        
                         for (j = node->keys; j > i; j--) {
                                 node->key[j] = node->key[j - 1];
@@ -290 +290 @@
                                 node->subtree[j + 1] = node->subtree[j];
                         }
-
+                        
                         node->subtree[j + 1] = node->subtree[j];
                         break;
                 }
         }
-
+        
         node->key[i] = key;
         node->value[i] = value;
         node->subtree[i] = lsubtree;
-
+        
         node->keys++;
 }
@@ -320 +320 @@
 {
         btree_key_t key = lnode->key[lnode->keys - 1];
-
+        
         if (LEAF_NODE(lnode)) {
                 void *value = lnode->value[lnode->keys - 1];
-
+                
                 node_remove_key_and_rsubtree(lnode, key);
                 node_insert_key_and_lsubtree(rnode, key, value, NULL);
@@ -329 +329 @@
         } else {
                 btree_node_t *rsubtree = lnode->subtree[lnode->keys];
-
+                
                 node_remove_key_and_rsubtree(lnode, key);
                 node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
                 lnode->parent->key[idx] = key;
-
+                
                 /* Fix parent link of the reconnected right subtree. */
                 rsubtree->parent = rnode;
@@ -356 +356 @@
 {
         btree_key_t key = rnode->key[0];
-
+        
         if (LEAF_NODE(rnode)) {
                 void *value = rnode->value[0];
-
+                
                 node_remove_key_and_lsubtree(rnode, key);
                 node_insert_key_and_rsubtree(lnode, key, value, NULL);
@@ -365 +365 @@
         } else {
                 btree_node_t *lsubtree = rnode->subtree[0];
-
+                
                 node_remove_key_and_lsubtree(rnode, key);
                 node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
                 rnode->parent->key[idx] = key;
-
+                
                 /* Fix parent link of the reconnected left subtree. */
                 lsubtree->parent = lnode;
@@ -395 +395 @@
         size_t idx;
         btree_node_t *lnode;
-
+        
         /*
          * If this is root node, the rotation can not be done.
@@ -401 +401 @@
         if (ROOT_NODE(node))
                 return false;
-
+        
         idx = find_key_by_subtree(node->parent, node, true);
         if ((int) idx == -1) {
@@ -410 +410 @@
                 return false;
         }
-
+        
         lnode = node->parent->subtree[idx];
         if (lnode->keys < BTREE_MAX_KEYS) {
@@ -420 +420 @@
                 return true;
         }
-
+        
         return false;
 }
@@ -444 +444 @@
         size_t idx;
         btree_node_t *rnode;
-
+        
         /*
          * If this is root node, the rotation can not be done.
@@ -450 +450 @@
         if (ROOT_NODE(node))
                 return false;
-
+        
         idx = find_key_by_subtree(node->parent, node, false);
         if (idx == node->parent->keys) {
@@ -459 +459 @@
                 return false;
         }
-
+        
         rnode = node->parent->subtree[idx + 1];
         if (rnode->keys < BTREE_MAX_KEYS) {
@@ -469 +469 @@
                 return true;
         }
-
+        
         return false;
 }
@@ -499 +499 @@
         size_t i;
         size_t 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.
@@ -520 +520 @@
         rnode->parent = node->parent;
         rnode->depth = node->depth;
-
+        
         /*
          * Copy big keys, values and subtree pointers to the new right sibling.
@@ -530 +530 @@
                 rnode->value[j] = node->value[i];
                 rnode->subtree[j] = node->subtree[i];
-
+                
                 /*
                  * Fix parent links in subtrees.
@@ -537 +537 @@
                         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;
 }
@@ -578 +578 @@
                 btree_node_t *rnode;
                 btree_key_t median;
-
+                
                 /*
                  * Node is full and both siblings (if both exist) are full too.
@@ -584 +584 @@
                  * bigger keys (i.e. the new node) into its parent.
                  */
-
+                
                 rnode = node_split(node, key, value, rsubtree, &median);
-
+                
                 if (LEAF_NODE(node)) {
                         list_insert_after(&rnode->leaf_link, &node->leaf_link);
                 }
-
+                
                 if (ROOT_NODE(node)) {
                         /*
@@ -599 +599 @@
                         rnode->parent = t->root;
                         node_initialize(t->root);
-
+                        
                         /*
                          * Left-hand side subtree will be the old root (i.e. node).
@@ -605 +605 @@
                          */
                         t->root->subtree[0] = node;
-
+                        
                         t->root->depth = node->depth + 1;
                 }
@@ -624 +624 @@
 {
         btree_node_t *lnode;
-
+        
         assert(value);
-
+        
         lnode = leaf_node;
         if (!lnode) {
@@ -632 +632 @@
                         panic("B-tree %p already contains key %" PRIu64 ".", t, key);
         }
-
+        
         _btree_insert(t, key, value, NULL, lnode);
 }
@@ -648 +648 @@
         size_t idx;
         btree_node_t *lnode;
-
+        
         /*
          * If this is root node, the rotation can not be done.
@@ -654 +654 @@
         if (ROOT_NODE(rnode))
                 return false;
-
+        
         idx = find_key_by_subtree(rnode->parent, rnode, true);
         if ((int) idx == -1) {
@@ -663 +663 @@
                 return false;
         }
-
+        
         lnode = rnode->parent->subtree[idx];
         if (lnode->keys > FILL_FACTOR) {
@@ -669 +669 @@
                 return true;
         }
-
+        
         return false;
 }
@@ -685 +685 @@
         size_t idx;
         btree_node_t *rnode;
-
+        
         /*
          * If this is root node, the rotation can not be done.
@@ -691 +691 @@
         if (ROOT_NODE(lnode))
                 return false;
-
+        
         idx = find_key_by_subtree(lnode->parent, lnode, false);
         if (idx == lnode->parent->keys) {
@@ -700 +700 @@
                 return false;
         }
-
+        
         rnode = lnode->parent->subtree[idx + 1];
         if (rnode->keys > FILL_FACTOR) {
@@ -706 +706 @@
                 return true;
         }
-
+        
         return false;
 }
@@ -724 +724 @@
         btree_node_t *rnode;
         size_t i;
-
+        
         assert(!ROOT_NODE(node));
-
+        
         idx = find_key_by_subtree(node->parent, node, false);
         if (idx == node->parent->keys) {
@@ -737 +737 @@
         } 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];
@@ -752 +752 @@
                 }
         }
-
+        
         if (INDEX_NODE(node)) {
                 node->subtree[node->keys + i] = rnode->subtree[i];
                 rnode->subtree[i]->parent = node;
         }
-
+        
         node->keys += rnode->keys;
         return rnode;
@@ -789 +789 @@
                         node_remove_key_and_rsubtree(node, key);
                 }
-
+                
                 return;
         }
-
+        
         if (node->keys <= FILL_FACTOR) {
                 /*
@@ -801 +801 @@
                         try_rotation_from_right(node);
         }
-
+        
         if (node->keys > FILL_FACTOR) {
                 size_t i;
-
+                
                 /*
                  * The key can be immediately removed.
@@ -813 +813 @@
                  */
                 node_remove_key_and_rsubtree(node, key);
-
+                
                 for (i = 0; i < node->parent->keys; i++) {
                         if (node->parent->key[i] == key)
@@ -822 +822 @@
                 btree_node_t *rnode;
                 btree_node_t *parent;
-
+                
                 /*
                  * The node is below the fill factor as well as its left and right sibling.
@@ -832 +832 @@
                 node_remove_key_and_rsubtree(node, key);
                 rnode = node_combine(node);
-
+                
                 if (LEAF_NODE(rnode))
                         list_remove(&rnode->leaf_link);
-
+                
                 idx = find_key_by_subtree(parent, rnode, true);
                 assert((int) idx != -1);
@@ -855 +855 @@
 {
         btree_node_t *lnode;
-
+        
         lnode = leaf_node;
         if (!lnode) {
@@ -861 +861 @@
                         panic("B-tree %p does not contain key %" PRIu64 ".", t, key);
         }
-
+        
         _btree_remove(t, key, lnode);
 }
@@ -877 +877 @@
 {
         btree_node_t *cur, *next;
-
+        
         /*
          * Iteratively descend to the leaf that can contain the searched key.
@@ -887 +887 @@
                  */
                 *leaf_node = cur;
-
+                
                 if (cur->keys == 0)
                         return NULL;
@@ -901 +901 @@
                         void *val;
                         size_t i;
-
+                        
                         /*
                          * Now if the key is smaller than cur->key[i]
@@ -911 +911 @@
                                         next = cur->subtree[i];
                                         val = cur->value[i - 1];
-
+                                        
                                         if (LEAF_NODE(cur))
                                                 return key == cur->key[i - 1] ? val : NULL;
-
+                                        
                                         goto descend;
                                 }
                         }
-
+                        
                         /*
                          * Last possibility is that the key is
@@ -925 +925 @@
                         next = cur->subtree[i];
                         val = cur->value[i - 1];
-
+                        
                         if (LEAF_NODE(cur))
                                 return key == cur->key[i - 1] ? val : NULL;
@@ -932 +932 @@
                 ;
         }
-
+        
         /*
          * The key was not found in the *leaf_node and
@@ -952 +952 @@
 {
         assert(LEAF_NODE(node));
-
+        
         if (node->leaf_link.prev != &t->leaf_list.head)
                 return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link);
@@ -971 +971 @@
 {
         assert(LEAF_NODE(node));
-
+        
         if (node->leaf_link.next != &t->leaf_list.head)
                 return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link);
@@ -988 +988 @@
         int depth = t->root->depth;
         list_t list;
-
+        
         printf("Printing B-tree:\n");
         list_initialize(&list);
         list_append(&t->root->bfs_link, &list);
-
+        
         /*
          * Use BFS search to print out the tree.
@@ -1000 +1000 @@
                 link_t *hlp;
                 btree_node_t *node;
-
+                
                 hlp = list_first(&list);
                 assert(hlp != NULL);
                 node = list_get_instance(hlp, btree_node_t, bfs_link);
                 list_remove(hlp);
-
+                
                 assert(node);
-
+                
                 if (node->depth != depth) {
                         printf("\n");
                         depth = node->depth;
                 }
-
+                
                 printf("(");
-
+                
                 for (i = 0; i < node->keys; i++) {
                         printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
@@ -1021 +1021 @@
                         }
                 }
-
+                
                 if (node->depth && node->subtree[i])
                         list_append(&node->subtree[i]->bfs_link, &list);
-
+                
                 printf(")");
         }
-
+        
         printf("\n");
-
+        
         printf("Printing list of leaves:\n");
         list_foreach(t->leaf_list, leaf_link, btree_node_t, node) {
                 assert(node);
-
+                
                 printf("(");
-
+                
                 for (i = 0; i < node->keys; i++)
                         printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
-
+                
                 printf(")");
         }
-
+        
         printf("\n");
 }