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 16 class BPositionIO; 17 18 19 // ****************** on-disk structures ******************** 20 21 #define BPLUSTREE_NULL -1LL 22 #define BPLUSTREE_FREE -2LL 23 24 struct __attribute__((packed)) 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 42 enum 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 52 struct __attribute((packed)) 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 78 enum bplustree_traversing { 79 BPLUSTREE_FORWARD = 1, 80 BPLUSTREE_BACKWARD = -1, 81 82 BPLUSTREE_BEGIN = 0, 83 BPLUSTREE_END = 1 84 }; 85 86 template<class T> class Stack; 87 class BPlusTree; 88 89 class 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 102 class 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 184 inline status_t BPlusTree::Rewind() 185 { 186 return Goto(BPLUSTREE_BEGIN); 187 } 188 189 inline 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 194 inline 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 199 inline 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 206 inline 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 213 inline 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 220 inline 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 227 inline 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 234 inline 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 241 inline 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 253 inline 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 263 inline uint16 *bplustree_node::KeyLengths() const 264 { 265 return (uint16 *)(((char *)this) + round_up(sizeof(bplustree_node) + all_key_length)); 266 } 267 268 inline off_t *bplustree_node::Values() const 269 { 270 return (off_t *)((char *)KeyLengths() + all_key_count * sizeof(uint16)); 271 } 272 273 inline uint8 *bplustree_node::Keys() const 274 { 275 return (uint8 *)this + sizeof(bplustree_node); 276 } 277 278 inline 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 283 inline uint8 bplustree_node::LinkType(off_t link) 284 { 285 return *(uint64 *)&link >> 62; 286 } 287 288 inline off_t bplustree_node::FragmentOffset(off_t link) 289 { 290 return link & 0x3ffffffffffffc00LL; 291 } 292 293 #endif /* B_PLUS_TREE_H */ 294