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