1//===----------------------------------------------------------------------===//
2// DuckDB
3//
4// duckdb/execution/index/art/node256.hpp
5//
6//
7//===----------------------------------------------------------------------===//
8
9#pragma once
10
11#include "duckdb/execution/index/art/art.hpp"
12#include "duckdb/execution/index/art/fixed_size_allocator.hpp"
13#include "duckdb/execution/index/art/node.hpp"
14#include "duckdb/execution/index/art/prefix.hpp"
15
16namespace duckdb {
17
18//! Node256 holds up to 256 ARTNode children which can be directly indexed by the key byte
19class Node256 {
20public:
21 //! Number of non-null children
22 uint16_t count;
23 //! Compressed path (prefix)
24 Prefix prefix;
25 //! ART node pointers to the child nodes
26 Node children[Node::NODE_256_CAPACITY];
27
28public:
29 //! Get a new Node256 node, might cause a new buffer allocation, and initialize it
30 static Node256 &New(ART &art, Node &node);
31 //! Free the node (and its subtree)
32 static void Free(ART &art, Node &node);
33 //! Get a reference to the node
34 static inline Node256 &Get(const ART &art, const Node ptr) {
35 return *Node::GetAllocator(art, type: NType::NODE_256).Get<Node256>(ptr);
36 }
37 //! Initializes all the fields of the node while growing a Node48 to a Node256
38 static Node256 &GrowNode48(ART &art, Node &node256, Node &node48);
39
40 //! Initializes a merge by incrementing the buffer IDs of the node
41 void InitializeMerge(ART &art, const ARTFlags &flags);
42
43 //! Insert a child node at byte
44 static void InsertChild(ART &art, Node &node, const uint8_t byte, const Node child);
45 //! Delete the child node at the respective byte
46 static void DeleteChild(ART &art, Node &node, const uint8_t byte);
47
48 //! Replace the child node at the respective byte
49 inline void ReplaceChild(const uint8_t byte, const Node child) {
50 children[byte] = child;
51 }
52
53 //! Get the child for the respective byte in the node
54 inline optional_ptr<Node> GetChild(const uint8_t byte) {
55 if (children[byte].IsSet()) {
56 return &children[byte];
57 }
58 return nullptr;
59 }
60 //! Get the first child that is greater or equal to the specific byte
61 optional_ptr<Node> GetNextChild(uint8_t &byte);
62
63 //! Serialize an ART node
64 BlockPointer Serialize(ART &art, MetaBlockWriter &writer);
65 //! Deserialize this node
66 void Deserialize(ART &art, MetaBlockReader &reader);
67
68 //! Vacuum the children of the node
69 void Vacuum(ART &art, const ARTFlags &flags);
70};
71} // namespace duckdb
72