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 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 185 inline status_t BPlusTree::Rewind() 186 { 187 return Goto(BPLUSTREE_BEGIN); 188 } 189 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 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 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 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 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 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 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 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 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 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 264 inline uint16 *bplustree_node::KeyLengths() const 265 { 266 return (uint16 *)(((char *)this) + round_up(sizeof(bplustree_node) + all_key_length)); 267 } 268 269 inline off_t *bplustree_node::Values() const 270 { 271 return (off_t *)((char *)KeyLengths() + all_key_count * sizeof(uint16)); 272 } 273 274 inline uint8 *bplustree_node::Keys() const 275 { 276 return (uint8 *)this + sizeof(bplustree_node); 277 } 278 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 284 inline uint8 bplustree_node::LinkType(off_t link) 285 { 286 return *(uint64 *)&link >> 62; 287 } 288 289 inline off_t bplustree_node::FragmentOffset(off_t link) 290 { 291 return link & 0x3ffffffffffffc00LL; 292 } 293 294 #endif /* B_PLUS_TREE_H */ 295