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
102
103
104
105
106
107
108
109
110
111
112
|
/*
* Copyright (c) 2021, Jan de Visser <jan@de-visser.net>
*
* SPDX-License-Identifier: BSD-2-Clause
*/
#include <LibSQL/BTree.h>
#include <LibSQL/Meta.h>
namespace SQL {
BTree::BTree(Serializer& serializer, NonnullRefPtr<TupleDescriptor> const& descriptor, bool unique, u32 pointer)
: Index(serializer, descriptor, unique, pointer)
, m_root(nullptr)
{
}
BTree::BTree(Serializer& serializer, NonnullRefPtr<TupleDescriptor> const& descriptor, u32 pointer)
: BTree(serializer, descriptor, true, pointer)
{
}
BTreeIterator BTree::begin()
{
if (!m_root)
initialize_root();
VERIFY(m_root);
return BTreeIterator(m_root, -1);
}
BTreeIterator BTree::end()
{
return BTreeIterator(nullptr, -1);
}
void BTree::initialize_root()
{
if (pointer()) {
if (serializer().has_block(pointer())) {
serializer().get_block(pointer());
m_root = serializer().make_and_deserialize<TreeNode>(*this, pointer());
} else {
m_root = make<TreeNode>(*this, nullptr, pointer());
}
} else {
set_pointer(new_record_pointer());
m_root = make<TreeNode>(*this, nullptr, pointer());
if (on_new_root)
on_new_root();
}
m_root->dump_if(0, "initialize_root");
}
TreeNode* BTree::new_root()
{
set_pointer(new_record_pointer());
m_root = make<TreeNode>(*this, nullptr, m_root.leak_ptr(), pointer());
serializer().serialize_and_write(*m_root.ptr());
if (on_new_root)
on_new_root();
return m_root;
}
bool BTree::insert(Key const& key)
{
if (!m_root)
initialize_root();
VERIFY(m_root);
return m_root->insert(key);
}
bool BTree::update_key_pointer(Key const& key)
{
if (!m_root)
initialize_root();
VERIFY(m_root);
return m_root->update_key_pointer(key);
}
Optional<u32> BTree::get(Key& key)
{
if (!m_root)
initialize_root();
VERIFY(m_root);
return m_root->get(key);
}
BTreeIterator BTree::find(Key const& key)
{
if (!m_root)
initialize_root();
VERIFY(m_root);
for (auto node = m_root->node_for(key); node; node = node->up()) {
for (auto ix = 0u; ix < node->size(); ix++) {
auto match = (*node)[ix].match(key);
if (match == 0)
return BTreeIterator(node, (int)ix);
else if (match > 0)
return end();
}
}
return end();
}
void BTree::list_tree()
{
if (!m_root)
initialize_root();
m_root->list_node(0);
}
}
|
