31 #include <type_traits>
53 return (a >
b) - (a <
b);
55 bool less(
const T& a,
const T&
b)
const {
58 bool equal(
const T& a,
const T&
b)
const {
85 template <
typename Key,
typename Iter,
typename Comp>
86 inline Iter
operator()(
const Key&
k, Iter a, Iter
b, Comp& comp)
const {
94 template <
typename Key,
typename Iter,
typename Comp>
95 inline Iter
lower_bound(
const Key&
k, Iter a, Iter
b, Comp& comp)
const {
111 template <
typename Key,
typename Iter,
typename Comp>
112 inline Iter
upper_bound(
const Key&
k, Iter a, Iter
b, Comp& comp)
const {
115 if (comp(*c,
k) > 0) {
141 template <
typename Key,
typename Iter,
typename Comp>
142 Iter
operator()(
const Key&
k, Iter a, Iter
b, Comp& comp)
const {
146 auto step =
count >> 1;
148 auto r = comp(*c,
k);
166 template <
typename Key,
typename Iter,
typename Comp>
167 Iter
lower_bound(
const Key&
k, Iter a, Iter
b, Comp& comp)
const {
171 auto step =
count >> 1;
173 if (comp(*c,
k) < 0) {
187 template <
typename Key,
typename Iter,
typename Comp>
188 Iter
upper_bound(
const Key&
k, Iter a, Iter
b, Comp& comp)
const {
192 auto step =
count >> 1;
194 if (comp(
k, *c) >= 0) {
211 template <
typename S>
212 struct strategy_selection {
216 struct linear :
public strategy_selection<linear_search> {};
217 struct binary :
public strategy_selection<binary_search> {};
220 template <
typename Key>
221 struct default_strategy :
public binary {};
224 struct default_strategy<int> :
public linear {};
226 template <
typename... Ts>
232 template <
typename T>
234 void update(T& ,
const T& ) {}
249 unsigned blockSize,
typename SearchStrategy,
bool isSet,
typename WeakComparator =
Comparator,
263 const static SearchStrategy
search;
269 bool less(
const Key& a,
const Key&
b)
const {
273 bool equal(
const Key& a,
const Key&
b)
const {
274 return comp.equal(a,
b);
279 bool weak_less(
const Key& a,
const Key&
b)
const {
290 void update(Key& old_k,
const Key& new_k) {
371 ((blockSize >
sizeof(
base)) ? blockSize -
sizeof(
base) : 0) /
sizeof(Key);
397 res->
keys[
i] = this->keys[
i];
409 ires->children[
i]->
parent = res;
421 assert(this->
inner &&
"Invalid cast!");
422 return *
static_cast<inner_node*
>(
this);
430 assert(this->
inner &&
"Invalid cast!");
431 return *
static_cast<const inner_node*
>(
this);
517 return this->numElements == 0;
524 return this->numElements ==
maxKeys;
547 assert(this->lock.is_write_locked());
555 assert(this->numElements ==
maxKeys);
566 sibling->lock.start_write();
567 locked_nodes.push_back(sibling);
571 for (
unsigned i = split_point + 1,
j = 0;
i <
maxKeys; ++
i, ++
j) {
578 auto* other =
static_cast<inner_node*
>(sibling);
579 for (
unsigned i = split_point + 1,
j = 0;
i <=
maxKeys; ++
i, ++
j) {
581 other->children[
j]->
parent = other;
587 this->numElements = split_point;
612 assert(this->lock.is_write_locked());
613 assert(!this->
parent || this->
parent->lock.is_write_locked());
614 assert((this->
parent !=
nullptr) || root_lock.is_write_locked());
622 assert(this->numElements ==
maxKeys);
634 if (!left->lock.try_start_write()) {
644 std::min<int>(
static_cast<int>(
maxKeys - left->numElements), idx));
651 left->keys[left->numElements] = *splitter;
653 left->keys[left->numElements + 1 +
i] =
keys[
i];
655 *splitter =
keys[num - 1];
658 for (
size_type i = 0;
i < this->numElements - num; ++
i) {
664 auto* ileft =
static_cast<inner_node*
>(left);
665 auto* iright =
static_cast<inner_node*
>(
this);
669 ileft->children[left->numElements +
i + 1] = iright->children[
i];
674 iright->children[
i]->parent = ileft;
675 iright->children[
i]->position =
680 for (
size_type i = 0;
i < this->numElements - num + 1; ++
i) {
681 iright->children[
i] = iright->children[
i + num];
685 for (
size_type i = 0;
i < this->numElements - num + 1; ++
i) {
691 left->numElements += num;
692 this->numElements -= num;
695 left->lock.end_write();
699 return static_cast<int>(num);
703 left->lock.abort_write();
727 assert(this->lock.is_write_locked());
728 assert(!this->
parent || this->
parent->lock.is_write_locked());
729 assert((this->
parent !=
nullptr) || root_lock.is_write_locked());
736 if (this->
parent ==
nullptr) {
737 assert(*
root ==
this);
740 auto* new_root =
new inner_node();
741 new_root->numElements = 1;
744 new_root->children[0] =
this;
745 new_root->children[1] = sibling;
749 sibling->
parent = new_root;
762 root,
root_lock, pos,
this,
keys[this->numElements], sibling, locked_nodes);
779 node* newNode, std::vector<node*>& locked_nodes) {
780 assert(this->lock.is_write_locked());
788 if (this->numElements >=
maxKeys) {
790 assert(!this->
parent || this->
parent->lock.is_write_locked());
791 assert((this->
parent) || root_lock.is_write_locked());
803 if (pos > this->numElements) {
805 pos = pos -
static_cast<unsigned int>(this->
numElements) - 1;
812 assert(other->lock.is_write_locked());
817 for (;
i <= other->numElements; ++
i) {
818 if (other->getChild(
i) == predecessor) {
823 pos = (
i > other->numElements) ? 0 :
i;
824 other->insert_inner(
root,
root_lock, pos, predecessor, key, newNode, locked_nodes);
826 other->insert_inner(
root,
root_lock, pos, predecessor, key, newNode);
833 for (
int i =
static_cast<int>(this->numElements) - 1;
i >= (int)pos; --
i) {
840 assert(
getChild(pos) == predecessor);
857 void printTree(std::ostream& out,
const std::string& prefix)
const {
859 out << prefix <<
"@" <<
this <<
"[" << ((int)(this->
position)) <<
"] - "
860 << (this->
inner ?
"i" :
"") <<
"node : " << this->numElements <<
"/" <<
maxKeys <<
" [";
865 if (
i != this->numElements - 1) {
876 if (
i != this->numElements) {
885 if (this->lock.is_write_locked()) {
886 std::cout <<
" locked";
894 for (
unsigned i = 0;
i < this->numElements + 1; ++
i) {
895 static_cast<const inner_node*
>(
this)->children[
i]->
printTree(out, prefix +
" ");
914 std::vector<chunk>& res,
size_type num,
const iterator&
begin,
const iterator&
end)
const {
932 if (this->
isLeaf() || num < (this->numElements + 1)) {
933 auto step = this->numElements / num;
944 for (
i = step - 1;
i < this->numElements - step;
i += step) {
958 auto part = num / (this->numElements + 1);
979 template <
typename Comp>
984 if (this->numElements >
maxKeys) {
985 std::cout <<
"Node with " << this->numElements <<
"/" <<
maxKeys <<
" encountered!\n";
991 if (this->
parent !=
nullptr) {
992 std::cout <<
"Root not properly linked!\n";
998 std::cout <<
"Invalid null-parent!\n";
1002 std::cout <<
"Parent reference invalid!\n";
1003 std::cout <<
" Node: " <<
this <<
"\n";
1004 std::cout <<
" Parent: " << this->
parent <<
"\n";
1005 std::cout <<
" Position: " << ((int)this->
position) <<
"\n";
1010 if (valid && this->
position != 0 &&
1012 std::cout <<
"Left parent key not lower bound!\n";
1013 std::cout <<
" Node: " <<
this <<
"\n";
1014 std::cout <<
" Parent: " << this->
parent <<
"\n";
1015 std::cout <<
" Position: " << ((int)this->
position) <<
"\n";
1017 std::cout <<
" Lower: " << (
keys[0]) <<
"\n";
1023 !(comp(
keys[this->numElements - 1], this->
parent->
keys[this->position]) <
1024 ((isSet) ? 0 : 1))) {
1025 std::cout <<
"Right parent key not lower bound!\n";
1026 std::cout <<
" Node: " <<
this <<
"\n";
1027 std::cout <<
" Parent: " << this->
parent <<
"\n";
1028 std::cout <<
" Position: " << ((int)this->
position) <<
"\n";
1030 std::cout <<
" Upper: " << (
keys[0]) <<
"\n";
1037 if (this->numElements > 0) {
1038 for (
unsigned i = 0;
i < this->numElements - 1;
i++) {
1039 if (valid && !(
comp(
keys[
i],
keys[
i + 1]) < ((isSet) ? 0 : 1))) {
1040 std::cout <<
"Element order invalid!\n";
1041 std::cout <<
" @" <<
this <<
" key " <<
i <<
" is " <<
keys[
i] <<
" vs "
1042 <<
keys[
i + 1] <<
"\n";
1064 struct inner_node :
public node {
1069 inner_node() :
node(true) {}
1074 if (children[
i] !=
nullptr) {
1076 delete static_cast<leaf_node*
>(children[
i]);
1108 using iterator_category = std::forward_iterator_tag;
1109 using value_type = Key;
1110 using difference_type = ptrdiff_t;
1111 using pointer = value_type*;
1112 using reference = value_type&;
1137 return !(*
this == other);
1141 const Key& operator*()
const {
1142 return cur->
keys[pos];
1180 void print(std::ostream& out = std::cout)
const {
1181 out << cur <<
"[" << (int)pos <<
"]";
1189 template <
unsigned size = 1>
1190 struct btree_operation_hints {
1191 using node_cache = LRUCache<node*, size>;
1194 node_cache last_insert;
1197 node_cache last_find_end;
1200 node_cache last_lower_bound_end;
1203 node_cache last_upper_bound_end;
1210 last_insert.clear(
nullptr);
1211 last_find_end.clear(
nullptr);
1212 last_lower_bound_end.clear(
nullptr);
1213 last_upper_bound_end.clear(
nullptr);
1240 struct hint_statistics {
1268 template <
typename Iter>
1276 other.root =
nullptr;
1277 other.leftmost =
nullptr;
1302 bool empty()
const {
1303 return root ==
nullptr;
1326 while (
root ==
nullptr) {
1334 if (
root !=
nullptr) {
1349 hints.last_insert.access(
leftmost);
1356 node* cur =
nullptr;
1359 lock_type::Lease cur_lease;
1361 auto checkHint = [&](
node* last_insert) {
1363 if (!last_insert)
return false;
1365 auto hint_lease = last_insert->lock.start_read();
1369 if (!last_insert->lock.validate(hint_lease))
return false;
1373 cur_lease = hint_lease;
1378 if (hints.last_insert.any(checkHint)) {
1396 cur_lease = cur->lock.start_read();
1409 auto a = &(cur->keys[0]);
1410 auto b = &(cur->keys[cur->numElements]);
1418 if (!cur->lock.validate(cur_lease)) {
1425 if (!cur->lock.try_upgrade_to_write(cur_lease)) {
1430 cur->lock.end_write();
1439 auto next = cur->getChild(idx);
1442 auto next_lease = next->lock.start_read();
1445 if (!cur->lock.end_read(cur_lease)) {
1454 cur_lease = next_lease;
1460 assert(!cur->inner);
1464 auto a = &(cur->keys[0]);
1465 auto b = &(cur->keys[cur->numElements]);
1471 if (isSet && pos != a &&
weak_equal(*(pos - 1),
k)) {
1473 if (!cur->lock.validate(cur_lease)) {
1479 if (
typeid(
Comparator) !=
typeid(WeakComparator) &&
less(
k, *(pos - 1))) {
1480 if (!cur->lock.try_upgrade_to_write(cur_lease)) {
1485 cur->lock.end_write();
1494 if (!cur->lock.try_upgrade_to_write(cur_lease)) {
1496 hints.last_insert.access(cur);
1504 std::vector<node*> parents;
1507 parent->lock.start_write();
1514 parent->lock.abort_write();
1516 parent->lock.start_write();
1524 parents.push_back(
parent);
1538 auto old_root =
root;
1542 for (
auto it = parents.rbegin(); it != parents.rend(); ++it) {
1547 parent->lock.end_write();
1549 if (old_root !=
root) {
1558 if (((
size_type)idx) > cur->numElements) {
1560 cur->lock.end_write();
1568 assert(cur->numElements <
node::maxKeys &&
"Split required!");
1571 for (
int j = cur->numElements;
j > idx; --
j) {
1572 cur->keys[
j] = cur->keys[
j - 1];
1580 cur->lock.end_write();
1583 hints.last_insert.access(cur);
1596 hints.last_insert.access(
leftmost);
1604 auto checkHints = [&](
node* last_insert) {
1605 if (!last_insert)
return false;
1612 if (hints.last_insert.any(checkHints)) {
1621 auto a = &(cur->keys[0]);
1622 auto b = &(cur->keys[cur->numElements]);
1638 cur = cur->getChild(idx);
1643 assert(!cur->inner);
1647 auto a = &(cur->keys[0]);
1648 auto b = &(cur->keys[cur->numElements]);
1654 if (isSet && pos != a &&
weak_equal(*(pos - 1),
k)) {
1656 if (
typeid(
Comparator) !=
typeid(WeakComparator) &&
less(
k, *(pos - 1))) {
1666 idx -= cur->rebalance_or_split(&
root,
root_lock,
static_cast<int>(idx));
1669 if (((
size_type)idx) > cur->numElements) {
1670 idx -= cur->numElements + 1;
1671 cur = cur->parent->getChild(cur->position + 1);
1676 assert(cur->numElements <
node::maxKeys &&
"Split required!");
1679 for (
int j =
static_cast<int>(cur->numElements);
j > idx; --
j) {
1680 cur->keys[
j] = cur->keys[
j - 1];
1688 hints.last_insert.access(cur);
1698 template <
typename Iter>
1699 void insert(
const Iter& a,
const Iter&
b) {
1703 for (
auto it = a; it !=
b; ++it) {
1710 iterator
begin()
const {
1715 iterator
end()
const {
1732 std::vector<chunk> res;
1758 iterator
find(
const Key&
k)
const {
1760 return find(
k, hints);
1774 auto checkHints = [&](
node* last_find_end) {
1775 if (!last_find_end)
return false;
1776 if (!
covers(last_find_end,
k))
return false;
1777 cur = last_find_end;
1782 if (hints.last_find_end.any(checkHints)) {
1793 auto a = &(cur->keys[0]);
1794 auto b = &(cur->keys[cur->numElements]);
1798 if (pos <
b &&
equal(*pos,
k)) {
1799 hints.last_find_end.access(cur);
1804 hints.last_find_end.access(cur);
1809 cur = cur->getChild(pos - a);
1835 auto checkHints = [&](
node* last_lower_bound_end) {
1836 if (!last_lower_bound_end)
return false;
1837 if (!
covers(last_lower_bound_end,
k))
return false;
1838 cur = last_lower_bound_end;
1843 if (hints.last_lower_bound_end.any(checkHints)) {
1849 iterator res =
end();
1851 auto a = &(cur->keys[0]);
1852 auto b = &(cur->keys[cur->numElements]);
1858 hints.last_lower_bound_end.access(cur);
1859 return (pos !=
b) ? iterator(cur, idx) : res;
1862 if (isSet && pos !=
b &&
equal(*pos,
k)) {
1863 return iterator(cur, idx);
1867 res = iterator(cur, idx);
1870 cur = cur->getChild(idx);
1896 auto checkHints = [&](
node* last_upper_bound_end) {
1897 if (!last_upper_bound_end)
return false;
1899 cur = last_upper_bound_end;
1904 if (hints.last_upper_bound_end.any(checkHints)) {
1910 iterator res =
end();
1912 auto a = &(cur->keys[0]);
1913 auto b = &(cur->keys[cur->numElements]);
1919 hints.last_upper_bound_end.access(cur);
1920 return (pos !=
b) ? iterator(cur, idx) : res;
1924 res = iterator(cur, idx);
1927 cur = cur->getChild(idx);
1935 if (
root !=
nullptr) {
1937 delete static_cast<leaf_node*
>(
root);
1939 delete static_cast<inner_node*
>(
root);
1960 if (
this == &other) {
1966 if (other.
empty()) {
1975 while (!tmp->isLeaf()) {
1978 leftmost =
static_cast<leaf_node*
>(tmp);
1987 if (
this == &other) {
1992 if (
size() != other.size()) {
1995 if (
size() < other.size()) {
1996 return other == *
this;
2000 for (
const auto& key : other) {
2010 return !(*
this == other);
2034 void printTree(std::ostream& out = std::cout)
const {
2035 out <<
"B-Tree with " <<
size() <<
" elements:\n";
2037 out <<
" - empty - \n";
2047 void printStats(std::ostream& out = std::cout)
const {
2049 out <<
" ---------------------------------\n";
2050 out <<
" Elements: " <<
size() <<
"\n";
2052 out <<
" Nodes: " << nodes <<
"\n";
2053 out <<
" ---------------------------------\n";
2054 out <<
" Size of inner node: " <<
sizeof(inner_node) <<
"\n";
2055 out <<
" Size of leaf node: " <<
sizeof(leaf_node) <<
"\n";
2056 out <<
" Size of Key: " <<
sizeof(Key) <<
"\n";
2058 out <<
" avg keys / node: " << (
size() / (double)nodes) <<
"\n";
2059 out <<
" avg filling rate: " << ((
size() / (double)nodes) /
node::maxKeys) <<
"\n";
2060 out <<
" ---------------------------------\n";
2069 out <<
" ---------------------------------\n";
2091 template <
typename R,
typename Iter>
2092 static typename std::enable_if<std::is_same<typename std::iterator_traits<Iter>::iterator_category,
2093 std::random_access_iterator_tag>::value,
2095 load(
const Iter& a,
const Iter&
b) {
2154 template <
typename Iter>
2159 int length = (
b - a) + 1;
2164 node* res =
new leaf_node();
2165 res->numElements = length;
2167 for (
int i = 0;
i < length; ++
i) {
2168 res->keys[
i] = a[
i];
2176 int step = ((length - numKeys) / (numKeys + 1));
2178 while (numKeys > 1 && (step < N / 2)) {
2180 step = ((length - numKeys) / (numKeys + 1));
2184 node* res =
new inner_node();
2185 res->numElements = numKeys;
2188 for (
int i = 0;
i < numKeys;
i++) {
2190 res->keys[
i] = c[step];
2194 child->parent = res;
2195 child->position =
i;
2196 res->getChildren()[
i] = child;
2203 child->parent = res;
2204 child->position = numKeys;
2205 res->getChildren()[numKeys] = child;
2213 template <
typename Key,
typename Comparator,
typename Allocator,
unsigned blockSize,
typename SearchStrategy,
2214 bool isSet,
typename WeakComparator,
typename Updater>
2215 const SearchStrategy
2229 template <
typename Key,
typename Comparator = detail::comparator<Key>,
2230 typename Allocator = std::allocator<Key>,
2231 unsigned blockSize = 256,
2232 typename SearchStrategy =
typename souffle::detail::default_strategy<Key>::type,
2233 typename WeakComparator = Comparator,
typename Updater = souffle::detail::updater<Key>>
2234 class btree_set :
public souffle::detail::btree<Key, Comparator, Allocator, blockSize, SearchStrategy, true,
2235 WeakComparator, Updater> {
2237 WeakComparator, Updater>;
2240 WeakComparator, Updater>;
2252 template <
typename Iter>
2265 template <
typename s,
typename n,
typename l>
2271 super::operator=(other);
2276 template <
typename Iter>
2278 return super::template load<btree_set>(a,
b);
2291 template <
typename Key,
typename Comparator = detail::comparator<Key>,
2292 typename Allocator = std::allocator<Key>,
2293 unsigned blockSize = 256,
2294 typename SearchStrategy =
typename souffle::detail::default_strategy<Key>::type,
2295 typename WeakComparator = Comparator,
typename Updater = souffle::detail::updater<Key>>
2297 false, WeakComparator, Updater> {
2299 WeakComparator, Updater>;
2302 WeakComparator, Updater>;
2314 template <
typename Iter>
2327 template <
typename s,
typename n,
typename l>
2333 super::operator=(other);
2338 template <
typename Iter>
2340 return super::template load<btree_multiset>(a,
b);