1//===----------------------------------------------------------------------===//
2// DuckDB
3//
4// duckdb/execution/index/art/prefix.hpp
5//
6//
7//===----------------------------------------------------------------------===//
8#pragma once
9
10#include "duckdb/execution/index/art/node.hpp"
11
12namespace duckdb {
13
14// classes
15class ARTKey;
16class PrefixSegment;
17
18class Prefix {
19public:
20 //! Number of bytes in this prefix
21 uint32_t count;
22 union {
23 //! Pointer to the head of the list of prefix segments
24 Node ptr;
25 //! Inlined prefix bytes
26 uint8_t inlined[Node::PREFIX_INLINE_BYTES];
27 } data;
28
29public:
30 //! Delete all prefix segments (if not inlined) and reset all fields
31 void Free(ART &art);
32 //! Initializes all the fields of an empty prefix
33 inline void Initialize() {
34 count = 0;
35 }
36 //! Initialize a prefix from an ART key
37 void Initialize(ART &art, const ARTKey &key, const uint32_t depth, const uint32_t count_p);
38 //! Initialize a prefix from another prefix up to count
39 void Initialize(ART &art, const Prefix &other, const uint32_t count_p);
40
41 //! Initializes a merge by incrementing the buffer IDs of the prefix segments
42 void InitializeMerge(ART &art, const idx_t buffer_count);
43
44 //! Move a prefix into this prefix
45 inline void Move(Prefix &other) {
46 count = other.count;
47 data = other.data;
48 other.Initialize();
49 }
50 //! Append a prefix to this prefix
51 void Append(ART &art, const Prefix &other);
52 //! Concatenate prefix with a partial key byte and another prefix: other.prefix + byte + this->prefix
53 void Concatenate(ART &art, const uint8_t byte, const Prefix &other);
54 //! Removes the first n bytes, and returns the new first byte
55 uint8_t Reduce(ART &art, const idx_t reduce_count);
56
57 //! Get the byte at position
58 uint8_t GetByte(const ART &art, const idx_t position) const;
59 //! Compare the key with the prefix of the node, return the position where they mismatch
60 uint32_t KeyMismatchPosition(const ART &art, const ARTKey &key, const uint32_t depth) const;
61 //! Compare this prefix to another prefix, return the position where they mismatch, or count otherwise
62 uint32_t MismatchPosition(const ART &art, const Prefix &other) const;
63
64 //! Serialize this prefix
65 void Serialize(const ART &art, MetaBlockWriter &writer) const;
66 //! Deserialize this prefix
67 void Deserialize(ART &art, MetaBlockReader &reader);
68
69 //! Vacuum the prefix segments of a prefix, if not inlined
70 void Vacuum(ART &art);
71
72private:
73 //! Returns whether this prefix is inlined
74 inline bool IsInlined() const {
75 return count <= Node::PREFIX_INLINE_BYTES;
76 }
77 //! Moves all inlined bytes onto a prefix segment, does not change the size
78 //! so this will be an (temporarily) invalid prefix
79 PrefixSegment &MoveInlinedToSegment(ART &art);
80 //! Inlines up to eight bytes on the first prefix segment
81 void MoveSegmentToInlined(ART &art);
82};
83
84} // namespace duckdb
85