1//===----------------------------------------------------------------------===//
2// DuckDB
3//
4// duckdb/execution/index/art/node48.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//! Node48 holds up to 48 ARTNode children. It contains a child_index array which can be directly indexed by the key
19//! byte, and which contains the position of the child node in the children array
20class Node48 {
21public:
22 //! Number of non-null children
23 uint8_t count;
24 //! Compressed path (prefix)
25 Prefix prefix;
26 //! Array containing all possible partial key bytes, those not set have an EMPTY_MARKER
27 uint8_t child_index[Node::NODE_256_CAPACITY];
28 //! ART node pointers to the child nodes
29 Node children[Node::NODE_48_CAPACITY];
30
31public:
32 //! Get a new Node48 node, might cause a new buffer allocation, and initialize it
33 static Node48 &New(ART &art, Node &node);
34 //! Free the node (and its subtree)
35 static void Free(ART &art, Node &node);
36 //! Get a reference to the node
37 static inline Node48 &Get(const ART &art, const Node ptr) {
38 return *Node::GetAllocator(art, type: NType::NODE_48).Get<Node48>(ptr);
39 }
40 //! Initializes all the fields of the node while growing a Node16 to a Node48
41 static Node48 &GrowNode16(ART &art, Node &node48, Node &node16);
42 //! Initializes all fields of the node while shrinking a Node256 to a Node48
43 static Node48 &ShrinkNode256(ART &art, Node &node48, Node &node256);
44
45 //! Initializes a merge by incrementing the buffer IDs of the node
46 void InitializeMerge(ART &art, const ARTFlags &flags);
47
48 //! Insert a child node at byte
49 static void InsertChild(ART &art, Node &node, const uint8_t byte, const Node child);
50 //! Delete the child node at the respective byte
51 static void DeleteChild(ART &art, Node &node, const uint8_t byte);
52
53 //! Replace the child node at the respective byte
54 inline void ReplaceChild(const uint8_t byte, const Node child) {
55 D_ASSERT(child_index[byte] != Node::EMPTY_MARKER);
56 children[child_index[byte]] = child;
57 }
58
59 //! Get the child for the respective byte in the node
60 inline optional_ptr<Node> GetChild(const uint8_t byte) {
61 if (child_index[byte] != Node::EMPTY_MARKER) {
62 D_ASSERT(children[child_index[byte]].IsSet());
63 return &children[child_index[byte]];
64 }
65 return nullptr;
66 }
67 //! Get the first child that is greater or equal to the specific byte
68 optional_ptr<Node> GetNextChild(uint8_t &byte);
69
70 //! Serialize an ART node
71 BlockPointer Serialize(ART &art, MetaBlockWriter &writer);
72 //! Deserialize this node
73 void Deserialize(ART &art, MetaBlockReader &reader);
74
75 //! Vacuum the children of the node
76 void Vacuum(ART &art, const ARTFlags &flags);
77};
78} // namespace duckdb
79