This source file includes following definitions.
- key_ptr
- value_base
- value_ptr
- value64
1
2
3
4
5
6
7 #ifndef DM_BTREE_INTERNAL_H
8 #define DM_BTREE_INTERNAL_H
9
10 #include "dm-btree.h"
11
12
13
14
15
16
17
18
19 enum node_flags {
20 INTERNAL_NODE = 1,
21 LEAF_NODE = 1 << 1
22 };
23
24
25
26
27
28 struct node_header {
29 __le32 csum;
30 __le32 flags;
31 __le64 blocknr;
32
33 __le32 nr_entries;
34 __le32 max_entries;
35 __le32 value_size;
36 __le32 padding;
37 } __packed;
38
39 struct btree_node {
40 struct node_header header;
41 __le64 keys[0];
42 } __packed;
43
44
45
46
47
48 int bn_read_lock(struct dm_btree_info *info, dm_block_t b,
49 struct dm_block **result);
50
51 void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
52 struct dm_btree_value_type *vt);
53
54 int new_block(struct dm_btree_info *info, struct dm_block **result);
55 void unlock_block(struct dm_btree_info *info, struct dm_block *b);
56
57
58
59
60
61
62
63 struct ro_spine {
64 struct dm_btree_info *info;
65
66 int count;
67 struct dm_block *nodes[2];
68 };
69
70 void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
71 int exit_ro_spine(struct ro_spine *s);
72 int ro_step(struct ro_spine *s, dm_block_t new_child);
73 void ro_pop(struct ro_spine *s);
74 struct btree_node *ro_node(struct ro_spine *s);
75
76 struct shadow_spine {
77 struct dm_btree_info *info;
78
79 int count;
80 struct dm_block *nodes[2];
81
82 dm_block_t root;
83 };
84
85 void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
86 int exit_shadow_spine(struct shadow_spine *s);
87
88 int shadow_step(struct shadow_spine *s, dm_block_t b,
89 struct dm_btree_value_type *vt);
90
91
92
93
94 struct dm_block *shadow_current(struct shadow_spine *s);
95
96
97
98
99 struct dm_block *shadow_parent(struct shadow_spine *s);
100
101 int shadow_has_parent(struct shadow_spine *s);
102
103 int shadow_root(struct shadow_spine *s);
104
105
106
107
108 static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
109 {
110 return n->keys + index;
111 }
112
113 static inline void *value_base(struct btree_node *n)
114 {
115 return &n->keys[le32_to_cpu(n->header.max_entries)];
116 }
117
118 static inline void *value_ptr(struct btree_node *n, uint32_t index)
119 {
120 uint32_t value_size = le32_to_cpu(n->header.value_size);
121 return value_base(n) + (value_size * index);
122 }
123
124
125
126
127 static inline uint64_t value64(struct btree_node *n, uint32_t index)
128 {
129 __le64 *values_le = value_base(n);
130
131 return le64_to_cpu(values_le[index]);
132 }
133
134
135
136
137 int lower_bound(struct btree_node *n, uint64_t key);
138
139 extern struct dm_block_validator btree_node_validator;
140
141
142
143
144 extern void init_le64_type(struct dm_transaction_manager *tm,
145 struct dm_btree_value_type *vt);
146
147 #endif