13 #ifndef STXXL_CONTAINERS_BTREE__BTREE_H
14 #define STXXL_CONTAINERS_BTREE__BTREE_H
17 #include <stxxl/bits/namespace.h>
18 #include <stxxl/bits/containers/btree/iterator.h>
19 #include <stxxl/bits/containers/btree/iterator_map.h>
20 #include <stxxl/bits/containers/btree/leaf.h>
21 #include <stxxl/bits/containers/btree/node_cache.h>
22 #include <stxxl/bits/containers/btree/root_node.h>
23 #include <stxxl/bits/containers/btree/node.h>
24 #include <stxxl/vector>
27 __STXXL_BEGIN_NAMESPACE
31 template <
class KeyType,
38 class btree :
private noncopyable
41 typedef KeyType key_type;
42 typedef DataType data_type;
43 typedef CompareType key_compare;
45 typedef btree<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> SelfType;
47 typedef PDAllocStrategy alloc_strategy_type;
49 typedef stxxl::uint64 size_type;
50 typedef stxxl::int64 difference_type;
51 typedef std::pair<const key_type, data_type> value_type;
52 typedef value_type & reference;
53 typedef const value_type & const_reference;
54 typedef value_type * pointer;
55 typedef value_type
const * const_pointer;
59 typedef normal_leaf<key_type, data_type, key_compare, RawLeafSize, SelfType> leaf_type;
60 friend class normal_leaf<key_type, data_type, key_compare, RawLeafSize, SelfType>;
61 typedef typename leaf_type::block_type leaf_block_type;
62 typedef typename leaf_type::bid_type leaf_bid_type;
63 typedef node_cache<leaf_type, SelfType> leaf_cache_type;
64 friend class node_cache<leaf_type, SelfType>;
66 typedef btree_iterator<SelfType> iterator;
67 typedef btree_const_iterator<SelfType> const_iterator;
68 friend class btree_iterator_base<SelfType>;
70 typedef iterator_map<SelfType> iterator_map_type;
72 typedef normal_node<key_type, key_compare, RawNodeSize, SelfType> node_type;
73 typedef typename node_type::block_type node_block_type;
74 friend class normal_node<key_type, key_compare, RawNodeSize, SelfType>;
75 typedef typename node_type::bid_type node_bid_type;
76 typedef node_cache<node_type, SelfType> node_cache_type;
77 friend class node_cache<node_type, SelfType>;
79 typedef typename leaf_type::value_compare value_compare;
82 min_node_size = node_type::min_size,
83 max_node_size = node_type::max_size,
84 min_leaf_size = leaf_type::min_size,
85 max_leaf_size = leaf_type::max_size
89 key_compare key_compare_;
90 mutable node_cache_type node_cache_;
91 mutable leaf_cache_type leaf_cache_;
92 iterator_map_type iterator_map_;
94 unsigned_type height_;
95 bool prefetching_enabled_;
97 alloc_strategy_type alloc_strategy_;
99 typedef std::map<key_type, node_bid_type, key_compare> root_node_type;
100 typedef typename root_node_type::iterator root_node_iterator_type;
101 typedef typename root_node_type::const_iterator root_node_const_iterator_type;
102 typedef std::pair<key_type, node_bid_type> root_node_pair_type;
105 root_node_type root_node_;
106 iterator end_iterator;
109 template <
class BIDType>
110 void insert_into_root(
const std::pair<key_type, BIDType> & splitter)
112 std::pair<root_node_iterator_type, bool> result =
113 root_node_.insert(splitter);
114 assert(result.second ==
true);
115 if (root_node_.size() > max_node_size)
117 STXXL_VERBOSE1(
"btree::insert_into_root, overflow happened, splitting");
119 node_bid_type LeftBid;
120 node_type * LeftNode = node_cache_.get_new_node(LeftBid);
122 node_bid_type RightBid;
123 node_type * RightNode = node_cache_.get_new_node(RightBid);
126 const unsigned_type old_size = root_node_.size();
127 const unsigned_type half = root_node_.size() / 2;
129 root_node_iterator_type it = root_node_.begin();
130 typename node_block_type::iterator block_it = LeftNode->block().begin();
138 LeftNode->block().info.cur_size = half;
139 key_type LeftKey = (LeftNode->block()[half - 1]).first;
141 block_it = RightNode->block().begin();
149 unsigned_type right_size = RightNode->block().info.cur_size = old_size - half;
150 key_type RightKey = (RightNode->block()[right_size - 1]).first;
152 assert(old_size == RightNode->size() + LeftNode->size());
156 root_node_.insert(root_node_pair_type(LeftKey, LeftBid));
157 root_node_.insert(root_node_pair_type(RightKey, RightBid));
161 STXXL_VERBOSE1(
"btree Increasing height to " << height_);
162 if (node_cache_.size() < (height_ - 1))
164 STXXL_THROW(std::runtime_error,
"btree::bulk_construction",
"The height of the tree (" << height_ <<
") has exceeded the required capacity ("
165 << (node_cache_.size() + 1) <<
") of the node cache. " <<
166 "Increase the node cache size.");
171 template <
class CacheType>
172 void fuse_or_balance(root_node_iterator_type UIt, CacheType & cache_)
174 typedef typename CacheType::node_type local_node_type;
175 typedef typename local_node_type::bid_type local_bid_type;
177 root_node_iterator_type leftIt, rightIt;
178 if (UIt->first == key_compare::max_value())
180 assert(UIt != root_node_.begin());
188 assert(rightIt != root_node_.end());
192 local_bid_type LeftBid = (local_bid_type)leftIt->second;
193 local_bid_type RightBid = (local_bid_type)rightIt->second;
194 local_node_type * LeftNode = cache_.get_node(LeftBid,
true);
195 local_node_type * RightNode = cache_.get_node(RightBid,
true);
197 const unsigned_type TotalSize = LeftNode->size() + RightNode->size();
198 if (TotalSize <= RightNode->max_nelements())
201 RightNode->fuse(*LeftNode);
203 cache_.unfix_node(RightBid);
204 cache_.delete_node(LeftBid);
206 root_node_.erase(leftIt);
212 key_type NewSplitter = RightNode->balance(*LeftNode);
214 root_node_.erase(leftIt);
216 root_node_.insert(root_node_pair_type(NewSplitter, (node_bid_type)LeftBid));
218 cache_.unfix_node(LeftBid);
219 cache_.unfix_node(RightBid);
223 void create_empty_leaf()
225 leaf_bid_type NewBid;
226 leaf_type * NewLeaf = leaf_cache_.get_new_node(NewBid);
228 end_iterator = NewLeaf->end();
229 root_node_.insert(root_node_pair_type(key_compare::max_value(), (node_bid_type)NewBid));
232 void deallocate_children()
237 root_node_const_iterator_type it = root_node_.begin();
238 for ( ; it != root_node_.end(); ++it)
241 leaf_cache_.delete_node((leaf_bid_type)it->second);
246 root_node_const_iterator_type it = root_node_.begin();
247 for ( ; it != root_node_.end(); ++it)
249 node_type * Node = node_cache_.get_node((node_bid_type)it->second);
251 Node->deallocate_children(height_ - 1);
253 node_cache_.delete_node((node_bid_type)it->second);
258 template <
class InputIterator>
259 void bulk_construction(InputIterator b, InputIterator e,
double node_fill_factor,
double leaf_fill_factor)
261 assert(node_fill_factor >= 0.5);
262 assert(leaf_fill_factor >= 0.5);
263 key_type lastKey = key_compare::max_value();
265 typedef std::pair<key_type, node_bid_type> key_bid_pair;
266 typedef typename stxxl::VECTOR_GENERATOR<key_bid_pair, 1, 1,
267 node_block_type::raw_size>::result key_bid_vector_type;
269 key_bid_vector_type Bids;
271 leaf_bid_type NewBid;
272 leaf_type * Leaf = leaf_cache_.get_new_node(NewBid);
273 const unsigned_type max_leaf_elements = unsigned_type(
double(Leaf->max_nelements()) * leaf_fill_factor);
280 if (key_compare_(b->first, lastKey) || key_compare_(lastKey, b->first))
283 if (Leaf->size() == max_leaf_elements)
286 Bids.push_back(key_bid_pair(Leaf->back().first, (node_bid_type)NewBid));
288 leaf_type * NewLeaf = leaf_cache_.get_new_node(NewBid);
291 Leaf->succ() = NewLeaf->my_bid();
292 NewLeaf->pred() = Leaf->my_bid();
303 if (Leaf->underflows() && !Bids.empty())
305 leaf_type * LeftLeaf = leaf_cache_.get_node((leaf_bid_type)(Bids.back().second));
307 if (LeftLeaf->size() + Leaf->size() <= Leaf->max_nelements())
309 Leaf->fuse(*LeftLeaf);
310 leaf_cache_.delete_node((leaf_bid_type)(Bids.back().second));
312 assert(!Leaf->overflows() && !Leaf->underflows());
317 const key_type NewSplitter = Leaf->balance(*LeftLeaf);
318 Bids.back().first = NewSplitter;
319 assert(!LeftLeaf->overflows() && !LeftLeaf->underflows());
323 assert(!Leaf->overflows() && (!Leaf->underflows() || size_ <= max_leaf_size));
325 end_iterator = Leaf->end();
327 Bids.push_back(key_bid_pair(key_compare::max_value(), (node_bid_type)NewBid));
329 const unsigned_type max_node_elements = unsigned_type(
double(max_node_size) * node_fill_factor);
331 while (Bids.size() > max_node_elements)
333 key_bid_vector_type ParentBids;
335 stxxl::uint64 nparents = div_ceil(Bids.size(), max_node_elements);
336 assert(nparents >= 2);
337 STXXL_VERBOSE1(
"btree bulk constructBids.size() " << Bids.size() <<
" nparents: " << nparents <<
" max_ns: "
338 << max_node_elements);
339 typename key_bid_vector_type::const_iterator it = Bids.begin();
343 node_bid_type NewBid;
344 node_type * Node = node_cache_.get_new_node(NewBid);
346 unsigned_type cnt = 0;
347 for ( ; cnt < max_node_elements && it != Bids.end(); ++cnt, ++it)
349 Node->push_back(*it);
351 STXXL_VERBOSE1(
"btree bulk construct Node size : " << Node->size() <<
" limits: " <<
352 Node->min_nelements() <<
" " << Node->max_nelements() <<
" max_node_elements: " << max_node_elements);
354 if (Node->underflows())
356 assert(it == Bids.end());
357 assert(!ParentBids.empty());
359 node_type * LeftNode = node_cache_.get_node(ParentBids.back().second);
361 if (LeftNode->size() + Node->size() <= Node->max_nelements())
363 Node->fuse(*LeftNode);
364 node_cache_.delete_node(ParentBids.back().second);
365 ParentBids.pop_back();
369 const key_type NewSplitter = Node->balance(*LeftNode);
370 ParentBids.back().first = NewSplitter;
371 assert(!LeftNode->overflows() && !LeftNode->underflows());
374 assert(!Node->overflows() && !Node->underflows());
376 ParentBids.push_back(key_bid_pair(Node->back().first, NewBid));
377 }
while (it != Bids.end());
379 std::swap(ParentBids, Bids);
381 assert(nparents == Bids.size() || (nparents - 1) == Bids.size());
384 STXXL_VERBOSE1(
"Increasing height to " << height_);
385 if (node_cache_.size() < (height_ - 1))
387 STXXL_THROW(std::runtime_error,
"btree::bulk_construction",
"The height of the tree (" << height_ <<
") has exceeded the required capacity ("
388 << (node_cache_.size() + 1) <<
") of the node cache. " <<
389 "Increase the node cache size.");
393 root_node_.insert(Bids.begin(), Bids.end());
397 btree(unsigned_type node_cache_size_in_bytes,
398 unsigned_type leaf_cache_size_in_bytes
400 node_cache_(node_cache_size_in_bytes, this, key_compare_),
401 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_),
405 prefetching_enabled_(true),
408 STXXL_VERBOSE1(
"Creating a btree, addr=" <<
this);
409 STXXL_VERBOSE1(
" bytes in a node: " << node_bid_type::size);
410 STXXL_VERBOSE1(
" bytes in a leaf: " << leaf_bid_type::size);
411 STXXL_VERBOSE1(
" elements in a node: " << node_block_type::size);
412 STXXL_VERBOSE1(
" elements in a leaf: " << leaf_block_type::size);
413 STXXL_VERBOSE1(
" size of a node element: " <<
sizeof(
typename node_block_type::value_type));
414 STXXL_VERBOSE1(
" size of a leaf element: " <<
sizeof(
typename leaf_block_type::value_type));
420 btree(
const key_compare & c_,
421 unsigned_type node_cache_size_in_bytes,
422 unsigned_type leaf_cache_size_in_bytes
425 node_cache_(node_cache_size_in_bytes, this, key_compare_),
426 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_),
430 prefetching_enabled_(true),
433 STXXL_VERBOSE1(
"Creating a btree, addr=" <<
this);
434 STXXL_VERBOSE1(
" bytes in a node: " << node_bid_type::size);
435 STXXL_VERBOSE1(
" bytes in a leaf: " << leaf_bid_type::size);
444 deallocate_children();
451 size_type size()
const
456 size_type max_size()
const
458 return (std::numeric_limits<size_type>::max)();
466 std::pair<iterator, bool> insert(
const value_type & x)
468 root_node_iterator_type it = root_node_.lower_bound(x.first);
469 assert(!root_node_.empty());
470 assert(it != root_node_.end());
473 STXXL_VERBOSE1(
"Inserting new value into a leaf");
474 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second,
true);
476 std::pair<key_type, leaf_bid_type> Splitter;
477 std::pair<iterator, bool> result = Leaf->insert(x, Splitter);
481 leaf_cache_.unfix_node((leaf_bid_type)it->second);
483 if (!(key_compare_(key_compare::max_value(), Splitter.first) ||
484 key_compare_(Splitter.first, key_compare::max_value())))
488 STXXL_VERBOSE1(
"Inserting new value into root node");
490 insert_into_root(Splitter);
492 assert(leaf_cache_.nfixed() == 0);
493 assert(node_cache_.nfixed() == 0);
498 STXXL_VERBOSE1(
"Inserting new value into a node");
499 node_type * Node = node_cache_.get_node((node_bid_type)it->second,
true);
501 std::pair<key_type, node_bid_type> Splitter;
502 std::pair<iterator, bool> result = Node->insert(x, height_ - 1, Splitter);
506 node_cache_.unfix_node((node_bid_type)it->second);
508 if (!(key_compare_(key_compare::max_value(), Splitter.first) ||
509 key_compare_(Splitter.first, key_compare::max_value())))
513 STXXL_VERBOSE1(
"Inserting new value into root node");
515 insert_into_root(Splitter);
517 assert(leaf_cache_.nfixed() == 0);
518 assert(node_cache_.nfixed() == 0);
525 root_node_iterator_type it = root_node_.begin();
526 assert(it != root_node_.end());
530 STXXL_VERBOSE1(
"btree: retrieving begin() from the first leaf");
531 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second);
534 assert(leaf_cache_.nfixed() == 0);
535 assert(node_cache_.nfixed() == 0);
536 return Leaf->begin();
540 STXXL_VERBOSE1(
"btree: retrieving begin() from the first node");
541 node_type * Node = node_cache_.get_node((node_bid_type)it->second,
true);
543 iterator result = Node->begin(height_ - 1);
544 node_cache_.unfix_node((node_bid_type)it->second);
546 assert(leaf_cache_.nfixed() == 0);
547 assert(node_cache_.nfixed() == 0);
552 const_iterator begin()
const
554 root_node_const_iterator_type it = root_node_.begin();
555 assert(it != root_node_.end());
559 STXXL_VERBOSE1(
"btree: retrieving begin() from the first leaf");
560 leaf_type
const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second);
562 assert(leaf_cache_.nfixed() == 0);
563 assert(node_cache_.nfixed() == 0);
564 return Leaf->begin();
568 STXXL_VERBOSE1(
"btree: retrieving begin() from the first node");
569 node_type
const * Node = node_cache_.get_const_node((node_bid_type)it->second,
true);
571 const_iterator result = Node->begin(height_ - 1);
572 node_cache_.unfix_node((node_bid_type)it->second);
573 assert(leaf_cache_.nfixed() == 0);
574 assert(node_cache_.nfixed() == 0);
583 const_iterator end()
const
588 data_type & operator [] (
const key_type & k)
590 return (*((insert(value_type(k, data_type()))).first)).second;
593 iterator
find(
const key_type & k)
595 root_node_iterator_type it = root_node_.lower_bound(k);
596 assert(it != root_node_.end());
600 STXXL_VERBOSE1(
"Searching in a leaf");
601 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second,
true);
603 iterator result = Leaf->find(k);
604 leaf_cache_.unfix_node((leaf_bid_type)it->second);
605 assert(result == end() || result->first == k);
606 assert(leaf_cache_.nfixed() == 0);
607 assert(node_cache_.nfixed() == 0);
612 STXXL_VERBOSE1(
"Searching in a node");
613 node_type * Node = node_cache_.get_node((node_bid_type)it->second,
true);
615 iterator result = Node->find(k, height_ - 1);
616 node_cache_.unfix_node((node_bid_type)it->second);
618 assert(result == end() || result->first == k);
619 assert(leaf_cache_.nfixed() == 0);
620 assert(node_cache_.nfixed() == 0);
624 const_iterator
find(
const key_type & k)
const
626 root_node_const_iterator_type it = root_node_.lower_bound(k);
627 assert(it != root_node_.end());
631 STXXL_VERBOSE1(
"Searching in a leaf");
632 leaf_type
const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second,
true);
634 const_iterator result = Leaf->find(k);
635 leaf_cache_.unfix_node((leaf_bid_type)it->second);
636 assert(result == end() || result->first == k);
637 assert(leaf_cache_.nfixed() == 0);
638 assert(node_cache_.nfixed() == 0);
643 STXXL_VERBOSE1(
"Searching in a node");
644 node_type
const * Node = node_cache_.get_const_node((node_bid_type)it->second,
true);
646 const_iterator result = Node->find(k, height_ - 1);
647 node_cache_.unfix_node((node_bid_type)it->second);
649 assert(result == end() || result->first == k);
650 assert(leaf_cache_.nfixed() == 0);
651 assert(node_cache_.nfixed() == 0);
655 iterator lower_bound(
const key_type & k)
657 root_node_iterator_type it = root_node_.lower_bound(k);
658 assert(it != root_node_.end());
662 STXXL_VERBOSE1(
"Searching lower bound in a leaf");
663 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second,
true);
665 iterator result = Leaf->lower_bound(k);
666 leaf_cache_.unfix_node((leaf_bid_type)it->second);
667 assert(leaf_cache_.nfixed() == 0);
668 assert(node_cache_.nfixed() == 0);
673 STXXL_VERBOSE1(
"Searching lower bound in a node");
674 node_type * Node = node_cache_.get_node((node_bid_type)it->second,
true);
676 iterator result = Node->lower_bound(k, height_ - 1);
677 node_cache_.unfix_node((node_bid_type)it->second);
679 assert(leaf_cache_.nfixed() == 0);
680 assert(node_cache_.nfixed() == 0);
684 const_iterator lower_bound(
const key_type & k)
const
686 root_node_const_iterator_type it = root_node_.lower_bound(k);
687 assert(it != root_node_.end());
691 STXXL_VERBOSE1(
"Searching lower bound in a leaf");
692 leaf_type
const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second,
true);
694 const_iterator result = Leaf->lower_bound(k);
695 leaf_cache_.unfix_node((leaf_bid_type)it->second);
697 assert(leaf_cache_.nfixed() == 0);
698 assert(node_cache_.nfixed() == 0);
703 STXXL_VERBOSE1(
"Searching lower bound in a node");
704 node_type
const * Node = node_cache_.get_const_node((node_bid_type)it->second,
true);
706 const_iterator result = Node->lower_bound(k, height_ - 1);
707 node_cache_.unfix_node((node_bid_type)it->second);
709 assert(leaf_cache_.nfixed() == 0);
710 assert(node_cache_.nfixed() == 0);
714 iterator upper_bound(
const key_type & k)
716 root_node_iterator_type it = root_node_.upper_bound(k);
717 assert(it != root_node_.end());
721 STXXL_VERBOSE1(
"Searching upper bound in a leaf");
722 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second,
true);
724 iterator result = Leaf->upper_bound(k);
725 leaf_cache_.unfix_node((leaf_bid_type)it->second);
727 assert(leaf_cache_.nfixed() == 0);
728 assert(node_cache_.nfixed() == 0);
733 STXXL_VERBOSE1(
"Searching upper bound in a node");
734 node_type * Node = node_cache_.get_node((node_bid_type)it->second,
true);
736 iterator result = Node->upper_bound(k, height_ - 1);
737 node_cache_.unfix_node((node_bid_type)it->second);
739 assert(leaf_cache_.nfixed() == 0);
740 assert(node_cache_.nfixed() == 0);
744 const_iterator upper_bound(
const key_type & k)
const
746 root_node_const_iterator_type it = root_node_.upper_bound(k);
747 assert(it != root_node_.end());
751 STXXL_VERBOSE1(
"Searching upper bound in a leaf");
752 leaf_type
const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second,
true);
754 const_iterator result = Leaf->upper_bound(k);
755 leaf_cache_.unfix_node((leaf_bid_type)it->second);
757 assert(leaf_cache_.nfixed() == 0);
758 assert(node_cache_.nfixed() == 0);
763 STXXL_VERBOSE1(
"Searching upper bound in a node");
764 node_type
const * Node = node_cache_.get_const_node((node_bid_type)it->second,
true);
766 const_iterator result = Node->upper_bound(k, height_ - 1);
767 node_cache_.unfix_node((node_bid_type)it->second);
769 assert(leaf_cache_.nfixed() == 0);
770 assert(node_cache_.nfixed() == 0);
774 std::pair<iterator, iterator> equal_range(
const key_type & k)
776 iterator l = lower_bound(k);
778 if (l == end() || key_compare_(k, l->first))
779 return std::pair<iterator, iterator>(l, l);
785 assert(leaf_cache_.nfixed() == 0);
786 assert(node_cache_.nfixed() == 0);
788 return std::pair<iterator, iterator>(l, u);
791 std::pair<const_iterator, const_iterator> equal_range(
const key_type & k)
const
793 const_iterator l = lower_bound(k);
795 if (l == end() || key_compare_(k, l->first))
796 return std::pair<const_iterator, const_iterator>(l, l);
799 const_iterator u = l;
802 assert(leaf_cache_.nfixed() == 0);
803 assert(node_cache_.nfixed() == 0);
804 return std::pair<const_iterator, const_iterator>(l, u);
807 size_type erase(
const key_type & k)
809 root_node_iterator_type it = root_node_.lower_bound(k);
810 assert(it != root_node_.end());
813 STXXL_VERBOSE1(
"Deleting key from a leaf");
814 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second,
true);
816 size_type result = Leaf->erase(k);
818 leaf_cache_.unfix_node((leaf_bid_type)it->second);
819 assert(leaf_cache_.nfixed() == 0);
820 assert(node_cache_.nfixed() == 0);
822 if ((!Leaf->underflows()) || root_node_.size() == 1)
826 STXXL_VERBOSE1(
"btree: Fusing or rebalancing a leaf");
827 fuse_or_balance(it, leaf_cache_);
829 assert(leaf_cache_.nfixed() == 0);
830 assert(node_cache_.nfixed() == 0);
836 STXXL_VERBOSE1(
"Deleting key from a node");
837 assert(root_node_.size() >= 2);
838 node_type * Node = node_cache_.get_node((node_bid_type)it->second,
true);
840 size_type result = Node->erase(k, height_ - 1);
842 node_cache_.unfix_node((node_bid_type)it->second);
843 assert(leaf_cache_.nfixed() == 0);
844 assert(node_cache_.nfixed() == 0);
845 if (!Node->underflows())
849 STXXL_VERBOSE1(
"Fusing or rebalancing a node");
850 fuse_or_balance(it, node_cache_);
852 if (root_node_.size() == 1)
854 STXXL_VERBOSE1(
"btree Root has size 1 and height > 2");
855 STXXL_VERBOSE1(
"btree Deallocate root and decrease height");
856 it = root_node_.begin();
857 node_bid_type RootBid = it->second;
858 assert(it->first == key_compare::max_value());
859 node_type * RootNode = node_cache_.get_node(RootBid);
861 assert(RootNode->back().first == key_compare::max_value());
863 root_node_.insert(RootNode->block().begin(),
864 RootNode->block().begin() + RootNode->size());
866 node_cache_.delete_node(RootBid);
868 STXXL_VERBOSE1(
"btree Decreasing height to " << height_);
871 assert(leaf_cache_.nfixed() == 0);
872 assert(node_cache_.nfixed() == 0);
877 size_type count(
const key_type & k)
879 if (
find(k) == end())
885 void erase(iterator pos)
887 assert(pos != end());
889 size_type old_size = size();
894 assert(size() == old_size - 1);
897 iterator insert(iterator ,
const value_type & x)
899 return insert(x).first;
904 deallocate_children();
912 assert(leaf_cache_.nfixed() == 0);
913 assert(node_cache_.nfixed() == 0);
916 template <
class InputIterator>
917 void insert(InputIterator b, InputIterator e)
925 template <
class InputIterator>
926 btree(InputIterator b,
928 const key_compare & c_,
929 unsigned_type node_cache_size_in_bytes,
930 unsigned_type leaf_cache_size_in_bytes,
931 bool range_sorted =
false,
932 double node_fill_factor = 0.75,
933 double leaf_fill_factor = 0.6
936 node_cache_(node_cache_size_in_bytes, this, key_compare_),
937 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_),
941 prefetching_enabled_(true),
944 STXXL_VERBOSE1(
"Creating a btree, addr=" <<
this);
945 STXXL_VERBOSE1(
" bytes in a node: " << node_bid_type::size);
946 STXXL_VERBOSE1(
" bytes in a leaf: " << leaf_bid_type::size);
948 if (range_sorted ==
false)
952 assert(leaf_cache_.nfixed() == 0);
953 assert(node_cache_.nfixed() == 0);
957 bulk_construction(b, e, node_fill_factor, leaf_fill_factor);
958 assert(leaf_cache_.nfixed() == 0);
959 assert(node_cache_.nfixed() == 0);
963 template <
class InputIterator>
964 btree(InputIterator b,
966 unsigned_type node_cache_size_in_bytes,
967 unsigned_type leaf_cache_size_in_bytes,
968 bool range_sorted =
false,
969 double node_fill_factor = 0.75,
970 double leaf_fill_factor = 0.6
972 node_cache_(node_cache_size_in_bytes, this, key_compare_),
973 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_),
977 prefetching_enabled_(true),
980 STXXL_VERBOSE1(
"Creating a btree, addr=" <<
this);
981 STXXL_VERBOSE1(
" bytes in a node: " << node_bid_type::size);
982 STXXL_VERBOSE1(
" bytes in a leaf: " << leaf_bid_type::size);
984 if (range_sorted ==
false)
988 assert(leaf_cache_.nfixed() == 0);
989 assert(node_cache_.nfixed() == 0);
993 bulk_construction(b, e, node_fill_factor, leaf_fill_factor);
994 assert(leaf_cache_.nfixed() == 0);
995 assert(node_cache_.nfixed() == 0);
998 void erase(iterator first, iterator last)
1000 if (first == begin() && last == end())
1004 while (first != last)
1008 key_compare key_comp()
const
1010 return key_compare_;
1012 value_compare value_comp()
const
1014 return value_compare(key_compare_);
1017 void swap(
btree & obj)
1019 std::swap(key_compare_, obj.key_compare_);
1021 std::swap(node_cache_, obj.node_cache_);
1022 std::swap(leaf_cache_, obj.leaf_cache_);
1025 std::swap(iterator_map_, obj.iterator_map_);
1027 std::swap(end_iterator, obj.end_iterator);
1028 std::swap(size_, obj.size_);
1029 std::swap(height_, obj.height_);
1030 std::swap(alloc_strategy_, obj.alloc_strategy_);
1031 std::swap(root_node_, obj.root_node_);
1034 void enable_prefetching()
1036 prefetching_enabled_ =
true;
1038 void disable_prefetching()
1040 prefetching_enabled_ =
false;
1042 bool prefetching_enabled()
1044 return prefetching_enabled_;
1047 void print_statistics(std::ostream & o)
const
1049 o <<
"Node cache statistics:" << std::endl;
1050 node_cache_.print_statistics(o);
1051 o <<
"Leaf cache statistics:" << std::endl;
1052 leaf_cache_.print_statistics(o);
1054 void reset_statistics()
1056 node_cache_.reset_statistics();
1057 leaf_cache_.reset_statistics();
1061 template <
class KeyType,
1064 unsigned LogNodeSize,
1065 unsigned LogLeafSize,
1066 class PDAllocStrategy
1068 inline bool operator == (
const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1069 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
1071 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
1074 template <
class KeyType,
1077 unsigned LogNodeSize,
1078 unsigned LogLeafSize,
1079 class PDAllocStrategy
1081 inline bool operator != (
const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1082 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
1088 template <
class KeyType,
1091 unsigned LogNodeSize,
1092 unsigned LogLeafSize,
1093 class PDAllocStrategy
1095 inline bool operator < (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1096 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
1098 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
1102 template <
class KeyType,
1105 unsigned LogNodeSize,
1106 unsigned LogLeafSize,
1107 class PDAllocStrategy
1109 inline bool operator > (
const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1110 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
1116 template <
class KeyType,
1119 unsigned LogNodeSize,
1120 unsigned LogLeafSize,
1121 class PDAllocStrategy
1123 inline bool operator <= (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1124 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
1129 template <
class KeyType,
1132 unsigned LogNodeSize,
1133 unsigned LogLeafSize,
1134 class PDAllocStrategy
1136 inline bool operator >= (
const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1137 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
1143 __STXXL_END_NAMESPACE
1148 template <
class KeyType,
1151 unsigned LogNodeSize,
1152 unsigned LogLeafSize,
1153 class PDAllocStrategy
1155 void swap(stxxl::btree::btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
1156 stxxl::btree::btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
Definition: test_stream.cpp:36
_ExtIterator find(_ExtIterator _begin, _ExtIterator _end, const _EqualityComparable &_value, int_type nbuffers)
External equivalent of std::find.
Definition: scan.h:215
Block manager class.
Definition: mng.h:59