1#include "duckdb/execution/index/art/node4.hpp"
2#include "duckdb/execution/index/art/node16.hpp"
3#include "duckdb/execution/index/art/art.hpp"
4
5using namespace duckdb;
6
7Node4::Node4(ART &art, size_t compressionLength) : Node(art, NodeType::N4, compressionLength) {
8 memset(key, 0, sizeof(key));
9}
10
11idx_t Node4::GetChildPos(uint8_t k) {
12 for (idx_t pos = 0; pos < count; pos++) {
13 if (key[pos] == k) {
14 return pos;
15 }
16 }
17 return Node::GetChildPos(k);
18}
19
20idx_t Node4::GetChildGreaterEqual(uint8_t k, bool &equal) {
21 for (idx_t pos = 0; pos < count; pos++) {
22 if (key[pos] >= k) {
23 if (key[pos] == k) {
24 equal = true;
25 } else {
26 equal = false;
27 }
28 return pos;
29 }
30 }
31 return Node::GetChildGreaterEqual(k, equal);
32}
33
34idx_t Node4::GetMin() {
35 return 0;
36}
37
38idx_t Node4::GetNextPos(idx_t pos) {
39 if (pos == INVALID_INDEX) {
40 return 0;
41 }
42 pos++;
43 return pos < count ? pos : INVALID_INDEX;
44}
45
46unique_ptr<Node> *Node4::GetChild(idx_t pos) {
47 assert(pos < count);
48 return &child[pos];
49}
50
51void Node4::insert(ART &art, unique_ptr<Node> &node, uint8_t keyByte, unique_ptr<Node> &child) {
52 Node4 *n = static_cast<Node4 *>(node.get());
53
54 // Insert leaf into inner node
55 if (node->count < 4) {
56 // Insert element
57 unsigned pos;
58 for (pos = 0; (pos < node->count) && (n->key[pos] < keyByte); pos++)
59 ;
60 if (n->child[pos] != nullptr) {
61 for (unsigned i = n->count; i > pos; i--) {
62 n->key[i] = n->key[i - 1];
63 n->child[i] = move(n->child[i - 1]);
64 }
65 }
66 n->key[pos] = keyByte;
67 n->child[pos] = move(child);
68 n->count++;
69 } else {
70 // Grow to Node16
71 auto newNode = make_unique<Node16>(art, n->prefix_length);
72 newNode->count = 4;
73 CopyPrefix(art, node.get(), newNode.get());
74 for (unsigned i = 0; i < 4; i++) {
75 newNode->key[i] = n->key[i];
76 newNode->child[i] = move(n->child[i]);
77 }
78 node = move(newNode);
79 Node16::insert(art, node, keyByte, child);
80 }
81}
82
83void Node4::erase(ART &art, unique_ptr<Node> &node, int pos) {
84 Node4 *n = static_cast<Node4 *>(node.get());
85 assert(pos < n->count);
86
87 // erase the child and decrease the count
88 n->child[pos].reset();
89 n->count--;
90 // potentially move any children backwards
91 for (; pos < n->count; pos++) {
92 n->key[pos] = n->key[pos + 1];
93 n->child[pos] = move(n->child[pos + 1]);
94 }
95
96 // This is a one way node
97 if (n->count == 1) {
98 auto childref = n->child[0].get();
99 //! concatenate prefixes
100 auto new_length = node->prefix_length + childref->prefix_length + 1;
101 //! have to allocate space in our prefix array
102 unique_ptr<uint8_t[]> new_prefix = unique_ptr<uint8_t[]>(new uint8_t[new_length]);
103 ;
104
105 //! first move the existing prefix (if any)
106 for (uint32_t i = 0; i < childref->prefix_length; i++) {
107 new_prefix[new_length - (i + 1)] = childref->prefix[childref->prefix_length - (i + 1)];
108 }
109 //! now move the current key as part of the prefix
110 new_prefix[node->prefix_length] = n->key[0];
111 //! finally add the old prefix
112 for (uint32_t i = 0; i < node->prefix_length; i++) {
113 new_prefix[i] = node->prefix[i];
114 }
115 //! set new prefix and move the child
116 childref->prefix = move(new_prefix);
117 childref->prefix_length = new_length;
118 node = move(n->child[0]);
119 }
120}
121