/kernel/trunk/test/btree/btree1/test.c |
---|
40,6 → 40,14 |
btree_create(&t); |
printf("Inserting keys.\n"); |
btree_insert(&t, 19, data, NULL); |
btree_insert(&t, 20, data, NULL); |
btree_insert(&t, 21, data, NULL); |
btree_insert(&t, 0, data, NULL); |
btree_insert(&t, 25, data, NULL); |
btree_insert(&t, 22, data, NULL); |
btree_insert(&t, 26, data, NULL); |
btree_insert(&t, 23, data, NULL); |
btree_insert(&t, 24, data, NULL); |
btree_insert(&t, 5, data, NULL); |
55,13 → 63,6 |
btree_insert(&t, 2, data, NULL); |
btree_insert(&t, 3, data, NULL); |
btree_insert(&t, 6, data, NULL); |
btree_insert(&t, 19, data, NULL); |
btree_insert(&t, 20, data, NULL); |
btree_insert(&t, 21, data, NULL); |
btree_insert(&t, 0, data, NULL); |
btree_insert(&t, 25, data, NULL); |
btree_insert(&t, 22, data, NULL); |
btree_insert(&t, 26, data, NULL); |
btree_insert(&t, 10, data, NULL); |
btree_insert(&t, 11, data, NULL); |
btree_insert(&t, 12, data, NULL); |
78,6 → 79,81 |
btree_print(&t); |
printf("Removing keys.\n"); |
btree_remove(&t, 50, NULL); |
btree_remove(&t, 49, NULL); |
btree_remove(&t, 51, NULL); |
btree_remove(&t, 46, NULL); |
btree_remove(&t, 45, NULL); |
btree_remove(&t, 48, NULL); |
btree_remove(&t, 53, NULL); |
btree_remove(&t, 47, NULL); |
btree_remove(&t, 52, NULL); |
btree_remove(&t, 54, NULL); |
btree_remove(&t, 65, NULL); |
btree_remove(&t, 60, NULL); |
btree_remove(&t, 99, NULL); |
btree_remove(&t, 97, NULL); |
btree_remove(&t, 57, NULL); |
btree_remove(&t, 58, NULL); |
btree_remove(&t, 61, NULL); |
btree_remove(&t, 64, NULL); |
btree_remove(&t, 56, NULL); |
btree_remove(&t, 41, NULL); |
for (i = 5; i < 20; i++) |
btree_remove(&t, i, NULL); |
btree_remove(&t, 2, NULL); |
btree_remove(&t, 43, NULL); |
btree_remove(&t, 22, NULL); |
btree_remove(&t, 100, NULL); |
btree_remove(&t, 98, NULL); |
btree_remove(&t, 96, NULL); |
btree_remove(&t, 66, NULL); |
btree_remove(&t, 1, NULL); |
for (i = 70; i < 90; i++) |
btree_remove(&t, i, NULL); |
btree_remove(&t, 20, NULL); |
btree_remove(&t, 0, NULL); |
btree_remove(&t, 40, NULL); |
btree_remove(&t, 3, NULL); |
btree_remove(&t, 4, NULL); |
btree_remove(&t, 21, NULL); |
btree_remove(&t, 44, NULL); |
btree_remove(&t, 55, NULL); |
btree_remove(&t, 62, NULL); |
btree_remove(&t, 26, NULL); |
btree_remove(&t, 27, NULL); |
btree_remove(&t, 28, NULL); |
btree_remove(&t, 29, NULL); |
btree_remove(&t, 30, NULL); |
btree_remove(&t, 31, NULL); |
btree_remove(&t, 32, NULL); |
btree_remove(&t, 33, NULL); |
btree_remove(&t, 93, NULL); |
btree_remove(&t, 95, NULL); |
btree_remove(&t, 94, NULL); |
btree_remove(&t, 69, NULL); |
btree_remove(&t, 68, NULL); |
btree_remove(&t, 92, NULL); |
btree_remove(&t, 91, NULL); |
btree_remove(&t, 67, NULL); |
btree_remove(&t, 63, NULL); |
btree_remove(&t, 90, NULL); |
btree_remove(&t, 59, NULL); |
btree_remove(&t, 23, NULL); |
btree_remove(&t, 24, NULL); |
btree_remove(&t, 25, NULL); |
btree_remove(&t, 37, NULL); |
btree_remove(&t, 38, NULL); |
btree_remove(&t, 42, NULL); |
btree_remove(&t, 39, NULL); |
btree_remove(&t, 34, NULL); |
btree_remove(&t, 35, NULL); |
btree_remove(&t, 36, NULL); |
btree_print(&t); |
} |
/kernel/trunk/generic/src/adt/btree.c |
---|
49,12 → 49,12 |
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 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); |
static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx); |
154,7 → 154,7 |
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)) { |
189,7 → 189,6 |
{ |
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)) { |
436,6 → 435,61 |
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 |
559,61 → 613,6 |
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. |
878,8 → 877,9 |
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); |
905,7 → 905,7 |
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); |
} |
916,4 → 916,19 |
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"); |
} |
/kernel/trunk/generic/src/mm/slab.c |
---|
39,7 → 39,7 |
* Following features are not currently supported but would be easy to do: |
* - 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 |
* good SMP scaling. |