Changeset 5b04fc7 in mainline


Ignore:
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.

Files:
3 edited

Legend:

Unmodified
Added
Removed

  • generic/src/adt/btree.c

    r0cb56f5d r5b04fc7  
    5050static void _btree_remove(btree_t *t, __native key, btree_node_t *node);
    5151static void node_initialize(btree_node_t *node);
    52 static void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
     52static void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree);
    5353static void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
     54static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);
     55static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);
    5456static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
    5557static btree_node_t *node_combine(btree_node_t *node);
    56 static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);
    57 static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);
    5858static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
    5959static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
    … …  
    155155
    156156                if (LEAF_NODE(node)) {
    157                         list_append(&rnode->leaf_link, &node->leaf_link);
     157                        list_prepend(&rnode->leaf_link, &node->leaf_link);
    158158                }
    159159               
    … …  
    190190        btree_node_t *lnode;
    191191       
    192         panic("%s needs testing and is disabled in revision %s\n", __FUNCTION__, REVISION);
    193192        lnode = leaf_node;
    194193        if (!lnode) {
    … …  
    437436}
    438437
    439 /** Split full B-tree node and insert new key-value-right-subtree triplet.
    440  *
    441  * This function will split a node and return pointer to a newly created
    442  * node containing keys greater than or equal to the greater of medians
    443  * (or median) of the old keys and the newly added key. It will also write
    444  * the median key to a memory address supplied by the caller.
    445  *
    446  * If the node being split is an index node, the median will not be
    447  * included in the new node. If the node is a leaf node,
    448  * the median will be copied there.
    449  *
    450  * @param node B-tree node wich is going to be split.
    451  * @param key The key to be inserted.
    452  * @param value Pointer to the value to be inserted.
    453  * @param rsubtree Pointer to the right subtree of the key being added.
    454  * @param median Address in memory, where the median key will be stored.
    455  *
    456  * @return Newly created right sibling of node.
    457  */
    458 btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median)
    459 {
    460         btree_node_t *rnode;
    461         int i, j;
    462 
    463         ASSERT(median);
    464         ASSERT(node->keys == BTREE_MAX_KEYS);
    465 
    466         /*
    467          * Use the extra space to store the extra node.
    468          */
    469         node_insert_key_and_rsubtree(node, key, value, rsubtree);
    470 
    471         /*
    472          * Compute median of keys.
    473          */
    474         *median = MEDIAN_HIGH(node);
    475                
    476         /*
    477          * Allocate and initialize new right sibling.
    478          */
    479         rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
    480         node_initialize(rnode);
    481         rnode->parent = node->parent;
    482         rnode->depth = node->depth;
    483        
    484         /*
    485          * Copy big keys, values and subtree pointers to the new right sibling.
    486          * If this is an index node, do not copy the median.
    487          */
    488         i = (int) INDEX_NODE(node);
    489         for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
    490                 rnode->key[j] = node->key[i];
    491                 rnode->value[j] = node->value[i];
    492                 rnode->subtree[j] = node->subtree[i];
    493                
    494                 /*
    495                  * Fix parent links in subtrees.
    496                  */
    497                 if (rnode->subtree[j])
    498                         rnode->subtree[j]->parent = rnode;
    499                        
    500         }
    501         rnode->subtree[j] = node->subtree[i];
    502         if (rnode->subtree[j])
    503                 rnode->subtree[j]->parent = rnode;
    504 
    505         rnode->keys = j;        /* Set number of keys of the new node. */
    506         node->keys /= 2;        /* Shrink the old node. */
    507                
    508         return rnode;
    509 }
    510 
    511 /** Combine node with any of its siblings.
    512  *
    513  * The siblings are required to be below the fill factor.
    514  *
    515  * @param node Node to combine with one of its siblings.
    516  *
    517  * @return Pointer to the rightmost of the two nodes.
    518  */
    519 btree_node_t *node_combine(btree_node_t *node)
    520 {
    521         index_t idx;
    522         btree_node_t *rnode;
    523         int i;
    524 
    525         ASSERT(!ROOT_NODE(node));
    526        
    527         idx = find_key_by_subtree(node->parent, node, false);
    528         if (idx == node->parent->keys) {
    529                 /*
    530                  * Rightmost subtree of its parent, combine with the left sibling.
    531                  */
    532                 idx--;
    533                 rnode = node;
    534                 node = node->parent->subtree[idx];
    535         } else {
    536                 rnode = node->parent->subtree[idx + 1];
    537         }
    538 
    539         /* Index nodes need to insert parent node key in between left and right node. */
    540         if (INDEX_NODE(node))
    541                 node->key[node->keys++] = node->parent->key[idx];
    542        
    543         /* Copy the key-value-subtree triplets from the right node. */
    544         for (i = 0; i < rnode->keys; i++) {
    545                 node->key[node->keys + i] = rnode->key[i];
    546                 node->value[node->keys + i] = rnode->value[i];
    547                 if (INDEX_NODE(node)) {
    548                         node->subtree[node->keys + i] = rnode->subtree[i];
    549                         rnode->subtree[i]->parent = node;
    550                 }
    551         }
    552         if (INDEX_NODE(node)) {
    553                 node->subtree[node->keys + i] = rnode->subtree[i];
    554                 rnode->subtree[i]->parent = node;
    555         }
    556 
    557         node->keys += rnode->keys;
    558 
    559         return rnode;
    560 }
    561 
    562438/** Remove key and its left subtree pointer from B-tree node.
    563439 *
    … …  
    615491}
    616492
     493/** Split full B-tree node and insert new key-value-right-subtree triplet.
     494 *
     495 * This function will split a node and return pointer to a newly created
     496 * node containing keys greater than or equal to the greater of medians
     497 * (or median) of the old keys and the newly added key. It will also write
     498 * the median key to a memory address supplied by the caller.
     499 *
     500 * If the node being split is an index node, the median will not be
     501 * included in the new node. If the node is a leaf node,
     502 * the median will be copied there.
     503 *
     504 * @param node B-tree node wich is going to be split.
     505 * @param key The key to be inserted.
     506 * @param value Pointer to the value to be inserted.
     507 * @param rsubtree Pointer to the right subtree of the key being added.
     508 * @param median Address in memory, where the median key will be stored.
     509 *
     510 * @return Newly created right sibling of node.
     511 */
     512btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median)
     513{
     514        btree_node_t *rnode;
     515        int i, j;
     516
     517        ASSERT(median);
     518        ASSERT(node->keys == BTREE_MAX_KEYS);
     519
     520        /*
     521         * Use the extra space to store the extra node.
     522         */
     523        node_insert_key_and_rsubtree(node, key, value, rsubtree);
     524
     525        /*
     526         * Compute median of keys.
     527         */
     528        *median = MEDIAN_HIGH(node);
     529               
     530        /*
     531         * Allocate and initialize new right sibling.
     532         */
     533        rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
     534        node_initialize(rnode);
     535        rnode->parent = node->parent;
     536        rnode->depth = node->depth;
     537       
     538        /*
     539         * Copy big keys, values and subtree pointers to the new right sibling.
     540         * If this is an index node, do not copy the median.
     541         */
     542        i = (int) INDEX_NODE(node);
     543        for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
     544                rnode->key[j] = node->key[i];
     545                rnode->value[j] = node->value[i];
     546                rnode->subtree[j] = node->subtree[i];
     547               
     548                /*
     549                 * Fix parent links in subtrees.
     550                 */
     551                if (rnode->subtree[j])
     552                        rnode->subtree[j]->parent = rnode;
     553                       
     554        }
     555        rnode->subtree[j] = node->subtree[i];
     556        if (rnode->subtree[j])
     557                rnode->subtree[j]->parent = rnode;
     558
     559        rnode->keys = j;        /* Set number of keys of the new node. */
     560        node->keys /= 2;        /* Shrink the old node. */
     561               
     562        return rnode;
     563}
     564
     565/** Combine node with any of its siblings.
     566 *
     567 * The siblings are required to be below the fill factor.
     568 *
     569 * @param node Node to combine with one of its siblings.
     570 *
     571 * @return Pointer to the rightmost of the two nodes.
     572 */
     573btree_node_t *node_combine(btree_node_t *node)
     574{
     575        index_t idx;
     576        btree_node_t *rnode;
     577        int i;
     578
     579        ASSERT(!ROOT_NODE(node));
     580       
     581        idx = find_key_by_subtree(node->parent, node, false);
     582        if (idx == node->parent->keys) {
     583                /*
     584                 * Rightmost subtree of its parent, combine with the left sibling.
     585                 */
     586                idx--;
     587                rnode = node;
     588                node = node->parent->subtree[idx];
     589        } else {
     590                rnode = node->parent->subtree[idx + 1];
     591        }
     592
     593        /* Index nodes need to insert parent node key in between left and right node. */
     594        if (INDEX_NODE(node))
     595                node->key[node->keys++] = node->parent->key[idx];
     596       
     597        /* Copy the key-value-subtree triplets from the right node. */
     598        for (i = 0; i < rnode->keys; i++) {
     599                node->key[node->keys + i] = rnode->key[i];
     600                node->value[node->keys + i] = rnode->value[i];
     601                if (INDEX_NODE(node)) {
     602                        node->subtree[node->keys + i] = rnode->subtree[i];
     603                        rnode->subtree[i]->parent = node;
     604                }
     605        }
     606        if (INDEX_NODE(node)) {
     607                node->subtree[node->keys + i] = rnode->subtree[i];
     608                rnode->subtree[i]->parent = node;
     609        }
     610
     611        node->keys += rnode->keys;
     612
     613        return rnode;
     614}
     615
    617616/** Find key by its left or right subtree.
    618617 *
    … …  
    879878{
    880879        int i, depth = t->root->depth;
    881         link_t head;
    882        
     880        link_t head, *cur;
     881
     882        printf("Printing B-tree:\n");
    883883        list_initialize(&head);
    884884        list_append(&t->root->bfs_link, &head);
    … …  
    906906                printf("(");
    907907                for (i = 0; i < node->keys; i++) {
    908                         printf("%d,", node->key[i]);
     908                        printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
    909909                        if (node->depth && node->subtree[i]) {
    910910                                list_append(&node->subtree[i]->bfs_link, &head);
    … …  
    917917        }
    918918        printf("\n");
    919 }
     919       
     920        printf("Printing list of leaves:\n");
     921        for (cur = t->leaf_head.next; cur != &t->leaf_head; cur = cur->next) {
     922                btree_node_t *node;
     923               
     924                node = list_get_instance(cur, btree_node_t, leaf_link);
     925               
     926                ASSERT(node);
     927
     928                printf("(");
     929                for (i = 0; i < node->keys; i++)
     930                        printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
     931                printf(")");
     932        }
     933        printf("\n");
     934}

  • generic/src/mm/slab.c

    r0cb56f5d r5b04fc7  
    4040 *   - cache coloring
    4141 *   - dynamic magazine growing (different magazine sizes are already
    42  *     supported, but we would need to adjust allocating strategy)
     42 *     supported, but we would need to adjust allocation strategy)
    4343 *
    4444 * The SLAB allocator supports per-CPU caches ('magazines') to facilitate

  • test/btree/btree1/test.c

    r0cb56f5d r5b04fc7  
    4141        btree_create(&t);
    4242
     43        printf("Inserting keys.\n");
     44        btree_insert(&t, 19, data, NULL);
     45        btree_insert(&t, 20, data, NULL);
     46        btree_insert(&t, 21, data, NULL);
     47        btree_insert(&t, 0, data, NULL);
     48        btree_insert(&t, 25, data, NULL);
     49        btree_insert(&t, 22, data, NULL);
     50        btree_insert(&t, 26, data, NULL);
    4351        btree_insert(&t, 23, data, NULL);
    4452        btree_insert(&t, 24, data, NULL);
    … …  
    5664        btree_insert(&t, 3, data, NULL);
    5765        btree_insert(&t, 6, data, NULL);
    58         btree_insert(&t, 19, data, NULL);
    59         btree_insert(&t, 20, data, NULL);
    60         btree_insert(&t, 21, data, NULL);
    61         btree_insert(&t, 0, data, NULL);
    62         btree_insert(&t, 25, data, NULL);
    63         btree_insert(&t, 22, data, NULL);
    64         btree_insert(&t, 26, data, NULL);
    6566        btree_insert(&t, 10, data, NULL);
    6667        btree_insert(&t, 11, data, NULL);
    … …  
    7980        btree_print(&t);
    8081       
     82        printf("Removing keys.\n");
    8183        btree_remove(&t, 50, NULL);
     84        btree_remove(&t, 49, NULL);
     85        btree_remove(&t, 51, NULL);
     86        btree_remove(&t, 46, NULL);
     87        btree_remove(&t, 45, NULL);
     88        btree_remove(&t, 48, NULL);
     89        btree_remove(&t, 53, NULL);
     90        btree_remove(&t, 47, NULL);
     91        btree_remove(&t, 52, NULL);
     92        btree_remove(&t, 54, NULL);
     93        btree_remove(&t, 65, NULL);
     94        btree_remove(&t, 60, NULL);
     95        btree_remove(&t, 99, NULL);
     96        btree_remove(&t, 97, NULL);
     97        btree_remove(&t, 57, NULL);
     98        btree_remove(&t, 58, NULL);
     99        btree_remove(&t, 61, NULL);
     100        btree_remove(&t, 64, NULL);
     101        btree_remove(&t, 56, NULL);
     102        btree_remove(&t, 41, NULL);
    82103
     104        for (i = 5; i < 20; i++)
     105                btree_remove(&t, i, NULL);
     106
     107        btree_remove(&t, 2, NULL);
     108        btree_remove(&t, 43, NULL);
     109        btree_remove(&t, 22, NULL);
     110        btree_remove(&t, 100, NULL);
     111        btree_remove(&t, 98, NULL);
     112        btree_remove(&t, 96, NULL);
     113        btree_remove(&t, 66, NULL);
     114        btree_remove(&t, 1, NULL);
     115
     116        for (i = 70; i < 90; i++)
     117                btree_remove(&t, i, NULL);
     118
     119        btree_remove(&t, 20, NULL);
     120        btree_remove(&t, 0, NULL);
     121        btree_remove(&t, 40, NULL);
     122        btree_remove(&t, 3, NULL);
     123        btree_remove(&t, 4, NULL);
     124        btree_remove(&t, 21, NULL);
     125        btree_remove(&t, 44, NULL);
     126        btree_remove(&t, 55, NULL);
     127        btree_remove(&t, 62, NULL);
     128        btree_remove(&t, 26, NULL);
     129        btree_remove(&t, 27, NULL);
     130        btree_remove(&t, 28, NULL);
     131        btree_remove(&t, 29, NULL);
     132        btree_remove(&t, 30, NULL);
     133        btree_remove(&t, 31, NULL);
     134        btree_remove(&t, 32, NULL);
     135        btree_remove(&t, 33, NULL);
     136        btree_remove(&t, 93, NULL);
     137        btree_remove(&t, 95, NULL);
     138        btree_remove(&t, 94, NULL);
     139        btree_remove(&t, 69, NULL);
     140        btree_remove(&t, 68, NULL);
     141        btree_remove(&t, 92, NULL);
     142        btree_remove(&t, 91, NULL);
     143        btree_remove(&t, 67, NULL);
     144        btree_remove(&t, 63, NULL);
     145        btree_remove(&t, 90, NULL);
     146        btree_remove(&t, 59, NULL);
     147        btree_remove(&t, 23, NULL);
     148        btree_remove(&t, 24, NULL);
     149        btree_remove(&t, 25, NULL);
     150        btree_remove(&t, 37, NULL);
     151        btree_remove(&t, 38, NULL);
     152        btree_remove(&t, 42, NULL);
     153        btree_remove(&t, 39, NULL);
     154        btree_remove(&t, 34, NULL);
     155        btree_remove(&t, 35, NULL);
     156        btree_remove(&t, 36, NULL);
     157
     158        btree_print(&t);
    83159}
Note: See TracChangeset for help on using the changeset viewer.