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