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