B-tree implementation template. More...
Classes | |
| struct | cp2d |
| struct | btree_node |
| struct | btree_node_p |
| struct | btree_node_structure |
| struct | btree |
Functions | |
| subroutine, public | btree_new (tree, order) |
| INTEGER, public | btree_get_entries (tree) |
| subroutine, public | btree_delete (tree, keys, values) |
| recursive subroutine | btree_delete_node (node, pos, keys, values) |
| subroutine, public | btree_add (tree, key, value, exists, existing_value, replace) |
| recursive subroutine | btree_add_into (tree, node, key, value, before, subtree) |
| subroutine | btree_simple_insertion (node, key, value, before, subtree) |
| subroutine | btree_left_insertion (tree, node, new_node, key, value, before, split_pos, subtree) |
| subroutine | btree_right_insertion (tree, node, new_node, key, value, before, split_pos, subtree) |
| subroutine | btree_adopt_subtrees (node) |
| subroutine, public | btree_remove (tree, key, value, exists) |
| subroutine | btree_remove_from (tree, node, key_in, before) |
| recursive subroutine | btree_rebalance (tree, node, parent_pos) |
| subroutine | btree_merge (node_left, node_right, left_pos) |
| subroutine | btree_snatch_from_right (node_left, node_right, left_pos) |
| subroutine | btree_snatch_from_left (node_left, node_right, left_pos) |
| subroutine | btree_new_root (tree, key, value) |
| subroutine | btree_new_node (tree, node) |
| subroutine | btree_free_node (node) |
| subroutine, public | btree_find (tree, key, value, exists) |
| subroutine | btree_pop_smallest (tree, key, value) |
| subroutine | btree_pop_greatest (tree, key, value) |
| subroutine | btree_node_find_ge2_pos (keys, key, position, filled) |
| subroutine | btree_node_find_ge_pos (keys, key, position, filled) |
| subroutine | btree_node_find_gt2_pos (keys, key, position, filled) |
| subroutine | btree_node_find_gt_pos (keys, key, position, filled) |
| subroutine | btree_node_find_gte_pos (keys, key, position, filled, first) |
| subroutine | btree_find_full (tree, key, node, position, ge_position, short) |
| subroutine | btree_find_leaf (tree, key, node, gti) |
| subroutine, public | btree_print_short (tree) |
| recursive subroutine | btree_print_short_node (node) |
| subroutine | btree_print (tree) |
| recursive subroutine | btree_print_node (node, level, lastv, count, num_nodes, max_leaf_level, min_leaf_level, printing) |
| recursive subroutine | btree_print_bynode (node, level) |
| subroutine | btree_verify (tree) |
| recursive subroutine | btree_verify_node (tree, node, level, nids, lastv, count, num_nodes, max_leaf_level, min_leaf_level, printing) |
Variables | |
| INTEGER, parameter | keyt = SELECTED_INT_KIND(10) |
| INTEGER, parameter | valt = SELECTED_INT_KIND(5); |
| INTEGER, parameter | sp = KIND(0.0) |
Detailed Description
B-tree implementation template.
- Date:
- 2000-05-12
- Version:
- 1.0 Modification history:
- Created
Function Documentation
| subroutine,public btree_i8_k_cp2d_v::btree_add | ( | TYPE(btree),intent(inout) | tree, |
| INTEGER(KIND=keyt),intent(in) | key, | ||
| TYPE(cp2d),intent(in) | value, | ||
| LOGICAL,intent(out),optional | exists, | ||
| TYPE(cp2d),intent(out),optional | existing_value, | ||
| LOGICAL,intent(in),optional | replace | ||
| ) |
Definition at line 165 of file btree_i8_k_cp2d_v.f90.
References btree_add_into(), btree_find_full(), and btree_find_leaf().
Here is the call graph for this function:
| recursive subroutine btree_i8_k_cp2d_v::btree_add_into | ( | TYPE(btree),intent(inout) | tree, |
| TYPE(btree_node),pointer | node, | ||
| INTEGER(KIND=keyt),intent(in) | key, | ||
| TYPE(cp2d),intent(in) | value, | ||
| INTEGER,intent(in),optional | before, | ||
| TYPE(btree_node),optional,pointer | subtree | ||
| ) |
Definition at line 202 of file btree_i8_k_cp2d_v.f90.
References btree_adopt_subtrees(), btree_left_insertion(), btree_new_node(), btree_new_root(), btree_node_find_gt_pos(), btree_right_insertion(), and btree_simple_insertion().
Referenced by btree_add().
Here is the call graph for this function:
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_adopt_subtrees | ( | TYPE(btree_node),pointer | node | ) |
Definition at line 392 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_add_into().
Here is the caller graph for this function:
| subroutine,public btree_i8_k_cp2d_v::btree_delete | ( | TYPE(btree),intent(inout) | tree, |
| INTEGER(KIND=keyt),dimension(:),intent(out),optional | keys, | ||
| TYPE(cp2d),dimension(:),intent(out),optional | values | ||
| ) |
Definition at line 101 of file btree_i8_k_cp2d_v.f90.
References btree_delete_node().
Here is the call graph for this function:
| recursive subroutine btree_i8_k_cp2d_v::btree_delete_node | ( | TYPE(btree_node),pointer | node, |
| INTEGER,intent(inout),optional | pos, | ||
| INTEGER(KIND=keyt),dimension(:),intent(inout),optional | keys, | ||
| TYPE(cp2d),dimension(:),intent(inout),optional | values | ||
| ) |
Definition at line 124 of file btree_i8_k_cp2d_v.f90.
References btree_free_node().
Referenced by btree_delete().
Here is the call graph for this function:
Here is the caller graph for this function:
| subroutine,public btree_i8_k_cp2d_v::btree_find | ( | TYPE(btree),intent(in) | tree, |
| INTEGER(KIND=keyt),intent(in) | key, | ||
| TYPE(cp2d),intent(out) | value, | ||
| LOGICAL,intent(out),optional | exists | ||
| ) |
Definition at line 790 of file btree_i8_k_cp2d_v.f90.
References btree_find_full().
Here is the call graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_find_full | ( | TYPE(btree),intent(in) | tree, |
| INTEGER(KIND=keyt),intent(in) | key, | ||
| TYPE(btree_node),pointer | node, | ||
| INTEGER,intent(out) | position, | ||
| INTEGER,intent(out),optional | ge_position, | ||
| LOGICAL,intent(in),optional | short | ||
| ) |
Definition at line 988 of file btree_i8_k_cp2d_v.f90.
References btree_node_find_ge_pos(), and btree_node_find_gte_pos().
Referenced by btree_add(), btree_find(), and btree_remove().
Here is the call graph for this function:
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_find_leaf | ( | TYPE(btree),intent(in) | tree, |
| INTEGER(KIND=keyt),intent(in) | key, | ||
| TYPE(btree_node),pointer | node, | ||
| INTEGER,intent(out) | gti | ||
| ) |
Definition at line 1046 of file btree_i8_k_cp2d_v.f90.
References btree_node_find_gt_pos().
Referenced by btree_add().
Here is the call graph for this function:
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_free_node | ( | TYPE(btree_node),pointer | node | ) |
Definition at line 778 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_delete_node(), and btree_merge().
Here is the caller graph for this function:
| INTEGER,public btree_i8_k_cp2d_v::btree_get_entries | ( | TYPE(btree),intent(inout) | tree | ) |
Definition at line 93 of file btree_i8_k_cp2d_v.f90.
| subroutine btree_i8_k_cp2d_v::btree_left_insertion | ( | TYPE(btree),intent(in) | tree, |
| TYPE(btree_node),intent(inout) | node, | ||
| TYPE(btree_node),intent(inout) | new_node, | ||
| INTEGER(KIND=keyt),intent(in) | key, | ||
| TYPE(cp2d),intent(in) | value, | ||
| INTEGER,intent(in) | before, | ||
| INTEGER,intent(in) | split_pos, | ||
| TYPE(btree_node),optional,pointer | subtree | ||
| ) |
Definition at line 317 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_add_into().
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_merge | ( | TYPE(btree_node),pointer | node_left, |
| TYPE(btree_node),pointer | node_right, | ||
| INTEGER,intent(in) | left_pos | ||
| ) |
Definition at line 601 of file btree_i8_k_cp2d_v.f90.
References btree_free_node().
Referenced by btree_rebalance().
Here is the call graph for this function:
Here is the caller graph for this function:
| subroutine,public btree_i8_k_cp2d_v::btree_new | ( | TYPE(btree),intent(out) | tree, |
| INTEGER,intent(in),optional | order | ||
| ) |
Definition at line 68 of file btree_i8_k_cp2d_v.f90.
| subroutine btree_i8_k_cp2d_v::btree_new_node | ( | TYPE(btree),intent(inout) | tree, |
| TYPE(btree_node),pointer | node | ||
| ) |
Definition at line 757 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_add_into(), and btree_new_root().
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_new_root | ( | TYPE(btree),intent(inout) | tree, |
| INTEGER(KIND=keyt),intent(in) | key, | ||
| TYPE(cp2d),intent(in) | value | ||
| ) |
Definition at line 734 of file btree_i8_k_cp2d_v.f90.
References btree_new_node().
Referenced by btree_add_into().
Here is the call graph for this function:
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_node_find_ge2_pos | ( | INTEGER(KIND=keyt),dimension(:) | keys, |
| INTEGER(KIND=keyt),intent(in) | key, | ||
| INTEGER,intent(out) | position, | ||
| INTEGER,intent(in) | filled | ||
| ) |
Definition at line 862 of file btree_i8_k_cp2d_v.f90.
| subroutine btree_i8_k_cp2d_v::btree_node_find_ge_pos | ( | INTEGER(KIND=keyt),dimension(:) | keys, |
| INTEGER(KIND=keyt),intent(in) | key, | ||
| INTEGER,intent(out) | position, | ||
| INTEGER,intent(in) | filled | ||
| ) |
Definition at line 876 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_find_full().
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_node_find_gt2_pos | ( | INTEGER(KIND=keyt),dimension(:) | keys, |
| INTEGER(KIND=keyt),intent(in) | key, | ||
| INTEGER,intent(out) | position, | ||
| INTEGER,intent(in) | filled | ||
| ) |
Definition at line 906 of file btree_i8_k_cp2d_v.f90.
| subroutine btree_i8_k_cp2d_v::btree_node_find_gt_pos | ( | INTEGER(KIND=keyt),dimension(:) | keys, |
| INTEGER(KIND=keyt),intent(in) | key, | ||
| INTEGER,intent(out) | position, | ||
| INTEGER,intent(in) | filled | ||
| ) |
Definition at line 920 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_add_into(), btree_find_leaf(), and btree_remove_from().
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_node_find_gte_pos | ( | INTEGER(KIND=keyt),dimension(:) | keys, |
| INTEGER(KIND=keyt),intent(in) | key, | ||
| INTEGER,intent(out) | position, | ||
| INTEGER,intent(in) | filled, | ||
| INTEGER,intent(in),optional | first | ||
| ) |
Definition at line 950 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_find_full().
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_pop_greatest | ( | TYPE(btree),intent(inout) | tree, |
| INTEGER(KIND=keyt),intent(out) | key, | ||
| TYPE(cp2d),intent(out) | value | ||
| ) |
Definition at line 836 of file btree_i8_k_cp2d_v.f90.
References btree_remove_from().
Here is the call graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_pop_smallest | ( | TYPE(btree),intent(inout) | tree, |
| INTEGER(KIND=keyt),intent(out) | key, | ||
| TYPE(cp2d),intent(out) | value | ||
| ) |
Definition at line 812 of file btree_i8_k_cp2d_v.f90.
References btree_remove_from().
Here is the call graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_print | ( | TYPE(btree),intent(inout) | tree | ) |
Definition at line 1114 of file btree_i8_k_cp2d_v.f90.
References btree_print_bynode(), btree_print_node(), and btree_verify().
Here is the call graph for this function:
| recursive subroutine btree_i8_k_cp2d_v::btree_print_bynode | ( | TYPE(btree_node),intent(in) | node, |
| INTEGER,intent(in) | level | ||
| ) |
Definition at line 1190 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_print().
Here is the caller graph for this function:
| recursive subroutine btree_i8_k_cp2d_v::btree_print_node | ( | TYPE(btree_node),intent(in) | node, |
| INTEGER,intent(in) | level, | ||
| INTEGER(KIND=keyt),intent(inout) | lastv, | ||
| INTEGER,intent(inout) | count, | ||
| INTEGER,intent(inout) | num_nodes, | ||
| INTEGER,intent(inout) | max_leaf_level, | ||
| INTEGER,intent(inout) | min_leaf_level, | ||
| LOGICAL,intent(inout) | printing | ||
| ) |
Definition at line 1142 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_print().
Here is the caller graph for this function:
| subroutine,public btree_i8_k_cp2d_v::btree_print_short | ( | TYPE(btree),intent(in) | tree | ) |
Definition at line 1086 of file btree_i8_k_cp2d_v.f90.
References btree_print_short_node().
Here is the call graph for this function:
| recursive subroutine btree_i8_k_cp2d_v::btree_print_short_node | ( | TYPE(btree_node),intent(in) | node | ) |
Definition at line 1095 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_print_short().
Here is the caller graph for this function:
| recursive subroutine btree_i8_k_cp2d_v::btree_rebalance | ( | TYPE(btree),intent(inout) | tree, |
| TYPE(btree_node),pointer | node, | ||
| INTEGER,intent(in),optional | parent_pos | ||
| ) |
Definition at line 520 of file btree_i8_k_cp2d_v.f90.
References btree_merge(), btree_snatch_from_left(), and btree_snatch_from_right().
Referenced by btree_remove_from().
Here is the call graph for this function:
Here is the caller graph for this function:
| subroutine,public btree_i8_k_cp2d_v::btree_remove | ( | TYPE(btree),intent(inout) | tree, |
| INTEGER(KIND=keyt),intent(in) | key, | ||
| TYPE(cp2d),intent(out),optional | value, | ||
| LOGICAL,intent(out),optional | exists | ||
| ) |
Definition at line 410 of file btree_i8_k_cp2d_v.f90.
References btree_find_full(), and btree_remove_from().
Here is the call graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_remove_from | ( | TYPE(btree),intent(inout) | tree, |
| TYPE(btree_node),pointer | node, | ||
| INTEGER(KIND=keyt),intent(in) | key_in, | ||
| INTEGER,intent(in),optional | before | ||
| ) |
Definition at line 457 of file btree_i8_k_cp2d_v.f90.
References btree_node_find_gt_pos(), and btree_rebalance().
Referenced by btree_pop_greatest(), btree_pop_smallest(), and btree_remove().
Here is the call graph for this function:
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_right_insertion | ( | TYPE(btree),intent(in) | tree, |
| TYPE(btree_node),intent(inout) | node, | ||
| TYPE(btree_node),intent(inout) | new_node, | ||
| INTEGER(KIND=keyt),intent(in) | key, | ||
| TYPE(cp2d),intent(in) | value, | ||
| INTEGER,intent(in) | before, | ||
| INTEGER,intent(in) | split_pos, | ||
| TYPE(btree_node),optional,pointer | subtree | ||
| ) |
Definition at line 361 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_add_into().
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_simple_insertion | ( | TYPE(btree_node),intent(inout) | node, |
| INTEGER(KIND=keyt),intent(in) | key, | ||
| TYPE(cp2d),intent(in) | value, | ||
| INTEGER,intent(in) | before, | ||
| TYPE(btree_node),optional,pointer | subtree | ||
| ) |
Definition at line 292 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_add_into().
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_snatch_from_left | ( | TYPE(btree_node),intent(inout) | node_left, |
| TYPE(btree_node),pointer | node_right, | ||
| INTEGER,intent(in) | left_pos | ||
| ) |
Definition at line 698 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_rebalance().
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_snatch_from_right | ( | TYPE(btree_node),pointer | node_left, |
| TYPE(btree_node),intent(inout) | node_right, | ||
| INTEGER,intent(in) | left_pos | ||
| ) |
Definition at line 656 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_rebalance().
Here is the caller graph for this function:
| subroutine btree_i8_k_cp2d_v::btree_verify | ( | TYPE(btree),intent(inout) | tree | ) |
Definition at line 1222 of file btree_i8_k_cp2d_v.f90.
References btree_verify_node().
Referenced by btree_print().
Here is the call graph for this function:
Here is the caller graph for this function:
| recursive subroutine btree_i8_k_cp2d_v::btree_verify_node | ( | TYPE(btree),intent(in) | tree, |
| TYPE(btree_node),intent(in) | node, | ||
| INTEGER,intent(in) | level, | ||
| LOGICAL,dimension(:),intent(inout) | nids, | ||
| INTEGER(KIND=keyt),intent(inout) | lastv, | ||
| INTEGER,intent(inout) | count, | ||
| INTEGER,intent(inout) | num_nodes, | ||
| INTEGER,intent(inout) | max_leaf_level, | ||
| INTEGER,intent(inout) | min_leaf_level, | ||
| LOGICAL,intent(inout) | printing | ||
| ) |
Definition at line 1254 of file btree_i8_k_cp2d_v.f90.
Referenced by btree_verify().
Here is the caller graph for this function:
Variable Documentation
| INTEGER,parameter btree_i8_k_cp2d_v::keyt = SELECTED_INT_KIND(10) |
Definition at line 30 of file btree_i8_k_cp2d_v.f90.
| INTEGER,parameter btree_i8_k_cp2d_v::sp = KIND(0.0) |
Definition at line 32 of file btree_i8_k_cp2d_v.f90.
| INTEGER,parameter btree_i8_k_cp2d_v::valt = SELECTED_INT_KIND(5); |
Definition at line 31 of file btree_i8_k_cp2d_v.f90.
