#ifndef B_PLUS_TREE_H
#define B_PLUS_TREE_H
**
** Copyright 2001 pinc Software. All Rights Reserved.
** Released under the terms of the MIT license.
*/
#include <List.h>
#include <string.h>
#include "Cache.h"
#include "bfs.h"
class BPositionIO;
#define BPLUSTREE_NULL -1LL
#define BPLUSTREE_FREE -2LL
struct __attribute__((packed)) bplustree_header
{
uint32 magic;
uint32 node_size;
uint32 max_number_of_levels;
uint32 data_type;
off_t root_node_pointer;
off_t free_node_pointer;
off_t maximum_size;
inline bool IsValidLink(off_t link);
};
#define BPLUSTREE_MAGIC 0x69f6c2e8
#define BPLUSTREE_NODE_SIZE 1024
#define BPLUSTREE_MAX_KEY_LENGTH 256
#define BPLUSTREE_MIN_KEY_LENGTH 1
enum bplustree_types {
BPLUSTREE_STRING_TYPE = 0,
BPLUSTREE_INT32_TYPE = 1,
BPLUSTREE_UINT32_TYPE = 2,
BPLUSTREE_INT64_TYPE = 3,
BPLUSTREE_UINT64_TYPE = 4,
BPLUSTREE_FLOAT_TYPE = 5,
BPLUSTREE_DOUBLE_TYPE = 6
};
struct __attribute((packed)) bplustree_node {
off_t left_link;
off_t right_link;
off_t overflow_link;
uint16 all_key_count;
uint16 all_key_length;
inline uint16 *KeyLengths() const;
inline off_t *Values() const;
inline uint8 *Keys() const;
inline int32 Used() const;
uint8 *KeyAt(int32 index, uint16 *keyLength) const;
uint8 CountDuplicates(off_t offset, bool isFragment) const;
off_t DuplicateAt(off_t offset, bool isFragment, int8 index) const;
static inline uint8 LinkType(off_t link);
static inline off_t FragmentOffset(off_t link);
};
#define BPLUSTREE_NODE 0
#define BPLUSTREE_DUPLICATE_NODE 2
#define BPLUSTREE_DUPLICATE_FRAGMENT 3
enum bplustree_traversing {
BPLUSTREE_FORWARD = 1,
BPLUSTREE_BACKWARD = -1,
BPLUSTREE_BEGIN = 0,
BPLUSTREE_END = 1
};
template<class T> class Stack;
class BPlusTree;
class NodeCache : public Cache<off_t> {
public:
NodeCache(BPlusTree *);
virtual Cacheable *NewCacheable(off_t offset);
bplustree_node *Get(off_t offset);
protected:
BPlusTree *fTree;
};
class BPlusTree {
public:
BPlusTree(int32 keyType, int32 nodeSize = BPLUSTREE_NODE_SIZE,
bool allowDuplicates = true);
BPlusTree(BPositionIO *stream, bool allowDuplicates = true);
BPlusTree();
~BPlusTree();
status_t SetTo(int32 keyType,int32 nodeSize = BPLUSTREE_NODE_SIZE,bool allowDuplicates = true);
status_t SetTo(BPositionIO *stream,bool allowDuplicates = true);
status_t InitCheck();
status_t Validate(bool verbose = false);
int32 Type() const { return fHeader->data_type; }
status_t Rewind();
status_t Goto(int8 to);
status_t GetNextEntry(void *key,uint16 *keyLength,uint16 maxLength,off_t *value);
status_t GetPreviousEntry(void *key,uint16 *keyLength,uint16 maxLength,off_t *value);
status_t Insert(uint8 *key, uint16 keyLength, off_t value);
status_t Insert(const char *key, off_t value);
status_t Insert(int32 key, off_t value);
status_t Insert(uint32 key, off_t value);
status_t Insert(int64 key, off_t value);
status_t Insert(uint64 key, off_t value);
status_t Insert(float key, off_t value);
status_t Insert(double key, off_t value);
status_t Find(uint8 *key, uint16 keyLength, off_t *value);
status_t WriteTo(BPositionIO *stream);
void SetHoldChanges(bool hold);
private:
struct node_and_key {
off_t nodeOffset;
uint16 keyIndex;
};
void Initialize(int32 nodeSize);
void SetCurrentNode(bplustree_node *node,off_t offset,int8 to = BPLUSTREE_BEGIN);
status_t Traverse(int8 direction,void *key,uint16 *keyLength,uint16 maxLength,off_t *value);
int32 CompareKeys(const void *key1, int keylength1, const void *key2, int keylength2);
status_t FindKey(bplustree_node *node, uint8 *key, uint16 keyLength, uint16 *index = NULL, off_t *next = NULL);
status_t SeekDown(Stack<node_and_key> &stack, uint8 *key, uint16 keyLength);
status_t SplitNode(bplustree_node *node, off_t nodeOffset, uint16 *_keyIndex, uint8 *key, uint16 *_keyLength, off_t *_value);
void InsertKey(bplustree_node *node, uint8 *key, uint16 keyLength, off_t value, uint16 index);
status_t InsertDuplicate(bplustree_node *node,uint16 index);
bool CheckNode(bplustree_node *node);
private:
friend class NodeCache;
bplustree_node *Node(off_t nodeoffset,bool check = true);
private:
BPositionIO *fStream;
bplustree_header *fHeader;
int32 fNodeSize;
bool fAllowDuplicates;
status_t fStatus;
NodeCache fCache;
off_t fCurrentNodeOffset;
int32 fCurrentKey;
off_t fDuplicateNode;
uint16 fDuplicate, fNumDuplicates;
bool fIsFragment;
};
inline status_t BPlusTree::Rewind()
{
return Goto(BPLUSTREE_BEGIN);
}
inline status_t BPlusTree::GetNextEntry(void *key,uint16 *keyLength,uint16 maxLength,off_t *value)
{
return Traverse(BPLUSTREE_FORWARD,key,keyLength,maxLength,value);
}
inline status_t BPlusTree::GetPreviousEntry(void *key,uint16 *keyLength,uint16 maxLength,off_t *value)
{
return Traverse(BPLUSTREE_BACKWARD,key,keyLength,maxLength,value);
}
inline status_t BPlusTree::Insert(const char *key,off_t value)
{
if (fHeader->data_type != BPLUSTREE_STRING_TYPE)
return B_BAD_TYPE;
return Insert((uint8 *)key, strlen(key), value);
}
inline status_t BPlusTree::Insert(int32 key, off_t value)
{
if (fHeader->data_type != BPLUSTREE_INT32_TYPE)
return B_BAD_TYPE;
return Insert((uint8 *)&key, sizeof(key), value);
}
inline status_t BPlusTree::Insert(uint32 key, off_t value)
{
if (fHeader->data_type != BPLUSTREE_UINT32_TYPE)
return B_BAD_TYPE;
return Insert((uint8 *)&key, sizeof(key), value);
}
inline status_t BPlusTree::Insert(int64 key, off_t value)
{
if (fHeader->data_type != BPLUSTREE_INT64_TYPE)
return B_BAD_TYPE;
return Insert((uint8 *)&key, sizeof(key), value);
}
inline status_t BPlusTree::Insert(uint64 key, off_t value)
{
if (fHeader->data_type != BPLUSTREE_UINT64_TYPE)
return B_BAD_TYPE;
return Insert((uint8 *)&key, sizeof(key), value);
}
inline status_t BPlusTree::Insert(float key, off_t value)
{
if (fHeader->data_type != BPLUSTREE_FLOAT_TYPE)
return B_BAD_TYPE;
return Insert((uint8 *)&key, sizeof(key), value);
}
inline status_t BPlusTree::Insert(double key, off_t value)
{
if (fHeader->data_type != BPLUSTREE_DOUBLE_TYPE)
return B_BAD_TYPE;
return Insert((uint8 *)&key, sizeof(key), value);
}
inline bool bplustree_header::IsValidLink(off_t link)
{
return link == BPLUSTREE_NULL || (link > 0 && link <= maximum_size - node_size);
}
inline uint16 *bplustree_node::KeyLengths() const
{
return (uint16 *)(((char *)this) + round_up(sizeof(bplustree_node) + all_key_length));
}
inline off_t *bplustree_node::Values() const
{
return (off_t *)((char *)KeyLengths() + all_key_count * sizeof(uint16));
}
inline uint8 *bplustree_node::Keys() const
{
return (uint8 *)this + sizeof(bplustree_node);
}
inline int32 bplustree_node::Used() const
{
return round_up(sizeof(bplustree_node) + all_key_length) + all_key_count * (sizeof(uint16) + sizeof(off_t));
}
inline uint8 bplustree_node::LinkType(off_t link)
{
return *(uint64 *)&link >> 62;
}
inline off_t bplustree_node::FragmentOffset(off_t link)
{
return link & 0x3ffffffffffffc00LL;
}
#endif
