00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef STXXL_CONTAINERS_BTREE__BTREE_H
00014 #define STXXL_CONTAINERS_BTREE__BTREE_H
00015
00016 #include <stxxl/bits/namespace.h>
00017 #include <stxxl/bits/containers/btree/iterator.h>
00018 #include <stxxl/bits/containers/btree/iterator_map.h>
00019 #include <stxxl/bits/containers/btree/leaf.h>
00020 #include <stxxl/bits/containers/btree/node_cache.h>
00021 #include <stxxl/bits/containers/btree/root_node.h>
00022 #include <stxxl/bits/containers/btree/node.h>
00023 #include <stxxl/vector>
00024
00025
00026 __STXXL_BEGIN_NAMESPACE
00027
00028 namespace btree
00029 {
00030 template <class KeyType,
00031 class DataType,
00032 class CompareType,
00033 unsigned RawNodeSize,
00034 unsigned RawLeafSize,
00035 class PDAllocStrategy
00036 >
00037 class btree : private noncopyable
00038 {
00039 public:
00040 typedef KeyType key_type;
00041 typedef DataType data_type;
00042 typedef CompareType key_compare;
00043
00044 typedef btree<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> SelfType;
00045
00046 typedef PDAllocStrategy alloc_strategy_type;
00047
00048 typedef stxxl::uint64 size_type;
00049 typedef stxxl::int64 difference_type;
00050 typedef std::pair<const key_type, data_type> value_type;
00051 typedef value_type & reference;
00052 typedef const value_type & const_reference;
00053 typedef value_type * pointer;
00054 typedef value_type const * const_pointer;
00055
00056
00057
00058 typedef normal_leaf<key_type, data_type, key_compare, RawLeafSize, SelfType> leaf_type;
00059 friend class normal_leaf<key_type, data_type, key_compare, RawLeafSize, SelfType>;
00060 typedef typename leaf_type::block_type leaf_block_type;
00061 typedef typename leaf_type::bid_type leaf_bid_type;
00062 typedef node_cache<leaf_type, SelfType> leaf_cache_type;
00063 friend class node_cache<leaf_type, SelfType>;
00064
00065 typedef btree_iterator<SelfType> iterator;
00066 typedef btree_const_iterator<SelfType> const_iterator;
00067 friend class btree_iterator_base<SelfType>;
00068
00069 typedef iterator_map<SelfType> iterator_map_type;
00070
00071 typedef normal_node<key_type, key_compare, RawNodeSize, SelfType> node_type;
00072 typedef typename node_type::block_type node_block_type;
00073 friend class normal_node<key_type, key_compare, RawNodeSize, SelfType>;
00074 typedef typename node_type::bid_type node_bid_type;
00075 typedef node_cache<node_type, SelfType> node_cache_type;
00076 friend class node_cache<node_type, SelfType>;
00077
00078 typedef typename leaf_type::value_compare value_compare;
00079
00080 enum {
00081 min_node_size = node_type::min_size,
00082 max_node_size = node_type::max_size,
00083 min_leaf_size = leaf_type::min_size,
00084 max_leaf_size = leaf_type::max_size
00085 };
00086
00087 private:
00088 key_compare key_compare_;
00089 mutable node_cache_type node_cache_;
00090 mutable leaf_cache_type leaf_cache_;
00091 iterator_map_type iterator_map_;
00092 size_type size_;
00093 unsigned_type height_;
00094 bool prefetching_enabled_;
00095 block_manager * bm_;
00096 alloc_strategy_type alloc_strategy_;
00097
00098 typedef std::map<key_type, node_bid_type, key_compare> root_node_type;
00099 typedef typename root_node_type::iterator root_node_iterator_type;
00100 typedef typename root_node_type::const_iterator root_node_const_iterator_type;
00101 typedef std::pair<key_type, node_bid_type> root_node_pair_type;
00102
00103
00104 root_node_type root_node_;
00105 iterator end_iterator;
00106
00107
00108 template <class BIDType>
00109 void insert_into_root(const std::pair<key_type, BIDType> & splitter)
00110 {
00111 std::pair<root_node_iterator_type, bool> result =
00112 root_node_.insert(splitter);
00113 assert(result.second == true);
00114 if (root_node_.size() > max_node_size)
00115 {
00116 STXXL_VERBOSE1("btree::insert_into_root, overflow happened, splitting");
00117
00118 node_bid_type LeftBid;
00119 node_type * LeftNode = node_cache_.get_new_node(LeftBid);
00120 assert(LeftNode);
00121 node_bid_type RightBid;
00122 node_type * RightNode = node_cache_.get_new_node(RightBid);
00123 assert(RightNode);
00124
00125 const unsigned_type old_size = root_node_.size();
00126 const unsigned_type half = root_node_.size() / 2;
00127 unsigned_type i = 0;
00128 root_node_iterator_type it = root_node_.begin();
00129 typename node_block_type::iterator block_it = LeftNode->block().begin();
00130 while (i < half)
00131 {
00132 *block_it = *it;
00133 ++i;
00134 ++block_it;
00135 ++it;
00136 }
00137 LeftNode->block().info.cur_size = half;
00138 key_type LeftKey = (LeftNode->block()[half - 1]).first;
00139
00140 block_it = RightNode->block().begin();
00141 while (i < old_size)
00142 {
00143 *block_it = *it;
00144 ++i;
00145 ++block_it;
00146 ++it;
00147 }
00148 unsigned_type right_size = RightNode->block().info.cur_size = old_size - half;
00149 key_type RightKey = (RightNode->block()[right_size - 1]).first;
00150
00151 assert(old_size == RightNode->size() + LeftNode->size());
00152
00153
00154 root_node_.clear();
00155 root_node_.insert(root_node_pair_type(LeftKey, LeftBid));
00156 root_node_.insert(root_node_pair_type(RightKey, RightBid));
00157
00158
00159 ++height_;
00160 STXXL_VERBOSE1("btree Increasing height to " << height_);
00161 if (node_cache_.size() < (height_ - 1))
00162 {
00163 STXXL_THROW(std::runtime_error, "btree::bulk_construction", "The height of the tree (" << height_ << ") has exceeded the required capacity ("
00164 << (node_cache_.size() + 1) << ") of the node cache. " <<
00165 "Increase the node cache size.");
00166 }
00167 }
00168 }
00169
00170 template <class CacheType>
00171 void fuse_or_balance(root_node_iterator_type UIt, CacheType & cache_)
00172 {
00173 typedef typename CacheType::node_type local_node_type;
00174 typedef typename local_node_type::bid_type local_bid_type;
00175
00176 root_node_iterator_type leftIt, rightIt;
00177 if (UIt->first == key_compare::max_value())
00178 {
00179 assert(UIt != root_node_.begin());
00180 rightIt = UIt;
00181 leftIt = --UIt;
00182 }
00183 else
00184 {
00185 leftIt = UIt;
00186 rightIt = ++UIt;
00187 assert(rightIt != root_node_.end());
00188 }
00189
00190
00191 local_bid_type LeftBid = (local_bid_type)leftIt->second;
00192 local_bid_type RightBid = (local_bid_type)rightIt->second;
00193 local_node_type * LeftNode = cache_.get_node(LeftBid, true);
00194 local_node_type * RightNode = cache_.get_node(RightBid, true);
00195
00196 const unsigned_type TotalSize = LeftNode->size() + RightNode->size();
00197 if (TotalSize <= RightNode->max_nelements())
00198 {
00199
00200 RightNode->fuse(*LeftNode);
00201
00202 cache_.unfix_node(RightBid);
00203 cache_.delete_node(LeftBid);
00204
00205 root_node_.erase(leftIt);
00206 }
00207 else
00208 {
00209
00210
00211 key_type NewSplitter = RightNode->balance(*LeftNode);
00212
00213 root_node_.erase(leftIt);
00214
00215 root_node_.insert(root_node_pair_type(NewSplitter, (node_bid_type)LeftBid));
00216
00217 cache_.unfix_node(LeftBid);
00218 cache_.unfix_node(RightBid);
00219 }
00220 }
00221
00222 void create_empty_leaf()
00223 {
00224 leaf_bid_type NewBid;
00225 leaf_type * NewLeaf = leaf_cache_.get_new_node(NewBid);
00226 assert(NewLeaf);
00227 end_iterator = NewLeaf->end();
00228 root_node_.insert(root_node_pair_type(key_compare::max_value(), (node_bid_type)NewBid));
00229 }
00230
00231 void deallocate_children()
00232 {
00233 if (height_ == 2)
00234 {
00235
00236 root_node_const_iterator_type it = root_node_.begin();
00237 for ( ; it != root_node_.end(); ++it)
00238 {
00239
00240 leaf_cache_.delete_node((leaf_bid_type)it->second);
00241 }
00242 }
00243 else
00244 {
00245 root_node_const_iterator_type it = root_node_.begin();
00246 for ( ; it != root_node_.end(); ++it)
00247 {
00248 node_type * Node = node_cache_.get_node((node_bid_type)it->second);
00249 assert(Node);
00250 Node->deallocate_children(height_ - 1);
00251
00252 node_cache_.delete_node((node_bid_type)it->second);
00253 }
00254 }
00255 }
00256
00257 template <class InputIterator>
00258 void bulk_construction(InputIterator b, InputIterator e, double node_fill_factor, double leaf_fill_factor)
00259 {
00260 assert(node_fill_factor >= 0.5);
00261 assert(leaf_fill_factor >= 0.5);
00262 key_type lastKey = key_compare::max_value();
00263
00264 typedef std::pair<key_type, node_bid_type> key_bid_pair;
00265 typedef typename stxxl::VECTOR_GENERATOR<key_bid_pair, 1, 1,
00266 node_block_type::raw_size>::result key_bid_vector_type;
00267
00268 key_bid_vector_type Bids;
00269
00270 leaf_bid_type NewBid;
00271 leaf_type * Leaf = leaf_cache_.get_new_node(NewBid);
00272 const unsigned_type max_leaf_elements = unsigned_type(double(Leaf->max_nelements()) * leaf_fill_factor);
00273
00274 while (b != e)
00275 {
00276
00277
00278
00279 if (key_compare_(b->first, lastKey) || key_compare_(lastKey, b->first))
00280 {
00281 ++size_;
00282 if (Leaf->size() == max_leaf_elements)
00283 {
00284
00285 Bids.push_back(key_bid_pair(Leaf->back().first, (node_bid_type)NewBid));
00286
00287 leaf_type * NewLeaf = leaf_cache_.get_new_node(NewBid);
00288 assert(NewLeaf);
00289
00290 Leaf->succ() = NewLeaf->my_bid();
00291 NewLeaf->pred() = Leaf->my_bid();
00292
00293 Leaf = NewLeaf;
00294 }
00295 Leaf->push_back(*b);
00296 lastKey = b->first;
00297 }
00298 ++b;
00299 }
00300
00301
00302 if (Leaf->underflows() && !Bids.empty())
00303 {
00304 leaf_type * LeftLeaf = leaf_cache_.get_node((leaf_bid_type)(Bids.back().second));
00305 assert(LeftLeaf);
00306 if (LeftLeaf->size() + Leaf->size() <= Leaf->max_nelements())
00307 {
00308 Leaf->fuse(*LeftLeaf);
00309 leaf_cache_.delete_node((leaf_bid_type)(Bids.back().second));
00310 Bids.pop_back();
00311 assert(!Leaf->overflows() && !Leaf->underflows());
00312 }
00313 else
00314 {
00315
00316 const key_type NewSplitter = Leaf->balance(*LeftLeaf);
00317 Bids.back().first = NewSplitter;
00318 assert(!LeftLeaf->overflows() && !LeftLeaf->underflows());
00319 }
00320 }
00321
00322 assert(!Leaf->overflows() && (!Leaf->underflows() || size_ <= max_leaf_size));
00323
00324 end_iterator = Leaf->end();
00325
00326 Bids.push_back(key_bid_pair(key_compare::max_value(), (node_bid_type)NewBid));
00327
00328 const unsigned_type max_node_elements = unsigned_type(double(max_node_size) * node_fill_factor);
00329
00330 while (Bids.size() > max_node_elements)
00331 {
00332 key_bid_vector_type ParentBids;
00333
00334 stxxl::uint64 nparents = div_and_round_up(Bids.size(), stxxl::uint64(max_node_elements));
00335 assert(nparents >= 2);
00336 STXXL_VERBOSE1("btree bulk constructBids.size() " << Bids.size() << " nparents: " << nparents << " max_ns: "
00337 << max_node_elements);
00338 typename key_bid_vector_type::const_iterator it = Bids.begin();
00339
00340 do
00341 {
00342 node_bid_type NewBid;
00343 node_type * Node = node_cache_.get_new_node(NewBid);
00344 assert(Node);
00345 unsigned_type cnt = 0;
00346 for ( ; cnt < max_node_elements && it != Bids.end(); ++cnt, ++it)
00347 {
00348 Node->push_back(*it);
00349 }
00350 STXXL_VERBOSE1("btree bulk construct Node size : " << Node->size() << " limits: " <<
00351 Node->min_nelements() << " " << Node->max_nelements() << " max_node_elements: " << max_node_elements);
00352
00353 if (Node->underflows())
00354 {
00355 assert(it == Bids.end());
00356 assert(!ParentBids.empty());
00357
00358 node_type * LeftNode = node_cache_.get_node(ParentBids.back().second);
00359 assert(LeftNode);
00360 if (LeftNode->size() + Node->size() <= Node->max_nelements())
00361 {
00362 Node->fuse(*LeftNode);
00363 node_cache_.delete_node(ParentBids.back().second);
00364 ParentBids.pop_back();
00365 }
00366 else
00367 {
00368 const key_type NewSplitter = Node->balance(*LeftNode);
00369 ParentBids.back().first = NewSplitter;
00370 assert(!LeftNode->overflows() && !LeftNode->underflows());
00371 }
00372 }
00373 assert(!Node->overflows() && !Node->underflows());
00374
00375 ParentBids.push_back(key_bid_pair(Node->back().first, NewBid));
00376 } while (it != Bids.end());
00377
00378 std::swap(ParentBids, Bids);
00379
00380 assert(nparents == Bids.size() || (nparents - 1) == Bids.size());
00381
00382 ++height_;
00383 STXXL_VERBOSE1("Increasing height to " << height_);
00384 if (node_cache_.size() < (height_ - 1))
00385 {
00386 STXXL_THROW(std::runtime_error, "btree::bulk_construction", "The height of the tree (" << height_ << ") has exceeded the required capacity ("
00387 << (node_cache_.size() + 1) << ") of the node cache. " <<
00388 "Increase the node cache size.");
00389 }
00390 }
00391
00392 root_node_.insert(Bids.begin(), Bids.end());
00393 }
00394
00395 public:
00396 btree(unsigned_type node_cache_size_in_bytes,
00397 unsigned_type leaf_cache_size_in_bytes
00398 ) :
00399 node_cache_(node_cache_size_in_bytes, this, key_compare_),
00400 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_),
00401 iterator_map_(this),
00402 size_(0),
00403 height_(2),
00404 prefetching_enabled_(true),
00405 bm_(block_manager::get_instance())
00406 {
00407 STXXL_VERBOSE1("Creating a btree, addr=" << this);
00408 STXXL_VERBOSE1(" bytes in a node: " << node_bid_type::size);
00409 STXXL_VERBOSE1(" bytes in a leaf: " << leaf_bid_type::size);
00410 STXXL_VERBOSE1(" elements in a node: " << node_block_type::size);
00411 STXXL_VERBOSE1(" elements in a leaf: " << leaf_block_type::size);
00412 STXXL_VERBOSE1(" size of a node element: " << sizeof(typename node_block_type::value_type));
00413 STXXL_VERBOSE1(" size of a leaf element: " << sizeof(typename leaf_block_type::value_type));
00414
00415
00416 create_empty_leaf();
00417 }
00418
00419 btree(const key_compare & c_,
00420 unsigned_type node_cache_size_in_bytes,
00421 unsigned_type leaf_cache_size_in_bytes
00422 ) :
00423 key_compare_(c_),
00424 node_cache_(node_cache_size_in_bytes, this, key_compare_),
00425 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_),
00426 iterator_map_(this),
00427 size_(0),
00428 height_(2),
00429 prefetching_enabled_(true),
00430 bm_(block_manager::get_instance())
00431 {
00432 STXXL_VERBOSE1("Creating a btree, addr=" << this);
00433 STXXL_VERBOSE1(" bytes in a node: " << node_bid_type::size);
00434 STXXL_VERBOSE1(" bytes in a leaf: " << leaf_bid_type::size);
00435
00436 create_empty_leaf();
00437 }
00438
00439 virtual ~btree()
00440 {
00441 try
00442 {
00443 deallocate_children();
00444 } catch (...)
00445 {
00446
00447 }
00448 }
00449
00450 size_type size() const
00451 {
00452 return size_;
00453 }
00454
00455 size_type max_size() const
00456 {
00457 return (std::numeric_limits<size_type>::max)();
00458 }
00459
00460 bool empty() const
00461 {
00462 return !size_;
00463 }
00464
00465 std::pair<iterator, bool> insert(const value_type & x)
00466 {
00467 root_node_iterator_type it = root_node_.lower_bound(x.first);
00468 assert(!root_node_.empty());
00469 assert(it != root_node_.end());
00470 if (height_ == 2)
00471 {
00472 STXXL_VERBOSE1("Inserting new value into a leaf");
00473 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second, true);
00474 assert(Leaf);
00475 std::pair<key_type, leaf_bid_type> Splitter;
00476 std::pair<iterator, bool> result = Leaf->insert(x, Splitter);
00477 if (result.second)
00478 ++size_;
00479
00480 leaf_cache_.unfix_node((leaf_bid_type)it->second);
00481
00482 if (!(key_compare_(key_compare::max_value(), Splitter.first) ||
00483 key_compare_(Splitter.first, key_compare::max_value())))
00484 return result;
00485
00486
00487 STXXL_VERBOSE1("Inserting new value into root node");
00488
00489 insert_into_root(Splitter);
00490
00491 assert(leaf_cache_.nfixed() == 0);
00492 assert(node_cache_.nfixed() == 0);
00493 return result;
00494 }
00495
00496
00497 STXXL_VERBOSE1("Inserting new value into a node");
00498 node_type * Node = node_cache_.get_node((node_bid_type)it->second, true);
00499 assert(Node);
00500 std::pair<key_type, node_bid_type> Splitter;
00501 std::pair<iterator, bool> result = Node->insert(x, height_ - 1, Splitter);
00502 if (result.second)
00503 ++size_;
00504
00505 node_cache_.unfix_node((node_bid_type)it->second);
00506
00507 if (!(key_compare_(key_compare::max_value(), Splitter.first) ||
00508 key_compare_(Splitter.first, key_compare::max_value())))
00509 return result;
00510
00511
00512 STXXL_VERBOSE1("Inserting new value into root node");
00513
00514 insert_into_root(Splitter);
00515
00516 assert(leaf_cache_.nfixed() == 0);
00517 assert(node_cache_.nfixed() == 0);
00518
00519 return result;
00520 }
00521
00522 iterator begin()
00523 {
00524 root_node_iterator_type it = root_node_.begin();
00525 assert(it != root_node_.end());
00526
00527 if (height_ == 2)
00528 {
00529 STXXL_VERBOSE1("btree: retrieving begin() from the first leaf");
00530 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second);
00531 assert(Leaf);
00532
00533 assert(leaf_cache_.nfixed() == 0);
00534 assert(node_cache_.nfixed() == 0);
00535 return Leaf->begin();
00536 }
00537
00538
00539 STXXL_VERBOSE1("btree: retrieving begin() from the first node");
00540 node_type * Node = node_cache_.get_node((node_bid_type)it->second, true);
00541 assert(Node);
00542 iterator result = Node->begin(height_ - 1);
00543 node_cache_.unfix_node((node_bid_type)it->second);
00544
00545 assert(leaf_cache_.nfixed() == 0);
00546 assert(node_cache_.nfixed() == 0);
00547
00548 return result;
00549 }
00550
00551 const_iterator begin() const
00552 {
00553 root_node_const_iterator_type it = root_node_.begin();
00554 assert(it != root_node_.end());
00555
00556 if (height_ == 2)
00557 {
00558 STXXL_VERBOSE1("btree: retrieving begin() from the first leaf");
00559 leaf_type const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second);
00560 assert(Leaf);
00561 assert(leaf_cache_.nfixed() == 0);
00562 assert(node_cache_.nfixed() == 0);
00563 return Leaf->begin();
00564 }
00565
00566
00567 STXXL_VERBOSE1("btree: retrieving begin() from the first node");
00568 node_type const * Node = node_cache_.get_const_node((node_bid_type)it->second, true);
00569 assert(Node);
00570 const_iterator result = Node->begin(height_ - 1);
00571 node_cache_.unfix_node((node_bid_type)it->second);
00572 assert(leaf_cache_.nfixed() == 0);
00573 assert(node_cache_.nfixed() == 0);
00574 return result;
00575 }
00576
00577 iterator end()
00578 {
00579 return end_iterator;
00580 }
00581
00582 const_iterator end() const
00583 {
00584 return end_iterator;
00585 }
00586
00587 data_type & operator [] (const key_type & k)
00588 {
00589 return (*((insert(value_type(k, data_type()))).first)).second;
00590 }
00591
00592 iterator find(const key_type & k)
00593 {
00594 root_node_iterator_type it = root_node_.lower_bound(k);
00595 assert(it != root_node_.end());
00596
00597 if (height_ == 2)
00598 {
00599 STXXL_VERBOSE1("Searching in a leaf");
00600 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second, true);
00601 assert(Leaf);
00602 iterator result = Leaf->find(k);
00603 leaf_cache_.unfix_node((leaf_bid_type)it->second);
00604 assert(result == end() || result->first == k);
00605 assert(leaf_cache_.nfixed() == 0);
00606 assert(node_cache_.nfixed() == 0);
00607 return result;
00608 }
00609
00610
00611 STXXL_VERBOSE1("Searching in a node");
00612 node_type * Node = node_cache_.get_node((node_bid_type)it->second, true);
00613 assert(Node);
00614 iterator result = Node->find(k, height_ - 1);
00615 node_cache_.unfix_node((node_bid_type)it->second);
00616
00617 assert(result == end() || result->first == k);
00618 assert(leaf_cache_.nfixed() == 0);
00619 assert(node_cache_.nfixed() == 0);
00620 return result;
00621 }
00622
00623 const_iterator find(const key_type & k) const
00624 {
00625 root_node_const_iterator_type it = root_node_.lower_bound(k);
00626 assert(it != root_node_.end());
00627
00628 if (height_ == 2)
00629 {
00630 STXXL_VERBOSE1("Searching in a leaf");
00631 leaf_type const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second, true);
00632 assert(Leaf);
00633 const_iterator result = Leaf->find(k);
00634 leaf_cache_.unfix_node((leaf_bid_type)it->second);
00635 assert(result == end() || result->first == k);
00636 assert(leaf_cache_.nfixed() == 0);
00637 assert(node_cache_.nfixed() == 0);
00638 return result;
00639 }
00640
00641
00642 STXXL_VERBOSE1("Searching in a node");
00643 node_type const * Node = node_cache_.get_const_node((node_bid_type)it->second, true);
00644 assert(Node);
00645 const_iterator result = Node->find(k, height_ - 1);
00646 node_cache_.unfix_node((node_bid_type)it->second);
00647
00648 assert(result == end() || result->first == k);
00649 assert(leaf_cache_.nfixed() == 0);
00650 assert(node_cache_.nfixed() == 0);
00651 return result;
00652 }
00653
00654 iterator lower_bound(const key_type & k)
00655 {
00656 root_node_iterator_type it = root_node_.lower_bound(k);
00657 assert(it != root_node_.end());
00658
00659 if (height_ == 2)
00660 {
00661 STXXL_VERBOSE1("Searching lower bound in a leaf");
00662 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second, true);
00663 assert(Leaf);
00664 iterator result = Leaf->lower_bound(k);
00665 leaf_cache_.unfix_node((leaf_bid_type)it->second);
00666 assert(leaf_cache_.nfixed() == 0);
00667 assert(node_cache_.nfixed() == 0);
00668 return result;
00669 }
00670
00671
00672 STXXL_VERBOSE1("Searching lower bound in a node");
00673 node_type * Node = node_cache_.get_node((node_bid_type)it->second, true);
00674 assert(Node);
00675 iterator result = Node->lower_bound(k, height_ - 1);
00676 node_cache_.unfix_node((node_bid_type)it->second);
00677
00678 assert(leaf_cache_.nfixed() == 0);
00679 assert(node_cache_.nfixed() == 0);
00680 return result;
00681 }
00682
00683 const_iterator lower_bound(const key_type & k) const
00684 {
00685 root_node_const_iterator_type it = root_node_.lower_bound(k);
00686 assert(it != root_node_.end());
00687
00688 if (height_ == 2)
00689 {
00690 STXXL_VERBOSE1("Searching lower bound in a leaf");
00691 leaf_type const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second, true);
00692 assert(Leaf);
00693 const_iterator result = Leaf->lower_bound(k);
00694 leaf_cache_.unfix_node((leaf_bid_type)it->second);
00695
00696 assert(leaf_cache_.nfixed() == 0);
00697 assert(node_cache_.nfixed() == 0);
00698 return result;
00699 }
00700
00701
00702 STXXL_VERBOSE1("Searching lower bound in a node");
00703 node_type const * Node = node_cache_.get_const_node((node_bid_type)it->second, true);
00704 assert(Node);
00705 const_iterator result = Node->lower_bound(k, height_ - 1);
00706 node_cache_.unfix_node((node_bid_type)it->second);
00707
00708 assert(leaf_cache_.nfixed() == 0);
00709 assert(node_cache_.nfixed() == 0);
00710 return result;
00711 }
00712
00713 iterator upper_bound(const key_type & k)
00714 {
00715 root_node_iterator_type it = root_node_.upper_bound(k);
00716 assert(it != root_node_.end());
00717
00718 if (height_ == 2)
00719 {
00720 STXXL_VERBOSE1("Searching upper bound in a leaf");
00721 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second, true);
00722 assert(Leaf);
00723 iterator result = Leaf->upper_bound(k);
00724 leaf_cache_.unfix_node((leaf_bid_type)it->second);
00725
00726 assert(leaf_cache_.nfixed() == 0);
00727 assert(node_cache_.nfixed() == 0);
00728 return result;
00729 }
00730
00731
00732 STXXL_VERBOSE1("Searching upper bound in a node");
00733 node_type * Node = node_cache_.get_node((node_bid_type)it->second, true);
00734 assert(Node);
00735 iterator result = Node->upper_bound(k, height_ - 1);
00736 node_cache_.unfix_node((node_bid_type)it->second);
00737
00738 assert(leaf_cache_.nfixed() == 0);
00739 assert(node_cache_.nfixed() == 0);
00740 return result;
00741 }
00742
00743 const_iterator upper_bound(const key_type & k) const
00744 {
00745 root_node_const_iterator_type it = root_node_.upper_bound(k);
00746 assert(it != root_node_.end());
00747
00748 if (height_ == 2)
00749 {
00750 STXXL_VERBOSE1("Searching upper bound in a leaf");
00751 leaf_type const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second, true);
00752 assert(Leaf);
00753 const_iterator result = Leaf->upper_bound(k);
00754 leaf_cache_.unfix_node((leaf_bid_type)it->second);
00755
00756 assert(leaf_cache_.nfixed() == 0);
00757 assert(node_cache_.nfixed() == 0);
00758 return result;
00759 }
00760
00761
00762 STXXL_VERBOSE1("Searching upper bound in a node");
00763 node_type const * Node = node_cache_.get_const_node((node_bid_type)it->second, true);
00764 assert(Node);
00765 const_iterator result = Node->upper_bound(k, height_ - 1);
00766 node_cache_.unfix_node((node_bid_type)it->second);
00767
00768 assert(leaf_cache_.nfixed() == 0);
00769 assert(node_cache_.nfixed() == 0);
00770 return result;
00771 }
00772
00773 std::pair<iterator, iterator> equal_range(const key_type & k)
00774 {
00775 iterator l = lower_bound(k);
00776
00777 if (l == end() || key_compare_(k, l->first))
00778 return std::pair<iterator, iterator>(l, l);
00779
00780
00781 iterator u = l;
00782 ++u;
00783
00784 assert(leaf_cache_.nfixed() == 0);
00785 assert(node_cache_.nfixed() == 0);
00786
00787 return std::pair<iterator, iterator>(l, u);
00788 }
00789
00790 std::pair<const_iterator, const_iterator> equal_range(const key_type & k) const
00791 {
00792 const_iterator l = lower_bound(k);
00793
00794 if (l == end() || key_compare_(k, l->first))
00795 return std::pair<const_iterator, const_iterator>(l, l);
00796
00797
00798 const_iterator u = l;
00799 ++u;
00800
00801 assert(leaf_cache_.nfixed() == 0);
00802 assert(node_cache_.nfixed() == 0);
00803 return std::pair<const_iterator, const_iterator>(l, u);
00804 }
00805
00806 size_type erase(const key_type & k)
00807 {
00808 root_node_iterator_type it = root_node_.lower_bound(k);
00809 assert(it != root_node_.end());
00810 if (height_ == 2)
00811 {
00812 STXXL_VERBOSE1("Deleting key from a leaf");
00813 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second, true);
00814 assert(Leaf);
00815 size_type result = Leaf->erase(k);
00816 size_ -= result;
00817 leaf_cache_.unfix_node((leaf_bid_type)it->second);
00818 assert(leaf_cache_.nfixed() == 0);
00819 assert(node_cache_.nfixed() == 0);
00820
00821 if ((!Leaf->underflows()) || root_node_.size() == 1)
00822 return result;
00823
00824
00825 STXXL_VERBOSE1("btree: Fusing or rebalancing a leaf");
00826 fuse_or_balance(it, leaf_cache_);
00827
00828 assert(leaf_cache_.nfixed() == 0);
00829 assert(node_cache_.nfixed() == 0);
00830
00831 return result;
00832 }
00833
00834
00835 STXXL_VERBOSE1("Deleting key from a node");
00836 assert(root_node_.size() >= 2);
00837 node_type * Node = node_cache_.get_node((node_bid_type)it->second, true);
00838 assert(Node);
00839 size_type result = Node->erase(k, height_ - 1);
00840 size_ -= result;
00841 node_cache_.unfix_node((node_bid_type)it->second);
00842 assert(leaf_cache_.nfixed() == 0);
00843 assert(node_cache_.nfixed() == 0);
00844 if (!Node->underflows())
00845 return result;
00846
00847
00848 STXXL_VERBOSE1("Fusing or rebalancing a node");
00849 fuse_or_balance(it, node_cache_);
00850
00851 if (root_node_.size() == 1)
00852 {
00853 STXXL_VERBOSE1("btree Root has size 1 and height > 2");
00854 STXXL_VERBOSE1("btree Deallocate root and decrease height");
00855 it = root_node_.begin();
00856 node_bid_type RootBid = it->second;
00857 assert(it->first == key_compare::max_value());
00858 node_type * RootNode = node_cache_.get_node(RootBid);
00859 assert(RootNode);
00860 assert(RootNode->back().first == key_compare::max_value());
00861 root_node_.clear();
00862 root_node_.insert(RootNode->block().begin(),
00863 RootNode->block().begin() + RootNode->size());
00864
00865 node_cache_.delete_node(RootBid);
00866 --height_;
00867 STXXL_VERBOSE1("btree Decreasing height to " << height_);
00868 }
00869
00870 assert(leaf_cache_.nfixed() == 0);
00871 assert(node_cache_.nfixed() == 0);
00872
00873 return result;
00874 }
00875
00876 size_type count(const key_type & k)
00877 {
00878 if (find(k) == end())
00879 return 0;
00880
00881 return 1;
00882 }
00883
00884 void erase(iterator pos)
00885 {
00886 assert(pos != end());
00887 #ifndef NDEBUG
00888 size_type old_size = size();
00889 #endif
00890
00891 erase(pos->first);
00892
00893 assert(size() == old_size - 1);
00894 }
00895
00896 iterator insert(iterator , const value_type & x)
00897 {
00898 return insert(x).first;
00899 }
00900
00901 void clear()
00902 {
00903 deallocate_children();
00904
00905 root_node_.clear();
00906
00907 size_ = 0;
00908 height_ = 2,
00909
00910 create_empty_leaf();
00911 assert(leaf_cache_.nfixed() == 0);
00912 assert(node_cache_.nfixed() == 0);
00913 }
00914
00915 template <class InputIterator>
00916 void insert(InputIterator b, InputIterator e)
00917 {
00918 while (b != e)
00919 {
00920 insert(*(b++));
00921 }
00922 }
00923
00924 template <class InputIterator>
00925 btree(InputIterator b,
00926 InputIterator e,
00927 const key_compare & c_,
00928 unsigned_type node_cache_size_in_bytes,
00929 unsigned_type leaf_cache_size_in_bytes,
00930 bool range_sorted = false,
00931 double node_fill_factor = 0.75,
00932 double leaf_fill_factor = 0.6
00933 ) :
00934 key_compare_(c_),
00935 node_cache_(node_cache_size_in_bytes, this, key_compare_),
00936 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_),
00937 iterator_map_(this),
00938 size_(0),
00939 height_(2),
00940 prefetching_enabled_(true),
00941 bm_(block_manager::get_instance())
00942 {
00943 STXXL_VERBOSE1("Creating a btree, addr=" << this);
00944 STXXL_VERBOSE1(" bytes in a node: " << node_bid_type::size);
00945 STXXL_VERBOSE1(" bytes in a leaf: " << leaf_bid_type::size);
00946
00947 if (range_sorted == false)
00948 {
00949 create_empty_leaf();
00950 insert(b, e);
00951 assert(leaf_cache_.nfixed() == 0);
00952 assert(node_cache_.nfixed() == 0);
00953 return;
00954 }
00955
00956 bulk_construction(b, e, node_fill_factor, leaf_fill_factor);
00957 assert(leaf_cache_.nfixed() == 0);
00958 assert(node_cache_.nfixed() == 0);
00959 }
00960
00961
00962 template <class InputIterator>
00963 btree(InputIterator b,
00964 InputIterator e,
00965 unsigned_type node_cache_size_in_bytes,
00966 unsigned_type leaf_cache_size_in_bytes,
00967 bool range_sorted = false,
00968 double node_fill_factor = 0.75,
00969 double leaf_fill_factor = 0.6
00970 ) :
00971 node_cache_(node_cache_size_in_bytes, this, key_compare_),
00972 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_),
00973 iterator_map_(this),
00974 size_(0),
00975 height_(2),
00976 prefetching_enabled_(true),
00977 bm_(block_manager::get_instance())
00978 {
00979 STXXL_VERBOSE1("Creating a btree, addr=" << this);
00980 STXXL_VERBOSE1(" bytes in a node: " << node_bid_type::size);
00981 STXXL_VERBOSE1(" bytes in a leaf: " << leaf_bid_type::size);
00982
00983 if (range_sorted == false)
00984 {
00985 create_empty_leaf();
00986 insert(b, e);
00987 assert(leaf_cache_.nfixed() == 0);
00988 assert(node_cache_.nfixed() == 0);
00989 return;
00990 }
00991
00992 bulk_construction(b, e, node_fill_factor, leaf_fill_factor);
00993 assert(leaf_cache_.nfixed() == 0);
00994 assert(node_cache_.nfixed() == 0);
00995 }
00996
00997 void erase(iterator first, iterator last)
00998 {
00999 if (first == begin() && last == end())
01000 clear();
01001
01002 else
01003 while (first != last)
01004 erase(first++);
01005 }
01006
01007 key_compare key_comp() const
01008 {
01009 return key_compare_;
01010 }
01011 value_compare value_comp() const
01012 {
01013 return value_compare(key_compare_);
01014 }
01015
01016 void swap(btree & obj)
01017 {
01018 std::swap(key_compare_, obj.key_compare_);
01019
01020 std::swap(node_cache_, obj.node_cache_);
01021 std::swap(leaf_cache_, obj.leaf_cache_);
01022
01023
01024 std::swap(iterator_map_, obj.iterator_map_);
01025
01026 std::swap(end_iterator, obj.end_iterator);
01027 std::swap(size_, obj.size_);
01028 std::swap(height_, obj.height_);
01029 std::swap(alloc_strategy_, obj.alloc_strategy_);
01030 std::swap(root_node_, obj.root_node_);
01031 }
01032
01033 void enable_prefetching()
01034 {
01035 prefetching_enabled_ = true;
01036 }
01037 void disable_prefetching()
01038 {
01039 prefetching_enabled_ = false;
01040 }
01041 bool prefetching_enabled()
01042 {
01043 return prefetching_enabled_;
01044 }
01045
01046 void print_statistics(std::ostream & o) const
01047 {
01048 o << "Node cache statistics:" << std::endl;
01049 node_cache_.print_statistics(o);
01050 o << "Leaf cache statistics:" << std::endl;
01051 leaf_cache_.print_statistics(o);
01052 }
01053 void reset_statistics()
01054 {
01055 node_cache_.reset_statistics();
01056 leaf_cache_.reset_statistics();
01057 }
01058 };
01059
01060 template <class KeyType,
01061 class DataType,
01062 class CompareType,
01063 unsigned LogNodeSize,
01064 unsigned LogLeafSize,
01065 class PDAllocStrategy
01066 >
01067 inline bool operator == (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
01068 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
01069 {
01070 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
01071 }
01072
01073 template <class KeyType,
01074 class DataType,
01075 class CompareType,
01076 unsigned LogNodeSize,
01077 unsigned LogLeafSize,
01078 class PDAllocStrategy
01079 >
01080 inline bool operator != (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
01081 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
01082 {
01083 return !(a == b);
01084 }
01085
01086
01087 template <class KeyType,
01088 class DataType,
01089 class CompareType,
01090 unsigned LogNodeSize,
01091 unsigned LogLeafSize,
01092 class PDAllocStrategy
01093 >
01094 inline bool operator < (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
01095 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
01096 {
01097 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
01098 }
01099
01100
01101 template <class KeyType,
01102 class DataType,
01103 class CompareType,
01104 unsigned LogNodeSize,
01105 unsigned LogLeafSize,
01106 class PDAllocStrategy
01107 >
01108 inline bool operator > (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
01109 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
01110 {
01111 return b < a;
01112 }
01113
01114
01115 template <class KeyType,
01116 class DataType,
01117 class CompareType,
01118 unsigned LogNodeSize,
01119 unsigned LogLeafSize,
01120 class PDAllocStrategy
01121 >
01122 inline bool operator <= (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
01123 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
01124 {
01125 return !(b < a);
01126 }
01127
01128 template <class KeyType,
01129 class DataType,
01130 class CompareType,
01131 unsigned LogNodeSize,
01132 unsigned LogLeafSize,
01133 class PDAllocStrategy
01134 >
01135 inline bool operator >= (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
01136 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
01137 {
01138 return !(a < b);
01139 }
01140 }
01141
01142 __STXXL_END_NAMESPACE
01143
01144
01145 namespace std
01146 {
01147 template <class KeyType,
01148 class DataType,
01149 class CompareType,
01150 unsigned LogNodeSize,
01151 unsigned LogLeafSize,
01152 class PDAllocStrategy
01153 >
01154 void swap(stxxl::btree::btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a,
01155 stxxl::btree::btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b)
01156 {
01157 if (&a != &b)
01158 a.swap(b);
01159 }
01160 }
01161
01162 #endif