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