Stxxl
1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/containers/btree/btree.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2006 Roman Dementiev <dementiev@ira.uka.de> 00007 * 00008 * Distributed under the Boost Software License, Version 1.0. 00009 * (See accompanying file LICENSE_1_0.txt or copy at 00010 * http://www.boost.org/LICENSE_1_0.txt) 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 // leaf type declarations 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 // iterator types 00065 typedef btree_iterator<SelfType> iterator; 00066 typedef btree_const_iterator<SelfType> const_iterator; 00067 friend class btree_iterator_base<SelfType>; 00068 // iterator map type 00069 typedef iterator_map<SelfType> iterator_map_type; 00070 // node type declarations 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) // root overflow 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) // copy smaller part 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) // copy larger part 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 // create new root node 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()) // UIt is the last entry in the root 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 // now fuse or balance nodes pointed by leftIt and rightIt 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 // fuse 00200 RightNode->fuse(*LeftNode); // add the content of LeftNode to RightNode 00201 00202 cache_.unfix_node(RightBid); 00203 cache_.delete_node(LeftBid); // 'delete_node' unfixes LeftBid also 00204 00205 root_node_.erase(leftIt); // delete left BID from the root 00206 } 00207 else 00208 { 00209 // balance 00210 00211 key_type NewSplitter = RightNode->balance(*LeftNode); 00212 00213 root_node_.erase(leftIt); // delete left BID from the root 00214 // reinsert with the new key 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(); // initialize end() iterator 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 // we have children leaves here 00236 root_node_const_iterator_type it = root_node_.begin(); 00237 for ( ; it != root_node_.end(); ++it) 00238 { 00239 // delete from leaf cache and deallocate bid 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 // delete from node cache and deallocate bid 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 // write data in leaves 00277 00278 // if *b not equal to the last element 00279 if (key_compare_(b->first, lastKey) || key_compare_(lastKey, b->first)) 00280 { 00281 ++size_; 00282 if (Leaf->size() == max_leaf_elements) 00283 { 00284 // overflow, need a new block 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 // Setting links 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 // rebalance the last leaf 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()) // can fuse 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 // need to rebalance 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(); // initialize end() iterator 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()); // this can happen only at the 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()) // can fuse 00361 { 00362 Node->fuse(*LeftNode); 00363 node_cache_.delete_node(ParentBids.back().second); 00364 ParentBids.pop_back(); 00365 } 00366 else 00367 { // need to rebalance 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 // no exceptions in destructor 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) // 'it' points to a leaf 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 //if(key_compare::max_value() == Splitter.first) 00482 if (!(key_compare_(key_compare::max_value(), Splitter.first) || 00483 key_compare_(Splitter.first, key_compare::max_value()))) 00484 return result; 00485 // no overflow/splitting happened 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 // 'it' points to a node 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 //if(key_compare::max_value() == Splitter.first) 00507 if (!(key_compare_(key_compare::max_value(), Splitter.first) || 00508 key_compare_(Splitter.first, key_compare::max_value()))) 00509 return result; 00510 // no overflow/splitting happened 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) // 'it' points to a leaf 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 // 'it' points to a node 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) // 'it' points to a leaf 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 // 'it' points to a node 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) // 'it' points to a leaf 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 // 'it' points to a node 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) // 'it' points to a leaf 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 // 'it' points to a node 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) // 'it' points to a leaf 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 // 'it' points to a node 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) // 'it' points to a leaf 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 // 'it' points to a node 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) // 'it' points to a leaf 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 // 'it' points to a node 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) // 'it' points to a leaf 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 // 'it' points to a node 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); // l->first >= k 00776 00777 if (l == end() || key_compare_(k, l->first)) // if (k < l->first) 00778 return std::pair<iterator, iterator>(l, l); 00779 // then upper_bound == lower_bound 00780 00781 iterator u = l; 00782 ++u; // only one element ==k can exist 00783 00784 assert(leaf_cache_.nfixed() == 0); 00785 assert(node_cache_.nfixed() == 0); 00786 00787 return std::pair<iterator, iterator>(l, u); // then upper_bound == (lower_bound+1) 00788 } 00789 00790 std::pair<const_iterator, const_iterator> equal_range(const key_type & k) const 00791 { 00792 const_iterator l = lower_bound(k); // l->first >= k 00793 00794 if (l == end() || key_compare_(k, l->first)) // if (k < l->first) 00795 return std::pair<const_iterator, const_iterator>(l, l); 00796 // then upper_bound == lower_bound 00797 00798 const_iterator u = l; 00799 ++u; // only one element ==k can exist 00800 00801 assert(leaf_cache_.nfixed() == 0); 00802 assert(node_cache_.nfixed() == 0); 00803 return std::pair<const_iterator, const_iterator>(l, u); // then upper_bound == (lower_bound+1) 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) // 'it' points to a leaf 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 // no underflow or root has a special degree 1 (too few elements) 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 // 'it' points to a node 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 // no underflow happened 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 /*pos*/, const value_type & x) 00897 { 00898 return insert(x).first; // pos ignored in the current version 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_); // OK 01019 01020 std::swap(node_cache_, obj.node_cache_); // OK 01021 std::swap(leaf_cache_, obj.leaf_cache_); // OK 01022 01023 01024 std::swap(iterator_map_, obj.iterator_map_); // must update all iterators 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 /* STXXL_CONTAINERS_BTREE__BTREE_H */