| /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)) { |