Rev 1164 | Rev 1702 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 1164 | Rev 1177 | ||
|---|---|---|---|
| Line 34... | Line 34... | ||
| 34 | #include <adt/list.h> |
34 | #include <adt/list.h> |
| 35 | 35 | ||
| 36 | #define BTREE_M 5 |
36 | #define BTREE_M 5 |
| 37 | #define BTREE_MAX_KEYS (BTREE_M - 1) |
37 | #define BTREE_MAX_KEYS (BTREE_M - 1) |
| 38 | 38 | ||
| - | 39 | typedef __u64 btree_key_t; |
|
| - | 40 | ||
| 39 | /** B-tree node structure. */ |
41 | /** B-tree node structure. */ |
| 40 | struct btree_node { |
42 | struct btree_node { |
| 41 | /** Number of keys. */ |
43 | /** Number of keys. */ |
| 42 | count_t keys; |
44 | count_t keys; |
| 43 | 45 | ||
| 44 | /** Keys. We currently support only single keys. Additional room for one extra key is provided. */ |
46 | /** Keys. We currently support only single keys. Additional room for one extra key is provided. */ |
| 45 | __native key[BTREE_MAX_KEYS + 1]; |
47 | btree_key_t key[BTREE_MAX_KEYS + 1]; |
| 46 | 48 | ||
| 47 | /** |
49 | /** |
| 48 | * Pointers to values. Sorted according to the key array. Defined only in leaf-level. |
50 | * Pointers to values. Sorted according to the key array. Defined only in leaf-level. |
| 49 | * There is room for storing value for the extra key. |
51 | * There is room for storing value for the extra key. |
| 50 | */ |
52 | */ |
| Line 79... | Line 81... | ||
| 79 | extern void btree_init(void); |
81 | extern void btree_init(void); |
| 80 | 82 | ||
| 81 | extern void btree_create(btree_t *t); |
83 | extern void btree_create(btree_t *t); |
| 82 | extern void btree_destroy(btree_t *t); |
84 | extern void btree_destroy(btree_t *t); |
| 83 | 85 | ||
| 84 | extern void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node); |
86 | extern void btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node); |
| 85 | extern void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node); |
87 | extern void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node); |
| 86 | extern void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node); |
88 | extern void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node); |
| 87 | 89 | ||
| 88 | extern btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node); |
90 | extern btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node); |
| 89 | extern btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node); |
91 | extern btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node); |
| 90 | 92 | ||
| 91 | extern void btree_print(btree_t *t); |
93 | extern void btree_print(btree_t *t); |