|
Stxxl
1.4.0
|
|
Stxxl
1.4.0
|
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, 2008 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 <limits> 00017 #include <stxxl/bits/namespace.h> 00018 #include <stxxl/bits/containers/btree/iterator.h> 00019 #include <stxxl/bits/containers/btree/iterator_map.h> 00020 #include <stxxl/bits/containers/btree/leaf.h> 00021 #include <stxxl/bits/containers/btree/node_cache.h> 00022 #include <stxxl/bits/containers/btree/root_node.h> 00023 #include <stxxl/bits/containers/btree/node.h> 00024 #include <stxxl/vector> 00025 00026 00027 __STXXL_BEGIN_NAMESPACE 00028 00029 namespace btree 00030 { 00031 template <class KeyType, 00032 class DataType, 00033 class CompareType, 00034 unsigned RawNodeSize, 00035 unsigned RawLeafSize, 00036 class PDAllocStrategy 00037 > 00038 class btree : private noncopyable 00039 { 00040 public: 00041 typedef KeyType key_type; 00042 typedef DataType data_type; 00043 typedef CompareType key_compare; 00044 00045 typedef btree<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> SelfType; 00046 00047 typedef PDAllocStrategy alloc_strategy_type; 00048 00049 typedef stxxl::uint64 size_type; 00050 typedef stxxl::int64 difference_type; 00051 typedef std::pair<const key_type, data_type> value_type; 00052 typedef value_type & reference; 00053 typedef const value_type & const_reference; 00054 typedef value_type * pointer; 00055 typedef value_type const * const_pointer; 00056 00057 00058 // leaf type declarations 00059 typedef normal_leaf<key_type, data_type, key_compare, RawLeafSize, SelfType> leaf_type; 00060 friend class normal_leaf<key_type, data_type, key_compare, RawLeafSize, SelfType>; 00061 typedef typename leaf_type::block_type leaf_block_type; 00062 typedef typename leaf_type::bid_type leaf_bid_type; 00063 typedef node_cache<leaf_type, SelfType> leaf_cache_type; 00064 friend class node_cache<leaf_type, SelfType>; 00065 // iterator types 00066 typedef btree_iterator<SelfType> iterator; 00067 typedef btree_const_iterator<SelfType> const_iterator; 00068 friend class btree_iterator_base<SelfType>; 00069 // iterator map type 00070 typedef iterator_map<SelfType> iterator_map_type; 00071 // node type declarations 00072 typedef normal_node<key_type, key_compare, RawNodeSize, SelfType> node_type; 00073 typedef typename node_type::block_type node_block_type; 00074 friend class normal_node<key_type, key_compare, RawNodeSize, SelfType>; 00075 typedef typename node_type::bid_type node_bid_type; 00076 typedef node_cache<node_type, SelfType> node_cache_type; 00077 friend class node_cache<node_type, SelfType>; 00078 00079 typedef typename leaf_type::value_compare value_compare; 00080 00081 enum { 00082 min_node_size = node_type::min_size, 00083 max_node_size = node_type::max_size, 00084 min_leaf_size = leaf_type::min_size, 00085 max_leaf_size = leaf_type::max_size 00086 }; 00087 00088 private: 00089 key_compare key_compare_; 00090 mutable node_cache_type node_cache_; 00091 mutable leaf_cache_type leaf_cache_; 00092 iterator_map_type iterator_map_; 00093 size_type size_; 00094 unsigned_type height_; 00095 bool prefetching_enabled_; 00096 block_manager * bm_; 00097 alloc_strategy_type alloc_strategy_; 00098 00099 typedef std::map<key_type, node_bid_type, key_compare> root_node_type; 00100 typedef typename root_node_type::iterator root_node_iterator_type; 00101 typedef typename root_node_type::const_iterator root_node_const_iterator_type; 00102 typedef std::pair<key_type, node_bid_type> root_node_pair_type; 00103 00104 00105 root_node_type root_node_; 00106 iterator end_iterator; 00107 00108 00109 void insert_into_root(const std::pair<key_type, node_bid_type> & 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_ceil(Bids.size(), 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 STXXL_UNUSED(nparents); 00339 typename key_bid_vector_type::const_iterator it = Bids.begin(); 00340 00341 do 00342 { 00343 node_bid_type NewBid; 00344 node_type * Node = node_cache_.get_new_node(NewBid); 00345 assert(Node); 00346 unsigned_type cnt = 0; 00347 for ( ; cnt < max_node_elements && it != Bids.end(); ++cnt, ++it) 00348 { 00349 Node->push_back(*it); 00350 } 00351 STXXL_VERBOSE1("btree bulk construct Node size : " << Node->size() << " limits: " << 00352 Node->min_nelements() << " " << Node->max_nelements() << " max_node_elements: " << max_node_elements); 00353 00354 if (Node->underflows()) 00355 { 00356 assert(it == Bids.end()); // this can happen only at the end 00357 assert(!ParentBids.empty()); 00358 00359 node_type * LeftNode = node_cache_.get_node(ParentBids.back().second); 00360 assert(LeftNode); 00361 if (LeftNode->size() + Node->size() <= Node->max_nelements()) // can fuse 00362 { 00363 Node->fuse(*LeftNode); 00364 node_cache_.delete_node(ParentBids.back().second); 00365 ParentBids.pop_back(); 00366 } 00367 else 00368 { // need to rebalance 00369 const key_type NewSplitter = Node->balance(*LeftNode); 00370 ParentBids.back().first = NewSplitter; 00371 assert(!LeftNode->overflows() && !LeftNode->underflows()); 00372 } 00373 } 00374 assert(!Node->overflows() && !Node->underflows()); 00375 00376 ParentBids.push_back(key_bid_pair(Node->back().first, NewBid)); 00377 } while (it != Bids.end()); 00378 00379 std::swap(ParentBids, Bids); 00380 00381 assert(nparents == Bids.size() || (nparents - 1) == Bids.size()); 00382 00383 ++height_; 00384 STXXL_VERBOSE1("Increasing height to " << height_); 00385 if (node_cache_.size() < (height_ - 1)) 00386 { 00387 STXXL_THROW(std::runtime_error, "btree::bulk_construction", "The height of the tree (" << height_ << ") has exceeded the required capacity (" 00388 << (node_cache_.size() + 1) << ") of the node cache. " << 00389 "Increase the node cache size."); 00390 } 00391 } 00392 00393 root_node_.insert(Bids.begin(), Bids.end()); 00394 } 00395 00396 public: 00397 btree(unsigned_type node_cache_size_in_bytes, 00398 unsigned_type leaf_cache_size_in_bytes 00399 ) : 00400 node_cache_(node_cache_size_in_bytes, this, key_compare_), 00401 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_), 00402 iterator_map_(this), 00403 size_(0), 00404 height_(2), 00405 prefetching_enabled_(true), 00406 bm_(block_manager::get_instance()) 00407 { 00408 STXXL_VERBOSE1("Creating a btree, addr=" << this); 00409 STXXL_VERBOSE1(" bytes in a node: " << node_bid_type::size); 00410 STXXL_VERBOSE1(" bytes in a leaf: " << leaf_bid_type::size); 00411 STXXL_VERBOSE1(" elements in a node: " << node_block_type::size); 00412 STXXL_VERBOSE1(" elements in a leaf: " << leaf_block_type::size); 00413 STXXL_VERBOSE1(" size of a node element: " << sizeof(typename node_block_type::value_type)); 00414 STXXL_VERBOSE1(" size of a leaf element: " << sizeof(typename leaf_block_type::value_type)); 00415 00416 00417 create_empty_leaf(); 00418 } 00419 00420 btree(const key_compare & c_, 00421 unsigned_type node_cache_size_in_bytes, 00422 unsigned_type leaf_cache_size_in_bytes 00423 ) : 00424 key_compare_(c_), 00425 node_cache_(node_cache_size_in_bytes, this, key_compare_), 00426 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_), 00427 iterator_map_(this), 00428 size_(0), 00429 height_(2), 00430 prefetching_enabled_(true), 00431 bm_(block_manager::get_instance()) 00432 { 00433 STXXL_VERBOSE1("Creating a btree, addr=" << this); 00434 STXXL_VERBOSE1(" bytes in a node: " << node_bid_type::size); 00435 STXXL_VERBOSE1(" bytes in a leaf: " << leaf_bid_type::size); 00436 00437 create_empty_leaf(); 00438 } 00439 00440 virtual ~btree() 00441 { 00442 try 00443 { 00444 deallocate_children(); 00445 } catch (...) 00446 { 00447 // no exceptions in destructor 00448 } 00449 } 00450 00451 size_type size() const 00452 { 00453 return size_; 00454 } 00455 00456 size_type max_size() const 00457 { 00458 return (std::numeric_limits<size_type>::max)(); 00459 } 00460 00461 bool empty() const 00462 { 00463 return !size_; 00464 } 00465 00466 std::pair<iterator, bool> insert(const value_type & x) 00467 { 00468 root_node_iterator_type it = root_node_.lower_bound(x.first); 00469 assert(!root_node_.empty()); 00470 assert(it != root_node_.end()); 00471 if (height_ == 2) // 'it' points to a leaf 00472 { 00473 STXXL_VERBOSE1("Inserting new value into a leaf"); 00474 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second, true); 00475 assert(Leaf); 00476 std::pair<key_type, leaf_bid_type> Splitter; 00477 std::pair<iterator, bool> result = Leaf->insert(x, Splitter); 00478 if (result.second) 00479 ++size_; 00480 00481 leaf_cache_.unfix_node((leaf_bid_type)it->second); 00482 //if(key_compare::max_value() == Splitter.first) 00483 if (!(key_compare_(key_compare::max_value(), Splitter.first) || 00484 key_compare_(Splitter.first, key_compare::max_value()))) 00485 return result; 00486 // no overflow/splitting happened 00487 00488 STXXL_VERBOSE1("Inserting new value into root node"); 00489 00490 insert_into_root(std::make_pair(Splitter.first, node_bid_type(Splitter.second))); 00491 00492 assert(leaf_cache_.nfixed() == 0); 00493 assert(node_cache_.nfixed() == 0); 00494 return result; 00495 } 00496 00497 // 'it' points to a node 00498 STXXL_VERBOSE1("Inserting new value into a node"); 00499 node_type * Node = node_cache_.get_node((node_bid_type)it->second, true); 00500 assert(Node); 00501 std::pair<key_type, node_bid_type> Splitter; 00502 std::pair<iterator, bool> result = Node->insert(x, height_ - 1, Splitter); 00503 if (result.second) 00504 ++size_; 00505 00506 node_cache_.unfix_node((node_bid_type)it->second); 00507 //if(key_compare::max_value() == Splitter.first) 00508 if (!(key_compare_(key_compare::max_value(), Splitter.first) || 00509 key_compare_(Splitter.first, key_compare::max_value()))) 00510 return result; 00511 // no overflow/splitting happened 00512 00513 STXXL_VERBOSE1("Inserting new value into root node"); 00514 00515 insert_into_root(Splitter); 00516 00517 assert(leaf_cache_.nfixed() == 0); 00518 assert(node_cache_.nfixed() == 0); 00519 00520 return result; 00521 } 00522 00523 iterator begin() 00524 { 00525 root_node_iterator_type it = root_node_.begin(); 00526 assert(it != root_node_.end()); 00527 00528 if (height_ == 2) // 'it' points to a leaf 00529 { 00530 STXXL_VERBOSE1("btree: retrieving begin() from the first leaf"); 00531 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second); 00532 assert(Leaf); 00533 00534 assert(leaf_cache_.nfixed() == 0); 00535 assert(node_cache_.nfixed() == 0); 00536 return Leaf->begin(); 00537 } 00538 00539 // 'it' points to a node 00540 STXXL_VERBOSE1("btree: retrieving begin() from the first node"); 00541 node_type * Node = node_cache_.get_node((node_bid_type)it->second, true); 00542 assert(Node); 00543 iterator result = Node->begin(height_ - 1); 00544 node_cache_.unfix_node((node_bid_type)it->second); 00545 00546 assert(leaf_cache_.nfixed() == 0); 00547 assert(node_cache_.nfixed() == 0); 00548 00549 return result; 00550 } 00551 00552 const_iterator begin() const 00553 { 00554 root_node_const_iterator_type it = root_node_.begin(); 00555 assert(it != root_node_.end()); 00556 00557 if (height_ == 2) // 'it' points to a leaf 00558 { 00559 STXXL_VERBOSE1("btree: retrieving begin() from the first leaf"); 00560 leaf_type const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second); 00561 assert(Leaf); 00562 assert(leaf_cache_.nfixed() == 0); 00563 assert(node_cache_.nfixed() == 0); 00564 return Leaf->begin(); 00565 } 00566 00567 // 'it' points to a node 00568 STXXL_VERBOSE1("btree: retrieving begin() from the first node"); 00569 node_type const * Node = node_cache_.get_const_node((node_bid_type)it->second, true); 00570 assert(Node); 00571 const_iterator result = Node->begin(height_ - 1); 00572 node_cache_.unfix_node((node_bid_type)it->second); 00573 assert(leaf_cache_.nfixed() == 0); 00574 assert(node_cache_.nfixed() == 0); 00575 return result; 00576 } 00577 00578 iterator end() 00579 { 00580 return end_iterator; 00581 } 00582 00583 const_iterator end() const 00584 { 00585 return end_iterator; 00586 } 00587 00588 data_type & operator [] (const key_type & k) 00589 { 00590 return (*((insert(value_type(k, data_type()))).first)).second; 00591 } 00592 00593 iterator find(const key_type & k) 00594 { 00595 root_node_iterator_type it = root_node_.lower_bound(k); 00596 assert(it != root_node_.end()); 00597 00598 if (height_ == 2) // 'it' points to a leaf 00599 { 00600 STXXL_VERBOSE1("Searching in a leaf"); 00601 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second, true); 00602 assert(Leaf); 00603 iterator result = Leaf->find(k); 00604 leaf_cache_.unfix_node((leaf_bid_type)it->second); 00605 assert(result == end() || result->first == k); 00606 assert(leaf_cache_.nfixed() == 0); 00607 assert(node_cache_.nfixed() == 0); 00608 return result; 00609 } 00610 00611 // 'it' points to a node 00612 STXXL_VERBOSE1("Searching in a node"); 00613 node_type * Node = node_cache_.get_node((node_bid_type)it->second, true); 00614 assert(Node); 00615 iterator result = Node->find(k, height_ - 1); 00616 node_cache_.unfix_node((node_bid_type)it->second); 00617 00618 assert(result == end() || result->first == k); 00619 assert(leaf_cache_.nfixed() == 0); 00620 assert(node_cache_.nfixed() == 0); 00621 return result; 00622 } 00623 00624 const_iterator find(const key_type & k) const 00625 { 00626 root_node_const_iterator_type it = root_node_.lower_bound(k); 00627 assert(it != root_node_.end()); 00628 00629 if (height_ == 2) // 'it' points to a leaf 00630 { 00631 STXXL_VERBOSE1("Searching in a leaf"); 00632 leaf_type const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second, true); 00633 assert(Leaf); 00634 const_iterator result = Leaf->find(k); 00635 leaf_cache_.unfix_node((leaf_bid_type)it->second); 00636 assert(result == end() || result->first == k); 00637 assert(leaf_cache_.nfixed() == 0); 00638 assert(node_cache_.nfixed() == 0); 00639 return result; 00640 } 00641 00642 // 'it' points to a node 00643 STXXL_VERBOSE1("Searching in a node"); 00644 node_type const * Node = node_cache_.get_const_node((node_bid_type)it->second, true); 00645 assert(Node); 00646 const_iterator result = Node->find(k, height_ - 1); 00647 node_cache_.unfix_node((node_bid_type)it->second); 00648 00649 assert(result == end() || result->first == k); 00650 assert(leaf_cache_.nfixed() == 0); 00651 assert(node_cache_.nfixed() == 0); 00652 return result; 00653 } 00654 00655 iterator lower_bound(const key_type & k) 00656 { 00657 root_node_iterator_type it = root_node_.lower_bound(k); 00658 assert(it != root_node_.end()); 00659 00660 if (height_ == 2) // 'it' points to a leaf 00661 { 00662 STXXL_VERBOSE1("Searching lower bound in a leaf"); 00663 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second, true); 00664 assert(Leaf); 00665 iterator result = Leaf->lower_bound(k); 00666 leaf_cache_.unfix_node((leaf_bid_type)it->second); 00667 assert(leaf_cache_.nfixed() == 0); 00668 assert(node_cache_.nfixed() == 0); 00669 return result; 00670 } 00671 00672 // 'it' points to a node 00673 STXXL_VERBOSE1("Searching lower bound in a node"); 00674 node_type * Node = node_cache_.get_node((node_bid_type)it->second, true); 00675 assert(Node); 00676 iterator result = Node->lower_bound(k, height_ - 1); 00677 node_cache_.unfix_node((node_bid_type)it->second); 00678 00679 assert(leaf_cache_.nfixed() == 0); 00680 assert(node_cache_.nfixed() == 0); 00681 return result; 00682 } 00683 00684 const_iterator lower_bound(const key_type & k) const 00685 { 00686 root_node_const_iterator_type it = root_node_.lower_bound(k); 00687 assert(it != root_node_.end()); 00688 00689 if (height_ == 2) // 'it' points to a leaf 00690 { 00691 STXXL_VERBOSE1("Searching lower bound in a leaf"); 00692 leaf_type const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second, true); 00693 assert(Leaf); 00694 const_iterator result = Leaf->lower_bound(k); 00695 leaf_cache_.unfix_node((leaf_bid_type)it->second); 00696 00697 assert(leaf_cache_.nfixed() == 0); 00698 assert(node_cache_.nfixed() == 0); 00699 return result; 00700 } 00701 00702 // 'it' points to a node 00703 STXXL_VERBOSE1("Searching lower bound in a node"); 00704 node_type const * Node = node_cache_.get_const_node((node_bid_type)it->second, true); 00705 assert(Node); 00706 const_iterator result = Node->lower_bound(k, height_ - 1); 00707 node_cache_.unfix_node((node_bid_type)it->second); 00708 00709 assert(leaf_cache_.nfixed() == 0); 00710 assert(node_cache_.nfixed() == 0); 00711 return result; 00712 } 00713 00714 iterator upper_bound(const key_type & k) 00715 { 00716 root_node_iterator_type it = root_node_.upper_bound(k); 00717 assert(it != root_node_.end()); 00718 00719 if (height_ == 2) // 'it' points to a leaf 00720 { 00721 STXXL_VERBOSE1("Searching upper bound in a leaf"); 00722 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second, true); 00723 assert(Leaf); 00724 iterator result = Leaf->upper_bound(k); 00725 leaf_cache_.unfix_node((leaf_bid_type)it->second); 00726 00727 assert(leaf_cache_.nfixed() == 0); 00728 assert(node_cache_.nfixed() == 0); 00729 return result; 00730 } 00731 00732 // 'it' points to a node 00733 STXXL_VERBOSE1("Searching upper bound in a node"); 00734 node_type * Node = node_cache_.get_node((node_bid_type)it->second, true); 00735 assert(Node); 00736 iterator result = Node->upper_bound(k, height_ - 1); 00737 node_cache_.unfix_node((node_bid_type)it->second); 00738 00739 assert(leaf_cache_.nfixed() == 0); 00740 assert(node_cache_.nfixed() == 0); 00741 return result; 00742 } 00743 00744 const_iterator upper_bound(const key_type & k) const 00745 { 00746 root_node_const_iterator_type it = root_node_.upper_bound(k); 00747 assert(it != root_node_.end()); 00748 00749 if (height_ == 2) // 'it' points to a leaf 00750 { 00751 STXXL_VERBOSE1("Searching upper bound in a leaf"); 00752 leaf_type const * Leaf = leaf_cache_.get_const_node((leaf_bid_type)it->second, true); 00753 assert(Leaf); 00754 const_iterator result = Leaf->upper_bound(k); 00755 leaf_cache_.unfix_node((leaf_bid_type)it->second); 00756 00757 assert(leaf_cache_.nfixed() == 0); 00758 assert(node_cache_.nfixed() == 0); 00759 return result; 00760 } 00761 00762 // 'it' points to a node 00763 STXXL_VERBOSE1("Searching upper bound in a node"); 00764 node_type const * Node = node_cache_.get_const_node((node_bid_type)it->second, true); 00765 assert(Node); 00766 const_iterator result = Node->upper_bound(k, height_ - 1); 00767 node_cache_.unfix_node((node_bid_type)it->second); 00768 00769 assert(leaf_cache_.nfixed() == 0); 00770 assert(node_cache_.nfixed() == 0); 00771 return result; 00772 } 00773 00774 std::pair<iterator, iterator> equal_range(const key_type & k) 00775 { 00776 iterator l = lower_bound(k); // l->first >= k 00777 00778 if (l == end() || key_compare_(k, l->first)) // if (k < l->first) 00779 return std::pair<iterator, iterator>(l, l); 00780 // then upper_bound == lower_bound 00781 00782 iterator u = l; 00783 ++u; // only one element ==k can exist 00784 00785 assert(leaf_cache_.nfixed() == 0); 00786 assert(node_cache_.nfixed() == 0); 00787 00788 return std::pair<iterator, iterator>(l, u); // then upper_bound == (lower_bound+1) 00789 } 00790 00791 std::pair<const_iterator, const_iterator> equal_range(const key_type & k) const 00792 { 00793 const_iterator l = lower_bound(k); // l->first >= k 00794 00795 if (l == end() || key_compare_(k, l->first)) // if (k < l->first) 00796 return std::pair<const_iterator, const_iterator>(l, l); 00797 // then upper_bound == lower_bound 00798 00799 const_iterator u = l; 00800 ++u; // only one element ==k can exist 00801 00802 assert(leaf_cache_.nfixed() == 0); 00803 assert(node_cache_.nfixed() == 0); 00804 return std::pair<const_iterator, const_iterator>(l, u); // then upper_bound == (lower_bound+1) 00805 } 00806 00807 size_type erase(const key_type & k) 00808 { 00809 root_node_iterator_type it = root_node_.lower_bound(k); 00810 assert(it != root_node_.end()); 00811 if (height_ == 2) // 'it' points to a leaf 00812 { 00813 STXXL_VERBOSE1("Deleting key from a leaf"); 00814 leaf_type * Leaf = leaf_cache_.get_node((leaf_bid_type)it->second, true); 00815 assert(Leaf); 00816 size_type result = Leaf->erase(k); 00817 size_ -= result; 00818 leaf_cache_.unfix_node((leaf_bid_type)it->second); 00819 assert(leaf_cache_.nfixed() == 0); 00820 assert(node_cache_.nfixed() == 0); 00821 00822 if ((!Leaf->underflows()) || root_node_.size() == 1) 00823 return result; 00824 // no underflow or root has a special degree 1 (too few elements) 00825 00826 STXXL_VERBOSE1("btree: Fusing or rebalancing a leaf"); 00827 fuse_or_balance(it, leaf_cache_); 00828 00829 assert(leaf_cache_.nfixed() == 0); 00830 assert(node_cache_.nfixed() == 0); 00831 00832 return result; 00833 } 00834 00835 // 'it' points to a node 00836 STXXL_VERBOSE1("Deleting key from a node"); 00837 assert(root_node_.size() >= 2); 00838 node_type * Node = node_cache_.get_node((node_bid_type)it->second, true); 00839 assert(Node); 00840 size_type result = Node->erase(k, height_ - 1); 00841 size_ -= result; 00842 node_cache_.unfix_node((node_bid_type)it->second); 00843 assert(leaf_cache_.nfixed() == 0); 00844 assert(node_cache_.nfixed() == 0); 00845 if (!Node->underflows()) 00846 return result; 00847 // no underflow happened 00848 00849 STXXL_VERBOSE1("Fusing or rebalancing a node"); 00850 fuse_or_balance(it, node_cache_); 00851 00852 if (root_node_.size() == 1) 00853 { 00854 STXXL_VERBOSE1("btree Root has size 1 and height > 2"); 00855 STXXL_VERBOSE1("btree Deallocate root and decrease height"); 00856 it = root_node_.begin(); 00857 node_bid_type RootBid = it->second; 00858 assert(it->first == key_compare::max_value()); 00859 node_type * RootNode = node_cache_.get_node(RootBid); 00860 assert(RootNode); 00861 assert(RootNode->back().first == key_compare::max_value()); 00862 root_node_.clear(); 00863 root_node_.insert(RootNode->block().begin(), 00864 RootNode->block().begin() + RootNode->size()); 00865 00866 node_cache_.delete_node(RootBid); 00867 --height_; 00868 STXXL_VERBOSE1("btree Decreasing height to " << height_); 00869 } 00870 00871 assert(leaf_cache_.nfixed() == 0); 00872 assert(node_cache_.nfixed() == 0); 00873 00874 return result; 00875 } 00876 00877 size_type count(const key_type & k) 00878 { 00879 if (find(k) == end()) 00880 return 0; 00881 00882 return 1; 00883 } 00884 00885 void erase(iterator pos) 00886 { 00887 assert(pos != end()); 00888 #ifndef NDEBUG 00889 size_type old_size = size(); 00890 #endif 00891 00892 erase(pos->first); 00893 00894 assert(size() == old_size - 1); 00895 } 00896 00897 iterator insert(iterator /*pos*/, const value_type & x) 00898 { 00899 return insert(x).first; // pos ignored in the current version 00900 } 00901 00902 void clear() 00903 { 00904 deallocate_children(); 00905 00906 root_node_.clear(); 00907 00908 size_ = 0; 00909 height_ = 2, 00910 00911 create_empty_leaf(); 00912 assert(leaf_cache_.nfixed() == 0); 00913 assert(node_cache_.nfixed() == 0); 00914 } 00915 00916 template <class InputIterator> 00917 void insert(InputIterator b, InputIterator e) 00918 { 00919 while (b != e) 00920 { 00921 insert(*(b++)); 00922 } 00923 } 00924 00925 template <class InputIterator> 00926 btree(InputIterator b, 00927 InputIterator e, 00928 const key_compare & c_, 00929 unsigned_type node_cache_size_in_bytes, 00930 unsigned_type leaf_cache_size_in_bytes, 00931 bool range_sorted = false, 00932 double node_fill_factor = 0.75, 00933 double leaf_fill_factor = 0.6 00934 ) : 00935 key_compare_(c_), 00936 node_cache_(node_cache_size_in_bytes, this, key_compare_), 00937 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_), 00938 iterator_map_(this), 00939 size_(0), 00940 height_(2), 00941 prefetching_enabled_(true), 00942 bm_(block_manager::get_instance()) 00943 { 00944 STXXL_VERBOSE1("Creating a btree, addr=" << this); 00945 STXXL_VERBOSE1(" bytes in a node: " << node_bid_type::size); 00946 STXXL_VERBOSE1(" bytes in a leaf: " << leaf_bid_type::size); 00947 00948 if (range_sorted == false) 00949 { 00950 create_empty_leaf(); 00951 insert(b, e); 00952 assert(leaf_cache_.nfixed() == 0); 00953 assert(node_cache_.nfixed() == 0); 00954 return; 00955 } 00956 00957 bulk_construction(b, e, node_fill_factor, leaf_fill_factor); 00958 assert(leaf_cache_.nfixed() == 0); 00959 assert(node_cache_.nfixed() == 0); 00960 } 00961 00962 00963 template <class InputIterator> 00964 btree(InputIterator b, 00965 InputIterator e, 00966 unsigned_type node_cache_size_in_bytes, 00967 unsigned_type leaf_cache_size_in_bytes, 00968 bool range_sorted = false, 00969 double node_fill_factor = 0.75, 00970 double leaf_fill_factor = 0.6 00971 ) : 00972 node_cache_(node_cache_size_in_bytes, this, key_compare_), 00973 leaf_cache_(leaf_cache_size_in_bytes, this, key_compare_), 00974 iterator_map_(this), 00975 size_(0), 00976 height_(2), 00977 prefetching_enabled_(true), 00978 bm_(block_manager::get_instance()) 00979 { 00980 STXXL_VERBOSE1("Creating a btree, addr=" << this); 00981 STXXL_VERBOSE1(" bytes in a node: " << node_bid_type::size); 00982 STXXL_VERBOSE1(" bytes in a leaf: " << leaf_bid_type::size); 00983 00984 if (range_sorted == false) 00985 { 00986 create_empty_leaf(); 00987 insert(b, e); 00988 assert(leaf_cache_.nfixed() == 0); 00989 assert(node_cache_.nfixed() == 0); 00990 return; 00991 } 00992 00993 bulk_construction(b, e, node_fill_factor, leaf_fill_factor); 00994 assert(leaf_cache_.nfixed() == 0); 00995 assert(node_cache_.nfixed() == 0); 00996 } 00997 00998 void erase(iterator first, iterator last) 00999 { 01000 if (first == begin() && last == end()) 01001 clear(); 01002 01003 else 01004 while (first != last) 01005 erase(first++); 01006 } 01007 01008 key_compare key_comp() const 01009 { 01010 return key_compare_; 01011 } 01012 value_compare value_comp() const 01013 { 01014 return value_compare(key_compare_); 01015 } 01016 01017 void swap(btree & obj) 01018 { 01019 std::swap(key_compare_, obj.key_compare_); // OK 01020 01021 std::swap(node_cache_, obj.node_cache_); // OK 01022 std::swap(leaf_cache_, obj.leaf_cache_); // OK 01023 01024 01025 std::swap(iterator_map_, obj.iterator_map_); // must update all iterators 01026 01027 std::swap(end_iterator, obj.end_iterator); 01028 std::swap(size_, obj.size_); 01029 std::swap(height_, obj.height_); 01030 std::swap(alloc_strategy_, obj.alloc_strategy_); 01031 std::swap(root_node_, obj.root_node_); 01032 } 01033 01034 void enable_prefetching() 01035 { 01036 prefetching_enabled_ = true; 01037 } 01038 void disable_prefetching() 01039 { 01040 prefetching_enabled_ = false; 01041 } 01042 bool prefetching_enabled() 01043 { 01044 return prefetching_enabled_; 01045 } 01046 01047 void print_statistics(std::ostream & o) const 01048 { 01049 o << "Node cache statistics:" << std::endl; 01050 node_cache_.print_statistics(o); 01051 o << "Leaf cache statistics:" << std::endl; 01052 leaf_cache_.print_statistics(o); 01053 } 01054 void reset_statistics() 01055 { 01056 node_cache_.reset_statistics(); 01057 leaf_cache_.reset_statistics(); 01058 } 01059 }; 01060 01061 template <class KeyType, 01062 class DataType, 01063 class CompareType, 01064 unsigned LogNodeSize, 01065 unsigned LogLeafSize, 01066 class PDAllocStrategy 01067 > 01068 inline bool operator == (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a, 01069 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b) 01070 { 01071 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin()); 01072 } 01073 01074 template <class KeyType, 01075 class DataType, 01076 class CompareType, 01077 unsigned LogNodeSize, 01078 unsigned LogLeafSize, 01079 class PDAllocStrategy 01080 > 01081 inline bool operator != (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a, 01082 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b) 01083 { 01084 return !(a == b); 01085 } 01086 01087 01088 template <class KeyType, 01089 class DataType, 01090 class CompareType, 01091 unsigned LogNodeSize, 01092 unsigned LogLeafSize, 01093 class PDAllocStrategy 01094 > 01095 inline bool operator < (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a, 01096 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b) 01097 { 01098 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); 01099 } 01100 01101 01102 template <class KeyType, 01103 class DataType, 01104 class CompareType, 01105 unsigned LogNodeSize, 01106 unsigned LogLeafSize, 01107 class PDAllocStrategy 01108 > 01109 inline bool operator > (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a, 01110 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b) 01111 { 01112 return b < a; 01113 } 01114 01115 01116 template <class KeyType, 01117 class DataType, 01118 class CompareType, 01119 unsigned LogNodeSize, 01120 unsigned LogLeafSize, 01121 class PDAllocStrategy 01122 > 01123 inline bool operator <= (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a, 01124 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b) 01125 { 01126 return !(b < a); 01127 } 01128 01129 template <class KeyType, 01130 class DataType, 01131 class CompareType, 01132 unsigned LogNodeSize, 01133 unsigned LogLeafSize, 01134 class PDAllocStrategy 01135 > 01136 inline bool operator >= (const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a, 01137 const btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b) 01138 { 01139 return !(a < b); 01140 } 01141 } 01142 01143 __STXXL_END_NAMESPACE 01144 01145 01146 namespace std 01147 { 01148 template <class KeyType, 01149 class DataType, 01150 class CompareType, 01151 unsigned LogNodeSize, 01152 unsigned LogLeafSize, 01153 class PDAllocStrategy 01154 > 01155 void swap(stxxl::btree::btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & a, 01156 stxxl::btree::btree<KeyType, DataType, CompareType, LogNodeSize, LogLeafSize, PDAllocStrategy> & b) 01157 { 01158 if (&a != &b) 01159 a.swap(b); 01160 } 01161 } 01162 01163 #endif /* STXXL_CONTAINERS_BTREE__BTREE_H */
1.7.6.1
