1#include "duckdb/execution/index/art/node16.hpp"
2
3#include "duckdb/execution/index/art/art.hpp"
4#include "duckdb/execution/index/art/node.hpp"
5#include "duckdb/execution/index/art/node4.hpp"
6#include "duckdb/execution/index/art/node48.hpp"
7#include "duckdb/storage/meta_block_reader.hpp"
8#include "duckdb/storage/meta_block_writer.hpp"
9
10namespace duckdb {
11
12Node16 &Node16::New(ART &art, Node &node) {
13
14 node.SetPtr(Node::GetAllocator(art, type: NType::NODE_16).New());
15 node.type = (uint8_t)NType::NODE_16;
16 auto &n16 = Node16::Get(art, ptr: node);
17
18 n16.count = 0;
19 n16.prefix.Initialize();
20 return n16;
21}
22
23void Node16::Free(ART &art, Node &node) {
24
25 D_ASSERT(node.IsSet());
26 D_ASSERT(!node.IsSwizzled());
27
28 auto &n16 = Node16::Get(art, ptr: node);
29
30 // free all children
31 for (idx_t i = 0; i < n16.count; i++) {
32 Node::Free(art, node&: n16.children[i]);
33 }
34}
35
36Node16 &Node16::GrowNode4(ART &art, Node &node16, Node &node4) {
37
38 auto &n4 = Node4::Get(art, ptr: node4);
39 auto &n16 = Node16::New(art, node&: node16);
40
41 n16.count = n4.count;
42 n16.prefix.Move(other&: n4.prefix);
43
44 for (idx_t i = 0; i < n4.count; i++) {
45 n16.key[i] = n4.key[i];
46 n16.children[i] = n4.children[i];
47 }
48
49 n4.count = 0;
50 Node::Free(art, node&: node4);
51 return n16;
52}
53
54Node16 &Node16::ShrinkNode48(ART &art, Node &node16, Node &node48) {
55
56 auto &n16 = Node16::New(art, node&: node16);
57 auto &n48 = Node48::Get(art, ptr: node48);
58
59 n16.count = 0;
60 n16.prefix.Move(other&: n48.prefix);
61
62 for (idx_t i = 0; i < Node::NODE_256_CAPACITY; i++) {
63 D_ASSERT(n16.count <= Node::NODE_16_CAPACITY);
64 if (n48.child_index[i] != Node::EMPTY_MARKER) {
65 n16.key[n16.count] = i;
66 n16.children[n16.count] = n48.children[n48.child_index[i]];
67 n16.count++;
68 }
69 }
70
71 n48.count = 0;
72 Node::Free(art, node&: node48);
73 return n16;
74}
75
76void Node16::InitializeMerge(ART &art, const ARTFlags &flags) {
77
78 for (idx_t i = 0; i < count; i++) {
79 children[i].InitializeMerge(art, flags);
80 }
81}
82
83void Node16::InsertChild(ART &art, Node &node, const uint8_t byte, const Node child) {
84
85 D_ASSERT(node.IsSet());
86 D_ASSERT(!node.IsSwizzled());
87 auto &n16 = Node16::Get(art, ptr: node);
88
89 // ensure that there is no other child at the same byte
90 for (idx_t i = 0; i < n16.count; i++) {
91 D_ASSERT(n16.key[i] != byte);
92 }
93
94 // insert new child node into node
95 if (n16.count < Node::NODE_16_CAPACITY) {
96 // still space, just insert the child
97 idx_t child_pos = 0;
98 while (child_pos < n16.count && n16.key[child_pos] < byte) {
99 child_pos++;
100 }
101 // move children backwards to make space
102 for (idx_t i = n16.count; i > child_pos; i--) {
103 n16.key[i] = n16.key[i - 1];
104 n16.children[i] = n16.children[i - 1];
105 }
106
107 n16.key[child_pos] = byte;
108 n16.children[child_pos] = child;
109 n16.count++;
110
111 } else {
112 // node is full, grow to Node48
113 auto node16 = node;
114 Node48::GrowNode16(art, node48&: node, node16);
115 Node48::InsertChild(art, node, byte, child);
116 }
117}
118
119void Node16::DeleteChild(ART &art, Node &node, const uint8_t byte) {
120
121 D_ASSERT(node.IsSet());
122 D_ASSERT(!node.IsSwizzled());
123 auto &n16 = Node16::Get(art, ptr: node);
124
125 idx_t child_pos = 0;
126 for (; child_pos < n16.count; child_pos++) {
127 if (n16.key[child_pos] == byte) {
128 break;
129 }
130 }
131
132 D_ASSERT(child_pos < n16.count);
133
134 // free the child and decrease the count
135 Node::Free(art, node&: n16.children[child_pos]);
136 n16.count--;
137
138 // potentially move any children backwards
139 for (idx_t i = child_pos; i < n16.count; i++) {
140 n16.key[i] = n16.key[i + 1];
141 n16.children[i] = n16.children[i + 1];
142 }
143
144 // shrink node to Node4
145 if (n16.count < Node::NODE_4_CAPACITY) {
146 auto node16 = node;
147 Node4::ShrinkNode16(art, node4&: node, node16);
148 }
149}
150
151void Node16::ReplaceChild(const uint8_t byte, const Node child) {
152 for (idx_t i = 0; i < count; i++) {
153 if (key[i] == byte) {
154 children[i] = child;
155 return;
156 }
157 }
158}
159
160optional_ptr<Node> Node16::GetChild(const uint8_t byte) {
161
162 for (idx_t i = 0; i < count; i++) {
163 if (key[i] == byte) {
164 D_ASSERT(children[i].IsSet());
165 return &children[i];
166 }
167 }
168 return nullptr;
169}
170
171optional_ptr<Node> Node16::GetNextChild(uint8_t &byte) {
172
173 for (idx_t i = 0; i < count; i++) {
174 if (key[i] >= byte) {
175 byte = key[i];
176 D_ASSERT(children[i].IsSet());
177 return &children[i];
178 }
179 }
180 return nullptr;
181}
182
183BlockPointer Node16::Serialize(ART &art, MetaBlockWriter &writer) {
184
185 // recurse into children and retrieve child block pointers
186 vector<BlockPointer> child_block_pointers;
187 for (idx_t i = 0; i < count; i++) {
188 child_block_pointers.push_back(x: children[i].Serialize(art, writer));
189 }
190 for (idx_t i = count; i < Node::NODE_16_CAPACITY; i++) {
191 child_block_pointers.emplace_back(args: (block_id_t)DConstants::INVALID_INDEX, args: 0);
192 }
193
194 // get pointer and write fields
195 auto block_pointer = writer.GetBlockPointer();
196 writer.Write(element: NType::NODE_16);
197 writer.Write<uint8_t>(element: count);
198 prefix.Serialize(art, writer);
199
200 // write key values
201 for (idx_t i = 0; i < Node::NODE_16_CAPACITY; i++) {
202 writer.Write(element: key[i]);
203 }
204
205 // write child block pointers
206 for (auto &child_block_pointer : child_block_pointers) {
207 writer.Write(element: child_block_pointer.block_id);
208 writer.Write(element: child_block_pointer.offset);
209 }
210
211 return block_pointer;
212}
213
214void Node16::Deserialize(ART &art, MetaBlockReader &reader) {
215
216 count = reader.Read<uint8_t>();
217 prefix.Deserialize(art, reader);
218
219 // read key values
220 for (idx_t i = 0; i < Node::NODE_16_CAPACITY; i++) {
221 key[i] = reader.Read<uint8_t>();
222 }
223
224 // read child block pointers
225 for (idx_t i = 0; i < Node::NODE_16_CAPACITY; i++) {
226 children[i] = Node(reader);
227 }
228}
229
230void Node16::Vacuum(ART &art, const ARTFlags &flags) {
231
232 for (idx_t i = 0; i < count; i++) {
233 Node::Vacuum(art, node&: children[i], flags);
234 }
235}
236
237} // namespace duckdb
238