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#include <AK/Debug.h>
8#include <AK/Format.h>
9#include <AK/NonnullOwnPtr.h>
10#include <AK/StringBuilder.h>
11#include <LibSQL/BTree.h>
12#include <LibSQL/Serializer.h>
13
14namespace SQL {
15
16DownPointer::DownPointer(TreeNode* owner, u32 pointer)
17 : m_owner(owner)
18 , m_pointer(pointer)
19 , m_node(nullptr)
20{
21}
22
23DownPointer::DownPointer(TreeNode* owner, TreeNode* node)
24 : m_owner(owner)
25 , m_pointer((node) ? node->pointer() : 0)
26 , m_node(adopt_own_if_nonnull(node))
27{
28}
29
30DownPointer::DownPointer(TreeNode* owner, DownPointer& down)
31 : m_owner(owner)
32 , m_pointer(down.m_pointer)
33 , m_node(move(down.m_node))
34{
35}
36
37DownPointer::DownPointer(DownPointer&& other)
38 : m_owner(other.m_owner)
39 , m_pointer(other.pointer())
40 , m_node(other.m_node ? move(other.m_node) : nullptr)
41{
42}
43
44TreeNode* DownPointer::node()
45{
46 if (!m_node)
47 deserialize(m_owner->tree().serializer());
48 return m_node;
49}
50
51void DownPointer::deserialize(Serializer& serializer)
52{
53 if (m_node || !m_pointer)
54 return;
55 serializer.get_block(m_pointer);
56 m_node = serializer.make_and_deserialize<TreeNode>(m_owner->tree(), m_owner, m_pointer);
57}
58
59TreeNode::TreeNode(BTree& tree, u32 pointer)
60 : IndexNode(pointer)
61 , m_tree(tree)
62 , m_up(nullptr)
63 , m_entries()
64 , m_down()
65{
66}
67
68TreeNode::TreeNode(BTree& tree, TreeNode* up, u32 pointer)
69 : IndexNode(pointer)
70 , m_tree(tree)
71 , m_up(up)
72 , m_entries()
73 , m_down()
74{
75 m_down.append(DownPointer(this, nullptr));
76 m_is_leaf = true;
77}
78
79TreeNode::TreeNode(BTree& tree, TreeNode* up, DownPointer& left, u32 pointer)
80 : IndexNode(pointer)
81 , m_tree(tree)
82 , m_up(up)
83 , m_entries()
84 , m_down()
85{
86 if (left.m_node != nullptr)
87 left.m_node->m_up = this;
88 m_down.append(DownPointer(this, left));
89 m_is_leaf = left.pointer() == 0;
90 if (!pointer)
91 set_pointer(m_tree.new_record_pointer());
92}
93
94TreeNode::TreeNode(BTree& tree, TreeNode* up, TreeNode* left, u32 pointer)
95 : IndexNode(pointer)
96 , m_tree(tree)
97 , m_up(up)
98 , m_entries()
99 , m_down()
100{
101 m_down.append(DownPointer(this, left));
102 m_is_leaf = left->pointer() == 0;
103}
104
105void TreeNode::deserialize(Serializer& serializer)
106{
107 auto nodes = serializer.deserialize<u32>();
108 dbgln_if(SQL_DEBUG, "Deserializing node. Size {}", nodes);
109 if (nodes > 0) {
110 for (u32 i = 0; i < nodes; i++) {
111 auto left = serializer.deserialize<u32>();
112 dbgln_if(SQL_DEBUG, "Down[{}] {}", i, left);
113 if (!m_down.is_empty())
114 VERIFY((left == 0) == m_is_leaf);
115 else
116 m_is_leaf = (left == 0);
117 m_entries.append(serializer.deserialize<Key>(m_tree.descriptor()));
118 m_down.empend(this, left);
119 }
120 auto right = serializer.deserialize<u32>();
121 dbgln_if(SQL_DEBUG, "Right {}", right);
122 VERIFY((right == 0) == m_is_leaf);
123 m_down.empend(this, right);
124 }
125}
126
127void TreeNode::serialize(Serializer& serializer) const
128{
129 u32 sz = size();
130 serializer.serialize<u32>(sz);
131 if (sz > 0) {
132 for (auto ix = 0u; ix < size(); ix++) {
133 auto& entry = m_entries[ix];
134 dbgln_if(SQL_DEBUG, "Serializing Left[{}] = {}", ix, m_down[ix].pointer());
135 serializer.serialize<u32>(is_leaf() ? 0u : m_down[ix].pointer());
136 serializer.serialize<Key>(entry);
137 }
138 dbgln_if(SQL_DEBUG, "Serializing Right = {}", m_down[size()].pointer());
139 serializer.serialize<u32>(is_leaf() ? 0u : m_down[size()].pointer());
140 }
141}
142
143size_t TreeNode::length() const
144{
145 if (!size())
146 return 0;
147 size_t len = sizeof(u32);
148 for (auto& key : m_entries) {
149 len += sizeof(u32) + key.length();
150 }
151 return len;
152}
153
154bool TreeNode::insert(Key const& key)
155{
156 dbgln_if(SQL_DEBUG, "[#{}] INSERT({})", pointer(), key.to_deprecated_string());
157 if (!is_leaf())
158 return node_for(key)->insert_in_leaf(key);
159 return insert_in_leaf(key);
160}
161
162bool TreeNode::update_key_pointer(Key const& key)
163{
164 dbgln_if(SQL_DEBUG, "[#{}] UPDATE({}, {})", pointer(), key.to_deprecated_string(), key.pointer());
165 if (!is_leaf())
166 return node_for(key)->update_key_pointer(key);
167
168 for (auto ix = 0u; ix < size(); ix++) {
169 if (key == m_entries[ix]) {
170 dbgln_if(SQL_DEBUG, "[#{}] {} == {}",
171 pointer(), key.to_deprecated_string(), m_entries[ix].to_deprecated_string());
172 if (m_entries[ix].pointer() != key.pointer()) {
173 m_entries[ix].set_pointer(key.pointer());
174 dump_if(SQL_DEBUG, "To WAL");
175 tree().serializer().serialize_and_write<TreeNode>(*this);
176 }
177 return true;
178 }
179 }
180 return false;
181}
182
183bool TreeNode::insert_in_leaf(Key const& key)
184{
185 VERIFY(is_leaf());
186 if (!m_tree.duplicates_allowed()) {
187 for (auto& entry : m_entries) {
188 if (key == entry) {
189 dbgln_if(SQL_DEBUG, "[#{}] duplicate key {}", pointer(), key.to_deprecated_string());
190 return false;
191 }
192 }
193 }
194
195 dbgln_if(SQL_DEBUG, "[#{}] insert_in_leaf({})", pointer(), key.to_deprecated_string());
196 just_insert(key, nullptr);
197 return true;
198}
199
200u32 TreeNode::down_pointer(size_t ix) const
201{
202 return m_down[ix].pointer();
203}
204
205TreeNode* TreeNode::down_node(size_t ix)
206{
207 return m_down[ix].node();
208}
209
210TreeNode* TreeNode::node_for(Key const& key)
211{
212 dump_if(SQL_DEBUG, DeprecatedString::formatted("node_for(Key {})", key.to_deprecated_string()));
213 if (is_leaf())
214 return this;
215 for (size_t ix = 0; ix < size(); ix++) {
216 if (key < m_entries[ix]) {
217 dbgln_if(SQL_DEBUG, "[{}] {} < {} v{}",
218 pointer(), (DeprecatedString)key, (DeprecatedString)m_entries[ix], m_down[ix].pointer());
219 return down_node(ix)->node_for(key);
220 }
221 }
222 dbgln_if(SQL_DEBUG, "[#{}] {} >= {} v{}",
223 pointer(), key.to_deprecated_string(), (DeprecatedString)m_entries[size() - 1], m_down[size()].pointer());
224 return down_node(size())->node_for(key);
225}
226
227Optional<u32> TreeNode::get(Key& key)
228{
229 dump_if(SQL_DEBUG, DeprecatedString::formatted("get({})", key.to_deprecated_string()));
230 for (auto ix = 0u; ix < size(); ix++) {
231 if (key < m_entries[ix]) {
232 if (is_leaf()) {
233 dbgln_if(SQL_DEBUG, "[#{}] {} < {} -> 0",
234 pointer(), key.to_deprecated_string(), (DeprecatedString)m_entries[ix]);
235 return {};
236 } else {
237 dbgln_if(SQL_DEBUG, "[{}] {} < {} ({} -> {})",
238 pointer(), key.to_deprecated_string(), (DeprecatedString)m_entries[ix],
239 ix, m_down[ix].pointer());
240 return down_node(ix)->get(key);
241 }
242 }
243 if (key == m_entries[ix]) {
244 dbgln_if(SQL_DEBUG, "[#{}] {} == {} -> {}",
245 pointer(), key.to_deprecated_string(), (DeprecatedString)m_entries[ix],
246 m_entries[ix].pointer());
247 key.set_pointer(m_entries[ix].pointer());
248 return m_entries[ix].pointer();
249 }
250 }
251 if (m_entries.is_empty()) {
252 dbgln_if(SQL_DEBUG, "[#{}] {} Empty node??", pointer(), key.to_deprecated_string());
253 VERIFY_NOT_REACHED();
254 }
255 if (is_leaf()) {
256 dbgln_if(SQL_DEBUG, "[#{}] {} > {} -> 0",
257 pointer(), key.to_deprecated_string(), (DeprecatedString)m_entries[size() - 1]);
258 return {};
259 }
260 dbgln_if(SQL_DEBUG, "[#{}] {} > {} ({} -> {})",
261 pointer(), key.to_deprecated_string(), (DeprecatedString)m_entries[size() - 1],
262 size(), m_down[size()].pointer());
263 return down_node(size())->get(key);
264}
265
266void TreeNode::just_insert(Key const& key, TreeNode* right)
267{
268 dbgln_if(SQL_DEBUG, "[#{}] just_insert({}, right = {})",
269 pointer(), (DeprecatedString)key, (right) ? right->pointer() : 0);
270 dump_if(SQL_DEBUG, "Before");
271 for (auto ix = 0u; ix < size(); ix++) {
272 if (key < m_entries[ix]) {
273 m_entries.insert(ix, key);
274 VERIFY(is_leaf() == (right == nullptr));
275 m_down.insert(ix + 1, DownPointer(this, right));
276 if (length() > BLOCKSIZE) {
277 split();
278 } else {
279 dump_if(SQL_DEBUG, "To WAL");
280 tree().serializer().serialize_and_write(*this);
281 }
282 return;
283 }
284 }
285 m_entries.append(key);
286 m_down.empend(this, right);
287
288 if (length() > BLOCKSIZE) {
289 split();
290 } else {
291 dump_if(SQL_DEBUG, "To WAL");
292 tree().serializer().serialize_and_write(*this);
293 }
294}
295
296void TreeNode::split()
297{
298 dump_if(SQL_DEBUG, "Splitting node");
299 if (!m_up)
300 // Make new m_up. This is the new root node.
301 m_up = m_tree.new_root();
302
303 // Take the left pointer for the new node:
304 auto median_index = size() / 2;
305 if (!(size() % 2))
306 ++median_index;
307 DownPointer left = m_down.take(median_index);
308
309 // Create the new right node:
310 auto* new_node = new TreeNode(tree(), m_up, left);
311
312 // Move the rightmost keys from this node to the new right node:
313 while (m_entries.size() > median_index) {
314 auto entry = m_entries.take(median_index);
315 auto down = m_down.take(median_index);
316
317 // Reparent to new right node:
318 if (down.m_node != nullptr) {
319 down.m_node->m_up = new_node;
320 }
321 new_node->m_entries.append(entry);
322 new_node->m_down.append(move(down));
323 }
324
325 // Move the median key in the node one level up. Its right node will
326 // be the new node:
327 auto median = m_entries.take_last();
328
329 dump_if(SQL_DEBUG, "Split Left To WAL");
330 tree().serializer().serialize_and_write(*this);
331 new_node->dump_if(SQL_DEBUG, "Split Right to WAL");
332 tree().serializer().serialize_and_write(*new_node);
333
334 m_up->just_insert(median, new_node);
335}
336
337void TreeNode::dump_if(int flag, DeprecatedString&& msg)
338{
339 if (!flag)
340 return;
341 StringBuilder builder;
342 builder.appendff("[#{}] ", pointer());
343 if (!msg.is_empty())
344 builder.appendff("{}", msg);
345 builder.append(": "sv);
346 if (m_up)
347 builder.appendff("[^{}] -> ", m_up->pointer());
348 else
349 builder.append("* -> "sv);
350 for (size_t ix = 0; ix < m_entries.size(); ix++) {
351 if (!is_leaf())
352 builder.appendff("[v{}] ", m_down[ix].pointer());
353 else
354 VERIFY(m_down[ix].pointer() == 0);
355 builder.appendff("'{}' ", (DeprecatedString)m_entries[ix]);
356 }
357 if (!is_leaf()) {
358 builder.appendff("[v{}]", m_down[size()].pointer());
359 } else {
360 VERIFY(m_down[size()].pointer() == 0);
361 }
362 builder.appendff(" (size {}", (int)size());
363 if (is_leaf()) {
364 builder.append(", leaf"sv);
365 }
366 builder.append(')');
367 dbgln(builder.to_deprecated_string());
368}
369
370void TreeNode::list_node(int indent)
371{
372 auto do_indent = [&]() {
373 for (int i = 0; i < indent; ++i) {
374 warn(" ");
375 }
376 };
377 do_indent();
378 warnln("--> #{}", pointer());
379 for (auto ix = 0u; ix < size(); ix++) {
380 if (!is_leaf()) {
381 down_node(ix)->list_node(indent + 2);
382 }
383 do_indent();
384 warnln("{}", m_entries[ix].to_deprecated_string());
385 }
386 if (!is_leaf()) {
387 down_node(size())->list_node(indent + 2);
388 }
389}
390
391}