1 #ifndef B_PLUS_TREE_H
2 #define B_PLUS_TREE_H
3 /* BPlusTree - BFS B+Tree implementation
4 **
5 ** Copyright 2001 pinc Software. All Rights Reserved.
6 ** Released under the terms of the MIT license.
7 */
8
9 #include <List.h>
10
11 #include <string.h>
12
13 #include "Cache.h"
14 #include "bfs.h"
15
16
17 class BPositionIO;
18
19
20 // ****************** on-disk structures ********************
21
22 #define BPLUSTREE_NULL -1LL
23 #define BPLUSTREE_FREE -2LL
24
25 struct __attribute__((packed)) bplustree_header
26 {
27 uint32 magic;
28 uint32 node_size;
29 uint32 max_number_of_levels;
30 uint32 data_type;
31 off_t root_node_pointer;
32 off_t free_node_pointer;
33 off_t maximum_size;
34
35 inline bool IsValidLink(off_t link);
36 };
37
38 #define BPLUSTREE_MAGIC 0x69f6c2e8
39 #define BPLUSTREE_NODE_SIZE 1024
40 #define BPLUSTREE_MAX_KEY_LENGTH 256
41 #define BPLUSTREE_MIN_KEY_LENGTH 1
42
43 enum bplustree_types {
44 BPLUSTREE_STRING_TYPE = 0,
45 BPLUSTREE_INT32_TYPE = 1,
46 BPLUSTREE_UINT32_TYPE = 2,
47 BPLUSTREE_INT64_TYPE = 3,
48 BPLUSTREE_UINT64_TYPE = 4,
49 BPLUSTREE_FLOAT_TYPE = 5,
50 BPLUSTREE_DOUBLE_TYPE = 6
51 };
52
53 struct __attribute((packed)) bplustree_node {
54 off_t left_link;
55 off_t right_link;
56 off_t overflow_link;
57 uint16 all_key_count;
58 uint16 all_key_length;
59
60 inline uint16 *KeyLengths() const;
61 inline off_t *Values() const;
62 inline uint8 *Keys() const;
63 inline int32 Used() const;
64 uint8 *KeyAt(int32 index, uint16 *keyLength) const;
65
66 uint8 CountDuplicates(off_t offset, bool isFragment) const;
67 off_t DuplicateAt(off_t offset, bool isFragment, int8 index) const;
68
69 static inline uint8 LinkType(off_t link);
70 static inline off_t FragmentOffset(off_t link);
71 };
72
73 #define BPLUSTREE_NODE 0
74 #define BPLUSTREE_DUPLICATE_NODE 2
75 #define BPLUSTREE_DUPLICATE_FRAGMENT 3
76
77 // **************************************
78
79 enum bplustree_traversing {
80 BPLUSTREE_FORWARD = 1,
81 BPLUSTREE_BACKWARD = -1,
82
83 BPLUSTREE_BEGIN = 0,
84 BPLUSTREE_END = 1
85 };
86
87 template<class T> class Stack;
88 class BPlusTree;
89
90 class NodeCache : public Cache<off_t> {
91 public:
92 NodeCache(BPlusTree *);
93
94 virtual Cacheable *NewCacheable(off_t offset);
95 bplustree_node *Get(off_t offset);
96 // void SetOffset(bplustree_node *, off_t offset);
97
98 protected:
99 BPlusTree *fTree;
100 };
101
102
103 class BPlusTree {
104 public:
105 BPlusTree(int32 keyType, int32 nodeSize = BPLUSTREE_NODE_SIZE,
106 bool allowDuplicates = true);
107 BPlusTree(BPositionIO *stream, bool allowDuplicates = true);
108 BPlusTree();
109 ~BPlusTree();
110
111 status_t SetTo(int32 keyType,int32 nodeSize = BPLUSTREE_NODE_SIZE,bool allowDuplicates = true);
112 status_t SetTo(BPositionIO *stream,bool allowDuplicates = true);
113
114 status_t InitCheck();
115 status_t Validate(bool verbose = false);
116
Type()117 int32 Type() const { return fHeader->data_type; }
118
119 status_t Rewind();
120 status_t Goto(int8 to);
121 status_t GetNextEntry(void *key,uint16 *keyLength,uint16 maxLength,off_t *value);
122 status_t GetPreviousEntry(void *key,uint16 *keyLength,uint16 maxLength,off_t *value);
123
124 status_t Insert(uint8 *key, uint16 keyLength, off_t value);
125
126 status_t Insert(const char *key, off_t value);
127 status_t Insert(int32 key, off_t value);
128 status_t Insert(uint32 key, off_t value);
129 status_t Insert(int64 key, off_t value);
130 status_t Insert(uint64 key, off_t value);
131 status_t Insert(float key, off_t value);
132 status_t Insert(double key, off_t value);
133
134 status_t Find(uint8 *key, uint16 keyLength, off_t *value);
135
136 status_t WriteTo(BPositionIO *stream);
137
138 void SetHoldChanges(bool hold);
139
140 private:
141 // needed for searching
142 struct node_and_key {
143 off_t nodeOffset;
144 uint16 keyIndex;
145 };
146
147 void Initialize(int32 nodeSize);
148
149 void SetCurrentNode(bplustree_node *node,off_t offset,int8 to = BPLUSTREE_BEGIN);
150 status_t Traverse(int8 direction,void *key,uint16 *keyLength,uint16 maxLength,off_t *value);
151
152 int32 CompareKeys(const void *key1, int keylength1, const void *key2, int keylength2);
153 status_t FindKey(bplustree_node *node, uint8 *key, uint16 keyLength, uint16 *index = NULL, off_t *next = NULL);
154 status_t SeekDown(Stack<node_and_key> &stack, uint8 *key, uint16 keyLength);
155
156 status_t SplitNode(bplustree_node *node, off_t nodeOffset, uint16 *_keyIndex, uint8 *key, uint16 *_keyLength, off_t *_value);
157
158 void InsertKey(bplustree_node *node, uint8 *key, uint16 keyLength, off_t value, uint16 index);
159 status_t InsertDuplicate(bplustree_node *node,uint16 index);
160
161 bool CheckNode(bplustree_node *node);
162
163 private:
164 friend class NodeCache;
165 bplustree_node *Node(off_t nodeoffset,bool check = true);
166
167 private:
168 BPositionIO *fStream;
169 bplustree_header *fHeader;
170 int32 fNodeSize;
171 bool fAllowDuplicates;
172 status_t fStatus;
173
174 NodeCache fCache;
175
176 off_t fCurrentNodeOffset; // traverse position
177 int32 fCurrentKey;
178 off_t fDuplicateNode;
179 uint16 fDuplicate, fNumDuplicates;
180 bool fIsFragment;
181 };
182
183 // inline functions
184
Rewind()185 inline status_t BPlusTree::Rewind()
186 {
187 return Goto(BPLUSTREE_BEGIN);
188 }
189
GetNextEntry(void * key,uint16 * keyLength,uint16 maxLength,off_t * value)190 inline status_t BPlusTree::GetNextEntry(void *key,uint16 *keyLength,uint16 maxLength,off_t *value)
191 {
192 return Traverse(BPLUSTREE_FORWARD,key,keyLength,maxLength,value);
193 }
194
GetPreviousEntry(void * key,uint16 * keyLength,uint16 maxLength,off_t * value)195 inline status_t BPlusTree::GetPreviousEntry(void *key,uint16 *keyLength,uint16 maxLength,off_t *value)
196 {
197 return Traverse(BPLUSTREE_BACKWARD,key,keyLength,maxLength,value);
198 }
199
Insert(const char * key,off_t value)200 inline status_t BPlusTree::Insert(const char *key,off_t value)
201 {
202 if (fHeader->data_type != BPLUSTREE_STRING_TYPE)
203 return B_BAD_TYPE;
204 return Insert((uint8 *)key, strlen(key), value);
205 }
206
Insert(int32 key,off_t value)207 inline status_t BPlusTree::Insert(int32 key, off_t value)
208 {
209 if (fHeader->data_type != BPLUSTREE_INT32_TYPE)
210 return B_BAD_TYPE;
211 return Insert((uint8 *)&key, sizeof(key), value);
212 }
213
Insert(uint32 key,off_t value)214 inline status_t BPlusTree::Insert(uint32 key, off_t value)
215 {
216 if (fHeader->data_type != BPLUSTREE_UINT32_TYPE)
217 return B_BAD_TYPE;
218 return Insert((uint8 *)&key, sizeof(key), value);
219 }
220
Insert(int64 key,off_t value)221 inline status_t BPlusTree::Insert(int64 key, off_t value)
222 {
223 if (fHeader->data_type != BPLUSTREE_INT64_TYPE)
224 return B_BAD_TYPE;
225 return Insert((uint8 *)&key, sizeof(key), value);
226 }
227
Insert(uint64 key,off_t value)228 inline status_t BPlusTree::Insert(uint64 key, off_t value)
229 {
230 if (fHeader->data_type != BPLUSTREE_UINT64_TYPE)
231 return B_BAD_TYPE;
232 return Insert((uint8 *)&key, sizeof(key), value);
233 }
234
Insert(float key,off_t value)235 inline status_t BPlusTree::Insert(float key, off_t value)
236 {
237 if (fHeader->data_type != BPLUSTREE_FLOAT_TYPE)
238 return B_BAD_TYPE;
239 return Insert((uint8 *)&key, sizeof(key), value);
240 }
241
Insert(double key,off_t value)242 inline status_t BPlusTree::Insert(double key, off_t value)
243 {
244 if (fHeader->data_type != BPLUSTREE_DOUBLE_TYPE)
245 return B_BAD_TYPE;
246 return Insert((uint8 *)&key, sizeof(key), value);
247 }
248
249
250 /************************ bplustree_header inline functions ************************/
251 // #pragma mark -
252
253
IsValidLink(off_t link)254 inline bool bplustree_header::IsValidLink(off_t link)
255 {
256 return link == BPLUSTREE_NULL || (link > 0 && link <= maximum_size - node_size);
257 }
258
259
260 /************************ bplustree_node inline functions ************************/
261 // #pragma mark -
262
263
KeyLengths()264 inline uint16 *bplustree_node::KeyLengths() const
265 {
266 return (uint16 *)(((char *)this) + round_up(sizeof(bplustree_node) + all_key_length));
267 }
268
Values()269 inline off_t *bplustree_node::Values() const
270 {
271 return (off_t *)((char *)KeyLengths() + all_key_count * sizeof(uint16));
272 }
273
Keys()274 inline uint8 *bplustree_node::Keys() const
275 {
276 return (uint8 *)this + sizeof(bplustree_node);
277 }
278
Used()279 inline int32 bplustree_node::Used() const
280 {
281 return round_up(sizeof(bplustree_node) + all_key_length) + all_key_count * (sizeof(uint16) + sizeof(off_t));
282 }
283
LinkType(off_t link)284 inline uint8 bplustree_node::LinkType(off_t link)
285 {
286 return *(uint64 *)&link >> 62;
287 }
288
FragmentOffset(off_t link)289 inline off_t bplustree_node::FragmentOffset(off_t link)
290 {
291 return link & 0x3ffffffffffffc00LL;
292 }
293
294 #endif /* B_PLUS_TREE_H */
295