souffle  2.0.2-371-g6315b36
BTree.h
Go to the documentation of this file.
1 /*
2  * Souffle - A Datalog Compiler
3  * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved
4  * Licensed under the Universal Permissive License v 1.0 as shown at:
5  * - https://opensource.org/licenses/UPL
6  * - <souffle root>/licenses/SOUFFLE-UPL.txt
7  */
8 
9 /************************************************************************
10  *
11  * @file BTree.h
12  *
13  * An implementation of a generic B-tree data structure including
14  * interfaces for utilizing instances as set or multiset containers.
15  *
16  ***********************************************************************/
17 
18 #pragma once
19 
23 #include <algorithm>
24 #include <cassert>
25 #include <cstddef>
26 #include <cstdint>
27 #include <iostream>
28 #include <iterator>
29 #include <string>
30 #include <tuple>
31 #include <type_traits>
32 #include <typeinfo>
33 #include <vector>
34 
35 namespace souffle {
36 
37 namespace detail {
38 
39 // ---------- comparators --------------
40 
41 /**
42  * A generic comparator implementation as it is used by
43  * a b-tree based on types that can be less-than and
44  * equality comparable.
45  */
46 template <typename T>
47 struct comparator {
48  /**
49  * Compares the values of a and b and returns
50  * -1 if a<b, 1 if a>b and 0 otherwise
51  */
52  int operator()(const T& a, const T& b) const {
53  return (a > b) - (a < b);
54  }
55  bool less(const T& a, const T& b) const {
56  return a < b;
57  }
58  bool equal(const T& a, const T& b) const {
59  return a == b;
60  }
61 };
62 
63 // ---------- search strategies --------------
64 
65 /**
66  * A common base class for search strategies in b-trees.
67  */
68 struct search_strategy {};
69 
70 /**
71  * A linear search strategy for looking up keys in b-tree nodes.
72  */
73 struct linear_search : public search_strategy {
74  /**
75  * Required user-defined default constructor.
76  */
77  linear_search() = default;
78 
79  /**
80  * Obtains an iterator referencing an element equivalent to the
81  * given key in the given range. If no such element is present,
82  * a reference to the first element not less than the given key
83  * is returned.
84  */
85  template <typename Key, typename Iter, typename Comp>
86  inline Iter operator()(const Key& k, Iter a, Iter b, Comp& comp) const {
87  return lower_bound(k, a, b, comp);
88  }
89 
90  /**
91  * Obtains a reference to the first element in the given range that
92  * is not less than the given key.
93  */
94  template <typename Key, typename Iter, typename Comp>
95  inline Iter lower_bound(const Key& k, Iter a, Iter b, Comp& comp) const {
96  auto c = a;
97  while (c < b) {
98  auto r = comp(*c, k);
99  if (r >= 0) {
100  return c;
101  }
102  ++c;
103  }
104  return b;
105  }
106 
107  /**
108  * Obtains a reference to the first element in the given range that
109  * such that the given key is less than the referenced element.
110  */
111  template <typename Key, typename Iter, typename Comp>
112  inline Iter upper_bound(const Key& k, Iter a, Iter b, Comp& comp) const {
113  auto c = a;
114  while (c < b) {
115  if (comp(*c, k) > 0) {
116  return c;
117  }
118  ++c;
119  }
120  return b;
121  }
122 };
123 
124 /**
125  * A binary search strategy for looking up keys in b-tree nodes.
126  */
127 struct binary_search : public search_strategy {
128  /**
129  * Required user-defined default constructor.
130  */
131  binary_search() = default;
132 
133  /**
134  * Obtains an iterator pointing to some element within the given
135  * range that is equal to the given key, if available. If multiple
136  * elements are equal to the given key, an undefined instance will
137  * be obtained (no guaranteed lower or upper boundary). If no such
138  * element is present, a reference to the first element not less than
139  * the given key will be returned.
140  */
141  template <typename Key, typename Iter, typename Comp>
142  Iter operator()(const Key& k, Iter a, Iter b, Comp& comp) const {
143  Iter c;
144  auto count = b - a;
145  while (count > 0) {
146  auto step = count >> 1;
147  c = a + step;
148  auto r = comp(*c, k);
149  if (r == 0) {
150  return c;
151  }
152  if (r < 0) {
153  a = ++c;
154  count -= step + 1;
155  } else {
156  count = step;
157  }
158  }
159  return a;
160  }
161 
162  /**
163  * Obtains a reference to the first element in the given range that
164  * is not less than the given key.
165  */
166  template <typename Key, typename Iter, typename Comp>
167  Iter lower_bound(const Key& k, Iter a, Iter b, Comp& comp) const {
168  Iter c;
169  auto count = b - a;
170  while (count > 0) {
171  auto step = count >> 1;
172  c = a + step;
173  if (comp(*c, k) < 0) {
174  a = ++c;
175  count -= step + 1;
176  } else {
177  count = step;
178  }
179  }
180  return a;
181  }
182 
183  /**
184  * Obtains a reference to the first element in the given range that
185  * such that the given key is less than the referenced element.
186  */
187  template <typename Key, typename Iter, typename Comp>
188  Iter upper_bound(const Key& k, Iter a, Iter b, Comp& comp) const {
189  Iter c;
190  auto count = b - a;
191  while (count > 0) {
192  auto step = count >> 1;
193  c = a + step;
194  if (comp(k, *c) >= 0) {
195  a = ++c;
196  count -= step + 1;
197  } else {
198  count = step;
199  }
200  }
201  return a;
202  }
203 };
204 
205 // ---------- search strategies selection --------------
206 
207 /**
208  * A template-meta class to select search strategies for b-trees
209  * depending on the key type.
210  */
211 template <typename S>
212 struct strategy_selection {
213  using type = S;
214 };
215 
216 struct linear : public strategy_selection<linear_search> {};
217 struct binary : public strategy_selection<binary_search> {};
218 
219 // by default every key utilizes binary search
220 template <typename Key>
221 struct default_strategy : public binary {};
222 
223 template <>
224 struct default_strategy<int> : public linear {};
225 
226 template <typename... Ts>
227 struct default_strategy<std::tuple<Ts...>> : public linear {};
228 
229 /**
230  * The default non-updater
231  */
232 template <typename T>
233 struct updater {
234  void update(T& /* old_t */, const T& /* new_t */) {}
235 };
236 
237 /**
238  * The actual implementation of a b-tree data structure.
239  *
240  * @tparam Key .. the element type to be stored in this tree
241  * @tparam Comparator .. a class defining an order on the stored elements
242  * @tparam Allocator .. utilized for allocating memory for required nodes
243  * @tparam blockSize .. determines the number of bytes/block utilized by leaf nodes
244  * @tparam SearchStrategy .. enables switching between linear, binary or any other search strategy
245  * @tparam isSet .. true = set, false = multiset
246  */
247 template <typename Key, typename Comparator,
248  typename Allocator, // is ignored so far - TODO: add support
249  unsigned blockSize, typename SearchStrategy, bool isSet, typename WeakComparator = Comparator,
250  typename Updater = detail::updater<Key>>
251 class btree {
252 public:
253  class iterator;
254  using const_iterator = iterator;
255 
256  using key_type = Key;
257  using element_type = Key;
258  using chunk = range<iterator>;
259 
260 protected:
261  /* ------------- static utilities ----------------- */
262 
263  const static SearchStrategy search;
264 
265  /* ---------- comparison utilities ---------------- */
266 
267  mutable Comparator comp;
268 
269  bool less(const Key& a, const Key& b) const {
270  return comp.less(a, b);
271  }
272 
273  bool equal(const Key& a, const Key& b) const {
274  return comp.equal(a, b);
275  }
276 
277  mutable WeakComparator weak_comp;
278 
279  bool weak_less(const Key& a, const Key& b) const {
280  return weak_comp.less(a, b);
281  }
282 
283  bool weak_equal(const Key& a, const Key& b) const {
284  return weak_comp.equal(a, b);
285  }
286 
287  /* -------------- updater utilities ------------- */
288 
289  mutable Updater upd;
290  void update(Key& old_k, const Key& new_k) {
291  upd.update(old_k, new_k);
292  }
293 
294  /* -------------- the node type ----------------- */
295 
296  using size_type = std::size_t;
297  using field_index_type = uint8_t;
299 
300  struct node;
301 
302  /**
303  * The base type of all node types containing essential
304  * book-keeping information.
305  */
306  struct base {
307 #ifdef IS_PARALLEL
308 
309  // the parent node
310  node* volatile parent;
311 
312  // a lock for synchronizing parallel operations on this node
313  lock_type lock;
314 
315  // the number of keys in this node
316  volatile size_type numElements;
317 
318  // the position in the parent node
319  volatile field_index_type position;
320 #else
321  // the parent node
322  node* parent;
323 
324  // the number of keys in this node
326 
327  // the position in the parent node
329 #endif
330 
331  // a flag indicating whether this is a inner node or not
332  const bool inner;
333 
334  /**
335  * A simple constructor for nodes
336  */
337  base(bool inner) : parent(nullptr), numElements(0), position(0), inner(inner) {}
338 
339  bool isLeaf() const {
340  return !inner;
341  }
342 
343  bool isInner() const {
344  return inner;
345  }
346 
347  node* getParent() const {
348  return parent;
349  }
350 
352  return position;
353  }
354 
355  size_type getNumElements() const {
356  return numElements;
357  }
358  };
359 
360  struct inner_node;
361 
362  /**
363  * The actual, generic node implementation covering the operations
364  * for both, inner and leaf nodes.
365  */
366  struct node : public base {
367  /**
368  * The number of keys/node desired by the user.
369  */
370  static constexpr size_t desiredNumKeys =
371  ((blockSize > sizeof(base)) ? blockSize - sizeof(base) : 0) / sizeof(Key);
372 
373  /**
374  * The actual number of keys/node corrected by functional requirements.
375  */
376  static constexpr size_t maxKeys = (desiredNumKeys > 3) ? desiredNumKeys : 3;
377 
378  // the keys stored in this node
379  Key keys[maxKeys];
380 
381  // a simple constructor
382  node(bool inner) : base(inner) {}
383 
384  /**
385  * A deep-copy operation creating a clone of this node.
386  */
387  node* clone() const {
388  // create a clone of this node
389  node* res = (this->isInner()) ? static_cast<node*>(new inner_node())
390  : static_cast<node*>(new leaf_node());
391 
392  // copy basic fields
393  res->position = this->position;
394  res->numElements = this->numElements;
395 
396  for (size_type i = 0; i < this->numElements; ++i) {
397  res->keys[i] = this->keys[i];
398  }
399 
400  // if this is a leaf we are done
401  if (this->isLeaf()) {
402  return res;
403  }
404 
405  // copy child nodes recursively
406  auto* ires = (inner_node*)res;
407  for (size_type i = 0; i <= this->numElements; ++i) {
408  ires->children[i] = this->getChild(i)->clone();
409  ires->children[i]->parent = res;
410  }
411 
412  // that's it
413  return res;
414  }
415 
416  /**
417  * A utility function providing a reference to this node as
418  * an inner node.
419  */
420  inner_node& asInnerNode() {
421  assert(this->inner && "Invalid cast!");
422  return *static_cast<inner_node*>(this);
423  }
424 
425  /**
426  * A utility function providing a reference to this node as
427  * a const inner node.
428  */
429  const inner_node& asInnerNode() const {
430  assert(this->inner && "Invalid cast!");
431  return *static_cast<const inner_node*>(this);
432  }
433 
434  /**
435  * Computes the number of nested levels of the tree rooted
436  * by this node.
437  */
438  size_type getDepth() const {
439  if (this->isLeaf()) {
440  return 1;
441  }
442  return getChild(0)->getDepth() + 1;
443  }
444 
445  /**
446  * Counts the number of nodes contained in the sub-tree rooted
447  * by this node.
448  */
449  size_type countNodes() const {
450  if (this->isLeaf()) {
451  return 1;
452  }
453  size_type sum = 1;
454  for (unsigned i = 0; i <= this->numElements; ++i) {
455  sum += getChild(i)->countNodes();
456  }
457  return sum;
458  }
459 
460  /**
461  * Counts the number of entries contained in the sub-tree rooted
462  * by this node.
463  */
464  size_type countEntries() const {
465  if (this->isLeaf()) {
466  return this->numElements;
467  }
468  size_type sum = this->numElements;
469  for (unsigned i = 0; i <= this->numElements; ++i) {
470  sum += getChild(i)->countEntries();
471  }
472  return sum;
473  }
474 
475  /**
476  * Determines the amount of memory used by the sub-tree rooted
477  * by this node.
478  */
479  size_type getMemoryUsage() const {
480  if (this->isLeaf()) {
481  return sizeof(leaf_node);
482  }
483  size_type res = sizeof(inner_node);
484  for (unsigned i = 0; i <= this->numElements; ++i) {
485  res += getChild(i)->getMemoryUsage();
486  }
487  return res;
488  }
489 
490  /**
491  * Obtains a pointer to the array of child-pointers
492  * of this node -- if it is an inner node.
493  */
494  node** getChildren() {
495  return asInnerNode().children;
496  }
497 
498  /**
499  * Obtains a pointer to the array of const child-pointers
500  * of this node -- if it is an inner node.
501  */
502  node* const* getChildren() const {
503  return asInnerNode().children;
504  }
505 
506  /**
507  * Obtains a reference to the child of the given index.
508  */
509  node* getChild(size_type s) const {
510  return asInnerNode().children[s];
511  }
512 
513  /**
514  * Checks whether this node is empty -- can happen due to biased insertion.
515  */
516  bool isEmpty() const {
517  return this->numElements == 0;
518  }
519 
520  /**
521  * Checks whether this node is full.
522  */
523  bool isFull() const {
524  return this->numElements == maxKeys;
525  }
526 
527  /**
528  * Obtains the point at which full nodes should be split.
529  * Conventional b-trees always split in half. However, in cases
530  * where in-order insertions are frequent, a split assigning
531  * larger portions to the right fragment provide higher performance
532  * and a better node-filling rate.
533  */
534  int getSplitPoint(int /*unused*/) {
535  return static_cast<int>(std::min(3 * maxKeys / 4, maxKeys - 2));
536  }
537 
538  /**
539  * Splits this node.
540  *
541  * @param root .. a pointer to the root-pointer of the enclosing b-tree
542  * (might have to be updated if the root-node needs to be split)
543  * @param idx .. the position of the insert causing the split
544  */
545 #ifdef IS_PARALLEL
546  void split(node** root, lock_type& root_lock, int idx, std::vector<node*>& locked_nodes) {
547  assert(this->lock.is_write_locked());
548  assert(!this->parent || this->parent->lock.is_write_locked());
549  assert((this->parent != nullptr) || root_lock.is_write_locked());
550  assert(this->isLeaf() || souffle::contains(locked_nodes, this));
551  assert(!this->parent || souffle::contains(locked_nodes, const_cast<node*>(this->parent)));
552 #else
553  void split(node** root, lock_type& root_lock, int idx) {
554 #endif
555  assert(this->numElements == maxKeys);
556 
557  // get middle element
558  int split_point = getSplitPoint(idx);
559 
560  // create a new sibling node
561  node* sibling = (this->inner) ? static_cast<node*>(new inner_node())
562  : static_cast<node*>(new leaf_node());
563 
564 #ifdef IS_PARALLEL
565  // lock sibling
566  sibling->lock.start_write();
567  locked_nodes.push_back(sibling);
568 #endif
569 
570  // move data over to the new node
571  for (unsigned i = split_point + 1, j = 0; i < maxKeys; ++i, ++j) {
572  sibling->keys[j] = keys[i];
573  }
574 
575  // move child pointers
576  if (this->inner) {
577  // move pointers to sibling
578  auto* other = static_cast<inner_node*>(sibling);
579  for (unsigned i = split_point + 1, j = 0; i <= maxKeys; ++i, ++j) {
580  other->children[j] = getChildren()[i];
581  other->children[j]->parent = other;
582  other->children[j]->position = static_cast<field_index_type>(j);
583  }
584  }
585 
586  // update number of elements
587  this->numElements = split_point;
588  sibling->numElements = maxKeys - split_point - 1;
589 
590  // update parent
591 #ifdef IS_PARALLEL
592  grow_parent(root, root_lock, sibling, locked_nodes);
593 #else
594  grow_parent(root, root_lock, sibling);
595 #endif
596  }
597 
598  /**
599  * Moves keys from this node to one of its siblings or splits
600  * this node to make some space for the insertion of an element at
601  * position idx.
602  *
603  * Returns the number of elements moved to the left side, 0 in case
604  * of a split. The number of moved elements will be <= the given idx.
605  *
606  * @param root .. the root node of the b-tree being part of
607  * @param idx .. the position of the insert triggering this operation
608  */
609  // TODO: remove root_lock ... no longer needed
610 #ifdef IS_PARALLEL
611  int rebalance_or_split(node** root, lock_type& root_lock, int idx, std::vector<node*>& locked_nodes) {
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());
615  assert(this->isLeaf() || souffle::contains(locked_nodes, this));
616  assert(!this->parent || souffle::contains(locked_nodes, const_cast<node*>(this->parent)));
617 #else
618  int rebalance_or_split(node** root, lock_type& root_lock, int idx) {
619 #endif
620 
621  // this node is full ... and needs some space
622  assert(this->numElements == maxKeys);
623 
624  // get snap-shot of parent
625  auto parent = this->parent;
626  auto pos = this->position;
627 
628  // Option A) re-balance data
629  if (parent && pos > 0) {
630  node* left = parent->getChild(pos - 1);
631 
632 #ifdef IS_PARALLEL
633  // lock access to left sibling
634  if (!left->lock.try_start_write()) {
635  // left node is currently updated => skip balancing and split
636  split(root, root_lock, idx, locked_nodes);
637  return 0;
638  }
639 #endif
640 
641  // compute number of elements to be movable to left
642  // space available in left vs. insertion index
643  size_type num = static_cast<size_type>(
644  std::min<int>(static_cast<int>(maxKeys - left->numElements), idx));
645 
646  // if there are elements to move ..
647  if (num > 0) {
648  Key* splitter = &(parent->keys[this->position - 1]);
649 
650  // .. move keys to left node
651  left->keys[left->numElements] = *splitter;
652  for (size_type i = 0; i < num - 1; ++i) {
653  left->keys[left->numElements + 1 + i] = keys[i];
654  }
655  *splitter = keys[num - 1];
656 
657  // shift keys in this node to the left
658  for (size_type i = 0; i < this->numElements - num; ++i) {
659  keys[i] = keys[i + num];
660  }
661 
662  // .. and children if necessary
663  if (this->isInner()) {
664  auto* ileft = static_cast<inner_node*>(left);
665  auto* iright = static_cast<inner_node*>(this);
666 
667  // move children
668  for (field_index_type i = 0; i < num; ++i) {
669  ileft->children[left->numElements + i + 1] = iright->children[i];
670  }
671 
672  // update moved children
673  for (size_type i = 0; i < num; ++i) {
674  iright->children[i]->parent = ileft;
675  iright->children[i]->position =
676  static_cast<field_index_type>(left->numElements + i) + 1;
677  }
678 
679  // shift child-pointer to the left
680  for (size_type i = 0; i < this->numElements - num + 1; ++i) {
681  iright->children[i] = iright->children[i + num];
682  }
683 
684  // update position of children
685  for (size_type i = 0; i < this->numElements - num + 1; ++i) {
686  iright->children[i]->position = static_cast<field_index_type>(i);
687  }
688  }
689 
690  // update node sizes
691  left->numElements += num;
692  this->numElements -= num;
693 
694 #ifdef IS_PARALLEL
695  left->lock.end_write();
696 #endif
697 
698  // done
699  return static_cast<int>(num);
700  }
701 
702 #ifdef IS_PARALLEL
703  left->lock.abort_write();
704 #endif
705  }
706 
707  // Option B) split node
708 #ifdef IS_PARALLEL
709  split(root, root_lock, idx, locked_nodes);
710 #else
711  split(root, root_lock, idx);
712 #endif
713  return 0; // = no re-balancing
714  }
715 
716  private:
717  /**
718  * Inserts a new sibling into the parent of this node utilizing
719  * the last key of this node as a separation key. (for internal
720  * use only)
721  *
722  * @param root .. a pointer to the root-pointer of the containing tree
723  * @param sibling .. the new right-sibling to be add to the parent node
724  */
725 #ifdef IS_PARALLEL
726  void grow_parent(node** root, lock_type& root_lock, node* sibling, std::vector<node*>& locked_nodes) {
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());
730  assert(this->isLeaf() || souffle::contains(locked_nodes, this));
731  assert(!this->parent || souffle::contains(locked_nodes, const_cast<node*>(this->parent)));
732 #else
733  void grow_parent(node** root, lock_type& root_lock, node* sibling) {
734 #endif
735 
736  if (this->parent == nullptr) {
737  assert(*root == this);
738 
739  // create a new root node
740  auto* new_root = new inner_node();
741  new_root->numElements = 1;
742  new_root->keys[0] = keys[this->numElements];
743 
744  new_root->children[0] = this;
745  new_root->children[1] = sibling;
746 
747  // link this and the sibling node to new root
748  this->parent = new_root;
749  sibling->parent = new_root;
750  sibling->position = 1;
751 
752  // switch root node
753  *root = new_root;
754 
755  } else {
756  // insert new element in parent element
757  auto parent = this->parent;
758  auto pos = this->position;
759 
760 #ifdef IS_PARALLEL
762  root, root_lock, pos, this, keys[this->numElements], sibling, locked_nodes);
763 #else
764  parent->insert_inner(root, root_lock, pos, this, keys[this->numElements], sibling);
765 #endif
766  }
767  }
768 
769  /**
770  * Inserts a new element into an inner node (for internal use only).
771  *
772  * @param root .. a pointer to the root-pointer of the containing tree
773  * @param pos .. the position to insert the new key
774  * @param key .. the key to insert
775  * @param newNode .. the new right-child of the inserted key
776  */
777 #ifdef IS_PARALLEL
778  void insert_inner(node** root, lock_type& root_lock, unsigned pos, node* predecessor, const Key& key,
779  node* newNode, std::vector<node*>& locked_nodes) {
780  assert(this->lock.is_write_locked());
781  assert(souffle::contains(locked_nodes, this));
782 #else
783  void insert_inner(node** root, lock_type& root_lock, unsigned pos, node* predecessor, const Key& key,
784  node* newNode) {
785 #endif
786 
787  // check capacity
788  if (this->numElements >= maxKeys) {
789 #ifdef IS_PARALLEL
790  assert(!this->parent || this->parent->lock.is_write_locked());
791  assert((this->parent) || root_lock.is_write_locked());
792  assert(!this->parent || souffle::contains(locked_nodes, const_cast<node*>(this->parent)));
793 #endif
794 
795  // split this node
796 #ifdef IS_PARALLEL
797  pos -= rebalance_or_split(root, root_lock, pos, locked_nodes);
798 #else
799  pos -= rebalance_or_split(root, root_lock, pos);
800 #endif
801 
802  // complete insertion within new sibling if necessary
803  if (pos > this->numElements) {
804  // correct position
805  pos = pos - static_cast<unsigned int>(this->numElements) - 1;
806 
807  // get new sibling
808  auto other = this->parent->getChild(this->position + 1);
809 
810 #ifdef IS_PARALLEL
811  // make sure other side is write locked
812  assert(other->lock.is_write_locked());
813  assert(souffle::contains(locked_nodes, other));
814 
815  // search for new position (since other may have been altered in the meanwhile)
816  size_type i = 0;
817  for (; i <= other->numElements; ++i) {
818  if (other->getChild(i) == predecessor) {
819  break;
820  }
821  }
822 
823  pos = (i > other->numElements) ? 0 : i;
824  other->insert_inner(root, root_lock, pos, predecessor, key, newNode, locked_nodes);
825 #else
826  other->insert_inner(root, root_lock, pos, predecessor, key, newNode);
827 #endif
828  return;
829  }
830  }
831 
832  // move bigger keys one forward
833  for (int i = static_cast<int>(this->numElements) - 1; i >= (int)pos; --i) {
834  keys[i + 1] = keys[i];
835  getChildren()[i + 2] = getChildren()[i + 1];
836  ++getChildren()[i + 2]->position;
837  }
838 
839  // ensure proper position
840  assert(getChild(pos) == predecessor);
841 
842  // insert new element
843  keys[pos] = key;
844  getChildren()[pos + 1] = newNode;
845  newNode->parent = this;
846  newNode->position = static_cast<field_index_type>(pos) + 1;
847  ++this->numElements;
848  }
849 
850  public:
851  /**
852  * Prints a textual representation of this tree to the given output stream.
853  * This feature is mainly intended for debugging and tuning purposes.
854  *
855  * @see btree::printTree
856  */
857  void printTree(std::ostream& out, const std::string& prefix) const {
858  // print the header
859  out << prefix << "@" << this << "[" << ((int)(this->position)) << "] - "
860  << (this->inner ? "i" : "") << "node : " << this->numElements << "/" << maxKeys << " [";
861 
862  // print the keys
863  for (unsigned i = 0; i < this->numElements; i++) {
864  out << keys[i];
865  if (i != this->numElements - 1) {
866  out << ",";
867  }
868  }
869  out << "]";
870 
871  // print references to children
872  if (this->inner) {
873  out << " - [";
874  for (unsigned i = 0; i <= this->numElements; i++) {
875  out << getChildren()[i];
876  if (i != this->numElements) {
877  out << ",";
878  }
879  }
880  out << "]";
881  }
882 
883 #ifdef IS_PARALLEL
884  // print the lock state
885  if (this->lock.is_write_locked()) {
886  std::cout << " locked";
887  }
888 #endif
889 
890  out << "\n";
891 
892  // print the children recursively
893  if (this->inner) {
894  for (unsigned i = 0; i < this->numElements + 1; ++i) {
895  static_cast<const inner_node*>(this)->children[i]->printTree(out, prefix + " ");
896  }
897  }
898  }
899 
900  /**
901  * A function decomposing the sub-tree rooted by this node into approximately equally
902  * sized chunks. To minimize computational overhead, no strict load balance nor limit
903  * on the number of actual chunks is given.
904  *
905  * @see btree::getChunks()
906  *
907  * @param res .. the list of chunks to be extended
908  * @param num .. the number of chunks to be produced
909  * @param begin .. the iterator to start the first chunk with
910  * @param end .. the iterator to end the last chunk with
911  * @return the handed in list of chunks extended by generated chunks
912  */
913  std::vector<chunk>& collectChunks(
914  std::vector<chunk>& res, size_type num, const iterator& begin, const iterator& end) const {
915  assert(num > 0);
916 
917  // special case: this node is empty
918  if (isEmpty()) {
919  if (begin != end) {
920  res.push_back(chunk(begin, end));
921  }
922  return res;
923  }
924 
925  // special case: a single chunk is requested
926  if (num == 1) {
927  res.push_back(chunk(begin, end));
928  return res;
929  }
930 
931  // cut-off
932  if (this->isLeaf() || num < (this->numElements + 1)) {
933  auto step = this->numElements / num;
934  if (step == 0) {
935  step = 1;
936  }
937 
938  size_type i = 0;
939 
940  // the first chunk starts at the begin
941  res.push_back(chunk(begin, iterator(this, static_cast<field_index_type>(step) - 1)));
942 
943  // split up the main part
944  for (i = step - 1; i < this->numElements - step; i += step) {
945  res.push_back(chunk(iterator(this, static_cast<field_index_type>(i)),
946  iterator(this, static_cast<field_index_type>(i + step))));
947  }
948 
949  // the last chunk runs to the end
950  res.push_back(chunk(iterator(this, static_cast<field_index_type>(i)), end));
951 
952  // done
953  return res;
954  }
955 
956  // else: collect chunks of sub-set elements
957 
958  auto part = num / (this->numElements + 1);
959  assert(part > 0);
960  getChild(0)->collectChunks(res, part, begin, iterator(this, 0));
961  for (size_type i = 1; i < this->numElements; i++) {
962  getChild(i)->collectChunks(res, part, iterator(this, static_cast<field_index_type>(i - 1)),
963  iterator(this, static_cast<field_index_type>(i)));
964  }
965  getChild(this->numElements)
966  ->collectChunks(res, num - (part * this->numElements),
967  iterator(this, static_cast<field_index_type>(this->numElements) - 1), end);
968 
969  // done
970  return res;
971  }
972 
973  /**
974  * A function to verify the consistency of this node.
975  *
976  * @param root ... a reference to the root of the enclosing tree.
977  * @return true if valid, false otherwise
978  */
979  template <typename Comp>
980  bool check(Comp& comp, const node* root) const {
981  bool valid = true;
982 
983  // check fill-state
984  if (this->numElements > maxKeys) {
985  std::cout << "Node with " << this->numElements << "/" << maxKeys << " encountered!\n";
986  valid = false;
987  }
988 
989  // check root state
990  if (root == this) {
991  if (this->parent != nullptr) {
992  std::cout << "Root not properly linked!\n";
993  valid = false;
994  }
995  } else {
996  // check parent relation
997  if (!this->parent) {
998  std::cout << "Invalid null-parent!\n";
999  valid = false;
1000  } else {
1001  if (this->parent->getChildren()[this->position] != this) {
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";
1006  valid = false;
1007  }
1008 
1009  // check parent key
1010  if (valid && this->position != 0 &&
1011  !(comp(this->parent->keys[this->position - 1], keys[0]) < ((isSet) ? 0 : 1))) {
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";
1016  std::cout << " Key: " << (this->parent->keys[this->position]) << "\n";
1017  std::cout << " Lower: " << (keys[0]) << "\n";
1018  valid = false;
1019  }
1020 
1021  // check parent key
1022  if (valid && this->position != this->parent->numElements &&
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";
1029  std::cout << " Key: " << (this->parent->keys[this->position]) << "\n";
1030  std::cout << " Upper: " << (keys[0]) << "\n";
1031  valid = false;
1032  }
1033  }
1034  }
1035 
1036  // check element order
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";
1043  valid = false;
1044  }
1045  }
1046  }
1047 
1048  // check state of sub-nodes
1049  if (this->inner) {
1050  for (unsigned i = 0; i <= this->numElements; i++) {
1051  valid &= getChildren()[i]->check(comp, root);
1052  }
1053  }
1054 
1055  return valid;
1056  }
1057  }; // namespace detail
1058 
1059  /**
1060  * The data type representing inner nodes of the b-tree. It extends
1061  * the generic implementation of a node by the storage locations
1062  * of child pointers.
1063  */
1064  struct inner_node : public node {
1065  // references to child nodes owned by this node
1066  node* children[node::maxKeys + 1];
1067 
1068  // a simple default constructor initializing member fields
1069  inner_node() : node(true) {}
1070 
1071  // clear up child nodes recursively
1072  ~inner_node() {
1073  for (unsigned i = 0; i <= this->numElements; ++i) {
1074  if (children[i] != nullptr) {
1075  if (children[i]->isLeaf()) {
1076  delete static_cast<leaf_node*>(children[i]);
1077  } else {
1078  delete static_cast<inner_node*>(children[i]);
1079  }
1080  }
1081  }
1082  }
1083  };
1084 
1085  /**
1086  * The data type representing leaf nodes of the b-tree. It does not
1087  * add any capabilities to the generic node type.
1088  */
1089  struct leaf_node : public node {
1090  // a simple default constructor initializing member fields
1091  leaf_node() : node(false) {}
1092  };
1093 
1094  // ------------------- iterators ------------------------
1095 
1096 public:
1097  /**
1098  * The iterator type to be utilized for scanning through btree instances.
1099  */
1100  class iterator {
1101  // a pointer to the node currently referred to
1102  node const* cur;
1104  // the index of the element currently addressed within the referenced node
1106 
1107  public:
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&;
1113 
1114  // default constructor -- creating an end-iterator
1115  iterator() : cur(nullptr) {}
1117  // creates an iterator referencing a specific element within a given node
1118  iterator(node const* cur, field_index_type pos) : cur(cur), pos(pos) {}
1120  // a copy constructor
1121  iterator(const iterator& other) : cur(other.cur), pos(other.pos) {}
1123  // an assignment operator
1124  iterator& operator=(const iterator& other) {
1125  cur = other.cur;
1126  pos = other.pos;
1127  return *this;
1128  }
1130  // the equality operator as required by the iterator concept
1131  bool operator==(const iterator& other) const {
1132  return cur == other.cur && pos == other.pos;
1133  }
1134 
1135  // the not-equality operator as required by the iterator concept
1136  bool operator!=(const iterator& other) const {
1137  return !(*this == other);
1138  }
1139 
1140  // the deref operator as required by the iterator concept
1141  const Key& operator*() const {
1142  return cur->keys[pos];
1143  }
1144 
1145  // the increment operator as required by the iterator concept
1146  iterator& operator++() {
1147  // the quick mode -- if in a leaf and there are elements left
1148  if (cur->isLeaf() && ++pos < cur->getNumElements()) {
1149  return *this;
1150  }
1151 
1152  // otherwise it is a bit more tricky
1153 
1154  // A) currently in an inner node => go to the left-most child
1155  if (cur->isInner()) {
1156  cur = cur->getChildren()[pos + 1];
1157  while (!cur->isLeaf()) {
1158  cur = cur->getChildren()[0];
1159  }
1160  pos = 0;
1161 
1162  // nodes may be empty due to biased insertion
1163  if (!cur->isEmpty()) {
1164  return *this;
1165  }
1166  }
1167 
1168  // B) we are at the right-most element of a leaf => go to next inner node
1169  assert(cur->isLeaf());
1170  assert(pos == cur->getNumElements());
1171 
1172  while (cur != nullptr && pos == cur->getNumElements()) {
1173  pos = cur->getPositionInParent();
1174  cur = cur->getParent();
1175  }
1176  return *this;
1177  }
1178 
1179  // prints a textual representation of this iterator to the given stream (mainly for debugging)
1180  void print(std::ostream& out = std::cout) const {
1181  out << cur << "[" << (int)pos << "]";
1182  }
1183  };
1184 
1185  /**
1186  * A collection of operation hints speeding up some of the involved operations
1187  * by exploiting temporal locality.
1188  */
1189  template <unsigned size = 1>
1190  struct btree_operation_hints {
1191  using node_cache = LRUCache<node*, size>;
1192 
1193  // the node where the last insertion terminated
1194  node_cache last_insert;
1195 
1196  // the node where the last find-operation terminated
1197  node_cache last_find_end;
1198 
1199  // the node where the last lower-bound operation terminated
1200  node_cache last_lower_bound_end;
1201 
1202  // the node where the last upper-bound operation terminated
1203  node_cache last_upper_bound_end;
1205  // default constructor
1206  btree_operation_hints() = default;
1207 
1208  // resets all hints (to be triggered e.g. when deleting nodes)
1209  void clear() {
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);
1214  }
1215  };
1216 
1218 
1219 protected:
1220 #ifdef IS_PARALLEL
1221  // a pointer to the root node of this tree
1222  node* volatile root;
1224  // a lock to synchronize update operations on the root pointer
1226 #else
1227  // a pointer to the root node of this tree
1228  node* root;
1229 
1230  // required to not duplicate too much code
1232 #endif
1233 
1234  // a pointer to the left-most node of this tree (initial note for iteration)
1235  leaf_node* leftmost;
1236 
1237  /* -------------- operator hint statistics ----------------- */
1238 
1239  // an aggregation of statistical values of the hint utilization
1240  struct hint_statistics {
1241  // the counter for insertion operations
1243 
1244  // the counter for contains operations
1246 
1247  // the counter for lower_bound operations
1250  // the counter for upper_bound operations
1252  };
1253 
1254  // the hint statistic of this b-tree instance
1255  mutable hint_statistics hint_stats;
1257 public:
1258  // the maximum number of keys stored per node
1259  static constexpr size_t max_keys_per_node = node::maxKeys;
1260 
1261  // -- ctors / dtors --
1263  // the default constructor creating an empty tree
1264  btree(Comparator comp = Comparator(), WeakComparator weak_comp = WeakComparator())
1265  : comp(std::move(comp)), weak_comp(std::move(weak_comp)), root(nullptr), leftmost(nullptr) {}
1266 
1267  // a constructor creating a tree from the given iterator range
1268  template <typename Iter>
1269  btree(const Iter& a, const Iter& b) : root(nullptr), leftmost(nullptr) {
1270  insert(a, b);
1271  }
1272 
1273  // a move constructor
1274  btree(btree&& other)
1275  : comp(other.comp), weak_comp(other.weak_comp), root(other.root), leftmost(other.leftmost) {
1276  other.root = nullptr;
1277  other.leftmost = nullptr;
1278  }
1279 
1280  // a copy constructor
1281  btree(const btree& set) : comp(set.comp), weak_comp(set.weak_comp), root(nullptr), leftmost(nullptr) {
1282  // use assignment operator for a deep copy
1283  *this = set;
1284  }
1285 
1286 protected:
1287  /**
1288  * An internal constructor enabling the specific creation of a tree
1289  * based on internal parameters.
1290  */
1291  btree(size_type /* size */, node* root, leaf_node* leftmost) : root(root), leftmost(leftmost) {}
1292 
1293 public:
1294  // the destructor freeing all contained nodes
1296  clear();
1297  }
1298 
1299  // -- mutators and observers --
1300 
1301  // emptiness check
1302  bool empty() const {
1303  return root == nullptr;
1304  }
1306  // determines the number of elements in this tree
1307  size_type size() const {
1308  return (root) ? root->countEntries() : 0;
1309  }
1310 
1311  /**
1312  * Inserts the given key into this tree.
1313  */
1314  bool insert(const Key& k) {
1315  operation_hints hints;
1316  return insert(k, hints);
1317  }
1318 
1319  /**
1320  * Inserts the given key into this tree.
1321  */
1322  bool insert(const Key& k, operation_hints& hints) {
1323 #ifdef IS_PARALLEL
1324 
1325  // special handling for inserting first element
1326  while (root == nullptr) {
1327  // try obtaining root-lock
1329  // somebody else was faster => re-check
1330  continue;
1331  }
1332 
1333  // check loop condition again
1334  if (root != nullptr) {
1335  // somebody else was faster => normal insert
1337  break;
1338  }
1339 
1340  // create new node
1341  leftmost = new leaf_node();
1342  leftmost->numElements = 1;
1343  leftmost->keys[0] = k;
1344  root = leftmost;
1345 
1346  // operation complete => we can release the root lock
1347  root_lock.end_write();
1348 
1349  hints.last_insert.access(leftmost);
1350 
1351  return true;
1352  }
1353 
1354  // insert using iterative implementation
1355 
1356  node* cur = nullptr;
1357 
1358  // test last insert hints
1359  lock_type::Lease cur_lease;
1360 
1361  auto checkHint = [&](node* last_insert) {
1362  // ignore null pointer
1363  if (!last_insert) return false;
1364  // get a read lease on indicated node
1365  auto hint_lease = last_insert->lock.start_read();
1366  // check whether it covers the key
1367  if (!weak_covers(last_insert, k)) return false;
1368  // and if there was no concurrent modification
1369  if (!last_insert->lock.validate(hint_lease)) return false;
1370  // use hinted location
1371  cur = last_insert;
1372  // and keep lease
1373  cur_lease = hint_lease;
1374  // we found a hit
1375  return true;
1376  };
1377 
1378  if (hints.last_insert.any(checkHint)) {
1379  // register this as a hit
1381  } else {
1382  // register this as a miss
1384  }
1385 
1386  // if there is no valid hint ..
1387  if (!cur) {
1388  do {
1389  // get root - access lock
1390  auto root_lease = root_lock.start_read();
1391 
1392  // start with root
1393  cur = root;
1394 
1395  // get lease of the next node to be accessed
1396  cur_lease = cur->lock.start_read();
1397 
1398  // check validity of root pointer
1399  if (root_lock.end_read(root_lease)) {
1400  break;
1401  }
1402 
1403  } while (true);
1404  }
1405 
1406  while (true) {
1407  // handle inner nodes
1408  if (cur->inner) {
1409  auto a = &(cur->keys[0]);
1410  auto b = &(cur->keys[cur->numElements]);
1411 
1412  auto pos = search.lower_bound(k, a, b, weak_comp);
1413  auto idx = pos - a;
1414 
1415  // early exit for sets
1416  if (isSet && pos != b && weak_equal(*pos, k)) {
1417  // validate results
1418  if (!cur->lock.validate(cur_lease)) {
1419  // start over again
1420  return insert(k, hints);
1421  }
1422 
1423  // update provenance information
1424  if (typeid(Comparator) != typeid(WeakComparator) && less(k, *pos)) {
1425  if (!cur->lock.try_upgrade_to_write(cur_lease)) {
1426  // start again
1427  return insert(k, hints);
1428  }
1429  update(*pos, k);
1430  cur->lock.end_write();
1431  return true;
1432  }
1433 
1434  // we found the element => no check of lock necessary
1435  return false;
1436  }
1437 
1438  // get next pointer
1439  auto next = cur->getChild(idx);
1440 
1441  // get lease on next level
1442  auto next_lease = next->lock.start_read();
1443 
1444  // check whether there was a write
1445  if (!cur->lock.end_read(cur_lease)) {
1446  // start over
1447  return insert(k, hints);
1448  }
1449 
1450  // go to next
1451  cur = next;
1452 
1453  // move on lease
1454  cur_lease = next_lease;
1455 
1456  continue;
1457  }
1458 
1459  // the rest is for leaf nodes
1460  assert(!cur->inner);
1461 
1462  // -- insert node in leaf node --
1463 
1464  auto a = &(cur->keys[0]);
1465  auto b = &(cur->keys[cur->numElements]);
1466 
1467  auto pos = search.upper_bound(k, a, b, weak_comp);
1468  auto idx = pos - a;
1469 
1470  // early exit for sets
1471  if (isSet && pos != a && weak_equal(*(pos - 1), k)) {
1472  // validate result
1473  if (!cur->lock.validate(cur_lease)) {
1474  // start over again
1475  return insert(k, hints);
1476  }
1477 
1478  // update provenance information
1479  if (typeid(Comparator) != typeid(WeakComparator) && less(k, *(pos - 1))) {
1480  if (!cur->lock.try_upgrade_to_write(cur_lease)) {
1481  // start again
1482  return insert(k, hints);
1483  }
1484  update(*(pos - 1), k);
1485  cur->lock.end_write();
1486  return true;
1487  }
1488 
1489  // we found the element => done
1490  return false;
1491  }
1492 
1493  // upgrade to write-permission
1494  if (!cur->lock.try_upgrade_to_write(cur_lease)) {
1495  // something has changed => restart
1496  hints.last_insert.access(cur);
1497  return insert(k, hints);
1498  }
1499 
1500  if (cur->numElements >= node::maxKeys) {
1501  // -- lock parents --
1502  auto priv = cur;
1503  auto parent = priv->parent;
1504  std::vector<node*> parents;
1505  do {
1506  if (parent) {
1507  parent->lock.start_write();
1508  while (true) {
1509  // check whether parent is correct
1510  if (parent == priv->parent) {
1511  break;
1512  }
1513  // switch parent
1514  parent->lock.abort_write();
1515  parent = priv->parent;
1516  parent->lock.start_write();
1517  }
1518  } else {
1519  // lock root lock => since cur is root
1521  }
1522 
1523  // record locked node
1524  parents.push_back(parent);
1525 
1526  // stop at "sphere of influence"
1527  if (!parent || !parent->isFull()) {
1528  break;
1529  }
1530 
1531  // go one step higher
1532  priv = parent;
1533  parent = parent->parent;
1534 
1535  } while (true);
1536 
1537  // split this node
1538  auto old_root = root;
1539  idx -= cur->rebalance_or_split(const_cast<node**>(&root), root_lock, idx, parents);
1540 
1541  // release parent lock
1542  for (auto it = parents.rbegin(); it != parents.rend(); ++it) {
1543  auto parent = *it;
1544 
1545  // release this lock
1546  if (parent) {
1547  parent->lock.end_write();
1548  } else {
1549  if (old_root != root) {
1550  root_lock.end_write();
1551  } else {
1553  }
1554  }
1555  }
1556 
1557  // insert element in right fragment
1558  if (((size_type)idx) > cur->numElements) {
1559  // release current lock
1560  cur->lock.end_write();
1561 
1562  // insert in sibling
1563  return insert(k, hints);
1564  }
1565  }
1566 
1567  // ok - no split necessary
1568  assert(cur->numElements < node::maxKeys && "Split required!");
1569 
1570  // move keys
1571  for (int j = cur->numElements; j > idx; --j) {
1572  cur->keys[j] = cur->keys[j - 1];
1573  }
1574 
1575  // insert new element
1576  cur->keys[idx] = k;
1577  cur->numElements++;
1578 
1579  // release lock on current node
1580  cur->lock.end_write();
1581 
1582  // remember last insertion position
1583  hints.last_insert.access(cur);
1584  return true;
1585  }
1586 
1587 #else
1588  // special handling for inserting first element
1589  if (empty()) {
1590  // create new node
1591  leftmost = new leaf_node();
1592  leftmost->numElements = 1;
1593  leftmost->keys[0] = k;
1594  root = leftmost;
1595 
1596  hints.last_insert.access(leftmost);
1597 
1598  return true;
1599  }
1600 
1601  // insert using iterative implementation
1602  node* cur = root;
1603 
1604  auto checkHints = [&](node* last_insert) {
1605  if (!last_insert) return false;
1606  if (!weak_covers(last_insert, k)) return false;
1607  cur = last_insert;
1608  return true;
1609  };
1610 
1611  // test last insert
1612  if (hints.last_insert.any(checkHints)) {
1614  } else {
1616  }
1617 
1618  while (true) {
1619  // handle inner nodes
1620  if (cur->inner) {
1621  auto a = &(cur->keys[0]);
1622  auto b = &(cur->keys[cur->numElements]);
1623 
1624  auto pos = search.lower_bound(k, a, b, weak_comp);
1625  auto idx = pos - a;
1626 
1627  // early exit for sets
1628  if (isSet && pos != b && weak_equal(*pos, k)) {
1629  // update provenance information
1630  if (typeid(Comparator) != typeid(WeakComparator) && less(k, *pos)) {
1631  update(*pos, k);
1632  return true;
1633  }
1634 
1635  return false;
1636  }
1637 
1638  cur = cur->getChild(idx);
1639  continue;
1640  }
1641 
1642  // the rest is for leaf nodes
1643  assert(!cur->inner);
1644 
1645  // -- insert node in leaf node --
1646 
1647  auto a = &(cur->keys[0]);
1648  auto b = &(cur->keys[cur->numElements]);
1649 
1650  auto pos = search.upper_bound(k, a, b, weak_comp);
1651  auto idx = pos - a;
1652 
1653  // early exit for sets
1654  if (isSet && pos != a && weak_equal(*(pos - 1), k)) {
1655  // update provenance information
1656  if (typeid(Comparator) != typeid(WeakComparator) && less(k, *(pos - 1))) {
1657  update(*(pos - 1), k);
1658  return true;
1659  }
1660 
1661  return false;
1662  }
1663 
1664  if (cur->numElements >= node::maxKeys) {
1665  // split this node
1666  idx -= cur->rebalance_or_split(&root, root_lock, static_cast<int>(idx));
1667 
1668  // insert element in right fragment
1669  if (((size_type)idx) > cur->numElements) {
1670  idx -= cur->numElements + 1;
1671  cur = cur->parent->getChild(cur->position + 1);
1672  }
1673  }
1674 
1675  // ok - no split necessary
1676  assert(cur->numElements < node::maxKeys && "Split required!");
1677 
1678  // move keys
1679  for (int j = static_cast<int>(cur->numElements); j > idx; --j) {
1680  cur->keys[j] = cur->keys[j - 1];
1681  }
1682 
1683  // insert new element
1684  cur->keys[idx] = k;
1685  cur->numElements++;
1686 
1687  // remember last insertion position
1688  hints.last_insert.access(cur);
1689 
1690  return true;
1691  }
1692 #endif
1693  }
1694 
1695  /**
1696  * Inserts the given range of elements into this tree.
1697  */
1698  template <typename Iter>
1699  void insert(const Iter& a, const Iter& b) {
1700  // TODO: improve this beyond a naive insert
1701  operation_hints hints;
1702  // a naive insert so far .. seems to work fine
1703  for (auto it = a; it != b; ++it) {
1704  // use insert with hint
1705  insert(*it, hints);
1706  }
1707  }
1708 
1709  // Obtains an iterator referencing the first element of the tree.
1710  iterator begin() const {
1711  return iterator(leftmost, 0);
1712  }
1714  // Obtains an iterator referencing the position after the last element of the tree.
1715  iterator end() const {
1716  return iterator();
1717  }
1718 
1719  /**
1720  * Partitions the full range of this set into up to a given number of chunks.
1721  * The chunks will cover approximately the same number of elements. Also, the
1722  * number of chunks will only approximate the desired number of chunks.
1723  *
1724  * @param num .. the number of chunks requested
1725  * @return a list of chunks partitioning this tree
1726  */
1727  std::vector<chunk> partition(size_type num) const {
1728  return getChunks(num);
1729  }
1730 
1731  std::vector<chunk> getChunks(size_type num) const {
1732  std::vector<chunk> res;
1733  if (empty()) {
1734  return res;
1735  }
1736  return root->collectChunks(res, num, begin(), end());
1737  }
1738 
1739  /**
1740  * Determines whether the given element is a member of this tree.
1741  */
1742  bool contains(const Key& k) const {
1743  operation_hints hints;
1744  return contains(k, hints);
1745  }
1746 
1747  /**
1748  * Determines whether the given element is a member of this tree.
1749  */
1750  bool contains(const Key& k, operation_hints& hints) const {
1751  return find(k, hints) != end();
1752  }
1753 
1754  /**
1755  * Locates the given key within this tree and returns an iterator
1756  * referencing its position. If not found, an end-iterator will be returned.
1757  */
1758  iterator find(const Key& k) const {
1759  operation_hints hints;
1760  return find(k, hints);
1761  }
1762 
1763  /**
1764  * Locates the given key within this tree and returns an iterator
1765  * referencing its position. If not found, an end-iterator will be returned.
1766  */
1767  iterator find(const Key& k, operation_hints& hints) const {
1768  if (empty()) {
1769  return end();
1770  }
1771 
1772  node* cur = root;
1773 
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;
1778  return true;
1779  };
1780 
1781  // test last location searched (temporal locality)
1782  if (hints.last_find_end.any(checkHints)) {
1783  // register it as a hit
1785  } else {
1786  // register it as a miss
1788  }
1789 
1790  // an iterative implementation (since 2/7 faster than recursive)
1791 
1792  while (true) {
1793  auto a = &(cur->keys[0]);
1794  auto b = &(cur->keys[cur->numElements]);
1795 
1796  auto pos = search(k, a, b, comp);
1797 
1798  if (pos < b && equal(*pos, k)) {
1799  hints.last_find_end.access(cur);
1800  return iterator(cur, static_cast<field_index_type>(pos - a));
1801  }
1802 
1803  if (!cur->inner) {
1804  hints.last_find_end.access(cur);
1805  return end();
1806  }
1807 
1808  // continue search in child node
1809  cur = cur->getChild(pos - a);
1810  }
1811  }
1812 
1813  /**
1814  * Obtains a lower boundary for the given key -- hence an iterator referencing
1815  * the smallest value that is not less the given key. If there is no such element,
1816  * an end-iterator will be returned.
1817  */
1818  iterator lower_bound(const Key& k) const {
1819  operation_hints hints;
1820  return lower_bound(k, hints);
1821  }
1822 
1823  /**
1824  * Obtains a lower boundary for the given key -- hence an iterator referencing
1825  * the smallest value that is not less the given key. If there is no such element,
1826  * an end-iterator will be returned.
1827  */
1828  iterator lower_bound(const Key& k, operation_hints& hints) const {
1829  if (empty()) {
1830  return end();
1831  }
1833  node* cur = root;
1834 
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;
1839  return true;
1840  };
1841 
1842  // test last searched node
1843  if (hints.last_lower_bound_end.any(checkHints)) {
1845  } else {
1847  }
1848 
1849  iterator res = end();
1850  while (true) {
1851  auto a = &(cur->keys[0]);
1852  auto b = &(cur->keys[cur->numElements]);
1853 
1854  auto pos = search.lower_bound(k, a, b, comp);
1855  auto idx = static_cast<field_index_type>(pos - a);
1856 
1857  if (!cur->inner) {
1858  hints.last_lower_bound_end.access(cur);
1859  return (pos != b) ? iterator(cur, idx) : res;
1860  }
1861 
1862  if (isSet && pos != b && equal(*pos, k)) {
1863  return iterator(cur, idx);
1864  }
1865 
1866  if (pos != b) {
1867  res = iterator(cur, idx);
1868  }
1869 
1870  cur = cur->getChild(idx);
1871  }
1872  }
1873 
1874  /**
1875  * Obtains an upper boundary for the given key -- hence an iterator referencing
1876  * the first element that the given key is less than the referenced value. If
1877  * there is no such element, an end-iterator will be returned.
1878  */
1879  iterator upper_bound(const Key& k) const {
1880  operation_hints hints;
1881  return upper_bound(k, hints);
1882  }
1883 
1884  /**
1885  * Obtains an upper boundary for the given key -- hence an iterator referencing
1886  * the first element that the given key is less than the referenced value. If
1887  * there is no such element, an end-iterator will be returned.
1888  */
1889  iterator upper_bound(const Key& k, operation_hints& hints) const {
1890  if (empty()) {
1891  return end();
1892  }
1894  node* cur = root;
1895 
1896  auto checkHints = [&](node* last_upper_bound_end) {
1897  if (!last_upper_bound_end) return false;
1898  if (!coversUpperBound(last_upper_bound_end, k)) return false;
1899  cur = last_upper_bound_end;
1900  return true;
1901  };
1902 
1903  // test last search node
1904  if (hints.last_upper_bound_end.any(checkHints)) {
1906  } else {
1908  }
1909 
1910  iterator res = end();
1911  while (true) {
1912  auto a = &(cur->keys[0]);
1913  auto b = &(cur->keys[cur->numElements]);
1914 
1915  auto pos = search.upper_bound(k, a, b, comp);
1916  auto idx = static_cast<field_index_type>(pos - a);
1917 
1918  if (!cur->inner) {
1919  hints.last_upper_bound_end.access(cur);
1920  return (pos != b) ? iterator(cur, idx) : res;
1921  }
1922 
1923  if (pos != b) {
1924  res = iterator(cur, idx);
1925  }
1926 
1927  cur = cur->getChild(idx);
1928  }
1929  }
1930 
1931  /**
1932  * Clears this tree.
1933  */
1934  void clear() {
1935  if (root != nullptr) {
1936  if (root->isLeaf()) {
1937  delete static_cast<leaf_node*>(root);
1938  } else {
1939  delete static_cast<inner_node*>(root);
1940  }
1941  }
1942  root = nullptr;
1943  leftmost = nullptr;
1944  }
1945 
1946  /**
1947  * Swaps the content of this tree with the given tree. This
1948  * is a much more efficient operation than creating a copy and
1949  * realizing the swap utilizing assignment operations.
1950  */
1951  void swap(btree& other) {
1952  // swap the content
1953  std::swap(root, other.root);
1954  std::swap(leftmost, other.leftmost);
1955  }
1956 
1957  // Implementation of the assignment operation for trees.
1958  btree& operator=(const btree& other) {
1959  // check identity
1960  if (this == &other) {
1961  return *this;
1962  }
1963 
1964  // create a deep-copy of the content of the other tree
1965  // shortcut for empty sets
1966  if (other.empty()) {
1967  return *this;
1968  }
1969 
1970  // clone content (deep copy)
1971  root = other.root->clone();
1973  // update leftmost reference
1974  auto tmp = root;
1975  while (!tmp->isLeaf()) {
1976  tmp = tmp->getChild(0);
1977  }
1978  leftmost = static_cast<leaf_node*>(tmp);
1979 
1980  // done
1981  return *this;
1982  }
1983 
1984  // Implementation of an equality operation for trees.
1985  bool operator==(const btree& other) const {
1986  // check identity
1987  if (this == &other) {
1988  return true;
1989  }
1990 
1991  // check size
1992  if (size() != other.size()) {
1993  return false;
1994  }
1995  if (size() < other.size()) {
1996  return other == *this;
1997  }
1998 
1999  // check content
2000  for (const auto& key : other) {
2001  if (!contains(key)) {
2002  return false;
2003  }
2004  }
2005  return true;
2006  }
2007 
2008  // Implementation of an inequality operation for trees.
2009  bool operator!=(const btree& other) const {
2010  return !(*this == other);
2011  }
2012 
2013  // -- for debugging --
2014 
2015  // Determines the number of levels contained in this tree.
2016  size_type getDepth() const {
2017  return (empty()) ? 0 : root->getDepth();
2018  }
2019 
2020  // Determines the number of nodes contained in this tree.
2021  size_type getNumNodes() const {
2022  return (empty()) ? 0 : root->countNodes();
2023  }
2024 
2025  // Determines the amount of memory used by this data structure
2026  size_type getMemoryUsage() const {
2027  return sizeof(*this) + (empty() ? 0 : root->getMemoryUsage());
2028  }
2029 
2030  /*
2031  * Prints a textual representation of this tree to the given
2032  * output stream (mostly for debugging and tuning).
2033  */
2034  void printTree(std::ostream& out = std::cout) const {
2035  out << "B-Tree with " << size() << " elements:\n";
2036  if (empty()) {
2037  out << " - empty - \n";
2038  } else {
2039  root->printTree(out, "");
2040  }
2041  }
2042 
2043  /**
2044  * Prints a textual summary of statistical properties of this
2045  * tree to the given output stream (for debugging and tuning).
2046  */
2047  void printStats(std::ostream& out = std::cout) const {
2048  auto nodes = getNumNodes();
2049  out << " ---------------------------------\n";
2050  out << " Elements: " << size() << "\n";
2051  out << " Depth: " << (empty() ? 0 : root->getDepth()) << "\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";
2057  out << " max keys / node: " << node::maxKeys << "\n";
2058  out << " avg keys / node: " << (size() / (double)nodes) << "\n";
2059  out << " avg filling rate: " << ((size() / (double)nodes) / node::maxKeys) << "\n";
2060  out << " ---------------------------------\n";
2061  out << " insert-hint (hits/misses/total): " << hint_stats.inserts.getHits() << "/"
2062  << hint_stats.inserts.getMisses() << "/" << hint_stats.inserts.getAccesses() << "\n";
2063  out << " contains-hint(hits/misses/total):" << hint_stats.contains.getHits() << "/"
2064  << hint_stats.contains.getMisses() << "/" << hint_stats.contains.getAccesses() << "\n";
2065  out << " lower-bound-hint (hits/misses/total):" << hint_stats.lower_bound.getHits() << "/"
2067  out << " upper-bound-hint (hits/misses/total):" << hint_stats.upper_bound.getHits() << "/"
2069  out << " ---------------------------------\n";
2070  }
2071 
2072  /**
2073  * Checks the consistency of this tree.
2074  */
2075  bool check() {
2076  auto ok = empty() || root->check(comp, root);
2077  if (!ok) {
2078  printTree();
2079  }
2080  return ok;
2081  }
2082 
2083  /**
2084  * A static member enabling the bulk-load of ordered data into an empty
2085  * tree. This function is much more efficient in creating a index over
2086  * an ordered set of elements than an iterative insertion of values.
2087  *
2088  * @tparam Iter .. the type of iterator specifying the range
2089  * it must be a random-access iterator
2090  */
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,
2094  R>::type
2095  load(const Iter& a, const Iter& b) {
2096  // quick exit - empty range
2097  if (a == b) {
2098  return R();
2099  }
2100 
2101  // resolve tree recursively
2102  auto root = buildSubTree(a, b - 1);
2103 
2104  // find leftmost node
2105  node* leftmost = root;
2106  while (!leftmost->isLeaf()) {
2107  leftmost = leftmost->getChild(0);
2108  }
2110  // build result
2111  return R(b - a, root, static_cast<leaf_node*>(leftmost));
2112  }
2113 
2114 protected:
2115  /**
2116  * Determines whether the range covered by the given node is also
2117  * covering the given key value.
2118  */
2119  bool covers(const node* node, const Key& k) const {
2120  if (isSet) {
2121  // in sets we can include the ends as covered elements
2122  return !node->isEmpty() && !less(k, node->keys[0]) && !less(node->keys[node->numElements - 1], k);
2123  }
2124  // in multi-sets the ends may not be completely covered
2125  return !node->isEmpty() && less(node->keys[0], k) && less(k, node->keys[node->numElements - 1]);
2126  }
2127 
2128  /**
2129  * Determines whether the range covered by the given node is also
2130  * covering the given key value.
2131  */
2132  bool weak_covers(const node* node, const Key& k) const {
2133  if (isSet) {
2134  // in sets we can include the ends as covered elements
2135  return !node->isEmpty() && !weak_less(k, node->keys[0]) &&
2136  !weak_less(node->keys[node->numElements - 1], k);
2137  }
2138  // in multi-sets the ends may not be completely covered
2139  return !node->isEmpty() && weak_less(node->keys[0], k) &&
2140  weak_less(k, node->keys[node->numElements - 1]);
2141  }
2142 
2143 private:
2144  /**
2145  * Determines whether the range covered by this node covers
2146  * the upper bound of the given key.
2147  */
2148  bool coversUpperBound(const node* node, const Key& k) const {
2149  // ignore edges
2150  return !node->isEmpty() && !less(k, node->keys[0]) && less(k, node->keys[node->numElements - 1]);
2151  }
2152 
2153  // Utility function for the load operation above.
2154  template <typename Iter>
2155  static node* buildSubTree(const Iter& a, const Iter& b) {
2156  const int N = node::maxKeys;
2157 
2158  // divide range in N+1 sub-ranges
2159  int length = (b - a) + 1;
2160 
2161  // terminal case: length is less then maxKeys
2162  if (length <= N) {
2163  // create a leaf node
2164  node* res = new leaf_node();
2165  res->numElements = length;
2166 
2167  for (int i = 0; i < length; ++i) {
2168  res->keys[i] = a[i];
2169  }
2170 
2171  return res;
2172  }
2173 
2174  // recursive case - compute step size
2175  int numKeys = N;
2176  int step = ((length - numKeys) / (numKeys + 1));
2177 
2178  while (numKeys > 1 && (step < N / 2)) {
2179  numKeys--;
2180  step = ((length - numKeys) / (numKeys + 1));
2181  }
2182 
2183  // create inner node
2184  node* res = new inner_node();
2185  res->numElements = numKeys;
2186 
2187  Iter c = a;
2188  for (int i = 0; i < numKeys; i++) {
2189  // get dividing key
2190  res->keys[i] = c[step];
2191 
2192  // get sub-tree
2193  auto child = buildSubTree(c, c + (step - 1));
2194  child->parent = res;
2195  child->position = i;
2196  res->getChildren()[i] = child;
2197 
2198  c = c + (step + 1);
2199  }
2200 
2201  // and the remaining part
2202  auto child = buildSubTree(c, b);
2203  child->parent = res;
2204  child->position = numKeys;
2205  res->getChildren()[numKeys] = child;
2206 
2207  // done
2208  return res;
2209  }
2210 }; // namespace souffle
2211 
2212 // Instantiation of static member search.
2213 template <typename Key, typename Comparator, typename Allocator, unsigned blockSize, typename SearchStrategy,
2214  bool isSet, typename WeakComparator, typename Updater>
2215 const SearchStrategy
2217 
2218 } // end namespace detail
2219 
2220 /**
2221  * A b-tree based set implementation.
2222  *
2223  * @tparam Key .. the element type to be stored in this set
2224  * @tparam Comparator .. a class defining an order on the stored elements
2225  * @tparam Allocator .. utilized for allocating memory for required nodes
2226  * @tparam blockSize .. determines the number of bytes/block utilized by leaf nodes
2227  * @tparam SearchStrategy .. enables switching between linear, binary or any other search strategy
2228  */
2229 template <typename Key, typename Comparator = detail::comparator<Key>,
2230  typename Allocator = std::allocator<Key>, // is ignored so far
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> {
2236  using super = souffle::detail::btree<Key, Comparator, Allocator, blockSize, SearchStrategy, true,
2237  WeakComparator, Updater>;
2238 
2239  friend class souffle::detail::btree<Key, Comparator, Allocator, blockSize, SearchStrategy, true,
2240  WeakComparator, Updater>;
2242 public:
2243  /**
2244  * A default constructor creating an empty set.
2245  */
2246  btree_set(const Comparator& comp = Comparator(), const WeakComparator& weak_comp = WeakComparator())
2248 
2249  /**
2250  * A constructor creating a set based on the given range.
2251  */
2252  template <typename Iter>
2253  btree_set(const Iter& a, const Iter& b) {
2254  this->insert(a, b);
2255  }
2256 
2257  // A copy constructor.
2258  btree_set(const btree_set& other) : super(other) {}
2259 
2260  // A move constructor.
2261  btree_set(btree_set&& other) : super(std::move(other)) {}
2262 
2263 private:
2264  // A constructor required by the bulk-load facility.
2265  template <typename s, typename n, typename l>
2266  btree_set(s size, n* root, l* leftmost) : super(size, root, leftmost) {}
2267 
2268 public:
2269  // Support for the assignment operator.
2270  btree_set& operator=(const btree_set& other) {
2271  super::operator=(other);
2272  return *this;
2273  }
2274 
2275  // Support for the bulk-load operator.
2276  template <typename Iter>
2277  static btree_set load(const Iter& a, const Iter& b) {
2278  return super::template load<btree_set>(a, b);
2279  }
2280 };
2281 
2282 /**
2283  * A b-tree based multi-set implementation.
2284  *
2285  * @tparam Key .. the element type to be stored in this set
2286  * @tparam Comparator .. a class defining an order on the stored elements
2287  * @tparam Allocator .. utilized for allocating memory for required nodes
2288  * @tparam blockSize .. determines the number of bytes/block utilized by leaf nodes
2289  * @tparam SearchStrategy .. enables switching between linear, binary or any other search strategy
2290  */
2291 template <typename Key, typename Comparator = detail::comparator<Key>,
2292  typename Allocator = std::allocator<Key>, // is ignored so far
2293  unsigned blockSize = 256,
2294  typename SearchStrategy = typename souffle::detail::default_strategy<Key>::type,
2295  typename WeakComparator = Comparator, typename Updater = souffle::detail::updater<Key>>
2296 class btree_multiset : public souffle::detail::btree<Key, Comparator, Allocator, blockSize, SearchStrategy,
2297  false, WeakComparator, Updater> {
2298  using super = souffle::detail::btree<Key, Comparator, Allocator, blockSize, SearchStrategy, false,
2299  WeakComparator, Updater>;
2300 
2301  friend class souffle::detail::btree<Key, Comparator, Allocator, blockSize, SearchStrategy, false,
2302  WeakComparator, Updater>;
2304 public:
2305  /**
2306  * A default constructor creating an empty set.
2307  */
2308  btree_multiset(const Comparator& comp = Comparator(), const WeakComparator& weak_comp = WeakComparator())
2310 
2311  /**
2312  * A constructor creating a set based on the given range.
2313  */
2314  template <typename Iter>
2315  btree_multiset(const Iter& a, const Iter& b) {
2316  this->insert(a, b);
2317  }
2318 
2319  // A copy constructor.
2320  btree_multiset(const btree_multiset& other) : super(other) {}
2321 
2322  // A move constructor.
2323  btree_multiset(btree_multiset&& other) : super(std::move(other)) {}
2324 
2325 private:
2326  // A constructor required by the bulk-load facility.
2327  template <typename s, typename n, typename l>
2329 
2330 public:
2331  // Support for the assignment operator.
2332  btree_multiset& operator=(const btree_multiset& other) {
2333  super::operator=(other);
2334  return *this;
2335  }
2336 
2337  // Support for the bulk-load operator.
2338  template <typename Iter>
2339  static btree_multiset load(const Iter& a, const Iter& b) {
2340  return super::template load<btree_multiset>(a, b);
2341  }
2342 };
2343 
2344 } // end of namespace souffle
souffle::detail::btree::root_lock
lock_type root_lock
Definition: BTree.h:1245
souffle::detail::btree::node::countNodes
size_type countNodes() const
Counts the number of nodes contained in the sub-tree rooted by this node.
Definition: BTree.h:463
souffle::detail::btree::empty
bool empty() const
Definition: BTree.h:1316
souffle::detail::btree::weak_less
bool weak_less(const Key &a, const Key &b) const
Definition: BTree.h:293
souffle::detail::btree::node::collectChunks
std::vector< chunk > & collectChunks(std::vector< chunk > &res, size_type num, const iterator &begin, const iterator &end) const
A function decomposing the sub-tree rooted by this node into approximately equally sized chunks.
Definition: BTree.h:927
souffle::detail::btree::search
const static SearchStrategy search
Definition: BTree.h:277
souffle::CacheAccessCounter::addMiss
void addMiss()
Definition: CacheUtil.h:283
souffle::interpreter::comparator
typename index_utils::get_full_index< Arity >::type::comparator comparator
Definition: Util.h:216
souffle::detail::btree::base::getNumElements
size_type getNumElements() const
Definition: BTree.h:369
souffle::detail::btree
The actual implementation of a b-tree data structure.
Definition: BTree.h:265
souffle::detail::btree::base::position
field_index_type position
Definition: BTree.h:342
souffle::detail::btree::node::rebalance_or_split
int rebalance_or_split(node **root, lock_type &root_lock, int idx)
Moves keys from this node to one of its siblings or splits this node to make some space for the inser...
Definition: BTree.h:632
souffle::detail::btree::inner_node
The data type representing inner nodes of the b-tree.
Definition: BTree.h:1078
souffle::detail::btree::node::check
bool check(Comp &comp, const node *root) const
A function to verify the consistency of this node.
Definition: BTree.h:994
souffle::btree_multiset
A b-tree based multi-set implementation.
Definition: BTree.h:2303
souffle::range
A utility class enabling representation of ranges by pairing two iterator instances marking lower and...
Definition: ContainerUtil.h:313
souffle::detail::btree::clear
void clear()
Clears this tree.
Definition: BTree.h:1948
souffle::detail::btree::update
void update(Key &old_k, const Key &new_k)
Definition: BTree.h:304
souffle::detail::btree::hint_statistics::upper_bound
CacheAccessCounter upper_bound
Definition: BTree.h:1265
souffle::detail::btree::leftmost
leaf_node * leftmost
Definition: BTree.h:1249
souffle::detail::search_strategy
A common base class for search strategies in b-trees.
Definition: BTree.h:82
souffle::detail::btree::equal
bool equal(const Key &a, const Key &b) const
Definition: BTree.h:287
souffle::detail::btree::end
iterator end() const
Definition: BTree.h:1729
souffle::detail::updater
The default non-updater.
Definition: BTree.h:247
souffle::detail::btree::base::getParent
node * getParent() const
Definition: BTree.h:361
souffle::detail::btree::node
The actual, generic node implementation covering the operations for both, inner and leaf nodes.
Definition: BTree.h:380
souffle::btree_set
A b-tree based set implementation.
Definition: BTree.h:2241
souffle::OptimisticReadWriteLock::start_read
Lease start_read()
Definition: ParallelUtil.h:532
souffle::detail::btree::node::getSplitPoint
int getSplitPoint(int)
Obtains the point at which full nodes should be split.
Definition: BTree.h:548
souffle::detail::btree::weak_comp
WeakComparator weak_comp
Definition: BTree.h:291
ParallelUtil.h
souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::field_index_type
uint8_t field_index_type
Definition: BTree.h:311
souffle::OptimisticReadWriteLock::is_write_locked
bool is_write_locked() const
Definition: ParallelUtil.h:558
souffle::detail::binary_search::operator()
Iter operator()(const Key &k, Iter a, Iter b, Comp &comp) const
Obtains an iterator pointing to some element within the given range that is equal to the given key,...
Definition: BTree.h:156
souffle::contains
bool contains(const C &container, const typename C::value_type &element)
A utility to check generically whether a given element is contained in a given container.
Definition: ContainerUtil.h:75
Comparator
souffle::detail::linear_search::upper_bound
Iter upper_bound(const Key &k, Iter a, Iter b, Comp &comp) const
Obtains a reference to the first element in the given range that such that the given key is less than...
Definition: BTree.h:126
S
#define S(x)
Definition: test.h:179
souffle::detail::btree::btree
btree(Comparator comp=Comparator(), WeakComparator weak_comp=WeakComparator())
Definition: BTree.h:1278
souffle::detail::btree::partition
std::vector< chunk > partition(size_type num) const
Partitions the full range of this set into up to a given number of chunks.
Definition: BTree.h:1741
souffle::detail::btree::less
bool less(const Key &a, const Key &b) const
Definition: BTree.h:283
souffle::detail::btree::comp
Comparator comp
Definition: BTree.h:281
souffle::detail::strategy_selection::type
S type
Definition: BTree.h:227
base
T & base
Definition: Reader.h:60
souffle::detail::btree::base::isInner
bool isInner() const
Definition: BTree.h:357
souffle::detail::btree::const_iterator
iterator const_iterator
Definition: BTree.h:268
souffle::detail::linear_search::operator()
Iter operator()(const Key &k, Iter a, Iter b, Comp &comp) const
Obtains an iterator referencing an element equivalent to the given key in the given range.
Definition: BTree.h:100
souffle::detail::btree::node::grow_parent
void grow_parent(node **root, lock_type &root_lock, node *sibling)
Inserts a new sibling into the parent of this node utilizing the last key of this node as a separatio...
Definition: BTree.h:747
souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::size_type
std::size_t size_type
Definition: BTree.h:310
souffle::detail::btree::operator!=
bool operator!=(const btree &other) const
Definition: BTree.h:2023
souffle::detail::linear_search::linear_search
linear_search()=default
Required user-defined default constructor.
souffle::detail::btree::getNumNodes
size_type getNumNodes() const
Definition: BTree.h:2035
souffle::detail::btree::chunk
range< iterator > chunk
Definition: BTree.h:272
souffle::detail::btree::max_keys_per_node
static constexpr size_t max_keys_per_node
Definition: BTree.h:1273
n
var n
Definition: htmlJsChartistMin.h:15
souffle::detail::btree::node::split
void split(node **root, lock_type &root_lock, int idx)
Splits this node.
Definition: BTree.h:567
souffle::detail::btree::upd
Updater upd
Definition: BTree.h:303
souffle::detail::btree::operator==
bool operator==(const btree &other) const
Definition: BTree.h:1999
j
var j
Definition: htmlJsChartistMin.h:15
souffle::detail::comparator::less
bool less(const T &a, const T &b) const
Definition: BTree.h:76
souffle::OptimisticReadWriteLock::abort_write
void abort_write()
Definition: ParallelUtil.h:554
souffle::detail::btree::getChunks
std::vector< chunk > getChunks(size_type num) const
Definition: BTree.h:1745
souffle::detail::btree::insert
bool insert(const Key &k)
Inserts the given key into this tree.
Definition: BTree.h:1328
souffle::detail::btree::node::getChildren
node ** getChildren()
Obtains a pointer to the array of child-pointers of this node – if it is an inner node.
Definition: BTree.h:508
souffle::detail::btree::weak_equal
bool weak_equal(const Key &a, const Key &b) const
Definition: BTree.h:297
souffle::detail::btree::buildSubTree
static node * buildSubTree(const Iter &a, const Iter &b)
Definition: BTree.h:2169
souffle::detail::btree::begin
iterator begin() const
Definition: BTree.h:1724
souffle::detail::btree::node::keys
Key keys[maxKeys]
Definition: BTree.h:393
l
var l
Definition: htmlJsChartistMin.h:15
souffle::detail::btree::weak_covers
bool weak_covers(const node *node, const Key &k) const
Determines whether the range covered by the given node is also covering the given key value.
Definition: BTree.h:2146
souffle::detail::btree::base::parent
node * parent
Definition: BTree.h:336
souffle::detail::btree::load
static std::enable_if< std::is_same< typename std::iterator_traits< Iter >::iterator_category, std::random_access_iterator_tag >::value, R >::type load(const Iter &a, const Iter &b)
A static member enabling the bulk-load of ordered data into an empty tree.
Definition: BTree.h:2109
souffle::detail::binary_search::upper_bound
Iter upper_bound(const Key &k, Iter a, Iter b, Comp &comp) const
Obtains a reference to the first element in the given range that such that the given key is less than...
Definition: BTree.h:202
souffle::CacheAccessCounter::getMisses
std::size_t getMisses()
Definition: CacheUtil.h:287
souffle::detail::linear_search::lower_bound
Iter lower_bound(const Key &k, Iter a, Iter b, Comp &comp) const
Obtains a reference to the first element in the given range that is not less than the given key.
Definition: BTree.h:109
i
size_t i
Definition: json11.h:663
ContainerUtil.h
souffle::btree_multiset::btree_multiset
btree_multiset(const Comparator &comp=Comparator(), const WeakComparator &weak_comp=WeakComparator())
A default constructor creating an empty set.
Definition: BTree.h:2315
souffle::OptimisticReadWriteLock
A 'sequential' non-locking implementation for an optimistic r/w lock.
Definition: ParallelUtil.h:526
souffle::detail::linear
Definition: BTree.h:230
souffle::detail::btree::base::numElements
size_type numElements
Definition: BTree.h:339
souffle::detail::btree::swap
void swap(btree &other)
Swaps the content of this tree with the given tree.
Definition: BTree.h:1965
souffle::detail::btree::node::desiredNumKeys
static constexpr size_t desiredNumKeys
The number of keys/node desired by the user.
Definition: BTree.h:384
souffle::detail::comparator::operator()
int operator()(const T &a, const T &b) const
Compares the values of a and b and returns -1 if a<b, 1 if a>b and 0 otherwise.
Definition: BTree.h:73
souffle::detail::btree::base
The base type of all node types containing essential book-keeping information.
Definition: BTree.h:320
souffle::detail::binary_search::binary_search
binary_search()=default
Required user-defined default constructor.
souffle::detail::btree::hint_statistics::inserts
CacheAccessCounter inserts
Definition: BTree.h:1256
souffle::detail::default_strategy
Definition: BTree.h:235
souffle::detail::btree::node::countEntries
size_type countEntries() const
Counts the number of entries contained in the sub-tree rooted by this node.
Definition: BTree.h:478
souffle::detail::btree::root
node * root
Definition: BTree.h:1242
souffle::test::count
int count(const C &c)
Definition: table_test.cpp:40
souffle::detail::btree::inner_node::children
node * children[node::maxKeys+1]
Definition: BTree.h:1080
souffle::detail::btree::lock_type
OptimisticReadWriteLock lock_type
Definition: BTree.h:312
souffle::detail::linear_search
A linear search strategy for looking up keys in b-tree nodes.
Definition: BTree.h:87
souffle::detail::comparator::equal
bool equal(const T &a, const T &b) const
Definition: BTree.h:79
souffle::OptimisticReadWriteLock::start_write
void start_write()
Definition: ParallelUtil.h:544
souffle::detail::btree::hint_stats
hint_statistics hint_stats
Definition: BTree.h:1269
souffle::CacheAccessCounter::getAccesses
std::size_t getAccesses()
Definition: CacheUtil.h:290
souffle::detail::btree::size
size_type size() const
Definition: BTree.h:1321
souffle::detail::btree::node::isFull
bool isFull() const
Checks whether this node is full.
Definition: BTree.h:537
souffle::detail::btree::node::insert_inner
void insert_inner(node **root, lock_type &root_lock, unsigned pos, node *predecessor, const Key &key, node *newNode)
Inserts a new element into an inner node (for internal use only).
Definition: BTree.h:797
souffle::detail::btree::node::getDepth
size_type getDepth() const
Computes the number of nested levels of the tree rooted by this node.
Definition: BTree.h:452
souffle::CacheAccessCounter::addHit
void addHit()
Definition: CacheUtil.h:282
souffle::detail::btree::node::getMemoryUsage
size_type getMemoryUsage() const
Determines the amount of memory used by the sub-tree rooted by this node.
Definition: BTree.h:493
souffle::OptimisticReadWriteLock::try_start_write
bool try_start_write()
Definition: ParallelUtil.h:546
k
var k
Definition: htmlJsChartistMin.h:15
souffle::detail::btree::find
iterator find(const Key &k) const
Locates the given key within this tree and returns an iterator referencing its position.
Definition: BTree.h:1772
souffle::detail::btree::node::clone
node * clone() const
A deep-copy operation creating a clone of this node.
Definition: BTree.h:401
souffle::detail::btree::base::isLeaf
bool isLeaf() const
Definition: BTree.h:353
souffle::detail::binary_search
A binary search strategy for looking up keys in b-tree nodes.
Definition: BTree.h:141
souffle::OptimisticReadWriteLock::end_write
void end_write()
Definition: ParallelUtil.h:556
souffle::detail::btree::covers
bool covers(const node *node, const Key &k) const
Determines whether the range covered by the given node is also covering the given key value.
Definition: BTree.h:2133
souffle::detail::btree::key_type
Key key_type
Definition: BTree.h:270
souffle::detail::btree::coversUpperBound
bool coversUpperBound(const node *node, const Key &k) const
Determines whether the range covered by this node covers the upper bound of the given key.
Definition: BTree.h:2162
souffle::detail::btree::base::getPositionInParent
field_index_type getPositionInParent() const
Definition: BTree.h:365
souffle::detail::btree::hint_statistics
Definition: BTree.h:1254
b
l j a showGridBackground &&c b raw series this eventEmitter b
Definition: htmlJsChartistMin.h:15
souffle::detail::btree::operator=
btree & operator=(const btree &other)
Definition: BTree.h:1972
souffle::detail::btree::iterator::cur
node const * cur
Definition: BTree.h:1116
std
Definition: Brie.h:3053
souffle::OptimisticReadWriteLock::end_read
bool end_read(const Lease &)
Definition: ParallelUtil.h:540
souffle::detail::btree::node::getChild
node * getChild(size_type s) const
Obtains a reference to the child of the given index.
Definition: BTree.h:523
souffle::detail::btree::upper_bound
iterator upper_bound(const Key &k) const
Obtains an upper boundary for the given key – hence an iterator referencing the first element that th...
Definition: BTree.h:1893
souffle::detail::btree::printStats
void printStats(std::ostream &out=std::cout) const
Prints a textual summary of statistical properties of this tree to the given output stream (for debug...
Definition: BTree.h:2061
souffle::CacheAccessCounter::getHits
std::size_t getHits()
Definition: CacheUtil.h:284
souffle::detail::binary_search::lower_bound
Iter lower_bound(const Key &k, Iter a, Iter b, Comp &comp) const
Obtains a reference to the first element in the given range that is not less than the given key.
Definition: BTree.h:181
souffle::detail::btree::btree_operation_hints
A collection of operation hints speeding up some of the involved operations by exploiting temporal lo...
Definition: BTree.h:1204
souffle::detail::btree::~btree
~btree()
Definition: BTree.h:1309
souffle::detail::btree::contains
bool contains(const Key &k) const
Determines whether the given element is a member of this tree.
Definition: BTree.h:1756
souffle::detail::btree::node::asInnerNode
inner_node & asInnerNode()
A utility function providing a reference to this node as an inner node.
Definition: BTree.h:434
souffle::detail::btree::iterator::pos
field_index_type pos
Definition: BTree.h:1119
souffle::detail::btree::element_type
Key element_type
Definition: BTree.h:271
souffle
Definition: AggregateOp.h:25
souffle::detail::btree::hint_statistics::contains
CacheAccessCounter contains
Definition: BTree.h:1259
souffle::detail::btree::node::printTree
void printTree(std::ostream &out, const std::string &prefix) const
Prints a textual representation of this tree to the given output stream.
Definition: BTree.h:871
souffle::detail::btree::node::isEmpty
bool isEmpty() const
Checks whether this node is empty – can happen due to biased insertion.
Definition: BTree.h:530
souffle::detail::btree::lower_bound
iterator lower_bound(const Key &k) const
Obtains a lower boundary for the given key – hence an iterator referencing the smallest value that is...
Definition: BTree.h:1832
souffle::detail::btree::operation_hints
btree_operation_hints< 1 > operation_hints
Definition: BTree.h:1231
souffle::detail::btree::iterator
The iterator type to be utilized for scanning through btree instances.
Definition: BTree.h:1114
CacheUtil.h
souffle::detail::btree::base::inner
const bool inner
Definition: BTree.h:346
souffle::CacheAccessCounter
cache hits/misses.
Definition: CacheUtil.h:278
souffle::btree_set::btree_set
btree_set(const Comparator &comp=Comparator(), const WeakComparator &weak_comp=WeakComparator())
A default constructor creating an empty set.
Definition: BTree.h:2253
souffle::tuple
Defines a tuple for the OO interface such that relations with varying columns can be accessed.
Definition: SouffleInterface.h:443
souffle::detail::btree::leaf_node
The data type representing leaf nodes of the b-tree.
Definition: BTree.h:1103
souffle::detail::btree::hint_statistics::lower_bound
CacheAccessCounter lower_bound
Definition: BTree.h:1262
souffle::detail::btree::node::maxKeys
static constexpr size_t maxKeys
The actual number of keys/node corrected by functional requirements.
Definition: BTree.h:390
souffle::detail::updater::update
void update(T &, const T &)
Definition: BTree.h:248
std::type
ElementType type
Definition: span.h:640
souffle::detail::btree::base::base
base(bool inner)
A simple constructor for nodes.
Definition: BTree.h:351
souffle::detail::btree::node::node
node(bool inner)
Definition: BTree.h:396