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
9namespace SQL {
10
11BTreeIterator::BTreeIterator(TreeNode* node, int index)
12 : m_current(node)
13 , m_index(index)
14{
15 if (!node) {
16 m_where = Where::End;
17 } else {
18 if (index < 0) {
19 while (!node->is_leaf() && (node->size() != 0)) {
20 node = node->down_node(0);
21 }
22 if (node->size() == 0) {
23 m_where = Where::End;
24 m_current = nullptr;
25 m_index = -1;
26 } else {
27 m_where = Where::Valid;
28 m_current = node;
29 m_index = 0;
30 }
31 } else {
32 VERIFY(m_index < (int)m_current->size());
33 }
34 }
35}
36
37int BTreeIterator::cmp(BTreeIterator const& other) const
38{
39 if (is_end())
40 return (other.is_end()) ? 0 : 1;
41 if (other.is_end())
42 return -1;
43 VERIFY(&other.m_current->tree() == &m_current->tree());
44 VERIFY((m_current->size() > 0) && (other.m_current->size() > 0));
45 if (&m_current != &other.m_current)
46 return (*m_current)[m_current->size() - 1].compare((*(other.m_current))[0]);
47 return (*m_current)[m_index].compare((*(other.m_current))[other.m_index]);
48}
49
50int BTreeIterator::cmp(Key const& other) const
51{
52 if (is_end())
53 return 1;
54 if (other.is_null())
55 return -1;
56 return key().compare(other);
57}
58
59BTreeIterator BTreeIterator::next() const
60{
61 if (is_end())
62 return end();
63
64 auto ix = m_index;
65 auto node = m_current;
66 if (ix < (int)(node->size() - 1)) {
67 if (node->is_leaf()) {
68 // We're in the middle of a leaf node. Next entry is
69 // is the next entry of the node:
70 return BTreeIterator(node, ix + 1);
71 } else {
72 /*
73 * We're in the middle of a non-leaf node. The iterator's
74 * next value is all the way down to the right, first entry.
75 *
76 * |
77 * +--+--+--+--+
78 * | |##| | |
79 * +--+--+--+--+
80 * / | | | \
81 * |
82 * +--+--+--+--+
83 * | | | | |
84 * +--+--+--+--+
85 * /
86 * +--+--+--+--+
87 * |++| | | |
88 * +--+--+--+--+
89 */
90 ix++;
91 while (!node->is_leaf()) {
92 node = node->down_node(ix);
93 ix = 0;
94 }
95 }
96 VERIFY(node->is_leaf() && (ix < (int)node->size()));
97 return BTreeIterator(node, ix);
98 }
99
100 if (node->is_leaf()) {
101 // We currently at the last entry of a leaf node. We need to check
102 // one or more levels up until we end up in the "middle" of a node.
103 // If one level up we're still at the end of the node, we need
104 // to keep going up until we hit the root node. If we're at the
105 // end of the root node, we reached the end of the btree.
106 for (auto up = node->up(); up; up = node->up()) {
107 for (size_t i = 0; i < up->size(); i++) {
108 // One level up, try to find the entry with the current
109 // node's pointer as the left pointer:
110 if (up->down_pointer(i) == node->pointer())
111 // Found it. This is the iterator's next value:
112 return BTreeIterator(up, (int)i);
113 }
114 // We didn't find the m_current's pointer as a left node. So
115 // it must be the right node all the way at the end and we need
116 // to go one more level up:
117 node = up;
118 }
119 // We reached the root node and we're still at the end of the node.
120 // That means we're at the end of the btree.
121 return end();
122 }
123
124 // If we're at the end of a non-leaf node, we need to follow the
125 // right pointer down until we find a leaf:
126 TreeNode* down;
127 for (down = node->down_node(node->size()); !down->is_leaf(); down = down->down_node(0))
128 ;
129 return BTreeIterator(down, 0);
130}
131
132// FIXME Reverse iterating doesn't quite work; we don't recognize the
133// end (which is really the beginning) of the tree.
134BTreeIterator BTreeIterator::previous() const
135{
136 if (is_end()) {
137 return end();
138 }
139
140 auto node = m_current;
141 auto ix = m_index;
142 if (ix > 0) {
143 if (node->is_leaf()) {
144 // We're in the middle of a leaf node. Previous entry is
145 // is the previous entry of the node:
146 return BTreeIterator(node, ix - 1);
147 } else {
148 /*
149 * We're in the middle of a non-leaf node. The iterator's
150 * previous value is all the way down to the left, last entry.
151 *
152 * |
153 * +--+--+--+--+
154 * | | |##| |
155 * +--+--+--+--+
156 * / | | | \
157 * |
158 * +--+--+--+--+
159 * | | | | |
160 * +--+--+--+--+
161 * \
162 * +--+--+--+--+
163 * | | | |++|
164 * +--+--+--+--+
165 */
166 while (!node->is_leaf()) {
167 node = node->down_node(ix);
168 ix = (int)node->size();
169 }
170 }
171 VERIFY(node->is_leaf() && (ix <= (int)node->size()));
172 return BTreeIterator(node, ix);
173 }
174
175 if (node->is_leaf()) {
176 // We currently at the first entry of a leaf node. We need to check one
177 // or more levels up until we end up in the "middle" of a node.
178 // If one level up we're still at the start of the node, we need
179 // to keep going up until we hit the root node. If we're at the
180 // start of the root node, we reached the start of the btree.
181 auto stash_current = node;
182 for (auto up = node->up(); up; up = node->up()) {
183 for (size_t i = up->size(); i > 0; i--) {
184 // One level up, try to find the entry with the current
185 // node's pointer as the right pointer:
186 if (up->down_pointer(i) == node->pointer()) {
187 // Found it. This is the iterator's next value:
188 node = up;
189 ix = (int)i - 1;
190 return BTreeIterator(node, ix);
191 }
192 }
193 // We didn't find the m_current's pointer as a right node. So
194 // it must be the left node all the way at the start and we need
195 // to go one more level up:
196 node = up;
197 }
198 // We reached the root node and we're still at the start of the node.
199 // That means we're at the start of the btree.
200 return BTreeIterator(stash_current, 0);
201 }
202
203 // If we're at the start of a non-leaf node, we need to follow the
204 // left pointer down until we find a leaf:
205 TreeNode* down = node->down_node(0);
206 while (!down->is_leaf())
207 down = down->down_node(down->size());
208 return BTreeIterator(down, down->size() - 1);
209}
210
211Key BTreeIterator::key() const
212{
213 if (is_end())
214 return {};
215 return (*m_current)[m_index];
216}
217
218bool BTreeIterator::update(Key const& new_value)
219{
220 if (is_end())
221 return false;
222 if ((cmp(new_value) == 0) && (key().pointer() == new_value.pointer()))
223 return true;
224 auto previous_iter = previous();
225 auto next_iter = next();
226 if (!m_current->tree().duplicates_allowed() && ((previous_iter == new_value) || (next_iter == new_value))) {
227 return false;
228 }
229 if ((previous_iter > new_value) || (next_iter < new_value))
230 return false;
231
232 // We are friend of BTree and TreeNode. Don't know how I feel about that.
233 m_current->m_entries[m_index] = new_value;
234 m_current->tree().serializer().serialize_and_write(*m_current);
235 return true;
236}
237
238BTreeIterator& BTreeIterator::operator=(BTreeIterator const& other)
239{
240 if (&other != this) {
241 m_current = other.m_current;
242 m_index = other.m_index;
243 m_where = other.m_where;
244 }
245 return *this;
246}
247
248}