00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
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
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
00107
00108 *place2insert = splitter;
00109
00110 ++(block_->info.cur_size);
00111
00112 if (size() > max_nelements())
00113 {
00114 STXXL_VERBOSE1("btree::normal_node::insert overflow happened, splitting");
00115
00116 bid_type NewBid;
00117 btree_->node_cache_.get_new_node(NewBid);
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
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
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))
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
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
00176 RightNode->fuse(*LeftNode);
00177
00178 cache_.unfix_node(RightBid);
00179 cache_.delete_node(LeftBid);
00180
00181 std::copy(leftIt + 1, block_->begin() + size(), leftIt);
00182 --(block_->info.cur_size);
00183 }
00184 else
00185 {
00186
00187
00188 key_type NewSplitter = RightNode->balance(*LeftNode);
00189
00190
00191 leftIt->first = NewSplitter;
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);
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
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
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)
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
00344 if (!(cmp_(key_compare::max_value(), BotSplitter.first) ||
00345 cmp_(BotSplitter.first, key_compare::max_value())))
00346 return result;
00347
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 {
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
00364 if (!(cmp_(key_compare::max_value(), BotSplitter.first) ||
00365 cmp_(BotSplitter.first, key_compare::max_value())))
00366 return result;
00367
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)
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 {
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)
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 {
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)
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
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)
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
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)
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
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)
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
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)
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
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)
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
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
00624
00625
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;
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
00654
00655
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;
00664
00665
00666 std::copy(block_->begin(),
00667 block_->begin() + nEl2Move, Left.block_->begin() + Left.size());
00668
00669 std::copy(block_->begin() + nEl2Move,
00670 block_->begin() + size(), block_->begin());
00671 }
00672
00673 block_->info.cur_size = newRightSize;
00674 Left.block_->info.cur_size = newLeftSize;
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)
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
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
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
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
00730 block_const_iterator it = block().begin();
00731 for ( ; it != block().begin() + size(); ++it)
00732 {
00733
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
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