1#include "duckdb/execution/index/art/node4.hpp"
2#include "duckdb/execution/index/art/node16.hpp"
3#include "duckdb/execution/index/art/node48.hpp"
4
5#include <cstring>
6
7using namespace duckdb;
8
9Node16::Node16(ART &art, size_t compressionLength) : Node(art, NodeType::N16, compressionLength) {
10 memset(key, 16, sizeof(key));
11}
12
13// TODO : In the future this can be performed using SIMD (#include <emmintrin.h> x86 SSE intrinsics)
14idx_t Node16::GetChildPos(uint8_t k) {
15 for (idx_t pos = 0; pos < count; pos++) {
16 if (key[pos] == k) {
17 return pos;
18 }
19 }
20 return Node::GetChildPos(k);
21}
22
23idx_t Node16::GetChildGreaterEqual(uint8_t k, bool &equal) {
24 for (idx_t pos = 0; pos < count; pos++) {
25 if (key[pos] >= k) {
26 if (key[pos] == k) {
27 equal = true;
28 } else {
29 equal = false;
30 }
31
32 return pos;
33 }
34 }
35 return Node::GetChildGreaterEqual(k, equal);
36}
37
38idx_t Node16::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> *Node16::GetChild(idx_t pos) {
47 assert(pos < count);
48 return &child[pos];
49}
50
51idx_t Node16::GetMin() {
52 return 0;
53}
54
55void Node16::insert(ART &art, unique_ptr<Node> &node, uint8_t keyByte, unique_ptr<Node> &child) {
56 Node16 *n = static_cast<Node16 *>(node.get());
57
58 if (n->count < 16) {
59 // Insert element
60 unsigned pos;
61 for (pos = 0; (pos < node->count) && (n->key[pos] < keyByte); pos++)
62 ;
63 if (n->child[pos] != nullptr) {
64 for (unsigned i = n->count; i > pos; i--) {
65 n->key[i] = n->key[i - 1];
66 n->child[i] = move(n->child[i - 1]);
67 }
68 }
69 n->key[pos] = keyByte;
70 n->child[pos] = move(child);
71 n->count++;
72 } else {
73 // Grow to Node48
74 auto newNode = make_unique<Node48>(art, n->prefix_length);
75 for (unsigned i = 0; i < node->count; i++) {
76 newNode->childIndex[n->key[i]] = i;
77 newNode->child[i] = move(n->child[i]);
78 }
79 CopyPrefix(art, n, newNode.get());
80 newNode->count = node->count;
81 node = move(newNode);
82
83 Node48::insert(art, node, keyByte, child);
84 }
85}
86
87void Node16::erase(ART &art, unique_ptr<Node> &node, int pos) {
88 Node16 *n = static_cast<Node16 *>(node.get());
89 // erase the child and decrease the count
90 n->child[pos].reset();
91 n->count--;
92 // potentially move any children backwards
93 for (; pos < n->count; pos++) {
94 n->key[pos] = n->key[pos + 1];
95 n->child[pos] = move(n->child[pos + 1]);
96 }
97 if (node->count <= 3) {
98 // Shrink node
99 auto newNode = make_unique<Node4>(art, n->prefix_length);
100 for (unsigned i = 0; i < n->count; i++) {
101 newNode->key[newNode->count] = n->key[i];
102 newNode->child[newNode->count++] = move(n->child[i]);
103 }
104 CopyPrefix(art, n, newNode.get());
105 node = move(newNode);
106 }
107}
108