Stxxl
1.3.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, value_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 STXXL_UNUSED(found_bid); 00335 00336 if (height == 2) // found_bid points to a leaf 00337 { 00338 STXXL_VERBOSE1("btree::normal_node Inserting new value into a leaf"); 00339 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)it->second, true); 00340 assert(Leaf); 00341 std::pair<key_type, leaf_bid_type> BotSplitter; 00342 std::pair<iterator, bool> result = Leaf->insert(x, BotSplitter); 00343 btree_->leaf_cache_.unfix_node((leaf_bid_type)it->second); 00344 //if(key_compare::max_value() == BotSplitter.first) 00345 if (!(cmp_(key_compare::max_value(), BotSplitter.first) || 00346 cmp_(BotSplitter.first, key_compare::max_value()))) 00347 return result; 00348 // no overflow/splitting happened 00349 00350 STXXL_VERBOSE1("btree::normal_node Inserting new value in *this"); 00351 00352 splitter = insert(BotSplitter, it); 00353 00354 return result; 00355 } 00356 else 00357 { // found_bid points to a node 00358 STXXL_VERBOSE1("btree::normal_node Inserting new value into a node"); 00359 node_type * Node = btree_->node_cache_.get_node((node_bid_type)it->second, true); 00360 assert(Node); 00361 std::pair<key_type, node_bid_type> BotSplitter; 00362 std::pair<iterator, bool> result = Node->insert(x, height - 1, BotSplitter); 00363 btree_->node_cache_.unfix_node((node_bid_type)it->second); 00364 //if(key_compare::max_value() == BotSplitter.first) 00365 if (!(cmp_(key_compare::max_value(), BotSplitter.first) || 00366 cmp_(BotSplitter.first, key_compare::max_value()))) 00367 return result; 00368 // no overflow/splitting happened 00369 00370 STXXL_VERBOSE1("btree::normal_node Inserting new value in *this"); 00371 00372 splitter = insert(BotSplitter, it); 00373 00374 return result; 00375 } 00376 } 00377 00378 iterator begin(unsigned height) 00379 { 00380 bid_type FirstBid = block_->begin()->second; 00381 if (height == 2) // FirstBid points to a leaf 00382 { 00383 assert(size() > 1); 00384 STXXL_VERBOSE1("btree::node retrieveing begin() from the first leaf"); 00385 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)FirstBid); 00386 assert(Leaf); 00387 return Leaf->begin(); 00388 } 00389 else 00390 { // FirstBid points to a node 00391 STXXL_VERBOSE1("btree: retrieveing begin() from the first node"); 00392 node_type * Node = btree_->node_cache_.get_node((node_bid_type)FirstBid, true); 00393 assert(Node); 00394 iterator result = Node->begin(height - 1); 00395 btree_->node_cache_.unfix_node((node_bid_type)FirstBid); 00396 return result; 00397 } 00398 } 00399 00400 const_iterator begin(unsigned height) const 00401 { 00402 bid_type FirstBid = block_->begin()->second; 00403 if (height == 2) // FirstBid points to a leaf 00404 { 00405 assert(size() > 1); 00406 STXXL_VERBOSE1("btree::node retrieveing begin() from the first leaf"); 00407 leaf_type const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)FirstBid); 00408 assert(Leaf); 00409 return Leaf->begin(); 00410 } 00411 else 00412 { // FirstBid points to a node 00413 STXXL_VERBOSE1("btree: retrieveing begin() from the first node"); 00414 node_type const * Node = btree_->node_cache_.get_const_node((node_bid_type)FirstBid, true); 00415 assert(Node); 00416 const_iterator result = Node->begin(height - 1); 00417 btree_->node_cache_.unfix_node((node_bid_type)FirstBid); 00418 return result; 00419 } 00420 } 00421 00422 iterator find(const key_type & k, unsigned height) 00423 { 00424 value_type Key2Search(k, bid_type()); 00425 00426 block_iterator it = 00427 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00428 00429 assert(it != (block_->begin() + size())); 00430 00431 bid_type found_bid = it->second; 00432 00433 if (height == 2) // found_bid points to a leaf 00434 { 00435 STXXL_VERBOSE1("Searching in a leaf"); 00436 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid, true); 00437 assert(Leaf); 00438 iterator result = Leaf->find(k); 00439 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid); 00440 00441 return result; 00442 } 00443 00444 // found_bid points to a node 00445 STXXL_VERBOSE1("Searching in a node"); 00446 node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid, true); 00447 assert(Node); 00448 iterator result = Node->find(k, height - 1); 00449 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00450 00451 return result; 00452 } 00453 00454 const_iterator find(const key_type & k, unsigned height) const 00455 { 00456 value_type Key2Search(k, bid_type()); 00457 00458 block_iterator it = 00459 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00460 00461 assert(it != (block_->begin() + size())); 00462 00463 bid_type found_bid = it->second; 00464 00465 if (height == 2) // found_bid points to a leaf 00466 { 00467 STXXL_VERBOSE1("Searching in a leaf"); 00468 leaf_type const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)found_bid, true); 00469 assert(Leaf); 00470 const_iterator result = Leaf->find(k); 00471 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid); 00472 00473 return result; 00474 } 00475 00476 // found_bid points to a node 00477 STXXL_VERBOSE1("Searching in a node"); 00478 node_type const * Node = btree_->node_cache_.get_const_node((node_bid_type)found_bid, true); 00479 assert(Node); 00480 const_iterator result = Node->find(k, height - 1); 00481 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00482 00483 return result; 00484 } 00485 00486 iterator lower_bound(const key_type & k, unsigned height) 00487 { 00488 value_type Key2Search(k, bid_type()); 00489 assert(!vcmp_(back(), Key2Search)); 00490 block_iterator it = 00491 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00492 00493 assert(it != (block_->begin() + size())); 00494 00495 bid_type found_bid = it->second; 00496 00497 if (height == 2) // found_bid points to a leaf 00498 { 00499 STXXL_VERBOSE1("Searching lower bound in a leaf"); 00500 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid, true); 00501 assert(Leaf); 00502 iterator result = Leaf->lower_bound(k); 00503 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid); 00504 00505 return result; 00506 } 00507 00508 // found_bid points to a node 00509 STXXL_VERBOSE1("Searching lower bound in a node"); 00510 node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid, true); 00511 assert(Node); 00512 iterator result = Node->lower_bound(k, height - 1); 00513 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00514 00515 return result; 00516 } 00517 00518 const_iterator lower_bound(const key_type & k, unsigned height) const 00519 { 00520 value_type Key2Search(k, bid_type()); 00521 assert(!vcmp_(back(), Key2Search)); 00522 block_iterator it = 00523 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00524 00525 assert(it != (block_->begin() + size())); 00526 00527 bid_type found_bid = it->second; 00528 00529 if (height == 2) // found_bid points to a leaf 00530 { 00531 STXXL_VERBOSE1("Searching lower bound in a leaf"); 00532 leaf_type const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)found_bid, true); 00533 assert(Leaf); 00534 const_iterator result = Leaf->lower_bound(k); 00535 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid); 00536 00537 return result; 00538 } 00539 00540 // found_bid points to a node 00541 STXXL_VERBOSE1("Searching lower bound in a node"); 00542 node_type const * Node = btree_->node_cache_.get_const_node((node_bid_type)found_bid, true); 00543 assert(Node); 00544 const_iterator result = Node->lower_bound(k, height - 1); 00545 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00546 00547 return result; 00548 } 00549 00550 iterator upper_bound(const key_type & k, unsigned height) 00551 { 00552 value_type Key2Search(k, bid_type()); 00553 assert(vcmp_(Key2Search, back())); 00554 block_iterator it = 00555 std::upper_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00556 00557 assert(it != (block_->begin() + size())); 00558 00559 bid_type found_bid = it->second; 00560 00561 if (height == 2) // found_bid points to a leaf 00562 { 00563 STXXL_VERBOSE1("Searching upper bound in a leaf"); 00564 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid, true); 00565 assert(Leaf); 00566 iterator result = Leaf->upper_bound(k); 00567 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid); 00568 00569 return result; 00570 } 00571 00572 // found_bid points to a node 00573 STXXL_VERBOSE1("Searching upper bound in a node"); 00574 node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid, true); 00575 assert(Node); 00576 iterator result = Node->upper_bound(k, height - 1); 00577 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00578 00579 return result; 00580 } 00581 00582 const_iterator upper_bound(const key_type & k, unsigned height) const 00583 { 00584 value_type Key2Search(k, bid_type()); 00585 assert(vcmp_(Key2Search, back())); 00586 block_iterator it = 00587 std::upper_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00588 00589 assert(it != (block_->begin() + size())); 00590 00591 bid_type found_bid = it->second; 00592 00593 if (height == 2) // found_bid points to a leaf 00594 { 00595 STXXL_VERBOSE1("Searching upper bound in a leaf"); 00596 leaf_type const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)found_bid, true); 00597 assert(Leaf); 00598 const_iterator result = Leaf->upper_bound(k); 00599 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid); 00600 00601 return result; 00602 } 00603 00604 // found_bid points to a node 00605 STXXL_VERBOSE1("Searching upper bound in a node"); 00606 node_type const * Node = btree_->node_cache_.get_const_node((node_bid_type)found_bid, true); 00607 assert(Node); 00608 const_iterator result = Node->upper_bound(k, height - 1); 00609 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00610 00611 return result; 00612 } 00613 00614 void fuse(const normal_node & Src) 00615 { 00616 assert(vcmp_(Src.back(), front())); 00617 const unsigned SrcSize = Src.size(); 00618 00619 block_iterator cur = block_->begin() + size() - 1; 00620 block_const_iterator begin = block_->begin(); 00621 00622 for ( ; cur >= begin; --cur) 00623 *(cur + SrcSize) = *cur; 00624 // move elements to make space for Src elements 00625 00626 // copy Src to *this leaf 00627 std::copy(Src.block_->begin(), Src.block_->begin() + SrcSize, block_->begin()); 00628 00629 block_->info.cur_size += SrcSize; 00630 } 00631 00632 00633 key_type balance(normal_node & Left) 00634 { 00635 const unsigned TotalSize = Left.size() + size(); 00636 unsigned newLeftSize = TotalSize / 2; 00637 assert(newLeftSize <= Left.max_nelements()); 00638 assert(newLeftSize >= Left.min_nelements()); 00639 unsigned newRightSize = TotalSize - newLeftSize; 00640 assert(newRightSize <= max_nelements()); 00641 assert(newRightSize >= min_nelements()); 00642 00643 assert(vcmp_(Left.back(), front()) || size() == 0); 00644 00645 if (newLeftSize < Left.size()) 00646 { 00647 const unsigned nEl2Move = Left.size() - newLeftSize; // #elements to move from Left to *this 00648 00649 block_iterator cur = block_->begin() + size() - 1; 00650 block_const_iterator begin = block_->begin(); 00651 00652 for ( ; cur >= begin; --cur) 00653 *(cur + nEl2Move) = *cur; 00654 // move elements to make space for Src elements 00655 00656 // copy Left to *this leaf 00657 std::copy(Left.block_->begin() + newLeftSize, 00658 Left.block_->begin() + Left.size(), block_->begin()); 00659 } 00660 else 00661 { 00662 assert(newRightSize < size()); 00663 00664 const unsigned nEl2Move = size() - newRightSize; // #elements to move from *this to Left 00665 00666 // copy *this to Left 00667 std::copy(block_->begin(), 00668 block_->begin() + nEl2Move, Left.block_->begin() + Left.size()); 00669 // move elements in *this 00670 std::copy(block_->begin() + nEl2Move, 00671 block_->begin() + size(), block_->begin()); 00672 } 00673 00674 block_->info.cur_size = newRightSize; // update size 00675 Left.block_->info.cur_size = newLeftSize; // update size 00676 00677 return Left.back().first; 00678 } 00679 00680 size_type erase(const key_type & k, unsigned height) 00681 { 00682 value_type Key2Search(k, bid_type()); 00683 00684 block_iterator it = 00685 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_); 00686 00687 assert(it != (block_->begin() + size())); 00688 00689 bid_type found_bid = it->second; 00690 00691 assert(size() >= 2); 00692 00693 if (height == 2) // 'found_bid' points to a leaf 00694 { 00695 STXXL_VERBOSE1("btree::normal_node Deleting key from a leaf"); 00696 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid, true); 00697 assert(Leaf); 00698 size_type result = Leaf->erase(k); 00699 btree_->leaf_cache_.unfix_node((leaf_bid_type)it->second); 00700 if (!Leaf->underflows()) 00701 return result; 00702 // no underflow or root has a special degree 1 (too few elements) 00703 00704 STXXL_VERBOSE1("btree::normal_node Fusing or rebalancing a leaf"); 00705 fuse_or_balance(it, btree_->leaf_cache_); 00706 00707 return result; 00708 } 00709 00710 // 'found_bid' points to a node 00711 STXXL_VERBOSE1("btree::normal_node Deleting key from a node"); 00712 node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid, true); 00713 assert(Node); 00714 size_type result = Node->erase(k, height - 1); 00715 btree_->node_cache_.unfix_node((node_bid_type)found_bid); 00716 if (!Node->underflows()) 00717 return result; 00718 // no underflow happened 00719 00720 STXXL_VERBOSE1("btree::normal_node Fusing or rebalancing a node"); 00721 fuse_or_balance(it, btree_->node_cache_); 00722 00723 return result; 00724 } 00725 00726 void deallocate_children(unsigned height) 00727 { 00728 if (height == 2) 00729 { 00730 // we have children leaves here 00731 block_const_iterator it = block().begin(); 00732 for ( ; it != block().begin() + size(); ++it) 00733 { 00734 // delete from leaf cache and deallocate bid 00735 btree_->leaf_cache_.delete_node((leaf_bid_type)it->second); 00736 } 00737 } 00738 else 00739 { 00740 block_const_iterator it = block().begin(); 00741 for ( ; it != block().begin() + size(); ++it) 00742 { 00743 node_type * Node = btree_->node_cache_.get_node((node_bid_type)it->second); 00744 assert(Node); 00745 Node->deallocate_children(height - 1); 00746 // delete from node cache and deallocate bid 00747 btree_->node_cache_.delete_node((node_bid_type)it->second); 00748 } 00749 } 00750 } 00751 00752 void push_back(const value_type & x) 00753 { 00754 (*this)[size()] = x; 00755 ++(block_->info.cur_size); 00756 } 00757 }; 00758 } 00759 00760 00761 __STXXL_END_NAMESPACE 00762 00763 00764 #endif /* STXXL_CONTAINERS_BTREE__NODE_H */