Stxxl 1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/containers/btree/node.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__NODE_H 00014 #define STXXL_CONTAINERS_BTREE__NODE_H 00015 00016 #include <stxxl/bits/containers/btree/iterator.h> 00017 #include <stxxl/bits/containers/btree/node_cache.h> 00018 00019 00020 __STXXL_BEGIN_NAMESPACE 00021 00022 namespace btree 00023 { 00024 template <class NodeType, class BTreeType> 00025 class node_cache; 00026 00027 template <class KeyType_, class KeyCmp_, unsigned RawSize_, class BTreeType> 00028 class normal_node : private noncopyable 00029 { 00030 public: 00031 typedef normal_node<KeyType_, KeyCmp_, RawSize_, BTreeType> SelfType; 00032 00033 friend class node_cache<SelfType, BTreeType>; 00034 00035 typedef KeyType_ key_type; 00036 typedef KeyCmp_ key_compare; 00037 00038 enum { 00039 raw_size = RawSize_ 00040 }; 00041 typedef BID<raw_size> bid_type; 00042 typedef bid_type node_bid_type; 00043 typedef SelfType node_type; 00044 typedef std::pair<key_type, bid_type> value_type; 00045 typedef value_type & reference; 00046 typedef const value_type & const_reference; 00047 00048 00049 struct InfoType 00050 { 00051 bid_type me; 00052 unsigned cur_size; 00053 }; 00054 typedef typed_block<raw_size, value_type, 0, InfoType> block_type; 00055 00056 enum { 00057 nelements = block_type::size - 1, 00058 max_size = nelements, 00059 min_size = nelements / 2 00060 }; 00061 typedef typename block_type::iterator block_iterator; 00062 typedef typename block_type::const_iterator block_const_iterator; 00063 00064 typedef BTreeType btree_type; 00065 typedef typename btree_type::size_type size_type; 00066 typedef typename btree_type::iterator iterator; 00067 typedef typename btree_type::const_iterator const_iterator; 00068 00069 typedef typename btree_type::value_type btree_value_type; 00070 typedef typename btree_type::leaf_bid_type leaf_bid_type; 00071 typedef typename btree_type::leaf_type leaf_type; 00072 00073 typedef node_cache<normal_node, btree_type> node_cache_type; 00074 00075 private: 00076 struct value_compare : public std::binary_function<value_type, bid_type, bool> 00077 { 00078 key_compare comp; 00079 00080 value_compare(key_compare c) : comp(c) { } 00081 00082 bool operator () (const value_type & x, const value_type & y) const 00083 { 00084 return comp(x.first, y.first); 00085 } 00086 }; 00087 00088 block_type * block_; 00089 btree_type * btree_; 00090 key_compare cmp_; 00091 value_compare vcmp_; 00092 00093 00094 template <class BIDType> 00095 std::pair<key_type, bid_type> insert(const std::pair<key_type, BIDType> & splitter, 00096 const block_iterator & place2insert) 00097 { 00098 std::pair<key_type, bid_type> result(key_compare::max_value(), bid_type()); 00099 00100 // splitter != *place2insert 00101 assert(vcmp_(*place2insert, splitter) || vcmp_(splitter, *place2insert)); 00102 00103 block_iterator cur = block_->begin() + size() - 1; 00104 for ( ; cur >= place2insert; --cur) 00105 *(cur + 1) = *cur; 00106 // copy elements to make space for the new element 00107 00108 *place2insert = splitter; // insert 00109 00110 ++(block_->info.cur_size); 00111 00112 if (size() > max_nelements()) // overflow! need to split 00113 { 00114 STXXL_VERBOSE1("btree::normal_node::insert overflow happened, splitting"); 00115 00116 bid_type NewBid; 00117 btree_->node_cache_.get_new_node(NewBid); // new (left) node 00118 normal_node * NewNode = btree_->node_cache_.get_node(NewBid, true); 00119 assert(NewNode); 00120 00121 const unsigned end_of_smaller_part = size() / 2; 00122 00123 result.first = ((*block_)[end_of_smaller_part - 1]).first; 00124 result.second = NewBid; 00125 00126 00127 const unsigned old_size = size(); 00128 // copy the smaller part 00129 std::copy(block_->begin(), block_->begin() + end_of_smaller_part, NewNode->block_->begin()); 00130 NewNode->block_->info.cur_size = end_of_smaller_part; 00131 // copy the larger part 00132 std::copy(block_->begin() + end_of_smaller_part, 00133 block_->begin() + old_size, block_->begin()); 00134 block_->info.cur_size = old_size - end_of_smaller_part; 00135 assert(size() + NewNode->size() == old_size); 00136 00137 btree_->node_cache_.unfix_node(NewBid); 00138 00139 STXXL_VERBOSE1("btree::normal_node split leaf " << this 00140 << " splitter: " << result.first); 00141 } 00142 00143 return result; 00144 } 00145 00146 template <class CacheType> 00147 void fuse_or_balance(block_iterator UIt, CacheType & cache_) 00148 { 00149 typedef typename CacheType::node_type local_node_type; 00150 typedef typename local_node_type::bid_type local_bid_type; 00151 00152 block_iterator leftIt, rightIt; 00153 if (UIt == (block_->begin() + size() - 1)) // UIt is the last entry in the root 00154 { 00155 assert(UIt != block_->begin()); 00156 rightIt = UIt; 00157 leftIt = --UIt; 00158 } 00159 else 00160 { 00161 leftIt = UIt; 00162 rightIt = ++UIt; 00163 assert(rightIt != (block_->begin() + size())); 00164 } 00165 00166 // now fuse or balance nodes pointed by leftIt and rightIt 00167 local_bid_type LeftBid = (local_bid_type)leftIt->second; 00168 local_bid_type RightBid = (local_bid_type)rightIt->second; 00169 local_node_type * LeftNode = cache_.get_node(LeftBid, true); 00170 local_node_type * RightNode = cache_.get_node(RightBid, true); 00171 00172 const unsigned TotalSize = LeftNode->size() + RightNode->size(); 00173 if (TotalSize <= RightNode->max_nelements()) 00174 { 00175 // fuse 00176 RightNode->fuse(*LeftNode); // add the content of LeftNode to RightNode 00177 00178 cache_.unfix_node(RightBid); 00179 cache_.delete_node(LeftBid); // 'delete_node' unfixes LeftBid also 00180 00181 std::copy(leftIt + 1, block_->begin() + size(), leftIt); // delete left BID from the root 00182 --(block_->info.cur_size); 00183 } 00184 else 00185 { 00186 // balance 00187 00188 key_type NewSplitter = RightNode->balance(*LeftNode); 00189 00190 00191 leftIt->first = NewSplitter; // change key 00192 assert(vcmp_(*leftIt, *rightIt)); 00193 00194 cache_.unfix_node(LeftBid); 00195 cache_.unfix_node(RightBid); 00196 } 00197 } 00198 00199 public: 00200 virtual ~normal_node() 00201 { 00202 delete block_; 00203 } 00204 00205 normal_node(btree_type * btree__, 00206 key_compare cmp) : 00207 block_(new block_type), 00208 btree_(btree__), 00209 cmp_(cmp), 00210 vcmp_(cmp) 00211 { 00212 assert(min_nelements() >= 2); 00213 assert(2 * min_nelements() - 1 <= max_nelements()); 00214 assert(max_nelements() <= nelements); 00215 assert(unsigned(block_type::size) >= nelements + 1); // extra space for an overflow 00216 } 00217 00218 block_type & block() 00219 { 00220 return *block_; 00221 } 00222 00223 bool overflows() const { return block_->info.cur_size > max_nelements(); } 00224 bool underflows() const { return block_->info.cur_size < min_nelements(); } 00225 00226 unsigned max_nelements() const { return max_size; } 00227 unsigned min_nelements() const { return min_size; } 00228 00229 /* 00230 template <class InputIterator> 00231 normal_node(InputIterator begin_, InputIterator end_, 00232 btree_type * btree__, 00233 key_compare cmp): 00234 block_(new block_type), 00235 btree_(btree__), 00236 cmp_(cmp), 00237 vcmp_(cmp) 00238 { 00239 assert(min_nelements() >=2); 00240 assert(2*min_nelements() - 1 <= max_nelements()); 00241 assert(max_nelements() <= nelements); 00242 assert(unsigned(block_type::size) >= nelements +1); // extra space for an overflow 00243 00244 unsigned new_size = end_ - begin_; 00245 assert(new_size <= max_nelements()); 00246 assert(new_size >= min_nelements()); 00247 00248 std::copy(begin_,end_,block_->begin()); 00249 assert(stxxl::is_sorted(block_->begin(),block_->begin() + new_size, vcmp_)); 00250 block_->info.cur_size = new_size; 00251 }*/ 00252 00253 unsigned size() const 00254 { 00255 return block_->info.cur_size; 00256 } 00257 00258 bid_type my_bid() const 00259 { 00260 return block_->info.me; 00261 } 00262 00263 void save() 00264 { 00265 request_ptr req = block_->write(my_bid()); 00266 req->wait(); 00267 } 00268 00269 request_ptr load(const bid_type & bid) 00270 { 00271 request_ptr req = block_->read(bid); 00272 req->wait(); 00273 assert(bid == my_bid()); 00274 return req; 00275 } 00276 00277 request_ptr prefetch(const bid_type & bid) 00278 { 00279 return block_->read(bid); 00280 } 00281 00282 void init(const bid_type & my_bid_) 00283 { 00284 block_->info.me = my_bid_; 00285 block_->info.cur_size = 0; 00286 } 00287 00288 reference operator [] (int i) 00289 { 00290 return (*block_)[i]; 00291 } 00292 00293 const_reference operator [] (int i) const 00294 { 00295 return (*block_)[i]; 00296 } 00297 00298 reference back() 00299 { 00300 return (*block_)[size() - 1]; 00301 } 00302 00303 reference front() 00304 { 00305 return *(block_->begin()); 00306 } 00307 00308 const_reference back() const 00309 { 00310 return (*block_)[size() - 1]; 00311 } 00312 00313 const_reference front() const 00314 { 00315 return *(block_->begin()); 00316 } 00317 00318 00319 std::pair<iterator, bool> insert( 00320 const btree_value_type & x, 00321 unsigned height, 00322 std::pair<key_type, bid_type> & splitter) 00323 { 00324 assert(size() <= max_nelements()); 00325 splitter.first = key_compare::max_value(); 00326 00327 value_type Key2Search(x.first, bid_type()); 00328 block_iterator it = 00329 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00330 00331 assert(it != (block_->begin() + size())); 00332 00333 bid_type found_bid = it->second; 00334 00335 if (height == 2) // found_bid points to a leaf 00336 { 00337 STXXL_VERBOSE1("btree::normal_node Inserting new value into a leaf"); 00338 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)it->second, true); 00339 assert(Leaf); 00340 std::pair<key_type, leaf_bid_type> BotSplitter; 00341 std::pair<iterator, bool> result = Leaf->insert(x, BotSplitter); 00342 btree_->leaf_cache_.unfix_node((leaf_bid_type)it->second); 00343 //if(key_compare::max_value() == BotSplitter.first) 00344 if (!(cmp_(key_compare::max_value(), BotSplitter.first) || 00345 cmp_(BotSplitter.first, key_compare::max_value()))) 00346 return result; 00347 // no overflow/splitting happened 00348 00349 STXXL_VERBOSE1("btree::normal_node Inserting new value in *this"); 00350 00351 splitter = insert(BotSplitter, it); 00352 00353 return result; 00354 } 00355 else 00356 { // found_bid points to a node 00357 STXXL_VERBOSE1("btree::normal_node Inserting new value into a node"); 00358 node_type * Node = btree_->node_cache_.get_node((node_bid_type)it->second, true); 00359 assert(Node); 00360 std::pair<key_type, node_bid_type> BotSplitter; 00361 std::pair<iterator, bool> result = Node->insert(x, height - 1, BotSplitter); 00362 btree_->node_cache_.unfix_node((node_bid_type)it->second); 00363 //if(key_compare::max_value() == BotSplitter.first) 00364 if (!(cmp_(key_compare::max_value(), BotSplitter.first) || 00365 cmp_(BotSplitter.first, key_compare::max_value()))) 00366 return result; 00367 // no overflow/splitting happened 00368 00369 STXXL_VERBOSE1("btree::normal_node Inserting new value in *this"); 00370 00371 splitter = insert(BotSplitter, it); 00372 00373 return result; 00374 } 00375 } 00376 00377 iterator begin(unsigned height) 00378 { 00379 bid_type FirstBid = block_->begin()->second; 00380 if (height == 2) // FirstBid points to a leaf 00381 { 00382 assert(size() > 1); 00383 STXXL_VERBOSE1("btree::node retrieveing begin() from the first leaf"); 00384 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)FirstBid); 00385 assert(Leaf); 00386 return Leaf->begin(); 00387 } 00388 else 00389 { // FirstBid points to a node 00390 STXXL_VERBOSE1("btree: retrieveing begin() from the first node"); 00391 node_type * Node = btree_->node_cache_.get_node((node_bid_type)FirstBid, true); 00392 assert(Node); 00393 iterator result = Node->begin(height - 1); 00394 btree_->node_cache_.unfix_node((node_bid_type)FirstBid); 00395 return result; 00396 } 00397 } 00398 00399 const_iterator begin(unsigned height) const 00400 { 00401 bid_type FirstBid = block_->begin()->second; 00402 if (height == 2) // FirstBid points to a leaf 00403 { 00404 assert(size() > 1); 00405 STXXL_VERBOSE1("btree::node retrieveing begin() from the first leaf"); 00406 leaf_type const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)FirstBid); 00407 assert(Leaf); 00408 return Leaf->begin(); 00409 } 00410 else 00411 { // FirstBid points to a node 00412 STXXL_VERBOSE1("btree: retrieveing begin() from the first node"); 00413 node_type const * Node = btree_->node_cache_.get_const_node((node_bid_type)FirstBid, true); 00414 assert(Node); 00415 const_iterator result = Node->begin(height - 1); 00416 btree_->node_cache_.unfix_node((node_bid_type)FirstBid); 00417 return result; 00418 } 00419 } 00420 00421 iterator find(const key_type & k, unsigned height) 00422 { 00423 value_type Key2Search(k, bid_type()); 00424 00425 block_iterator it = 00426 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00427 00428 assert(it != (block_->begin() + size())); 00429 00430 bid_type found_bid = it->second; 00431 00432 if (height == 2) // found_bid points to a leaf 00433 { 00434 STXXL_VERBOSE1("Searching in a leaf"); 00435 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid, true); 00436 assert(Leaf); 00437 iterator result = Leaf->find(k); 00438 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid); 00439 00440 return result; 00441 } 00442 00443 // found_bid points to a node 00444 STXXL_VERBOSE1("Searching in a node"); 00445 node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid, true); 00446 assert(Node); 00447 iterator result = Node->find(k, height - 1); 00448 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00449 00450 return result; 00451 } 00452 00453 const_iterator find(const key_type & k, unsigned height) const 00454 { 00455 value_type Key2Search(k, bid_type()); 00456 00457 block_iterator it = 00458 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00459 00460 assert(it != (block_->begin() + size())); 00461 00462 bid_type found_bid = it->second; 00463 00464 if (height == 2) // found_bid points to a leaf 00465 { 00466 STXXL_VERBOSE1("Searching in a leaf"); 00467 leaf_type const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)found_bid, true); 00468 assert(Leaf); 00469 const_iterator result = Leaf->find(k); 00470 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid); 00471 00472 return result; 00473 } 00474 00475 // found_bid points to a node 00476 STXXL_VERBOSE1("Searching in a node"); 00477 node_type const * Node = btree_->node_cache_.get_const_node((node_bid_type)found_bid, true); 00478 assert(Node); 00479 const_iterator result = Node->find(k, height - 1); 00480 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00481 00482 return result; 00483 } 00484 00485 iterator lower_bound(const key_type & k, unsigned height) 00486 { 00487 value_type Key2Search(k, bid_type()); 00488 assert(!vcmp_(back(), Key2Search)); 00489 block_iterator it = 00490 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00491 00492 assert(it != (block_->begin() + size())); 00493 00494 bid_type found_bid = it->second; 00495 00496 if (height == 2) // found_bid points to a leaf 00497 { 00498 STXXL_VERBOSE1("Searching lower bound in a leaf"); 00499 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid, true); 00500 assert(Leaf); 00501 iterator result = Leaf->lower_bound(k); 00502 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid); 00503 00504 return result; 00505 } 00506 00507 // found_bid points to a node 00508 STXXL_VERBOSE1("Searching lower bound in a node"); 00509 node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid, true); 00510 assert(Node); 00511 iterator result = Node->lower_bound(k, height - 1); 00512 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00513 00514 return result; 00515 } 00516 00517 const_iterator lower_bound(const key_type & k, unsigned height) const 00518 { 00519 value_type Key2Search(k, bid_type()); 00520 assert(!vcmp_(back(), Key2Search)); 00521 block_iterator it = 00522 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00523 00524 assert(it != (block_->begin() + size())); 00525 00526 bid_type found_bid = it->second; 00527 00528 if (height == 2) // found_bid points to a leaf 00529 { 00530 STXXL_VERBOSE1("Searching lower bound in a leaf"); 00531 leaf_type const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)found_bid, true); 00532 assert(Leaf); 00533 const_iterator result = Leaf->lower_bound(k); 00534 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid); 00535 00536 return result; 00537 } 00538 00539 // found_bid points to a node 00540 STXXL_VERBOSE1("Searching lower bound in a node"); 00541 node_type const * Node = btree_->node_cache_.get_const_node((node_bid_type)found_bid, true); 00542 assert(Node); 00543 const_iterator result = Node->lower_bound(k, height - 1); 00544 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00545 00546 return result; 00547 } 00548 00549 iterator upper_bound(const key_type & k, unsigned height) 00550 { 00551 value_type Key2Search(k, bid_type()); 00552 assert(vcmp_(Key2Search, back())); 00553 block_iterator it = 00554 std::upper_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00555 00556 assert(it != (block_->begin() + size())); 00557 00558 bid_type found_bid = it->second; 00559 00560 if (height == 2) // found_bid points to a leaf 00561 { 00562 STXXL_VERBOSE1("Searching upper bound in a leaf"); 00563 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid, true); 00564 assert(Leaf); 00565 iterator result = Leaf->upper_bound(k); 00566 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid); 00567 00568 return result; 00569 } 00570 00571 // found_bid points to a node 00572 STXXL_VERBOSE1("Searching upper bound in a node"); 00573 node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid, true); 00574 assert(Node); 00575 iterator result = Node->upper_bound(k, height - 1); 00576 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00577 00578 return result; 00579 } 00580 00581 const_iterator upper_bound(const key_type & k, unsigned height) const 00582 { 00583 value_type Key2Search(k, bid_type()); 00584 assert(vcmp_(Key2Search, back())); 00585 block_iterator it = 00586 std::upper_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00587 00588 assert(it != (block_->begin() + size())); 00589 00590 bid_type found_bid = it->second; 00591 00592 if (height == 2) // found_bid points to a leaf 00593 { 00594 STXXL_VERBOSE1("Searching upper bound in a leaf"); 00595 leaf_type const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)found_bid, true); 00596 assert(Leaf); 00597 const_iterator result = Leaf->upper_bound(k); 00598 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid); 00599 00600 return result; 00601 } 00602 00603 // found_bid points to a node 00604 STXXL_VERBOSE1("Searching upper bound in a node"); 00605 node_type const * Node = btree_->node_cache_.get_const_node((node_bid_type)found_bid, true); 00606 assert(Node); 00607 const_iterator result = Node->upper_bound(k, height - 1); 00608 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00609 00610 return result; 00611 } 00612 00613 void fuse(const normal_node & Src) 00614 { 00615 assert(vcmp_(Src.back(), front())); 00616 const unsigned SrcSize = Src.size(); 00617 00618 block_iterator cur = block_->begin() + size() - 1; 00619 block_const_iterator begin = block_->begin(); 00620 00621 for ( ; cur >= begin; --cur) 00622 *(cur + SrcSize) = *cur; 00623 // move elements to make space for Src elements 00624 00625 // copy Src to *this leaf 00626 std::copy(Src.block_->begin(), Src.block_->begin() + SrcSize, block_->begin()); 00627 00628 block_->info.cur_size += SrcSize; 00629 } 00630 00631 00632 key_type balance(normal_node & Left) 00633 { 00634 const unsigned TotalSize = Left.size() + size(); 00635 unsigned newLeftSize = TotalSize / 2; 00636 assert(newLeftSize <= Left.max_nelements()); 00637 assert(newLeftSize >= Left.min_nelements()); 00638 unsigned newRightSize = TotalSize - newLeftSize; 00639 assert(newRightSize <= max_nelements()); 00640 assert(newRightSize >= min_nelements()); 00641 00642 assert(vcmp_(Left.back(), front()) || size() == 0); 00643 00644 if (newLeftSize < Left.size()) 00645 { 00646 const unsigned nEl2Move = Left.size() - newLeftSize; // #elements to move from Left to *this 00647 00648 block_iterator cur = block_->begin() + size() - 1; 00649 block_const_iterator begin = block_->begin(); 00650 00651 for ( ; cur >= begin; --cur) 00652 *(cur + nEl2Move) = *cur; 00653 // move elements to make space for Src elements 00654 00655 // copy Left to *this leaf 00656 std::copy(Left.block_->begin() + newLeftSize, 00657 Left.block_->begin() + Left.size(), block_->begin()); 00658 } 00659 else 00660 { 00661 assert(newRightSize < size()); 00662 00663 const unsigned nEl2Move = size() - newRightSize; // #elements to move from *this to Left 00664 00665 // copy *this to Left 00666 std::copy(block_->begin(), 00667 block_->begin() + nEl2Move, Left.block_->begin() + Left.size()); 00668 // move elements in *this 00669 std::copy(block_->begin() + nEl2Move, 00670 block_->begin() + size(), block_->begin()); 00671 } 00672 00673 block_->info.cur_size = newRightSize; // update size 00674 Left.block_->info.cur_size = newLeftSize; // update size 00675 00676 return Left.back().first; 00677 } 00678 00679 size_type erase(const key_type & k, unsigned height) 00680 { 00681 value_type Key2Search(k, bid_type()); 00682 00683 block_iterator it = 00684 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00685 00686 assert(it != (block_->begin() + size())); 00687 00688 bid_type found_bid = it->second; 00689 00690 assert(size() >= 2); 00691 00692 if (height == 2) // 'found_bid' points to a leaf 00693 { 00694 STXXL_VERBOSE1("btree::normal_node Deleting key from a leaf"); 00695 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid, true); 00696 assert(Leaf); 00697 size_type result = Leaf->erase(k); 00698 btree_->leaf_cache_.unfix_node((leaf_bid_type)it->second); 00699 if (!Leaf->underflows()) 00700 return result; 00701 // no underflow or root has a special degree 1 (too few elements) 00702 00703 STXXL_VERBOSE1("btree::normal_node Fusing or rebalancing a leaf"); 00704 fuse_or_balance(it, btree_->leaf_cache_); 00705 00706 return result; 00707 } 00708 00709 // 'found_bid' points to a node 00710 STXXL_VERBOSE1("btree::normal_node Deleting key from a node"); 00711 node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid, true); 00712 assert(Node); 00713 size_type result = Node->erase(k, height - 1); 00714 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00715 if (!Node->underflows()) 00716 return result; 00717 // no underflow happened 00718 00719 STXXL_VERBOSE1("btree::normal_node Fusing or rebalancing a node"); 00720 fuse_or_balance(it, btree_->node_cache_); 00721 00722 return result; 00723 } 00724 00725 void deallocate_children(unsigned height) 00726 { 00727 if (height == 2) 00728 { 00729 // we have children leaves here 00730 block_const_iterator it = block().begin(); 00731 for ( ; it != block().begin() + size(); ++it) 00732 { 00733 // delete from leaf cache and deallocate bid 00734 btree_->leaf_cache_.delete_node((leaf_bid_type)it->second); 00735 } 00736 } 00737 else 00738 { 00739 block_const_iterator it = block().begin(); 00740 for ( ; it != block().begin() + size(); ++it) 00741 { 00742 node_type * Node = btree_->node_cache_.get_node((node_bid_type)it->second); 00743 assert(Node); 00744 Node->deallocate_children(height - 1); 00745 // delete from node cache and deallocate bid 00746 btree_->node_cache_.delete_node((node_bid_type)it->second); 00747 } 00748 } 00749 } 00750 00751 void push_back(const value_type & x) 00752 { 00753 (*this)[size()] = x; 00754 ++(block_->info.cur_size); 00755 } 00756 }; 00757 } 00758 00759 00760 __STXXL_END_NAMESPACE 00761 00762 00763 #endif /* STXXL_CONTAINERS_BTREE__NODE_H */