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