1//===----------------------------------------------------------------------===//
2// DuckDB
3//
4// duckdb/execution/index/art/iterator.hpp
5//
6//
7//===----------------------------------------------------------------------===//
8#pragma once
9
10#include "duckdb/common/stack.hpp"
11#include "duckdb/execution/index/art/art_key.hpp"
12#include "duckdb/execution/index/art/leaf.hpp"
13#include "duckdb/execution/index/art/node.hpp"
14
15namespace duckdb {
16
17struct IteratorEntry {
18 IteratorEntry() {
19 }
20 IteratorEntry(Node node, uint8_t byte) : node(node), byte(byte) {
21 }
22
23 Node node;
24 uint8_t byte = 0;
25};
26
27//! Keeps track of the current key in the iterator
28class IteratorCurrentKey {
29public:
30 //! Push byte into current key
31 void Push(const uint8_t key);
32 //! Pops n elements from the key
33 void Pop(const idx_t n);
34
35 //! Subscript operator
36 uint8_t &operator[](idx_t idx);
37 //! Greater than operator
38 bool operator>(const ARTKey &k) const;
39 //! Greater than or equal to operator
40 bool operator>=(const ARTKey &k) const;
41 //! Equal to operator
42 bool operator==(const ARTKey &k) const;
43
44private:
45 //! The current key position
46 idx_t cur_key_pos = 0;
47 //! The current key corresponding to the current leaf
48 vector<uint8_t> key;
49};
50
51class Iterator {
52public:
53 //! All information about the current key
54 IteratorCurrentKey cur_key;
55 //! Pointer to the ART
56 ART *art = nullptr;
57
58 //! Scan the tree
59 bool Scan(const ARTKey &key, const idx_t &max_count, vector<row_t> &result_ids, const bool &is_inclusive);
60 //! Finds the minimum value of the tree
61 void FindMinimum(Node &node);
62 //! Goes to the lower bound of the tree
63 bool LowerBound(Node node, const ARTKey &key, const bool &is_inclusive);
64
65private:
66 //! Stack of iterator entries
67 stack<IteratorEntry> nodes;
68 //! Last visited leaf
69 Leaf *last_leaf = nullptr;
70
71 //! Go to the next node
72 bool Next();
73 //! Push part of the key to the current key
74 void PushKey(const Node &node, const uint8_t byte);
75 //! Pop node from the stack of iterator entries
76 void PopNode();
77};
78} // namespace duckdb
79