13 #ifndef STXXL_CONTAINERS_BTREE__BTREE_H
14 #define STXXL_CONTAINERS_BTREE__BTREE_H
16 #include <stxxl/bits/namespace.h>
17 #include <stxxl/bits/containers/btree/iterator.h>
18 #include <stxxl/bits/containers/btree/iterator_map.h>
19 #include <stxxl/bits/containers/btree/leaf.h>
20 #include <stxxl/bits/containers/btree/node_cache.h>
21 #include <stxxl/bits/containers/btree/root_node.h>
22 #include <stxxl/bits/containers/btree/node.h>
23 #include <stxxl/vector>
26 __STXXL_BEGIN_NAMESPACE
30 template <
class KeyType,
37 class btree :
private noncopyable
40 typedef KeyType key_type;
41 typedef DataType data_type;
42 typedef CompareType key_compare;
44 typedef btree<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> SelfType;
46 typedef PDAllocStrategy alloc_strategy_type;
48 typedef stxxl::uint64 size_type;
49 typedef stxxl::int64 difference_type;
50 typedef std::pair<const key_type, data_type> value_type;
51 typedef value_type & reference;
52 typedef const value_type & const_reference;
53 typedef value_type * pointer;
54 typedef value_type
const * const_pointer;
58 typedef normal_leaf<key_type, data_type, key_compare, RawLeafSize, SelfType> leaf_type;
59 friend class normal_leaf<key_type, data_type, key_compare, RawLeafSize, SelfType>;
60 typedef typename leaf_type::block_type leaf_block_type;
61 typedef typename leaf_type::bid_type leaf_bid_type;
62 typedef node_cache<leaf_type, SelfType> leaf_cache_type;
63 friend class node_cache<leaf_type, SelfType>;
65 typedef btree_iterator<SelfType> iterator;
66 typedef btree_const_iterator<SelfType> const_iterator;
67 friend class btree_iterator_base<SelfType>;
69 typedef iterator_map<SelfType> iterator_map_type;
71 typedef normal_node<key_type, key_compare, RawNodeSize, SelfType> node_type;
72 typedef typename node_type::block_type node_block_type;
73 friend class normal_node<key_type, key_compare, RawNodeSize, SelfType>;
74 typedef typename node_type::bid_type node_bid_type;
75 typedef node_cache<node_type, SelfType> node_cache_type;
76 friend class node_cache<node_type, SelfType>;
78 typedef typename leaf_type::value_compare value_compare;
81 min_node_size = node_type::min_size,
82 max_node_size = node_type::max_size,
83 min_leaf_size = leaf_type::min_size,
84 max_leaf_size = leaf_type::max_size
88 key_compare key_compare_;
89 mutable node_cache_type node_cache_;
90 mutable leaf_cache_type leaf_cache_;
91 iterator_map_type iterator_map_;
93 unsigned_type height_;
94 bool prefetching_enabled_;
96 alloc_strategy_type alloc_strategy_;
98 typedef std::map<key_type, node_bid_type, key_compare> root_node_type;
99 typedef typename root_node_type::iterator root_node_iterator_type;
100 typedef typename root_node_type::const_iterator root_node_const_iterator_type;
101 typedef std::pair<key_type, node_bid_type> root_node_pair_type;
104 root_node_type root_node_;
105 iterator end_iterator;
108 template <
class BIDType>
109 void insert_into_root(
const std::pair<key_type, BIDType> & splitter)
111 std::pair<root_node_iterator_type, bool> result =
112 root_node_.insert(splitter);
113 assert(result.second ==
true);
114 if (root_node_.size() > max_node_size)
116 STXXL_VERBOSE1(
"btree::insert_into_root, overflow happened, splitting");
118 node_bid_type LeftBid;
119 node_type * LeftNode = node_cache_.get_new_node(LeftBid);
121 node_bid_type RightBid;
122 node_type * RightNode = node_cache_.get_new_node(RightBid);
125 const unsigned_type old_size = root_node_.size();
126 const unsigned_type half = root_node_.size() / 2;
128 root_node_iterator_type it = root_node_.begin();
129 typename node_block_type::iterator block_it = LeftNode->block().begin();
137 LeftNode->block().info.cur_size = half;
138 key_type LeftKey = (LeftNode->block()[half - 1]).first;
140 block_it = RightNode->block().begin();
148 unsigned_type right_size = RightNode->block().info.cur_size = old_size - half;
149 key_type RightKey = (RightNode->block()[right_size - 1]).first;
151 assert(old_size == RightNode->size() + LeftNode->size());
155 root_node_.insert(root_node_pair_type(LeftKey, LeftBid));
156 root_node_.insert(root_node_pair_type(RightKey, RightBid));
160 STXXL_VERBOSE1(
"btree Increasing height to " << height_);
161 if (node_cache_.size() < (height_ - 1))
163 STXXL_THROW(std::runtime_error,
"btree::bulk_construction",
"The height of the tree (" << height_ <<
") has exceeded the required capacity ("
164 << (node_cache_.size() + 1) <<
") of the node cache. " <<
165 "Increase the node cache size.");
170 template <
class CacheType>
171 void fuse_or_balance(root_node_iterator_type UIt, CacheType & cache_)
173 typedef typename CacheType::node_type local_node_type;
174 typedef typename local_node_type::bid_type local_bid_type;
176 root_node_iterator_type leftIt, rightIt;
177 if (UIt->first == key_compare::max_value())
179 assert(UIt != root_node_.begin());
187 assert(rightIt != root_node_.end());
191 local_bid_type LeftBid = (local_bid_type)leftIt->second;
192 local_bid_type RightBid = (local_bid_type)rightIt->second;
193 local_node_type * LeftNode = cache_.get_node(LeftBid,
true);
194 local_node_type * RightNode = cache_.get_node(RightBid,
true);
196 const unsigned_type TotalSize = LeftNode->size() + RightNode->size();
197 if (TotalSize <= RightNode->max_nelements())
200 RightNode->fuse(*LeftNode);
202 cache_.unfix_node(RightBid);
203 cache_.delete_node(LeftBid);
205 root_node_.erase(leftIt);
211 key_type NewSplitter = RightNode->balance(*LeftNode);
213 root_node_.erase(leftIt);
215 root_node_.insert(root_node_pair_type(NewSplitter, (node_bid_type)LeftBid));
217 cache_.unfix_node(LeftBid);
218 cache_.unfix_node(RightBid);
222 void create_empty_leaf()
224 leaf_bid_type NewBid;
225 leaf_type * NewLeaf = leaf_cache_.get_new_node(NewBid);
227 end_iterator = NewLeaf->end();
228 root_node_.insert(root_node_pair_type(key_compare::max_value(), (node_bid_type)NewBid));
231 void deallocate_children()
236 root_node_const_iterator_type it = root_node_.begin();
237 for ( ; it != root_node_.end(); ++it)
240 leaf_cache_.delete_node((leaf_bid_type)it->second);
245 root_node_const_iterator_type it = root_node_.begin();
246 for ( ; it != root_node_.end(); ++it)
248 node_type * Node = node_cache_.get_node((node_bid_type)it->second);
250 Node->deallocate_children(height_ - 1);
252 node_cache_.delete_node((node_bid_type)it->second);
257 template <
class InputIterator>
258 void bulk_construction(InputIterator b, InputIterator e,
double node_fill_factor,
double leaf_fill_factor)
260 assert(node_fill_factor >= 0.5);
261 assert(leaf_fill_factor >= 0.5);
262 key_type lastKey = key_compare::max_value();
264 typedef std::pair<key_type, node_bid_type> key_bid_pair;
265 typedef typename stxxl::VECTOR_GENERATOR<key_bid_pair, 1, 1,
268 key_bid_vector_type Bids;
270 leaf_bid_type NewBid;
271 leaf_type * Leaf = leaf_cache_.get_new_node(NewBid);
272 const unsigned_type max_leaf_elements = unsigned_type(
double(Leaf->max_nelements()) * leaf_fill_factor);
279 if (key_compare_(b->first, lastKey) || key_compare_(lastKey, b->first))
282 if (Leaf->size() == max_leaf_elements)
285 Bids.push_back(key_bid_pair(Leaf->back().first, (node_bid_type)NewBid));
287 leaf_type * NewLeaf = leaf_cache_.get_new_node(NewBid);
290 Leaf->succ() = NewLeaf->my_bid();
291 NewLeaf->pred() = Leaf->my_bid();
302 if (Leaf->underflows() && !Bids.empty())
304 leaf_type * LeftLeaf = leaf_cache_.get_node((leaf_bid_type)(Bids.back().second));
306 if (LeftLeaf->size() + Leaf->size() <= Leaf->max_nelements())
308 Leaf->fuse(*LeftLeaf);
309 leaf_cache_.delete_node((leaf_bid_type)(Bids.back().second));
311 assert(!Leaf->overflows() && !Leaf->underflows());
316 const key_type NewSplitter = Leaf->balance(*LeftLeaf);
317 Bids.back().first = NewSplitter;
318 assert(!LeftLeaf->overflows() && !LeftLeaf->underflows());
322 assert(!Leaf->overflows() && (!Leaf->underflows() || size_ <= max_leaf_size));
324 end_iterator = Leaf->end();
326 Bids.push_back(key_bid_pair(key_compare::max_value(), (node_bid_type)NewBid));
328 const unsigned_type max_node_elements = unsigned_type(
double(max_node_size) * node_fill_factor);
330 while (Bids.size() > max_node_elements)
332 key_bid_vector_type ParentBids;
334 stxxl::uint64 nparents = div_and_round_up(Bids.size(), stxxl::uint64(max_node_elements));
335 assert(nparents >= 2);
336 STXXL_VERBOSE1(
"btree bulk constructBids.size() " << Bids.size() <<
" nparents: " << nparents <<
" max_ns: "
337 << max_node_elements);
338 typename key_bid_vector_type::const_iterator it = Bids.begin();
342 node_bid_type NewBid;
343 node_type * Node = node_cache_.get_new_node(NewBid);
345 unsigned_type cnt = 0;
346 for ( ; cnt < max_node_elements && it != Bids.end(); ++cnt, ++it)
348 Node->push_back(*it);
350 STXXL_VERBOSE1(
"btree bulk construct Node size : " << Node->size() <<
" limits: " <<
351 Node->min_nelements() <<
" " << Node->max_nelements() <<
" max_node_elements: " << max_node_elements);
353 if (Node->underflows())
355 assert(it == Bids.end());
356 assert(!ParentBids.empty());
358 node_type * LeftNode = node_cache_.get_node(ParentBids.back().second);
360 if (LeftNode->size() + Node->size() <= Node->max_nelements())
362 Node->fuse(*LeftNode);
363 node_cache_.delete_node(ParentBids.back().second);
364 ParentBids.pop_back();
368 const key_type NewSplitter = Node->balance(*LeftNode);
369 ParentBids.back().first = NewSplitter;
370 assert(!LeftNode->overflows() && !LeftNode->underflows());
373 assert(!Node->overflows() && !Node->underflows());
375 ParentBids.push_back(key_bid_pair(Node->back().first, NewBid));
376 }
while (it != Bids.end());
378 std::swap(ParentBids, Bids);
380 assert(nparents == Bids.size() || (nparents - 1) == Bids.size());
383 STXXL_VERBOSE1(
"Increasing height to " << height_);
384 if (node_cache_.size() < (height_ - 1))
386 STXXL_THROW(std::runtime_error,
"btree::bulk_construction",
"The height of the tree (" << height_ <<
") has exceeded the required capacity ("
387 << (node_cache_.size() + 1) <<
") of the node cache. " <<
388 "Increase the node cache size.");
392 root_node_.insert(Bids.begin(), Bids.end());
396 btree(unsigned_type node_cache_size_in_bytes,
397 unsigned_type leaf_cache_size_in_bytes
399 node_cache_(node_cache_size_in_bytes, this, key_compare_),
400 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_),
404 prefetching_enabled_(true),
407 STXXL_VERBOSE1(
"Creating a btree, addr=" <<
this);
412 STXXL_VERBOSE1(
" size of a node element: " <<
sizeof(
typename node_block_type::value_type));
413 STXXL_VERBOSE1(
" size of a leaf element: " <<
sizeof(
typename leaf_block_type::value_type));
419 btree(
const key_compare & c_,
420 unsigned_type node_cache_size_in_bytes,
421 unsigned_type leaf_cache_size_in_bytes
424 node_cache_(node_cache_size_in_bytes, this, key_compare_),
425 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_),
429 prefetching_enabled_(true),
432 STXXL_VERBOSE1(
"Creating a btree, addr=" <<
this);
443 deallocate_children();
450 size_type size()
const
455 size_type max_size()
const
457 return (std::numeric_limits<size_type>::max)();
465 std::pair<iterator, bool> insert(
const value_type & x)
467 root_node_iterator_type it = root_node_.lower_bound(x.first);
468 assert(!root_node_.empty());
469 assert(it != root_node_.end());
472 STXXL_VERBOSE1(
"Inserting new value into a leaf");
473 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second,
true);
475 std::pair<key_type, leaf_bid_type> Splitter;
476 std::pair<iterator, bool> result = Leaf->insert(x, Splitter);
480 leaf_cache_.unfix_node((leaf_bid_type)it->second);
482 if (!(key_compare_(key_compare::max_value(), Splitter.first) ||
483 key_compare_(Splitter.first, key_compare::max_value())))
487 STXXL_VERBOSE1(
"Inserting new value into root node");
489 insert_into_root(Splitter);
491 assert(leaf_cache_.nfixed() == 0);
492 assert(node_cache_.nfixed() == 0);
497 STXXL_VERBOSE1(
"Inserting new value into a node");
498 node_type * Node = node_cache_.get_node((node_bid_type)it->second,
true);
500 std::pair<key_type, node_bid_type> Splitter;
501 std::pair<iterator, bool> result = Node->insert(x, height_ - 1, Splitter);
505 node_cache_.unfix_node((node_bid_type)it->second);
507 if (!(key_compare_(key_compare::max_value(), Splitter.first) ||
508 key_compare_(Splitter.first, key_compare::max_value())))
512 STXXL_VERBOSE1(
"Inserting new value into root node");
514 insert_into_root(Splitter);
516 assert(leaf_cache_.nfixed() == 0);
517 assert(node_cache_.nfixed() == 0);
524 root_node_iterator_type it = root_node_.begin();
525 assert(it != root_node_.end());
529 STXXL_VERBOSE1(
"btree: retrieving begin() from the first leaf");
530 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second);
533 assert(leaf_cache_.nfixed() == 0);
534 assert(node_cache_.nfixed() == 0);
535 return Leaf->begin();
539 STXXL_VERBOSE1(
"btree: retrieving begin() from the first node");
540 node_type * Node = node_cache_.get_node((node_bid_type)it->second,
true);
542 iterator result = Node->begin(height_ - 1);
543 node_cache_.unfix_node((node_bid_type)it->second);
545 assert(leaf_cache_.nfixed() == 0);
546 assert(node_cache_.nfixed() == 0);
551 const_iterator begin()
const
553 root_node_const_iterator_type it = root_node_.begin();
554 assert(it != root_node_.end());
558 STXXL_VERBOSE1(
"btree: retrieving begin() from the first leaf");
559 leaf_type
const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second);
561 assert(leaf_cache_.nfixed() == 0);
562 assert(node_cache_.nfixed() == 0);
563 return Leaf->begin();
567 STXXL_VERBOSE1(
"btree: retrieving begin() from the first node");
568 node_type
const * Node = node_cache_.get_const_node((node_bid_type)it->second,
true);
570 const_iterator result = Node->begin(height_ - 1);
571 node_cache_.unfix_node((node_bid_type)it->second);
572 assert(leaf_cache_.nfixed() == 0);
573 assert(node_cache_.nfixed() == 0);
582 const_iterator end()
const
587 data_type & operator [] (
const key_type & k)
589 return (*((insert(value_type(k, data_type()))).first)).second;
592 iterator
find(
const key_type & k)
594 root_node_iterator_type it = root_node_.lower_bound(k);
595 assert(it != root_node_.end());
599 STXXL_VERBOSE1(
"Searching in a leaf");
600 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second,
true);
602 iterator result = Leaf->find(k);
603 leaf_cache_.unfix_node((leaf_bid_type)it->second);
604 assert(result == end() || result->first == k);
605 assert(leaf_cache_.nfixed() == 0);
606 assert(node_cache_.nfixed() == 0);
611 STXXL_VERBOSE1(
"Searching in a node");
612 node_type * Node = node_cache_.get_node((node_bid_type)it->second,
true);
614 iterator result = Node->find(k, height_ - 1);
615 node_cache_.unfix_node((node_bid_type)it->second);
617 assert(result == end() || result->first == k);
618 assert(leaf_cache_.nfixed() == 0);
619 assert(node_cache_.nfixed() == 0);
623 const_iterator
find(
const key_type & k)
const
625 root_node_const_iterator_type it = root_node_.lower_bound(k);
626 assert(it != root_node_.end());
630 STXXL_VERBOSE1(
"Searching in a leaf");
631 leaf_type
const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second,
true);
633 const_iterator result = Leaf->find(k);
634 leaf_cache_.unfix_node((leaf_bid_type)it->second);
635 assert(result == end() || result->first == k);
636 assert(leaf_cache_.nfixed() == 0);
637 assert(node_cache_.nfixed() == 0);
642 STXXL_VERBOSE1(
"Searching in a node");
643 node_type
const * Node = node_cache_.get_const_node((node_bid_type)it->second,
true);
645 const_iterator result = Node->find(k, height_ - 1);
646 node_cache_.unfix_node((node_bid_type)it->second);
648 assert(result == end() || result->first == k);
649 assert(leaf_cache_.nfixed() == 0);
650 assert(node_cache_.nfixed() == 0);
654 iterator lower_bound(
const key_type & k)
656 root_node_iterator_type it = root_node_.lower_bound(k);
657 assert(it != root_node_.end());
661 STXXL_VERBOSE1(
"Searching lower bound in a leaf");
662 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second,
true);
664 iterator result = Leaf->lower_bound(k);
665 leaf_cache_.unfix_node((leaf_bid_type)it->second);
666 assert(leaf_cache_.nfixed() == 0);
667 assert(node_cache_.nfixed() == 0);
672 STXXL_VERBOSE1(
"Searching lower bound in a node");
673 node_type * Node = node_cache_.get_node((node_bid_type)it->second,
true);
675 iterator result = Node->lower_bound(k, height_ - 1);
676 node_cache_.unfix_node((node_bid_type)it->second);
678 assert(leaf_cache_.nfixed() == 0);
679 assert(node_cache_.nfixed() == 0);
683 const_iterator lower_bound(
const key_type & k)
const
685 root_node_const_iterator_type it = root_node_.lower_bound(k);
686 assert(it != root_node_.end());
690 STXXL_VERBOSE1(
"Searching lower bound in a leaf");
691 leaf_type
const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second,
true);
693 const_iterator result = Leaf->lower_bound(k);
694 leaf_cache_.unfix_node((leaf_bid_type)it->second);
696 assert(leaf_cache_.nfixed() == 0);
697 assert(node_cache_.nfixed() == 0);
702 STXXL_VERBOSE1(
"Searching lower bound in a node");
703 node_type
const * Node = node_cache_.get_const_node((node_bid_type)it->second,
true);
705 const_iterator result = Node->lower_bound(k, height_ - 1);
706 node_cache_.unfix_node((node_bid_type)it->second);
708 assert(leaf_cache_.nfixed() == 0);
709 assert(node_cache_.nfixed() == 0);
713 iterator upper_bound(
const key_type & k)
715 root_node_iterator_type it = root_node_.upper_bound(k);
716 assert(it != root_node_.end());
720 STXXL_VERBOSE1(
"Searching upper bound in a leaf");
721 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second,
true);
723 iterator result = Leaf->upper_bound(k);
724 leaf_cache_.unfix_node((leaf_bid_type)it->second);
726 assert(leaf_cache_.nfixed() == 0);
727 assert(node_cache_.nfixed() == 0);
732 STXXL_VERBOSE1(
"Searching upper bound in a node");
733 node_type * Node = node_cache_.get_node((node_bid_type)it->second,
true);
735 iterator result = Node->upper_bound(k, height_ - 1);
736 node_cache_.unfix_node((node_bid_type)it->second);
738 assert(leaf_cache_.nfixed() == 0);
739 assert(node_cache_.nfixed() == 0);
743 const_iterator upper_bound(
const key_type & k)
const
745 root_node_const_iterator_type it = root_node_.upper_bound(k);
746 assert(it != root_node_.end());
750 STXXL_VERBOSE1(
"Searching upper bound in a leaf");
751 leaf_type
const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second,
true);
753 const_iterator result = Leaf->upper_bound(k);
754 leaf_cache_.unfix_node((leaf_bid_type)it->second);
756 assert(leaf_cache_.nfixed() == 0);
757 assert(node_cache_.nfixed() == 0);
762 STXXL_VERBOSE1(
"Searching upper bound in a node");
763 node_type
const * Node = node_cache_.get_const_node((node_bid_type)it->second,
true);
765 const_iterator result = Node->upper_bound(k, height_ - 1);
766 node_cache_.unfix_node((node_bid_type)it->second);
768 assert(leaf_cache_.nfixed() == 0);
769 assert(node_cache_.nfixed() == 0);
773 std::pair<iterator, iterator> equal_range(
const key_type & k)
775 iterator l = lower_bound(k);
777 if (l == end() || key_compare_(k, l->first))
778 return std::pair<iterator, iterator>(l, l);
784 assert(leaf_cache_.nfixed() == 0);
785 assert(node_cache_.nfixed() == 0);
787 return std::pair<iterator, iterator>(l, u);
790 std::pair<const_iterator, const_iterator> equal_range(
const key_type & k)
const
792 const_iterator l = lower_bound(k);
794 if (l == end() || key_compare_(k, l->first))
795 return std::pair<const_iterator, const_iterator>(l, l);
798 const_iterator u = l;
801 assert(leaf_cache_.nfixed() == 0);
802 assert(node_cache_.nfixed() == 0);
803 return std::pair<const_iterator, const_iterator>(l, u);
806 size_type erase(
const key_type & k)
808 root_node_iterator_type it = root_node_.lower_bound(k);
809 assert(it != root_node_.end());
812 STXXL_VERBOSE1(
"Deleting key from a leaf");
813 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second,
true);
815 size_type result = Leaf->erase(k);
817 leaf_cache_.unfix_node((leaf_bid_type)it->second);
818 assert(leaf_cache_.nfixed() == 0);
819 assert(node_cache_.nfixed() == 0);
821 if ((!Leaf->underflows()) || root_node_.size() == 1)
825 STXXL_VERBOSE1(
"btree: Fusing or rebalancing a leaf");
826 fuse_or_balance(it, leaf_cache_);
828 assert(leaf_cache_.nfixed() == 0);
829 assert(node_cache_.nfixed() == 0);
835 STXXL_VERBOSE1(
"Deleting key from a node");
836 assert(root_node_.size() >= 2);
837 node_type * Node = node_cache_.get_node((node_bid_type)it->second,
true);
839 size_type result = Node->erase(k, height_ - 1);
841 node_cache_.unfix_node((node_bid_type)it->second);
842 assert(leaf_cache_.nfixed() == 0);
843 assert(node_cache_.nfixed() == 0);
844 if (!Node->underflows())
848 STXXL_VERBOSE1(
"Fusing or rebalancing a node");
849 fuse_or_balance(it, node_cache_);
851 if (root_node_.size() == 1)
853 STXXL_VERBOSE1(
"btree Root has size 1 and height > 2");
854 STXXL_VERBOSE1(
"btree Deallocate root and decrease height");
855 it = root_node_.begin();
856 node_bid_type RootBid = it->second;
857 assert(it->first == key_compare::max_value());
858 node_type * RootNode = node_cache_.get_node(RootBid);
860 assert(RootNode->back().first == key_compare::max_value());
862 root_node_.insert(RootNode->block().begin(),
863 RootNode->block().begin() + RootNode->size());
865 node_cache_.delete_node(RootBid);
867 STXXL_VERBOSE1(
"btree Decreasing height to " << height_);
870 assert(leaf_cache_.nfixed() == 0);
871 assert(node_cache_.nfixed() == 0);
876 size_type count(
const key_type & k)
878 if (
find(k) == end())
884 void erase(iterator pos)
886 assert(pos != end());
888 size_type old_size = size();
893 assert(size() == old_size - 1);
896 iterator insert(iterator ,
const value_type & x)
898 return insert(x).first;
903 deallocate_children();
911 assert(leaf_cache_.nfixed() == 0);
912 assert(node_cache_.nfixed() == 0);
915 template <
class InputIterator>
916 void insert(InputIterator b, InputIterator e)
924 template <
class InputIterator>
925 btree(InputIterator b,
927 const key_compare & c_,
928 unsigned_type node_cache_size_in_bytes,
929 unsigned_type leaf_cache_size_in_bytes,
930 bool range_sorted =
false,
931 double node_fill_factor = 0.75,
932 double leaf_fill_factor = 0.6
935 node_cache_(node_cache_size_in_bytes, this, key_compare_),
936 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_),
940 prefetching_enabled_(true),
943 STXXL_VERBOSE1(
"Creating a btree, addr=" <<
this);
947 if (range_sorted ==
false)
951 assert(leaf_cache_.nfixed() == 0);
952 assert(node_cache_.nfixed() == 0);
956 bulk_construction(b, e, node_fill_factor, leaf_fill_factor);
957 assert(leaf_cache_.nfixed() == 0);
958 assert(node_cache_.nfixed() == 0);
962 template <
class InputIterator>
963 btree(InputIterator b,
965 unsigned_type node_cache_size_in_bytes,
966 unsigned_type leaf_cache_size_in_bytes,
967 bool range_sorted =
false,
968 double node_fill_factor = 0.75,
969 double leaf_fill_factor = 0.6
971 node_cache_(node_cache_size_in_bytes, this, key_compare_),
972 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_),
976 prefetching_enabled_(true),
979 STXXL_VERBOSE1(
"Creating a btree, addr=" <<
this);
983 if (range_sorted ==
false)
987 assert(leaf_cache_.nfixed() == 0);
988 assert(node_cache_.nfixed() == 0);
992 bulk_construction(b, e, node_fill_factor, leaf_fill_factor);
993 assert(leaf_cache_.nfixed() == 0);
994 assert(node_cache_.nfixed() == 0);
997 void erase(iterator first, iterator last)
999 if (first == begin() && last == end())
1003 while (first != last)
1007 key_compare key_comp()
const
1009 return key_compare_;
1011 value_compare value_comp()
const
1013 return value_compare(key_compare_);
1016 void swap(btree & obj)
1018 std::swap(key_compare_, obj.key_compare_);
1020 std::swap(node_cache_, obj.node_cache_);
1021 std::swap(leaf_cache_, obj.leaf_cache_);
1024 std::swap(iterator_map_, obj.iterator_map_);
1026 std::swap(end_iterator, obj.end_iterator);
1027 std::swap(size_, obj.size_);
1028 std::swap(height_, obj.height_);
1029 std::swap(alloc_strategy_, obj.alloc_strategy_);
1030 std::swap(root_node_, obj.root_node_);
1033 void enable_prefetching()
1035 prefetching_enabled_ =
true;
1037 void disable_prefetching()
1039 prefetching_enabled_ =
false;
1041 bool prefetching_enabled()
1043 return prefetching_enabled_;
1046 void print_statistics(std::ostream & o)
const
1048 o <<
"Node cache statistics:" << std::endl;
1049 node_cache_.print_statistics(o);
1050 o <<
"Leaf cache statistics:" << std::endl;
1051 leaf_cache_.print_statistics(o);
1053 void reset_statistics()
1055 node_cache_.reset_statistics();
1056 leaf_cache_.reset_statistics();
1060 template <
class KeyType,
1063 unsigned LogNodeSize,
1064 unsigned LogLeafSize,
1065 class PDAllocStrategy
1067 inline bool operator == (
const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1068 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
1070 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
1073 template <
class KeyType,
1076 unsigned LogNodeSize,
1077 unsigned LogLeafSize,
1078 class PDAllocStrategy
1080 inline bool operator != (
const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1081 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
1087 template <
class KeyType,
1090 unsigned LogNodeSize,
1091 unsigned LogLeafSize,
1092 class PDAllocStrategy
1094 inline bool operator < (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1095 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
1097 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
1101 template <
class KeyType,
1104 unsigned LogNodeSize,
1105 unsigned LogLeafSize,
1106 class PDAllocStrategy
1108 inline bool operator > (
const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1109 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
1115 template <
class KeyType,
1118 unsigned LogNodeSize,
1119 unsigned LogLeafSize,
1120 class PDAllocStrategy
1122 inline bool operator <= (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1123 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
1128 template <
class KeyType,
1131 unsigned LogNodeSize,
1132 unsigned LogLeafSize,
1133 class PDAllocStrategy
1135 inline bool operator >= (
const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1136 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
1142 __STXXL_END_NAMESPACE
1147 template <
class KeyType,
1150 unsigned LogNodeSize,
1151 unsigned LogLeafSize,
1152 class PDAllocStrategy
1154 void swap(stxxl::btree::btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1155 stxxl::btree::btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)