1#include "duckdb/execution/index/art/node256.hpp"
2
3#include "duckdb/execution/index/art/art.hpp"
4#include "duckdb/execution/index/art/node.hpp"
5#include "duckdb/execution/index/art/node48.hpp"
6#include "duckdb/storage/meta_block_reader.hpp"
7#include "duckdb/storage/meta_block_writer.hpp"
8
9namespace duckdb {
10
11Node256 &Node256::New(ART &art, Node &node) {
12
13 node.SetPtr(Node::GetAllocator(art, type: NType::NODE_256).New());
14 node.type = (uint8_t)NType::NODE_256;
15 auto &n256 = Node256::Get(art, ptr: node);
16
17 n256.count = 0;
18 n256.prefix.Initialize();
19
20 for (idx_t i = 0; i < Node::NODE_256_CAPACITY; i++) {
21 n256.children[i].Reset();
22 }
23
24 return n256;
25}
26
27void Node256::Free(ART &art, Node &node) {
28
29 D_ASSERT(node.IsSet());
30 D_ASSERT(!node.IsSwizzled());
31
32 auto &n256 = Node256::Get(art, ptr: node);
33
34 if (!n256.count) {
35 return;
36 }
37
38 // free all children
39 for (idx_t i = 0; i < Node::NODE_256_CAPACITY; i++) {
40 if (n256.children[i].IsSet()) {
41 Node::Free(art, node&: n256.children[i]);
42 }
43 }
44}
45
46Node256 &Node256::GrowNode48(ART &art, Node &node256, Node &node48) {
47
48 auto &n48 = Node48::Get(art, ptr: node48);
49 auto &n256 = Node256::New(art, node&: node256);
50
51 n256.count = n48.count;
52 n256.prefix.Move(other&: n48.prefix);
53
54 for (idx_t i = 0; i < Node::NODE_256_CAPACITY; i++) {
55 if (n48.child_index[i] != Node::EMPTY_MARKER) {
56 n256.children[i] = n48.children[n48.child_index[i]];
57 } else {
58 n256.children[i].Reset();
59 }
60 }
61
62 n48.count = 0;
63 Node::Free(art, node&: node48);
64 return n256;
65}
66
67void Node256::InitializeMerge(ART &art, const ARTFlags &flags) {
68
69 for (idx_t i = 0; i < Node::NODE_256_CAPACITY; i++) {
70 if (children[i].IsSet()) {
71 children[i].InitializeMerge(art, flags);
72 }
73 }
74}
75
76void Node256::InsertChild(ART &art, Node &node, const uint8_t byte, const Node child) {
77
78 D_ASSERT(node.IsSet());
79 D_ASSERT(!node.IsSwizzled());
80 auto &n256 = Node256::Get(art, ptr: node);
81
82 // ensure that there is no other child at the same byte
83 D_ASSERT(!n256.children[byte].IsSet());
84
85 n256.count++;
86 D_ASSERT(n256.count <= Node::NODE_256_CAPACITY);
87 n256.children[byte] = child;
88}
89
90void Node256::DeleteChild(ART &art, Node &node, const uint8_t byte) {
91
92 D_ASSERT(node.IsSet());
93 D_ASSERT(!node.IsSwizzled());
94 auto &n256 = Node256::Get(art, ptr: node);
95
96 // free the child and decrease the count
97 Node::Free(art, node&: n256.children[byte]);
98 n256.count--;
99
100 // shrink node to Node48
101 if (n256.count <= Node::NODE_256_SHRINK_THRESHOLD) {
102 auto node256 = node;
103 Node48::ShrinkNode256(art, node48&: node, node256);
104 }
105}
106
107optional_ptr<Node> Node256::GetNextChild(uint8_t &byte) {
108
109 for (idx_t i = byte; i < Node::NODE_256_CAPACITY; i++) {
110 if (children[i].IsSet()) {
111 byte = i;
112 return &children[i];
113 }
114 }
115 return nullptr;
116}
117
118BlockPointer Node256::Serialize(ART &art, MetaBlockWriter &writer) {
119
120 // recurse into children and retrieve child block pointers
121 vector<BlockPointer> child_block_pointers;
122 for (idx_t i = 0; i < Node::NODE_256_CAPACITY; i++) {
123 child_block_pointers.push_back(x: children[i].Serialize(art, writer));
124 }
125
126 // get pointer and write fields
127 auto block_pointer = writer.GetBlockPointer();
128 writer.Write(element: NType::NODE_256);
129 writer.Write<uint16_t>(element: count);
130 prefix.Serialize(art, writer);
131
132 // write child block pointers
133 for (auto &child_block_pointer : child_block_pointers) {
134 writer.Write(element: child_block_pointer.block_id);
135 writer.Write(element: child_block_pointer.offset);
136 }
137
138 return block_pointer;
139}
140
141void Node256::Deserialize(ART &art, MetaBlockReader &reader) {
142
143 count = reader.Read<uint16_t>();
144 prefix.Deserialize(art, reader);
145
146 // read child block pointers
147 for (idx_t i = 0; i < Node::NODE_256_CAPACITY; i++) {
148 children[i] = Node(reader);
149 }
150}
151
152void Node256::Vacuum(ART &art, const ARTFlags &flags) {
153
154 for (idx_t i = 0; i < Node::NODE_256_CAPACITY; i++) {
155 if (children[i].IsSet()) {
156 Node::Vacuum(art, node&: children[i], flags);
157 }
158 }
159}
160
161} // namespace duckdb
162