1#include "duckdb/execution/index/art/node48.hpp"
2#include "duckdb/execution/index/art/node256.hpp"
3
4using namespace duckdb;
5
6Node256::Node256(ART &art, size_t compressionLength) : Node(art, NodeType::N256, compressionLength) {
7}
8
9idx_t Node256::GetChildPos(uint8_t k) {
10 if (child[k]) {
11 return k;
12 } else {
13 return INVALID_INDEX;
14 }
15}
16
17idx_t Node256::GetChildGreaterEqual(uint8_t k, bool &equal) {
18 for (idx_t pos = k; pos < 256; pos++) {
19 if (child[pos]) {
20 if (pos == k) {
21 equal = true;
22 } else {
23 equal = false;
24 }
25 return pos;
26 }
27 }
28 return INVALID_INDEX;
29}
30
31idx_t Node256::GetMin() {
32 for (idx_t i = 0; i < 256; i++) {
33 if (child[i]) {
34 return i;
35 }
36 }
37 return INVALID_INDEX;
38}
39
40idx_t Node256::GetNextPos(idx_t pos) {
41 for (pos == INVALID_INDEX ? pos = 0 : pos++; pos < 256; pos++) {
42 if (child[pos]) {
43 return pos;
44 }
45 }
46 return Node::GetNextPos(pos);
47}
48
49unique_ptr<Node> *Node256::GetChild(idx_t pos) {
50 assert(child[pos]);
51 return &child[pos];
52}
53
54void Node256::insert(ART &art, unique_ptr<Node> &node, uint8_t keyByte, unique_ptr<Node> &child) {
55 Node256 *n = static_cast<Node256 *>(node.get());
56
57 n->count++;
58 n->child[keyByte] = move(child);
59}
60
61void Node256::erase(ART &art, unique_ptr<Node> &node, int pos) {
62 Node256 *n = static_cast<Node256 *>(node.get());
63
64 n->child[pos].reset();
65 n->count--;
66 if (node->count <= 36) {
67 auto newNode = make_unique<Node48>(art, n->prefix_length);
68 CopyPrefix(art, n, newNode.get());
69 for (idx_t i = 0; i < 256; i++) {
70 if (n->child[i]) {
71 newNode->childIndex[i] = newNode->count;
72 newNode->child[newNode->count] = move(n->child[i]);
73 newNode->count++;
74 }
75 }
76 node = move(newNode);
77 }
78}
79