Rev 2071 | Rev 2106 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 2071 | Rev 2089 | ||
|---|---|---|---|
| Line 34... | Line 34... | ||
| 34 | 34 | ||
| 35 | #ifndef KERN_BTREE_H_ |
35 | #ifndef KERN_BTREE_H_ |
| 36 | #define KERN_BTREE_H_ |
36 | #define KERN_BTREE_H_ |
| 37 | 37 | ||
| 38 | #include <arch/types.h> |
38 | #include <arch/types.h> |
| 39 | #include <typedefs.h> |
- | |
| 40 | #include <adt/list.h> |
39 | #include <adt/list.h> |
| 41 | 40 | ||
| 42 | #define BTREE_M 5 |
41 | #define BTREE_M 5 |
| 43 | #define BTREE_MAX_KEYS (BTREE_M - 1) |
42 | #define BTREE_MAX_KEYS (BTREE_M - 1) |
| 44 | 43 | ||
| 45 | typedef uint64_t btree_key_t; |
44 | typedef uint64_t btree_key_t; |
| 46 | 45 | ||
| 47 | /** B-tree node structure. */ |
46 | /** B-tree node structure. */ |
| 48 | struct btree_node { |
47 | typedef struct btree_node { |
| 49 | /** Number of keys. */ |
48 | /** Number of keys. */ |
| 50 | count_t keys; |
49 | count_t keys; |
| 51 | 50 | ||
| 52 | /** Keys. We currently support only single keys. Additional room for one extra key is provided. */ |
51 | /** Keys. We currently support only single keys. Additional room for one extra key is provided. */ |
| 53 | btree_key_t key[BTREE_MAX_KEYS + 1]; |
52 | btree_key_t key[BTREE_MAX_KEYS + 1]; |
| Line 63... | Line 62... | ||
| 63 | * subtree[0] points to subtree with keys lesser than to key[0]. |
62 | * subtree[0] points to subtree with keys lesser than to key[0]. |
| 64 | * subtree[1] points to subtree with keys greater than or equal to key[0] and lesser than key[1]. |
63 | * subtree[1] points to subtree with keys greater than or equal to key[0] and lesser than key[1]. |
| 65 | * ... |
64 | * ... |
| 66 | * There is room for storing a subtree pointer for the extra key. |
65 | * There is room for storing a subtree pointer for the extra key. |
| 67 | */ |
66 | */ |
| 68 | btree_node_t *subtree[BTREE_M + 1]; |
67 | struct btree_node *subtree[BTREE_M + 1]; |
| 69 | 68 | ||
| 70 | /** Pointer to parent node. Root node has NULL parent. */ |
69 | /** Pointer to parent node. Root node has NULL parent. */ |
| 71 | btree_node_t *parent; |
70 | struct btree_node *parent; |
| 72 | 71 | ||
| 73 | /** Link connecting leaf-level nodes. Defined only when this node is a leaf. */ |
72 | /** Link connecting leaf-level nodes. Defined only when this node is a leaf. */ |
| 74 | link_t leaf_link; |
73 | link_t leaf_link; |
| 75 | 74 | ||
| 76 | /** Variables needed by btree_print(). */ |
75 | /** Variables needed by btree_print(). */ |
| 77 | link_t bfs_link; |
76 | link_t bfs_link; |
| 78 | int depth; |
77 | int depth; |
| 79 | }; |
78 | } btree_node_t; |
| 80 | 79 | ||
| 81 | /** B-tree structure. */ |
80 | /** B-tree structure. */ |
| 82 | struct btree { |
81 | typedef struct { |
| 83 | btree_node_t *root; /**< B-tree root node pointer. */ |
82 | btree_node_t *root; /**< B-tree root node pointer. */ |
| 84 | link_t leaf_head; /**< Leaf-level list head. */ |
83 | link_t leaf_head; /**< Leaf-level list head. */ |
| 85 | }; |
84 | } btree_t; |
| 86 | 85 | ||
| 87 | extern void btree_init(void); |
86 | extern void btree_init(void); |
| 88 | 87 | ||
| 89 | extern void btree_create(btree_t *t); |
88 | extern void btree_create(btree_t *t); |
| 90 | extern void btree_destroy(btree_t *t); |
89 | extern void btree_destroy(btree_t *t); |