Subversion Repositories HelenOS-historic

Compare Revisions

Regard whitespace Rev 1139 → Rev 1140

/kernel/trunk/generic/src/adt/btree.c
28,7 → 28,7
 
/*
* This B-tree has the following properties:
* - it is a ballanced 2-3-4 tree (i.e. BTREE_M = 4)
* - it is a ballanced 2-3-4-5 tree (i.e. BTREE_M = 5)
* - values (i.e. pointers to values) are stored only in leaves
* - leaves are linked in a list
* - technically, it is a B+-tree (because of the previous properties)
61,6 → 61,8
#define INDEX_NODE(n) ((n)->subtree[0] != NULL)
#define LEAF_NODE(n) ((n)->subtree[0] == NULL)
 
#define FILL_FACTOR ((BTREE_M-1)/2)
 
#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2)
#define MEDIAN_HIGH_INDEX(n) ((n)->keys/2)
#define MEDIAN_LOW(n) ((n)->key[MEDIAN_LOW_INDEX((n))]);
171,11 → 173,27
}
 
/* TODO */
void btree_remove(btree_t *t, __native key)
/** Remove B-tree node.
*
* @param B-tree.
* @param key Key to be removed from the B-tree along with its associated value.
* @param leaf_node If not NULL, pointer to the leaf node where the key is found.
*/
void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node)
{
btree_node_t *lnode;
lnode = leaf_node;
if (!lnode) {
if (!btree_search(t, key, &lnode)) {
panic("B-tree %P does not contain key %d\n", t, key);
}
}
 
/* TODO */
 
}
 
/** Search key in a B-tree.
*
* @param t B-tree.