-
Notifications
You must be signed in to change notification settings - Fork 0
/
BPlusTree.hpp
101 lines (90 loc) · 2.57 KB
/
BPlusTree.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#ifndef BPLUS_HPP_
#define BPLUS_HPP_
#include <stdlib.h>
#include <string>
#include <vector>
#ifndef CACHELINESIZE
#define CACHELINESIZE 64
#endif
#ifdef ALIGNED_MEM
#define ALLOC_MEM(type, num) \
(type*)aligned_alloc(CACHELINESIZE, sizeof(type) * num)
#define ALLOC_OBJ(objInstance) new (1, CACHELINESIZE) objInstance
#else
#define ALLOC_MEM(type, num) (type*)malloc(sizeof(type) * num)
#define ALLOC_OBJ(objInstance) new objInstance
#endif
enum class SearchCriteria { GT, GTE, LT, LTE };
enum class LowerBound { GT, GTE };
enum class UpperBound { LT, LTE };
struct NodeFlags {
enum : std::uint8_t {
isRoot = 1 << 1,
isLeaf = 1 << 2,
};
};
template <int degree>
class BPlusTree;
template <int degree>
class Node {
int* keys;
Node<degree>** children;
int numKeys = 0;
uint8_t flags = 0;
Node<degree>* next = nullptr;
Node<degree>* prev = nullptr;
Node() {
keys = ALLOC_MEM(int, degree);
children = ALLOC_MEM(Node<degree>*, degree + 1);
}
Node(uint8_t flags) {
keys = ALLOC_MEM(int, degree);
children = ALLOC_MEM(Node<degree>*, degree + 1);
this->flags |= flags;
}
void killSelf() {
free(keys);
free(children);
}
friend BPlusTree<degree>;
};
template <int degree>
class BPlusTree {
Node<degree>* root;
int height = 0;
public:
BPlusTree();
std::string inorderString() const;
// TODO: inorderRecords (ASC, DESC)
void clear();
int getHeight() const;
std::string getRoot() const;
// TODO: ASC o DESC
std::vector<void*> range(SearchCriteria criteria, int bound);
// TODO: ASC o DESC
std::vector<void*> range(LowerBound lowerSearch,
int lowerBound,
UpperBound upperSearch,
int upperBound);
void* search(int k) const;
void insert(int k, void* record);
~BPlusTree() noexcept;
private:
std::vector<void*> rangeSearchHelper(Node<degree>* node,
int bound,
SearchCriteria criteria);
std::vector<void*> rangeSearchHelper(Node<degree>* node,
LowerBound lowerSearch,
int lowerBound,
UpperBound upperSearch,
int upperBound);
void insert(Node<degree>* parent,
Node<degree>* node,
int k,
void* record,
int parentChildIndex);
void* search(Node<degree>* node, int k) const;
void inorder(std::string& str) const;
void clear(Node<degree>* node);
};
#endif