btree_node Struct Reference
[Data types]


Data Fields

count_t keys
btree_key_t key [BTREE_MAX_KEYS+1]
void * value [BTREE_MAX_KEYS+1]
btree_node_tsubtree [BTREE_M+1]
btree_node_tparent
link_t leaf_link
link_t bfs_link
int depth

Detailed Description

B-tree node structure.

Definition at line 48 of file btree.h.


Field Documentation

link_t bfs_link
 

Variables needed by btree_print().

Definition at line 77 of file btree.h.

Referenced by btree_print().

int depth
 

Definition at line 78 of file btree.h.

Referenced by _btree_insert(), btree_print(), and node_split().

btree_key_t key[BTREE_MAX_KEYS+1]
 

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().

count_t keys
 

Number of keys.

Definition at line 50 of file btree.h.

Referenced by _btree_insert(), _btree_remove(), anon_page_fault(), anon_share(), as_area_destroy(), btree_destroy_subtree(), btree_print(), btree_search(), check_area_conflicts(), elf_page_fault(), elf_share(), find_area_and_lock(), find_key_by_subtree(), 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(), sh_info_remove_reference(), task_print_list(), thread_print_list(), try_insert_by_rotation_to_left(), try_insert_by_rotation_to_right(), try_rotation_from_left(), try_rotation_from_right(), used_space_insert(), and used_space_remove().

link_t leaf_link
 

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().

btree_node_t* parent
 

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().

btree_node_t* subtree[BTREE_M+1]
 

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().

void* value[BTREE_MAX_KEYS+1]
 

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().


Generated on Sun Jun 18 16:30:18 2006 for HelenOS Kernel (amd64) by  doxygen 1.4.6