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 <LibSQL/BTree.h>
8#include <LibSQL/Meta.h>
9
10namespace SQL {
11
12BTree::BTree(Serializer& serializer, NonnullRefPtr<TupleDescriptor> const& descriptor, bool unique, u32 pointer)
13 : Index(serializer, descriptor, unique, pointer)
14 , m_root(nullptr)
15{
16}
17
18BTree::BTree(Serializer& serializer, NonnullRefPtr<TupleDescriptor> const& descriptor, u32 pointer)
19 : BTree(serializer, descriptor, true, pointer)
20{
21}
22
23BTreeIterator BTree::begin()
24{
25 if (!m_root)
26 initialize_root();
27 VERIFY(m_root);
28 return BTreeIterator(m_root, -1);
29}
30
31BTreeIterator BTree::end()
32{
33 return BTreeIterator(nullptr, -1);
34}
35
36void BTree::initialize_root()
37{
38 if (pointer()) {
39 if (serializer().has_block(pointer())) {
40 serializer().get_block(pointer());
41 m_root = serializer().make_and_deserialize<TreeNode>(*this, pointer());
42 } else {
43 m_root = make<TreeNode>(*this, nullptr, pointer());
44 }
45 } else {
46 set_pointer(new_record_pointer());
47 m_root = make<TreeNode>(*this, nullptr, pointer());
48 if (on_new_root)
49 on_new_root();
50 }
51 m_root->dump_if(0, "initialize_root");
52}
53
54TreeNode* BTree::new_root()
55{
56 set_pointer(new_record_pointer());
57 m_root = make<TreeNode>(*this, nullptr, m_root.leak_ptr(), pointer());
58 serializer().serialize_and_write(*m_root.ptr());
59 if (on_new_root)
60 on_new_root();
61 return m_root;
62}
63
64bool BTree::insert(Key const& key)
65{
66 if (!m_root)
67 initialize_root();
68 VERIFY(m_root);
69 return m_root->insert(key);
70}
71
72bool BTree::update_key_pointer(Key const& key)
73{
74 if (!m_root)
75 initialize_root();
76 VERIFY(m_root);
77 return m_root->update_key_pointer(key);
78}
79
80Optional<u32> BTree::get(Key& key)
81{
82 if (!m_root)
83 initialize_root();
84 VERIFY(m_root);
85 return m_root->get(key);
86}
87
88BTreeIterator BTree::find(Key const& key)
89{
90 if (!m_root)
91 initialize_root();
92 VERIFY(m_root);
93 for (auto node = m_root->node_for(key); node; node = node->up()) {
94 for (auto ix = 0u; ix < node->size(); ix++) {
95 auto match = (*node)[ix].match(key);
96 if (match == 0)
97 return BTreeIterator(node, (int)ix);
98 else if (match > 0)
99 return end();
100 }
101 }
102 return end();
103}
104
105void BTree::list_tree()
106{
107 if (!m_root)
108 initialize_root();
109 m_root->list_node(0);
110}
111
112}