1//===----------------------------------------------------------------------===//
2// DuckDB
3//
4// duckdb/execution/index/art/node4.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//! Node4 holds up to four ARTNode children sorted by their key byte
19class Node4 {
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_4_CAPACITY];
27 //! ART node pointers to the child nodes
28 Node children[Node::NODE_4_CAPACITY];
29
30public:
31 //! Get a new Node4 node, might cause a new buffer allocation, and initialize it
32 static Node4 &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 Node4 &Get(const ART &art, const Node ptr) {
37 return *Node::GetAllocator(art, type: NType::NODE_4).Get<Node4>(ptr);
38 }
39 //! Initializes all fields of the node while shrinking a Node16 to a Node4
40 static Node4 &ShrinkNode16(ART &art, Node &node4, Node &node16);
41
42 //! Initializes a merge by incrementing the buffer IDs of the node
43 void InitializeMerge(ART &art, const ARTFlags &flags);
44
45 //! Insert a child node at byte
46 static void InsertChild(ART &art, Node &node, const uint8_t byte, const Node child);
47 //! Delete the child node at the respective byte
48 static void DeleteChild(ART &art, Node &node, const uint8_t byte);
49
50 //! Replace the child node at the respective byte
51 void ReplaceChild(const uint8_t byte, const Node child);
52
53 //! Get the child for the respective byte in the node
54 optional_ptr<Node> GetChild(const uint8_t byte);
55 //! Get the first child that is greater or equal to the specific byte
56 optional_ptr<Node> GetNextChild(uint8_t &byte);
57
58 //! Serialize an ART node
59 BlockPointer Serialize(ART &art, MetaBlockWriter &writer);
60 //! Deserialize this node
61 void Deserialize(ART &art, MetaBlockReader &reader);
62
63 //! Vacuum the children of the node
64 void Vacuum(ART &art, const ARTFlags &flags);
65};
66} // namespace duckdb
67