jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, Jan de Visser <jan@de-visser.net>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#pragma once
8
9#include <AK/DeprecatedString.h>
10#include <AK/Function.h>
11#include <AK/NonnullRefPtr.h>
12#include <AK/Optional.h>
13#include <AK/RefPtr.h>
14#include <AK/Vector.h>
15#include <LibCore/Object.h>
16#include <LibSQL/Forward.h>
17#include <LibSQL/Heap.h>
18#include <LibSQL/Index.h>
19#include <LibSQL/Key.h>
20
21namespace SQL {
22
23/**
24 * The BTree class models a B-Tree index. It contains a collection of
25 * Key objects organized in TreeNode objects. Keys can be inserted,
26 * located, deleted, and the set can be traversed in sort order. All keys in
27 * a tree have the same underlying structure. A BTree's TreeNodes and
28 * the keys it includes are lazily loaded from the Heap when needed.
29 *
30 * The classes implementing the B-Tree functionality are BTree, TreeNode,
31 * BTreeIterator, and DownPointer (a smart pointer-like helper class).
32 */
33class DownPointer {
34public:
35 explicit DownPointer(TreeNode*, u32 = 0);
36 DownPointer(TreeNode*, TreeNode*);
37 DownPointer(DownPointer&&);
38 DownPointer(TreeNode*, DownPointer&);
39 ~DownPointer() = default;
40 [[nodiscard]] u32 pointer() const { return m_pointer; }
41 TreeNode* node();
42
43private:
44 void deserialize(Serializer&);
45
46 TreeNode* m_owner;
47 u32 m_pointer { 0 };
48 OwnPtr<TreeNode> m_node { nullptr };
49 friend TreeNode;
50};
51
52class TreeNode : public IndexNode {
53public:
54 TreeNode(BTree&, u32 = 0);
55 TreeNode(BTree&, TreeNode*, u32 = 0);
56 TreeNode(BTree&, TreeNode*, TreeNode*, u32 = 0);
57 ~TreeNode() override = default;
58
59 [[nodiscard]] BTree& tree() const { return m_tree; }
60 [[nodiscard]] TreeNode* up() const { return m_up; }
61 [[nodiscard]] size_t size() const { return m_entries.size(); }
62 [[nodiscard]] size_t length() const;
63 [[nodiscard]] Vector<Key> entries() const { return m_entries; }
64 [[nodiscard]] u32 down_pointer(size_t) const;
65 [[nodiscard]] TreeNode* down_node(size_t);
66 [[nodiscard]] bool is_leaf() const { return m_is_leaf; }
67
68 Key const& operator[](size_t index) const { return m_entries[index]; }
69 bool insert(Key const&);
70 bool update_key_pointer(Key const&);
71 TreeNode* node_for(Key const&);
72 Optional<u32> get(Key&);
73 void deserialize(Serializer&);
74 void serialize(Serializer&) const;
75
76private:
77 TreeNode(BTree&, TreeNode*, DownPointer&, u32 = 0);
78 void dump_if(int, DeprecatedString&& = "");
79 bool insert_in_leaf(Key const&);
80 void just_insert(Key const&, TreeNode* = nullptr);
81 void split();
82 void list_node(int);
83
84 BTree& m_tree;
85 TreeNode* m_up;
86 Vector<Key> m_entries;
87 bool m_is_leaf { true };
88 Vector<DownPointer> m_down;
89
90 friend BTree;
91 friend BTreeIterator;
92};
93
94class BTree : public Index {
95 C_OBJECT(BTree);
96
97public:
98 ~BTree() override = default;
99
100 u32 root() const { return (m_root) ? m_root->pointer() : 0; }
101 bool insert(Key const&);
102 bool update_key_pointer(Key const&);
103 Optional<u32> get(Key&);
104 BTreeIterator find(Key const& key);
105 BTreeIterator begin();
106 static BTreeIterator end();
107 void list_tree();
108
109 Function<void(void)> on_new_root;
110
111private:
112 BTree(Serializer&, NonnullRefPtr<TupleDescriptor> const&, bool unique, u32 pointer);
113 BTree(Serializer&, NonnullRefPtr<TupleDescriptor> const&, u32 pointer);
114 void initialize_root();
115 TreeNode* new_root();
116 OwnPtr<TreeNode> m_root { nullptr };
117
118 friend BTreeIterator;
119 friend DownPointer;
120 friend TreeNode;
121};
122
123class BTreeIterator {
124public:
125 [[nodiscard]] bool is_end() const { return m_where == Where::End; }
126 [[nodiscard]] size_t index() const { return m_index; }
127 bool update(Key const&);
128
129 bool operator==(BTreeIterator const& other) const { return cmp(other) == 0; }
130 bool operator!=(BTreeIterator const& other) const { return cmp(other) != 0; }
131 bool operator<(BTreeIterator const& other) const { return cmp(other) < 0; }
132 bool operator>(BTreeIterator const& other) const { return cmp(other) > 0; }
133 bool operator<=(BTreeIterator const& other) const { return cmp(other) <= 0; }
134 bool operator>=(BTreeIterator const& other) const { return cmp(other) >= 0; }
135 bool operator==(Key const& other) const { return cmp(other) == 0; }
136 bool operator!=(Key const& other) const { return cmp(other) != 0; }
137 bool operator<(Key const& other) const { return cmp(other) < 0; }
138 bool operator>(Key const& other) const { return cmp(other) > 0; }
139 bool operator<=(Key const& other) const { return cmp(other) <= 0; }
140 bool operator>=(Key const& other) const { return cmp(other) >= 0; }
141
142 BTreeIterator operator++()
143 {
144 *this = next();
145 return *this;
146 }
147
148 BTreeIterator operator++(int)
149 {
150 *this = next();
151 return *this;
152 }
153
154 BTreeIterator operator--()
155 {
156 *this = previous();
157 return *this;
158 }
159
160 BTreeIterator const operator--(int)
161 {
162 *this = previous();
163 return *this;
164 }
165
166 Key const& operator*() const
167 {
168 VERIFY(!is_end());
169 return (*m_current)[m_index];
170 }
171
172 Key const& operator->() const
173 {
174 VERIFY(!is_end());
175 return (*m_current)[m_index];
176 }
177
178 BTreeIterator& operator=(BTreeIterator const&);
179 BTreeIterator(BTreeIterator const&) = default;
180
181private:
182 BTreeIterator(TreeNode*, int index);
183 static BTreeIterator end() { return BTreeIterator(nullptr, -1); }
184
185 [[nodiscard]] int cmp(BTreeIterator const&) const;
186 [[nodiscard]] int cmp(Key const&) const;
187 [[nodiscard]] BTreeIterator next() const;
188 [[nodiscard]] BTreeIterator previous() const;
189 [[nodiscard]] Key key() const;
190
191 enum class Where {
192 Valid,
193 End
194 };
195
196 Where m_where { Where::Valid };
197 TreeNode* m_current { nullptr };
198 int m_index { -1 };
199
200 friend BTree;
201};
202
203}