Data Fields | |
count_t | keys |
btree_key_t | key [BTREE_MAX_KEYS+1] |
void * | value [BTREE_MAX_KEYS+1] |
btree_node_t * | subtree [BTREE_M+1] |
btree_node_t * | parent |
link_t | leaf_link |
link_t | bfs_link |
int | depth |
Definition at line 48 of file btree.h.
|
Variables needed by btree_print(). Definition at line 77 of file btree.h. Referenced by btree_print(). |
|
Definition at line 78 of file btree.h. Referenced by _btree_insert(), btree_print(), and node_split(). |
|
Keys. We currently support only single keys. Additional room for one extra key is provided. Definition at line 53 of file btree.h. Referenced by _btree_remove(), anon_page_fault(), anon_share(), as_area_destroy(), btree_print(), btree_search(), elf_page_fault(), elf_share(), futex_cleanup(), node_combine(), node_initialize(), node_insert_key_and_lsubtree(), node_insert_key_and_rsubtree(), node_remove_key_and_lsubtree(), node_remove_key_and_rsubtree(), node_split(), rotate_from_left(), rotate_from_right(), used_space_insert(), and used_space_remove(). |
|
|
Link connecting leaf-level nodes. Defined only when this node is a leaf. Definition at line 74 of file btree.h. Referenced by _btree_insert(), btree_create(), btree_leaf_node_left_neighbour(), btree_leaf_node_right_neighbour(), and elf_share(). |
|
Pointer to parent node. Root node has NULL parent. Definition at line 71 of file btree.h. Referenced by _btree_insert(), _btree_remove(), node_combine(), node_split(), rotate_from_left(), rotate_from_right(), try_insert_by_rotation_to_left(), try_insert_by_rotation_to_right(), try_rotation_from_left(), and try_rotation_from_right(). |
|
Pointers to descendants of this node sorted according to the key array. subtree[0] points to subtree with keys lesser than to key[0]. subtree[1] points to subtree with keys greater than or equal to key[0] and lesser than key[1]. ... There is room for storing a subtree pointer for the extra key. Definition at line 68 of file btree.h. Referenced by _btree_insert(), _btree_remove(), btree_destroy_subtree(), btree_print(), btree_search(), find_key_by_subtree(), node_combine(), node_initialize(), node_insert_key_and_lsubtree(), node_insert_key_and_rsubtree(), node_remove_key_and_lsubtree(), node_remove_key_and_rsubtree(), node_split(), rotate_from_left(), rotate_from_right(), try_insert_by_rotation_to_left(), try_insert_by_rotation_to_right(), try_rotation_from_left(), and try_rotation_from_right(). |
|
Pointers to values. Sorted according to the key array. Defined only in leaf-level. There is room for storing value for the extra key. Definition at line 59 of file btree.h. Referenced by anon_share(), as_area_destroy(), btree_search(), check_area_conflicts(), elf_share(), find_area_and_lock(), futex_cleanup(), node_combine(), node_initialize(), node_insert_key_and_lsubtree(), node_insert_key_and_rsubtree(), node_remove_key_and_lsubtree(), node_remove_key_and_rsubtree(), node_split(), rotate_from_left(), rotate_from_right(), sh_info_remove_reference(), task_print_list(), thread_print_list(), used_space_insert(), and used_space_remove(). |