src/bin/bfs_tools/lib/BPlusTree.h

   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 */