1//===----------------------------------------------------------------------===//
2// DuckDB
3//
4// duckdb/execution/index/art/leaf.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// classes
19class Node;
20class ARTKey;
21class MetaBlockWriter;
22class MetaBlockReader;
23
24// structs
25struct BlockPointer;
26
27class Leaf {
28public:
29 //! Number of row IDs
30 uint32_t count;
31 //! Compressed path (prefix)
32 Prefix prefix;
33 union {
34 //! The pointer to the head of the list of leaf segments
35 Node ptr;
36 //! Inlined row ID
37 row_t inlined;
38 } row_ids;
39
40public:
41 //! Get a new leaf node, might cause a new buffer allocation, and initializes a leaf holding one
42 //! row ID and a prefix starting at depth
43 static Leaf &New(ART &art, Node &node, const ARTKey &key, const uint32_t depth, const row_t row_id);
44 //! Get a new leaf node, might cause a new buffer allocation, and initializes a leaf holding
45 //! n_row_ids row IDs and a prefix starting at depth
46 static Leaf &New(ART &art, Node &node, const ARTKey &key, const uint32_t depth, const row_t *row_ids,
47 const idx_t count);
48 //! Free the leaf
49 static void Free(ART &art, Node &node);
50 //! Get a reference to the leaf
51 static inline Leaf &Get(const ART &art, const Node ptr) {
52 return *Node::GetAllocator(art, type: NType::LEAF).Get<Leaf>(ptr);
53 }
54
55 //! Initializes a merge by incrementing the buffer IDs of the leaf segments
56 void InitializeMerge(const ART &art, const idx_t buffer_count);
57 //! Merge leaves
58 void Merge(ART &art, Node &other);
59
60 //! Insert a row ID into a leaf
61 void Insert(ART &art, const row_t row_id);
62 //! Remove a row ID from a leaf
63 void Remove(ART &art, const row_t row_id);
64
65 //! Returns whether this leaf is inlined
66 inline bool IsInlined() const {
67 return count <= 1;
68 }
69 //! Get the row ID at the position
70 row_t GetRowId(const ART &art, const idx_t position) const;
71 //! Returns the position of a row ID, and an invalid index, if the leaf does not contain the row ID,
72 //! and sets the ptr to point to the segment containing the row ID
73 uint32_t FindRowId(const ART &art, Node &ptr, const row_t row_id) const;
74
75 //! Returns the string representation of a leaf
76 string VerifyAndToString(const ART &art, const bool only_verify) const;
77
78 //! Serialize this leaf
79 BlockPointer Serialize(const ART &art, MetaBlockWriter &writer) const;
80 //! Deserialize this leaf
81 void Deserialize(ART &art, MetaBlockReader &reader);
82
83 //! Vacuum the leaf segments of a leaf, if not inlined
84 void Vacuum(ART &art);
85
86private:
87 //! Moves the inlined row ID onto a leaf segment, does not change the size
88 //! so this will be a (temporarily) invalid leaf
89 void MoveInlinedToSegment(ART &art);
90};
91
92} // namespace duckdb
93