Subversion Repositories HelenOS-historic

Compare Revisions

Ignore whitespace Rev 1143 → Rev 1144

/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.