Rev 1101 | Rev 1142 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 1101 | Rev 1140 | ||
|---|---|---|---|
| Line 31... | Line 31... | ||
| 31 | 31 | ||
| 32 | #include <arch/types.h> |
32 | #include <arch/types.h> |
| 33 | #include <typedefs.h> |
33 | #include <typedefs.h> |
| 34 | #include <adt/list.h> |
34 | #include <adt/list.h> |
| 35 | 35 | ||
| 36 | #define BTREE_M 4 |
36 | #define BTREE_M 5 |
| 37 | #define BTREE_MAX_KEYS (BTREE_M - 1) |
37 | #define BTREE_MAX_KEYS (BTREE_M - 1) |
| 38 | 38 | ||
| 39 | /** B-tree node structure. */ |
39 | /** B-tree node structure. */ |
| 40 | struct btree_node { |
40 | struct btree_node { |
| 41 | /** Number of keys. */ |
41 | /** Number of keys. */ |
| Line 50... | Line 50... | ||
| 50 | */ |
50 | */ |
| 51 | void *value[BTREE_MAX_KEYS + 1]; |
51 | void *value[BTREE_MAX_KEYS + 1]; |
| 52 | 52 | ||
| 53 | /** |
53 | /** |
| 54 | * Pointers to descendants of this node sorted according to the key array. |
54 | * Pointers to descendants of this node sorted according to the key array. |
| 55 | * subtree[0] points to subtree with keys lesser than or equal to key[0]. |
55 | * subtree[0] points to subtree with keys lesser than to key[0]. |
| 56 | * subtree[1] points to subtree with keys greater than key[0] and lesser than or equal to key[1]. |
56 | * subtree[1] points to subtree with keys greater than or equal to key[0] and lesser than key[1]. |
| 57 | * ... |
57 | * ... |
| 58 | * There is room for storing a subtree pointer for the extra key. |
58 | * There is room for storing a subtree pointer for the extra key. |
| 59 | */ |
59 | */ |
| 60 | btree_node_t *subtree[BTREE_M + 1]; |
60 | btree_node_t *subtree[BTREE_M + 1]; |
| 61 | 61 | ||
| Line 78... | Line 78... | ||
| 78 | 78 | ||
| 79 | extern void btree_create(btree_t *t); |
79 | extern void btree_create(btree_t *t); |
| 80 | extern void btree_destroy(btree_t *t); |
80 | extern void btree_destroy(btree_t *t); |
| 81 | 81 | ||
| 82 | extern void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node); |
82 | extern void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node); |
| 83 | extern void btree_remove(btree_t *t, __native key); |
83 | extern void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node); |
| 84 | extern void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node); |
84 | extern void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node); |
| 85 | 85 | ||
| 86 | extern void *btree_node_min(btree_node_t *node); |
86 | extern void *btree_node_min(btree_node_t *node); |
| 87 | extern void *btree_node_max(btree_node_t *node); |
87 | extern void *btree_node_max(btree_node_t *node); |
| 88 | 88 | ||