1#include "duckdb/execution/index/art/node16.hpp"
2#include "duckdb/execution/index/art/node48.hpp"
3#include "duckdb/execution/index/art/node256.hpp"
4
5using namespace duckdb;
6
7Node48::Node48(ART &art, size_t compressionLength) : Node(art, NodeType::N48, compressionLength) {
8 for (idx_t i = 0; i < 256; i++) {
9 childIndex[i] = Node::EMPTY_MARKER;
10 }
11}
12
13idx_t Node48::GetChildPos(uint8_t k) {
14 if (childIndex[k] == Node::EMPTY_MARKER) {
15 return INVALID_INDEX;
16 } else {
17 return k;
18 }
19}
20
21idx_t Node48::GetChildGreaterEqual(uint8_t k, bool &equal) {
22 for (idx_t pos = k; pos < 256; pos++) {
23 if (childIndex[pos] != Node::EMPTY_MARKER) {
24 if (pos == k) {
25 equal = true;
26 } else {
27 equal = false;
28 }
29 return pos;
30 }
31 }
32 return Node::GetChildGreaterEqual(k, equal);
33}
34
35idx_t Node48::GetNextPos(idx_t pos) {
36 for (pos == INVALID_INDEX ? pos = 0 : pos++; pos < 256; pos++) {
37 if (childIndex[pos] != Node::EMPTY_MARKER) {
38 return pos;
39 }
40 }
41 return Node::GetNextPos(pos);
42}
43
44unique_ptr<Node> *Node48::GetChild(idx_t pos) {
45 assert(childIndex[pos] != Node::EMPTY_MARKER);
46 return &child[childIndex[pos]];
47}
48
49idx_t Node48::GetMin() {
50 for (idx_t i = 0; i < 256; i++) {
51 if (childIndex[i] != Node::EMPTY_MARKER) {
52 return i;
53 }
54 }
55 return INVALID_INDEX;
56}
57
58void Node48::insert(ART &art, unique_ptr<Node> &node, uint8_t keyByte, unique_ptr<Node> &child) {
59 Node48 *n = static_cast<Node48 *>(node.get());
60
61 // Insert leaf into inner node
62 if (node->count < 48) {
63 // Insert element
64 idx_t pos = n->count;
65 if (n->child[pos]) {
66 // find an empty position in the node list if the current position is occupied
67 pos = 0;
68 while (n->child[pos]) {
69 pos++;
70 }
71 }
72 n->child[pos] = move(child);
73 n->childIndex[keyByte] = pos;
74 n->count++;
75 } else {
76 // Grow to Node256
77 auto newNode = make_unique<Node256>(art, n->prefix_length);
78 for (idx_t i = 0; i < 256; i++) {
79 if (n->childIndex[i] != Node::EMPTY_MARKER) {
80 newNode->child[i] = move(n->child[n->childIndex[i]]);
81 }
82 }
83 newNode->count = n->count;
84 CopyPrefix(art, n, newNode.get());
85 node = move(newNode);
86 Node256::insert(art, node, keyByte, child);
87 }
88}
89
90void Node48::erase(ART &art, unique_ptr<Node> &node, int pos) {
91 Node48 *n = static_cast<Node48 *>(node.get());
92
93 n->child[n->childIndex[pos]].reset();
94 n->childIndex[pos] = Node::EMPTY_MARKER;
95 n->count--;
96 if (node->count <= 12) {
97 auto newNode = make_unique<Node16>(art, n->prefix_length);
98 CopyPrefix(art, n, newNode.get());
99 for (idx_t i = 0; i < 256; i++) {
100 if (n->childIndex[i] != Node::EMPTY_MARKER) {
101 newNode->key[newNode->count] = i;
102 newNode->child[newNode->count++] = move(n->child[n->childIndex[i]]);
103 }
104 }
105 node = move(newNode);
106 }
107}
108