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
17class BPositionIO;
18
19
20// ****************** on-disk structures ********************
21
22#define BPLUSTREE_NULL			-1LL
23#define BPLUSTREE_FREE			-2LL
24
25struct __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
43enum 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
53struct __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
79enum bplustree_traversing {
80	BPLUSTREE_FORWARD = 1,
81	BPLUSTREE_BACKWARD = -1,
82
83	BPLUSTREE_BEGIN = 0,
84	BPLUSTREE_END = 1
85};
86
87template<class T> class Stack;
88class BPlusTree;
89
90class 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
103class 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
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
185inline status_t BPlusTree::Rewind()
186{
187	return Goto(BPLUSTREE_BEGIN);
188}
189
190inline 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
195inline 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
200inline 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
207inline 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
214inline 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
221inline 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
228inline 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
235inline 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
242inline 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
254inline 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
264inline uint16 *bplustree_node::KeyLengths() const
265{
266	return (uint16 *)(((char *)this) + round_up(sizeof(bplustree_node) + all_key_length));
267}
268
269inline off_t *bplustree_node::Values() const
270{
271	return (off_t *)((char *)KeyLengths() + all_key_count * sizeof(uint16));
272}
273
274inline uint8 *bplustree_node::Keys() const
275{
276	return (uint8 *)this + sizeof(bplustree_node);
277}
278
279inline 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
284inline uint8 bplustree_node::LinkType(off_t link)
285{
286	return *(uint64 *)&link >> 62;
287}
288
289inline off_t bplustree_node::FragmentOffset(off_t link)
290{
291	return link & 0x3ffffffffffffc00LL;
292}
293
294#endif	/* B_PLUS_TREE_H */
295