/kernel/trunk/generic/include/adt/btree.h |
---|
83,8 → 83,8 |
extern void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node); |
extern void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node); |
extern btree_node_t *btree_node_left_sibling(btree_t *t, btree_node_t *node); |
extern btree_node_t *btree_node_right_sibling(btree_t *t, btree_node_t *node); |
extern btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node); |
extern btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node); |
extern void btree_print(btree_t *t); |
#endif |
/kernel/trunk/generic/src/adt/btree.c |
---|
340,14 → 340,14 |
return NULL; |
} |
/** Return pointer to B-tree node's left sibling. |
/** Return pointer to B-tree leaf node's left neighbour. |
* |
* @param t B-tree. |
* @param node Node whose left sibling will be returned. |
* @param node Node whose left neighbour will be returned. |
* |
* @return Left sibling of the node or NULL if the node does not have the left sibling. |
* @return Left neighbour of the node or NULL if the node does not have the left neighbour. |
*/ |
btree_node_t *btree_node_left_sibling(btree_t *t, btree_node_t *node) |
btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node) |
{ |
ASSERT(LEAF_NODE(node)); |
if (node->leaf_link.prev != &t->leaf_head) |
356,14 → 356,14 |
return NULL; |
} |
/** Return pointer to B-tree node's right sibling. |
/** Return pointer to B-tree leaf node's right neighbour. |
* |
* @param t B-tree. |
* @param node Node whose right sibling will be returned. |
* @param node Node whose right neighbour will be returned. |
* |
* @return Right sibling of the node or NULL if the node does not have the right sibling. |
* @return Right neighbour of the node or NULL if the node does not have the right neighbour. |
*/ |
btree_node_t *btree_node_right_sibling(btree_t *t, btree_node_t *node) |
btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node) |
{ |
ASSERT(LEAF_NODE(node)); |
if (node->leaf_link.next != &t->leaf_head) |
/kernel/trunk/generic/src/mm/as.c |
---|
525,7 → 525,7 |
} |
/* |
* Search the leaf node and the righmost record of its left sibling |
* Search the leaf node and the righmost record of its left neighbour |
* to find out whether this is a miss or va belongs to an address |
* space area found there. |
*/ |
541,10 → 541,10 |
} |
/* |
* Second, locate the left sibling and test its last record. |
* Second, locate the left neighbour and test its last record. |
* Because of its position in the B+tree, it must have base < va. |
*/ |
if ((lnode = btree_node_left_sibling(&as->as_area_btree, leaf))) { |
if ((lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) { |
a = (as_area_t *) lnode->value[lnode->keys - 1]; |
spinlock_lock(&a->lock); |
if (va < a->base + a->pages * PAGE_SIZE) { |
583,8 → 583,8 |
* The leaf node is found in O(log n), where n is proportional to |
* the number of address space areas belonging to as. |
* The check for conflicts is then attempted on the rightmost |
* record in the left sibling, the leftmost record in the right |
* sibling and all records in the leaf node itself. |
* record in the left neighbour, the leftmost record in the right |
* neighbour and all records in the leaf node itself. |
*/ |
if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) { |
593,7 → 593,7 |
} |
/* First, check the two border cases. */ |
if ((node = btree_node_left_sibling(&as->as_area_btree, leaf))) { |
if ((node = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) { |
a = (as_area_t *) node->value[node->keys - 1]; |
spinlock_lock(&a->lock); |
if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) { |
602,7 → 602,7 |
} |
spinlock_unlock(&a->lock); |
} |
if ((node = btree_node_right_sibling(&as->as_area_btree, leaf))) { |
if ((node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf))) { |
a = (as_area_t *) node->value[0]; |
spinlock_lock(&a->lock); |
if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) { |