Stxxl  1.2.1
node.h
1 /***************************************************************************
2  * include/stxxl/bits/containers/btree/node.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2006 Roman Dementiev <dementiev@ira.uka.de>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef STXXL_CONTAINERS_BTREE__NODE_H
14 #define STXXL_CONTAINERS_BTREE__NODE_H
15 
16 #include <stxxl/bits/containers/btree/iterator.h>
17 #include <stxxl/bits/containers/btree/node_cache.h>
18 
19 
20 __STXXL_BEGIN_NAMESPACE
21 
22 namespace btree
23 {
24  template <class NodeType, class BTreeType>
25  class node_cache;
26 
27  template <class KeyType_, class KeyCmp_, unsigned RawSize_, class BTreeType>
28  class normal_node : private noncopyable
29  {
30  public:
31  typedef normal_node<KeyType_, KeyCmp_, RawSize_, BTreeType> SelfType;
32 
33  friend class node_cache<SelfType, BTreeType>;
34 
35  typedef KeyType_ key_type;
36  typedef KeyCmp_ key_compare;
37 
38  enum {
39  raw_size = RawSize_
40  };
41  typedef BID<raw_size> bid_type;
42  typedef bid_type node_bid_type;
43  typedef SelfType node_type;
44  typedef std::pair<key_type, bid_type> value_type;
45  typedef value_type & reference;
46  typedef const value_type & const_reference;
47 
48 
49  struct InfoType
50  {
51  bid_type me;
52  unsigned cur_size;
53  };
55 
56  enum {
57  nelements = block_type::size - 1,
58  max_size = nelements,
59  min_size = nelements / 2
60  };
61  typedef typename block_type::iterator block_iterator;
62  typedef typename block_type::const_iterator block_const_iterator;
63 
64  typedef BTreeType btree_type;
65  typedef typename btree_type::size_type size_type;
66  typedef typename btree_type::iterator iterator;
67  typedef typename btree_type::const_iterator const_iterator;
68 
69  typedef typename btree_type::value_type btree_value_type;
70  typedef typename btree_type::leaf_bid_type leaf_bid_type;
71  typedef typename btree_type::leaf_type leaf_type;
72 
73  typedef node_cache<normal_node, btree_type> node_cache_type;
74 
75  private:
76  struct value_compare : public std::binary_function<value_type, bid_type, bool>
77  {
78  key_compare comp;
79 
80  value_compare(key_compare c) : comp(c) { }
81 
82  bool operator () (const value_type & x, const value_type & y) const
83  {
84  return comp(x.first, y.first);
85  }
86  };
87 
88  block_type * block_;
89  btree_type * btree_;
90  key_compare cmp_;
91  value_compare vcmp_;
92 
93 
94  template <class BIDType>
95  std::pair<key_type, bid_type> insert(const std::pair<key_type, BIDType> & splitter,
96  const block_iterator & place2insert)
97  {
98  std::pair<key_type, bid_type> result(key_compare::max_value(), bid_type());
99 
100  // splitter != *place2insert
101  assert(vcmp_(*place2insert, splitter) || vcmp_(splitter, *place2insert));
102 
103  block_iterator cur = block_->begin() + size() - 1;
104  for ( ; cur >= place2insert; --cur)
105  *(cur + 1) = *cur;
106  // copy elements to make space for the new element
107 
108  *place2insert = splitter; // insert
109 
110  ++(block_->info.cur_size);
111 
112  if (size() > max_nelements()) // overflow! need to split
113  {
114  STXXL_VERBOSE1("btree::normal_node::insert overflow happened, splitting");
115 
116  bid_type NewBid;
117  btree_->node_cache_.get_new_node(NewBid); // new (left) node
118  normal_node * NewNode = btree_->node_cache_.get_node(NewBid, true);
119  assert(NewNode);
120 
121  const unsigned end_of_smaller_part = size() / 2;
122 
123  result.first = ((*block_)[end_of_smaller_part - 1]).first;
124  result.second = NewBid;
125 
126 
127  const unsigned old_size = size();
128  // copy the smaller part
129  std::copy(block_->begin(), block_->begin() + end_of_smaller_part, NewNode->block_->begin());
130  NewNode->block_->info.cur_size = end_of_smaller_part;
131  // copy the larger part
132  std::copy(block_->begin() + end_of_smaller_part,
133  block_->begin() + old_size, block_->begin());
134  block_->info.cur_size = old_size - end_of_smaller_part;
135  assert(size() + NewNode->size() == old_size);
136 
137  btree_->node_cache_.unfix_node(NewBid);
138 
139  STXXL_VERBOSE1("btree::normal_node split leaf " << this
140  << " splitter: " << result.first);
141  }
142 
143  return result;
144  }
145 
146  template <class CacheType>
147  void fuse_or_balance(block_iterator UIt, CacheType & cache_)
148  {
149  typedef typename CacheType::node_type local_node_type;
150  typedef typename local_node_type::bid_type local_bid_type;
151 
152  block_iterator leftIt, rightIt;
153  if (UIt == (block_->begin() + size() - 1)) // UIt is the last entry in the root
154  {
155  assert(UIt != block_->begin());
156  rightIt = UIt;
157  leftIt = --UIt;
158  }
159  else
160  {
161  leftIt = UIt;
162  rightIt = ++UIt;
163  assert(rightIt != (block_->begin() + size()));
164  }
165 
166  // now fuse or balance nodes pointed by leftIt and rightIt
167  local_bid_type LeftBid = (local_bid_type)leftIt->second;
168  local_bid_type RightBid = (local_bid_type)rightIt->second;
169  local_node_type * LeftNode = cache_.get_node(LeftBid, true);
170  local_node_type * RightNode = cache_.get_node(RightBid, true);
171 
172  const unsigned TotalSize = LeftNode->size() + RightNode->size();
173  if (TotalSize <= RightNode->max_nelements())
174  {
175  // fuse
176  RightNode->fuse(*LeftNode); // add the content of LeftNode to RightNode
177 
178  cache_.unfix_node(RightBid);
179  cache_.delete_node(LeftBid); // 'delete_node' unfixes LeftBid also
180 
181  std::copy(leftIt + 1, block_->begin() + size(), leftIt); // delete left BID from the root
182  --(block_->info.cur_size);
183  }
184  else
185  {
186  // balance
187 
188  key_type NewSplitter = RightNode->balance(*LeftNode);
189 
190 
191  leftIt->first = NewSplitter; // change key
192  assert(vcmp_(*leftIt, *rightIt));
193 
194  cache_.unfix_node(LeftBid);
195  cache_.unfix_node(RightBid);
196  }
197  }
198 
199  public:
200  virtual ~normal_node()
201  {
202  delete block_;
203  }
204 
205  normal_node(btree_type * btree__,
206  key_compare cmp) :
207  block_(new block_type),
208  btree_(btree__),
209  cmp_(cmp),
210  vcmp_(cmp)
211  {
212  assert(min_nelements() >= 2);
213  assert(2 * min_nelements() - 1 <= max_nelements());
214  assert(max_nelements() <= nelements);
215  assert(unsigned(block_type::size) >= nelements + 1); // extra space for an overflow
216  }
217 
218  block_type & block()
219  {
220  return *block_;
221  }
222 
223  bool overflows() const { return block_->info.cur_size > max_nelements(); }
224  bool underflows() const { return block_->info.cur_size < min_nelements(); }
225 
226  unsigned max_nelements() const { return max_size; }
227  unsigned min_nelements() const { return min_size; }
228 
229  /*
230  template <class InputIterator>
231  normal_node(InputIterator begin_, InputIterator end_,
232  btree_type * btree__,
233  key_compare cmp):
234  block_(new block_type),
235  btree_(btree__),
236  cmp_(cmp),
237  vcmp_(cmp)
238  {
239  assert(min_nelements() >=2);
240  assert(2*min_nelements() - 1 <= max_nelements());
241  assert(max_nelements() <= nelements);
242  assert(unsigned(block_type::size) >= nelements +1); // extra space for an overflow
243 
244  unsigned new_size = end_ - begin_;
245  assert(new_size <= max_nelements());
246  assert(new_size >= min_nelements());
247 
248  std::copy(begin_,end_,block_->begin());
249  assert(stxxl::is_sorted(block_->begin(),block_->begin() + new_size, vcmp_));
250  block_->info.cur_size = new_size;
251  }*/
252 
253  unsigned size() const
254  {
255  return block_->info.cur_size;
256  }
257 
258  bid_type my_bid() const
259  {
260  return block_->info.me;
261  }
262 
263  void save()
264  {
265  request_ptr req = block_->write(my_bid());
266  req->wait();
267  }
268 
269  request_ptr load(const bid_type & bid)
270  {
271  request_ptr req = block_->read(bid);
272  req->wait();
273  assert(bid == my_bid());
274  return req;
275  }
276 
277  request_ptr prefetch(const bid_type & bid)
278  {
279  return block_->read(bid);
280  }
281 
282  void init(const bid_type & my_bid_)
283  {
284  block_->info.me = my_bid_;
285  block_->info.cur_size = 0;
286  }
287 
288  reference operator [] (int i)
289  {
290  return (*block_)[i];
291  }
292 
293  const_reference operator [] (int i) const
294  {
295  return (*block_)[i];
296  }
297 
298  reference back()
299  {
300  return (*block_)[size() - 1];
301  }
302 
303  reference front()
304  {
305  return *(block_->begin());
306  }
307 
308  const_reference back() const
309  {
310  return (*block_)[size() - 1];
311  }
312 
313  const_reference front() const
314  {
315  return *(block_->begin());
316  }
317 
318 
319  std::pair<iterator, bool> insert(
320  const btree_value_type & x,
321  unsigned height,
322  std::pair<key_type, bid_type> & splitter)
323  {
324  assert(size() <= max_nelements());
325  splitter.first = key_compare::max_value();
326 
327  value_type Key2Search(x.first, bid_type());
328  block_iterator it =
329  std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
330 
331  assert(it != (block_->begin() + size()));
332 
333  bid_type found_bid = it->second;
334 
335  if (height == 2) // found_bid points to a leaf
336  {
337  STXXL_VERBOSE1("btree::normal_node Inserting new value into a leaf");
338  leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)it->second, true);
339  assert(Leaf);
340  std::pair<key_type, leaf_bid_type> BotSplitter;
341  std::pair<iterator, bool> result = Leaf->insert(x, BotSplitter);
342  btree_->leaf_cache_.unfix_node((leaf_bid_type)it->second);
343  //if(key_compare::max_value() == BotSplitter.first)
344  if (!(cmp_(key_compare::max_value(), BotSplitter.first) ||
345  cmp_(BotSplitter.first, key_compare::max_value())))
346  return result;
347  // no overflow/splitting happened
348 
349  STXXL_VERBOSE1("btree::normal_node Inserting new value in *this");
350 
351  splitter = insert(BotSplitter, it);
352 
353  return result;
354  }
355  else
356  { // found_bid points to a node
357  STXXL_VERBOSE1("btree::normal_node Inserting new value into a node");
358  node_type * Node = btree_->node_cache_.get_node((node_bid_type)it->second, true);
359  assert(Node);
360  std::pair<key_type, node_bid_type> BotSplitter;
361  std::pair<iterator, bool> result = Node->insert(x, height - 1, BotSplitter);
362  btree_->node_cache_.unfix_node((node_bid_type)it->second);
363  //if(key_compare::max_value() == BotSplitter.first)
364  if (!(cmp_(key_compare::max_value(), BotSplitter.first) ||
365  cmp_(BotSplitter.first, key_compare::max_value())))
366  return result;
367  // no overflow/splitting happened
368 
369  STXXL_VERBOSE1("btree::normal_node Inserting new value in *this");
370 
371  splitter = insert(BotSplitter, it);
372 
373  return result;
374  }
375  }
376 
377  iterator begin(unsigned height)
378  {
379  bid_type FirstBid = block_->begin()->second;
380  if (height == 2) // FirstBid points to a leaf
381  {
382  assert(size() > 1);
383  STXXL_VERBOSE1("btree::node retrieveing begin() from the first leaf");
384  leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)FirstBid);
385  assert(Leaf);
386  return Leaf->begin();
387  }
388  else
389  { // FirstBid points to a node
390  STXXL_VERBOSE1("btree: retrieveing begin() from the first node");
391  node_type * Node = btree_->node_cache_.get_node((node_bid_type)FirstBid, true);
392  assert(Node);
393  iterator result = Node->begin(height - 1);
394  btree_->node_cache_.unfix_node((node_bid_type)FirstBid);
395  return result;
396  }
397  }
398 
399  const_iterator begin(unsigned height) const
400  {
401  bid_type FirstBid = block_->begin()->second;
402  if (height == 2) // FirstBid points to a leaf
403  {
404  assert(size() > 1);
405  STXXL_VERBOSE1("btree::node retrieveing begin() from the first leaf");
406  leaf_type const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)FirstBid);
407  assert(Leaf);
408  return Leaf->begin();
409  }
410  else
411  { // FirstBid points to a node
412  STXXL_VERBOSE1("btree: retrieveing begin() from the first node");
413  node_type const * Node = btree_->node_cache_.get_const_node((node_bid_type)FirstBid, true);
414  assert(Node);
415  const_iterator result = Node->begin(height - 1);
416  btree_->node_cache_.unfix_node((node_bid_type)FirstBid);
417  return result;
418  }
419  }
420 
421  iterator find(const key_type & k, unsigned height)
422  {
423  value_type Key2Search(k, bid_type());
424 
425  block_iterator it =
426  std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
427 
428  assert(it != (block_->begin() + size()));
429 
430  bid_type found_bid = it->second;
431 
432  if (height == 2) // found_bid points to a leaf
433  {
434  STXXL_VERBOSE1("Searching in a leaf");
435  leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid, true);
436  assert(Leaf);
437  iterator result = Leaf->find(k);
438  btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid);
439 
440  return result;
441  }
442 
443  // found_bid points to a node
444  STXXL_VERBOSE1("Searching in a node");
445  node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid, true);
446  assert(Node);
447  iterator result = Node->find(k, height - 1);
448  btree_->node_cache_.unfix_node((node_bid_type)found_bid);
449 
450  return result;
451  }
452 
453  const_iterator find(const key_type & k, unsigned height) const
454  {
455  value_type Key2Search(k, bid_type());
456 
457  block_iterator it =
458  std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
459 
460  assert(it != (block_->begin() + size()));
461 
462  bid_type found_bid = it->second;
463 
464  if (height == 2) // found_bid points to a leaf
465  {
466  STXXL_VERBOSE1("Searching in a leaf");
467  leaf_type const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)found_bid, true);
468  assert(Leaf);
469  const_iterator result = Leaf->find(k);
470  btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid);
471 
472  return result;
473  }
474 
475  // found_bid points to a node
476  STXXL_VERBOSE1("Searching in a node");
477  node_type const * Node = btree_->node_cache_.get_const_node((node_bid_type)found_bid, true);
478  assert(Node);
479  const_iterator result = Node->find(k, height - 1);
480  btree_->node_cache_.unfix_node((node_bid_type)found_bid);
481 
482  return result;
483  }
484 
485  iterator lower_bound(const key_type & k, unsigned height)
486  {
487  value_type Key2Search(k, bid_type());
488  assert(!vcmp_(back(), Key2Search));
489  block_iterator it =
490  std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
491 
492  assert(it != (block_->begin() + size()));
493 
494  bid_type found_bid = it->second;
495 
496  if (height == 2) // found_bid points to a leaf
497  {
498  STXXL_VERBOSE1("Searching lower bound in a leaf");
499  leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid, true);
500  assert(Leaf);
501  iterator result = Leaf->lower_bound(k);
502  btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid);
503 
504  return result;
505  }
506 
507  // found_bid points to a node
508  STXXL_VERBOSE1("Searching lower bound in a node");
509  node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid, true);
510  assert(Node);
511  iterator result = Node->lower_bound(k, height - 1);
512  btree_->node_cache_.unfix_node((node_bid_type)found_bid);
513 
514  return result;
515  }
516 
517  const_iterator lower_bound(const key_type & k, unsigned height) const
518  {
519  value_type Key2Search(k, bid_type());
520  assert(!vcmp_(back(), Key2Search));
521  block_iterator it =
522  std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
523 
524  assert(it != (block_->begin() + size()));
525 
526  bid_type found_bid = it->second;
527 
528  if (height == 2) // found_bid points to a leaf
529  {
530  STXXL_VERBOSE1("Searching lower bound in a leaf");
531  leaf_type const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)found_bid, true);
532  assert(Leaf);
533  const_iterator result = Leaf->lower_bound(k);
534  btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid);
535 
536  return result;
537  }
538 
539  // found_bid points to a node
540  STXXL_VERBOSE1("Searching lower bound in a node");
541  node_type const * Node = btree_->node_cache_.get_const_node((node_bid_type)found_bid, true);
542  assert(Node);
543  const_iterator result = Node->lower_bound(k, height - 1);
544  btree_->node_cache_.unfix_node((node_bid_type)found_bid);
545 
546  return result;
547  }
548 
549  iterator upper_bound(const key_type & k, unsigned height)
550  {
551  value_type Key2Search(k, bid_type());
552  assert(vcmp_(Key2Search, back()));
553  block_iterator it =
554  std::upper_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
555 
556  assert(it != (block_->begin() + size()));
557 
558  bid_type found_bid = it->second;
559 
560  if (height == 2) // found_bid points to a leaf
561  {
562  STXXL_VERBOSE1("Searching upper bound in a leaf");
563  leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid, true);
564  assert(Leaf);
565  iterator result = Leaf->upper_bound(k);
566  btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid);
567 
568  return result;
569  }
570 
571  // found_bid points to a node
572  STXXL_VERBOSE1("Searching upper bound in a node");
573  node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid, true);
574  assert(Node);
575  iterator result = Node->upper_bound(k, height - 1);
576  btree_->node_cache_.unfix_node((node_bid_type)found_bid);
577 
578  return result;
579  }
580 
581  const_iterator upper_bound(const key_type & k, unsigned height) const
582  {
583  value_type Key2Search(k, bid_type());
584  assert(vcmp_(Key2Search, back()));
585  block_iterator it =
586  std::upper_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
587 
588  assert(it != (block_->begin() + size()));
589 
590  bid_type found_bid = it->second;
591 
592  if (height == 2) // found_bid points to a leaf
593  {
594  STXXL_VERBOSE1("Searching upper bound in a leaf");
595  leaf_type const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)found_bid, true);
596  assert(Leaf);
597  const_iterator result = Leaf->upper_bound(k);
598  btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid);
599 
600  return result;
601  }
602 
603  // found_bid points to a node
604  STXXL_VERBOSE1("Searching upper bound in a node");
605  node_type const * Node = btree_->node_cache_.get_const_node((node_bid_type)found_bid, true);
606  assert(Node);
607  const_iterator result = Node->upper_bound(k, height - 1);
608  btree_->node_cache_.unfix_node((node_bid_type)found_bid);
609 
610  return result;
611  }
612 
613  void fuse(const normal_node & Src)
614  {
615  assert(vcmp_(Src.back(), front()));
616  const unsigned SrcSize = Src.size();
617 
618  block_iterator cur = block_->begin() + size() - 1;
619  block_const_iterator begin = block_->begin();
620 
621  for ( ; cur >= begin; --cur)
622  *(cur + SrcSize) = *cur;
623  // move elements to make space for Src elements
624 
625  // copy Src to *this leaf
626  std::copy(Src.block_->begin(), Src.block_->begin() + SrcSize, block_->begin());
627 
628  block_->info.cur_size += SrcSize;
629  }
630 
631 
632  key_type balance(normal_node & Left)
633  {
634  const unsigned TotalSize = Left.size() + size();
635  unsigned newLeftSize = TotalSize / 2;
636  assert(newLeftSize <= Left.max_nelements());
637  assert(newLeftSize >= Left.min_nelements());
638  unsigned newRightSize = TotalSize - newLeftSize;
639  assert(newRightSize <= max_nelements());
640  assert(newRightSize >= min_nelements());
641 
642  assert(vcmp_(Left.back(), front()) || size() == 0);
643 
644  if (newLeftSize < Left.size())
645  {
646  const unsigned nEl2Move = Left.size() - newLeftSize; // #elements to move from Left to *this
647 
648  block_iterator cur = block_->begin() + size() - 1;
649  block_const_iterator begin = block_->begin();
650 
651  for ( ; cur >= begin; --cur)
652  *(cur + nEl2Move) = *cur;
653  // move elements to make space for Src elements
654 
655  // copy Left to *this leaf
656  std::copy(Left.block_->begin() + newLeftSize,
657  Left.block_->begin() + Left.size(), block_->begin());
658  }
659  else
660  {
661  assert(newRightSize < size());
662 
663  const unsigned nEl2Move = size() - newRightSize; // #elements to move from *this to Left
664 
665  // copy *this to Left
666  std::copy(block_->begin(),
667  block_->begin() + nEl2Move, Left.block_->begin() + Left.size());
668  // move elements in *this
669  std::copy(block_->begin() + nEl2Move,
670  block_->begin() + size(), block_->begin());
671  }
672 
673  block_->info.cur_size = newRightSize; // update size
674  Left.block_->info.cur_size = newLeftSize; // update size
675 
676  return Left.back().first;
677  }
678 
679  size_type erase(const key_type & k, unsigned height)
680  {
681  value_type Key2Search(k, bid_type());
682 
683  block_iterator it =
684  std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
685 
686  assert(it != (block_->begin() + size()));
687 
688  bid_type found_bid = it->second;
689 
690  assert(size() >= 2);
691 
692  if (height == 2) // 'found_bid' points to a leaf
693  {
694  STXXL_VERBOSE1("btree::normal_node Deleting key from a leaf");
695  leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid, true);
696  assert(Leaf);
697  size_type result = Leaf->erase(k);
698  btree_->leaf_cache_.unfix_node((leaf_bid_type)it->second);
699  if (!Leaf->underflows())
700  return result;
701  // no underflow or root has a special degree 1 (too few elements)
702 
703  STXXL_VERBOSE1("btree::normal_node Fusing or rebalancing a leaf");
704  fuse_or_balance(it, btree_->leaf_cache_);
705 
706  return result;
707  }
708 
709  // 'found_bid' points to a node
710  STXXL_VERBOSE1("btree::normal_node Deleting key from a node");
711  node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid, true);
712  assert(Node);
713  size_type result = Node->erase(k, height - 1);
714  btree_->node_cache_.unfix_node((node_bid_type)found_bid);
715  if (!Node->underflows())
716  return result;
717  // no underflow happened
718 
719  STXXL_VERBOSE1("btree::normal_node Fusing or rebalancing a node");
720  fuse_or_balance(it, btree_->node_cache_);
721 
722  return result;
723  }
724 
725  void deallocate_children(unsigned height)
726  {
727  if (height == 2)
728  {
729  // we have children leaves here
730  block_const_iterator it = block().begin();
731  for ( ; it != block().begin() + size(); ++it)
732  {
733  // delete from leaf cache and deallocate bid
734  btree_->leaf_cache_.delete_node((leaf_bid_type)it->second);
735  }
736  }
737  else
738  {
739  block_const_iterator it = block().begin();
740  for ( ; it != block().begin() + size(); ++it)
741  {
742  node_type * Node = btree_->node_cache_.get_node((node_bid_type)it->second);
743  assert(Node);
744  Node->deallocate_children(height - 1);
745  // delete from node cache and deallocate bid
746  btree_->node_cache_.delete_node((node_bid_type)it->second);
747  }
748  }
749  }
750 
751  void push_back(const value_type & x)
752  {
753  (*this)[size()] = x;
754  ++(block_->info.cur_size);
755  }
756  };
757 }
758 
759 
760 __STXXL_END_NAMESPACE
761 
762 
763 #endif /* STXXL_CONTAINERS_BTREE__NODE_H */