STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
leaf.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/btree/leaf.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_LEAF_HEADER
14 #define STXXL_CONTAINERS_BTREE_LEAF_HEADER
15 
18 
20 
21 namespace btree {
22 
23 template <class NodeType, class BTreeType>
24 class node_cache;
25 
26 template <class KeyType, class DataType, class KeyCmp, unsigned RawSize, class BTreeType>
27 class normal_leaf : private noncopyable
28 {
29 public:
31 
32  friend class node_cache<self_type, BTreeType>;
33 
34  typedef KeyType key_type;
35  typedef DataType data_type;
36  typedef KeyCmp key_compare;
37  typedef std::pair<key_type, data_type> value_type;
39  typedef const value_type& const_reference;
40 
41  enum {
42  raw_size = RawSize
43  };
44 
46 
48  {
49  bid_type me, pred, succ;
50  unsigned cur_size;
51  };
52 
54  enum {
55  nelements = block_type::size - 1,
56  max_size = nelements,
57  min_size = nelements / 2
58  };
59 
60  typedef BTreeType btree_type;
61  typedef typename btree_type::size_type size_type;
65 
67 
68 public:
69  struct value_compare : public std::binary_function<value_type, value_type, bool>
70  {
72 
73  value_compare(key_compare c) : comp(c) { }
74 
75  bool operator () (const value_type& x, const value_type& y) const
76  {
77  return comp(x.first, y.first);
78  }
79  };
80 
81 private:
84 
87 
88  void split(std::pair<key_type, bid_type>& splitter)
89  {
90  bid_type new_bid;
91  m_btree->m_leaf_cache.get_new_node(new_bid); // new (left) leaf
92  normal_leaf* new_leaf = m_btree->m_leaf_cache.get_node(new_bid, true);
93  assert(new_leaf);
94 
95  // update links
96  new_leaf->succ() = my_bid();
97  normal_leaf* pred_leaf = NULL;
98  if (pred().valid())
99  {
100  new_leaf->pred() = pred();
101  pred_leaf = m_btree->m_leaf_cache.get_node(pred());
102  assert(pred_leaf);
103  assert(m_vcmp(pred_leaf->back(), front()));
104  pred_leaf->succ() = new_bid;
105  }
106  pred() = new_bid;
107 
108  typedef std::vector<iterator_base*> iterators2fix_type;
109  iterators2fix_type iterators2fix;
110  m_btree->m_iterator_map.find(my_bid(), 0, size(), iterators2fix);
111 
112  const unsigned end_of_smaller_part = size() / 2;
113 
114  splitter.first = ((*m_block)[end_of_smaller_part - 1]).first;
115  splitter.second = new_bid;
116 
117  const unsigned old_size = size();
118  // copy the smaller part
119  std::copy(m_block->begin(), m_block->begin() + end_of_smaller_part,
120  new_leaf->m_block->begin());
121  new_leaf->m_block->info.cur_size = end_of_smaller_part;
122  // copy the larger part
123  std::copy(m_block->begin() + end_of_smaller_part,
124  m_block->begin() + old_size, m_block->begin());
125  m_block->info.cur_size = old_size - end_of_smaller_part;
126  assert(size() + new_leaf->size() == old_size);
127 
128  // fix iterators
129  for (typename iterators2fix_type::iterator it2fix = iterators2fix.begin();
130  it2fix != iterators2fix.end(); ++it2fix)
131  {
132  m_btree->m_iterator_map.unregister_iterator(**it2fix);
133 
134  if ((*it2fix)->pos < end_of_smaller_part) // belongs to the smaller part
135  (*it2fix)->bid = new_bid;
136 
137  else
138  (*it2fix)->pos -= end_of_smaller_part;
139 
140  m_btree->m_iterator_map.register_iterator(**it2fix);
141  }
142 
143  STXXL_VERBOSE1("btree::normal_leaf split leaf " << this
144  << " splitter: " << splitter.first);
145 
146 #if STXXL_VERBOSE_LEVEL >= 1
147  if (pred_leaf)
148  {
149  STXXL_VERBOSE1("btree::normal_leaf pred_part.smallest = " << pred_leaf->front().first);
150  STXXL_VERBOSE1("btree::normal_leaf pred_part.largest = " << pred_leaf->back().first);
151  }
152 #endif
153  STXXL_VERBOSE1("btree::normal_leaf smaller_part.smallest = " << new_leaf->front().first);
154  STXXL_VERBOSE1("btree::normal_leaf smaller_part.largest = " << new_leaf->back().first);
155  STXXL_VERBOSE1("btree::normal_leaf larger_part.smallest = " << front().first);
156  STXXL_VERBOSE1("btree::normal_leaf larger_part.largest = " << back().first);
157 
158  m_btree->m_leaf_cache.unfix_node(new_bid);
159  }
160 
161 public:
162  virtual ~normal_leaf()
163  {
164  delete m_block;
165  }
166 
168  key_compare cmp)
169  : m_block(new block_type),
170  m_btree(btree),
171  m_cmp(cmp),
172  m_vcmp(cmp)
173  {
174  assert(min_nelements() >= 2);
175  assert(2 * min_nelements() - 1 <= max_nelements());
176  assert(max_nelements() <= nelements);
177  assert(unsigned(block_type::size) >= nelements + 1); // extra space for an overflow
178  }
179 
180  bool overflows() const { return m_block->info.cur_size > max_nelements(); }
181  bool underflows() const { return m_block->info.cur_size < min_nelements(); }
182 
183  static unsigned max_nelements() { return max_size; }
184  static unsigned min_nelements() { return min_size; }
185 
187  {
188  return m_block->info.succ;
189  }
191  {
192  return m_block->info.pred;
193  }
194 
195  const bid_type & succ() const
196  {
197  return m_block->info.succ;
198  }
199  const bid_type & pred() const
200  {
201  return m_block->info.pred;
202  }
203 
204  /*
205  template <class InputIterator>
206  normal_leaf(InputIterator begin_, InputIterator end_,
207  btree_type * btree,
208  key_compare cmp):
209  m_block(new block_type),
210  m_btree(btree),
211  m_cmp(cmp),
212  m_vcmp(cmp)
213  {
214  assert(min_nelements() >=2);
215  assert(2*min_nelements() - 1 <= max_nelements());
216  assert(max_nelements() <= nelements);
217  assert(unsigned(block_type::size) >= nelements +1); // extra space for an overflow element
218 
219  unsigned new_size = end_ - begin_;
220  assert(new_size <= max_nelements());
221  assert(new_size >= min_nelements());
222 
223  std::copy(begin_,end_,m_block->begin());
224  assert(stxxl::is_sorted(m_block->begin(),m_block->begin() + new_size, m_vcmp));
225  m_block->info.cur_size = new_size;
226  }*/
227 
228  unsigned size() const
229  {
230  return m_block->info.cur_size;
231  }
232 
233  const bid_type & my_bid() const
234  {
235  return m_block->info.me;
236  }
237 
238  void save()
239  {
240  request_ptr req = m_block->write(my_bid());
241  req->wait();
242  }
243 
245  {
246  request_ptr req = m_block->read(bid);
247  req->wait();
248  assert(bid == my_bid());
249  return req;
250  }
251 
253  {
254  return m_block->read(bid);
255  }
256 
257  void init(const bid_type& my_bid_)
258  {
259  m_block->info.me = my_bid_;
260  m_block->info.succ = bid_type();
261  m_block->info.pred = bid_type();
262  m_block->info.cur_size = 0;
263  }
264 
265  reference operator [] (unsigned_type i)
266  {
267  return (*m_block)[i];
268  }
269 
270  const_reference operator [] (unsigned_type i) const
271  {
272  return (*m_block)[i];
273  }
274 
276  {
277  return (*m_block)[size() - 1];
278  }
279 
281  {
282  return *(m_block->begin());
283  }
284 
286  {
287  return (*m_block)[size() - 1];
288  }
289 
291  {
292  return *(m_block->begin());
293  }
294 
295  void dump()
296  {
297  STXXL_VERBOSE2("Dump of leaf " << this);
298  for (unsigned i = 0; i < size(); ++i)
299  STXXL_VERBOSE2((*this)[i].first << " " << (*this)[i].second);
300  }
301 
302  std::pair<iterator, bool> insert(
303  const value_type& x,
304  std::pair<key_type, bid_type>& splitter)
305  {
306  assert(size() <= max_nelements());
307  splitter.first = key_compare::max_value();
308 
309  typename block_type::iterator it =
310  std::lower_bound(m_block->begin(), m_block->begin() + size(), x, m_vcmp);
311 
312  if (!(m_vcmp(*it, x) || m_vcmp(x, *it)) && it != (m_block->begin() + size())) // *it == x
313  {
314  // already exists
315  return std::pair<iterator, bool>(
316  iterator(m_btree, my_bid(), unsigned(it - m_block->begin())),
317  false);
318  }
319 
320  typename block_type::iterator cur = m_block->begin() + size() - 1;
321 
322  for ( ; cur >= it; --cur)
323  *(cur + 1) = *cur;
324  // move elements to make space for the new element
325 
326  *it = x;
327 
328  std::vector<iterator_base*> iterators2fix;
329  m_btree->m_iterator_map.find(my_bid(), unsigned(it - m_block->begin()), size(), iterators2fix);
330  typename std::vector<iterator_base*>::iterator it2fix = iterators2fix.begin();
331  for ( ; it2fix != iterators2fix.end(); ++it2fix)
332  {
333  m_btree->m_iterator_map.unregister_iterator(**it2fix);
334  ++((*it2fix)->pos); // fixing iterators
335  m_btree->m_iterator_map.register_iterator(**it2fix);
336  }
337 
338  ++(m_block->info.cur_size);
339 
340  std::pair<iterator, bool> result(iterator(m_btree, my_bid(), unsigned(it - m_block->begin())), true);
341 
342  if (size() <= max_nelements())
343  {
344  // no overflow
345  dump();
346  return result;
347  }
348 
349  // overflow
350 
351  split(splitter);
352 
353  return result;
354  }
355 
357  {
358  return iterator(m_btree, my_bid(), 0);
359  }
360 
362  {
363  return const_iterator(m_btree, my_bid(), 0);
364  }
365 
367  {
368  return iterator(m_btree, my_bid(), size());
369  }
370 
372  {
373  assert(it.bid == my_bid());
374  assert(it.pos != size());
375 
376  m_btree->m_iterator_map.unregister_iterator(it);
377 
378  ++(it.pos);
379  if (it.pos == size() && succ().valid())
380  {
381  // run to the end of the leaf
382  STXXL_VERBOSE1("btree::normal_leaf jumping to the next block");
383  it.pos = 0;
384  it.bid = succ();
385  }
386  // increment of pos from 0 to 1
387  else if (it.pos == 1 && m_btree->m_prefetching_enabled)
388  {
389  // prefetch the succ leaf
390  if (succ().valid())
391  m_btree->m_leaf_cache.prefetch_node(succ());
392  }
393  m_btree->m_iterator_map.register_iterator(it);
394  }
395 
397  {
398  assert(it.bid == my_bid());
399 
400  m_btree->m_iterator_map.unregister_iterator(it);
401 
402  if (it.pos == 0)
403  {
404  assert(pred().valid());
405 
406  it.bid = pred();
407  normal_leaf const* pred_leaf = m_btree->m_leaf_cache.get_const_node(pred(), true);
408  assert(pred_leaf);
409  it.pos = pred_leaf->size() - 1;
410 
411  // prefetch the pred leaf of pred_leaf
412  if (m_btree->m_prefetching_enabled && pred_leaf->pred().valid())
413  m_btree->m_leaf_cache.prefetch_node(pred_leaf->pred());
414 
415  m_btree->m_leaf_cache.unfix_node(pred());
416  }
417  else
418  --it.pos;
419 
420  m_btree->m_iterator_map.register_iterator(it);
421  }
422 
424  {
425  value_type search_val(k, data_type());
426  typename block_type::iterator lb =
427  std::lower_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
428  if (lb == m_block->begin() + size() || lb->first != k)
429  return m_btree->end();
430 
431  return iterator(m_btree, my_bid(), unsigned(lb - m_block->begin()));
432  }
433 
434  const_iterator find(const key_type& k) const
435  {
436  value_type search_val(k, data_type());
437  typename block_type::iterator lb =
438  std::lower_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
439  if (lb == m_block->begin() + size() || lb->first != k)
440  return m_btree->end();
441 
442  return const_iterator(m_btree, my_bid(), unsigned(lb - m_block->begin()));
443  }
444 
446  {
447  value_type search_val(k, data_type());
448 
449  typename block_type::iterator lb =
450  std::lower_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
451 
452  // lower_bound is in the succ block
453  if (lb == m_block->begin() + size() && succ().valid())
454  {
455  return iterator(m_btree, succ(), 0);
456  }
457 
458  return iterator(m_btree, my_bid(), unsigned(lb - m_block->begin()));
459  }
460 
462  {
463  value_type search_val(k, data_type());
464  typename block_type::iterator lb =
465  std::lower_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
466 
467  // lower_bound is in the succ block
468  if (lb == m_block->begin() + size() && succ().valid())
469  {
470  return iterator(m_btree, succ(), 0);
471  }
472 
473  return const_iterator(m_btree, my_bid(), unsigned(lb - m_block->begin()));
474  }
475 
477  {
478  value_type search_val(k, data_type());
479  typename block_type::iterator lb =
480  std::upper_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
481 
482  // upper_bound is in the succ block
483  if (lb == m_block->begin() + size() && succ().valid())
484  {
485  return iterator(m_btree, succ(), 0);
486  }
487 
488  return iterator(m_btree, my_bid(), unsigned(lb - m_block->begin()));
489  }
490 
492  {
493  value_type search_val(k, data_type());
494  typename block_type::iterator lb =
495  std::upper_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
496 
497  // upper_bound is in the succ block
498  if (lb == m_block->begin() + size() && succ().valid())
499  {
500  return const_iterator(m_btree, succ(), 0);
501  }
502 
503  return const_iterator(m_btree, my_bid(), unsigned(lb - m_block->begin()));
504  }
505 
507  {
508  value_type search_val(k, data_type());
509  typename block_type::iterator it =
510  std::lower_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
511 
512  if (it == m_block->begin() + size() || it->first != k)
513  return 0;
514  // no such element
515 
516  // move elements one position left
517  std::copy(it + 1, m_block->begin() + size(), it);
518 
519  std::vector<iterator_base*> iterators2fix;
520  m_btree->m_iterator_map.find(my_bid(), unsigned(it + 1 - m_block->begin()), size(), iterators2fix);
521  typename std::vector<iterator_base*>::iterator it2fix = iterators2fix.begin();
522  for ( ; it2fix != iterators2fix.end(); ++it2fix)
523  {
524  STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) << " (pos--)");
525  m_btree->m_iterator_map.unregister_iterator(**it2fix);
526  --((*it2fix)->pos); // fixing iterators
527  m_btree->m_iterator_map.register_iterator(**it2fix);
528  }
529 
530  --(m_block->info.cur_size);
531 
532  return 1;
533  }
534 
535  void fuse(const normal_leaf& src)
536  {
537  STXXL_VERBOSE1("btree::normal_leaf Fusing");
538  assert(m_vcmp(src.back(), front()));
539  const unsigned src_size = src.size();
540 
541  typename block_type::iterator cur = m_block->begin() + size() - 1;
542  typename block_type::const_iterator begin = m_block->begin();
543 
544  for ( ; cur >= begin; --cur)
545  *(cur + src_size) = *cur;
546  // move elements to make space for Src elements
547 
548  // copy Src to *this leaf
549  std::copy(src.m_block->begin(), src.m_block->begin() + src_size, m_block->begin());
550 
551  std::vector<iterator_base*> iterators2fix;
552  m_btree->m_iterator_map.find(my_bid(), 0, size(), iterators2fix);
553  typename std::vector<iterator_base*>::iterator it2fix = iterators2fix.begin();
554  for ( ; it2fix != iterators2fix.end(); ++it2fix)
555  {
556  STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
557  " (pos+" << src_size << ")");
558  m_btree->m_iterator_map.unregister_iterator(**it2fix);
559  ((*it2fix)->pos) += src_size; // fixing iterators
560  m_btree->m_iterator_map.register_iterator(**it2fix);
561  }
562 
563  iterators2fix.clear();
564  m_btree->m_iterator_map.find(src.my_bid(), 0, src_size, iterators2fix);
565  for (it2fix = iterators2fix.begin(); it2fix != iterators2fix.end(); ++it2fix)
566  {
567  STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
568  " (bid=" << my_bid() << ")");
569  m_btree->m_iterator_map.unregister_iterator(**it2fix);
570  ((*it2fix)->bid) = my_bid(); // fixing iterators
571  m_btree->m_iterator_map.register_iterator(**it2fix);
572  }
573 
574  m_block->info.cur_size += src_size;
575 
576  // update links
577  pred() = src.pred();
578  if (pred().valid())
579  { // update successor link
580  normal_leaf* new_pred = m_btree->m_leaf_cache.get_node(pred());
581  assert(new_pred);
582  new_pred->succ() = my_bid();
583  }
584  }
585 
587  {
588  STXXL_VERBOSE1("btree::normal_leaf Balancing leaves with bids " <<
589  left.my_bid() << " and " << my_bid());
590  const unsigned total_size = left.size() + size();
591  unsigned new_left_size = total_size / 2;
592  assert(new_left_size <= left.max_nelements());
593  assert(new_left_size >= left.min_nelements());
594  unsigned new_right_size = total_size - new_left_size;
595  assert(new_right_size <= max_nelements());
596  assert(new_right_size >= min_nelements());
597 
598  assert(m_vcmp(left.back(), front()) || size() == 0);
599 
600  if (new_left_size < left.size())
601  {
602  // #elements to move from left to *this
603  const unsigned nEl2Move = left.size() - new_left_size;
604 
605  typename block_type::iterator cur = m_block->begin() + size() - 1;
606  typename block_type::const_iterator begin = m_block->begin();
607 
608  for ( ; cur >= begin; --cur)
609  *(cur + nEl2Move) = *cur;
610  // move elements to make space for Src elements
611 
612  // copy Left to *this leaf
613  std::copy(left.m_block->begin() + new_left_size,
614  left.m_block->begin() + left.size(), m_block->begin());
615 
616  std::vector<iterator_base*> iterators2fix1;
617  std::vector<iterator_base*> iterators2fix2;
618  m_btree->m_iterator_map.find(my_bid(), 0, size(), iterators2fix1);
619  m_btree->m_iterator_map.find(left.my_bid(), new_left_size, left.size(), iterators2fix2);
620 
621  typename std::vector<iterator_base*>::iterator it2fix = iterators2fix1.begin();
622  for ( ; it2fix != iterators2fix1.end(); ++it2fix)
623  {
624  STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
625  " (pos+" << nEl2Move << ")");
626  m_btree->m_iterator_map.unregister_iterator(**it2fix);
627  ((*it2fix)->pos) += nEl2Move; // fixing iterators
628  m_btree->m_iterator_map.register_iterator(**it2fix);
629  }
630 
631  it2fix = iterators2fix2.begin();
632  for ( ; it2fix != iterators2fix2.end(); ++it2fix)
633  {
634  STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
635  " (pos-" << new_left_size << " bid=" << my_bid() << ")");
636  m_btree->m_iterator_map.unregister_iterator(**it2fix);
637  ((*it2fix)->bid) = my_bid(); // fixing iterators
638  ((*it2fix)->pos) -= new_left_size; // fixing iterators
639  m_btree->m_iterator_map.register_iterator(**it2fix);
640  }
641  }
642  else
643  {
644  assert(new_right_size < size());
645 
646  const unsigned nEl2Move = size() - new_right_size; // #elements to move from *this to Left
647 
648  // copy *this to Left
649  std::copy(m_block->begin(),
650  m_block->begin() + nEl2Move, left.m_block->begin() + left.size());
651  // move elements in *this
652  std::copy(m_block->begin() + nEl2Move,
653  m_block->begin() + size(), m_block->begin());
654 
655  std::vector<iterator_base*> iterators2fix1;
656  std::vector<iterator_base*> iterators2fix2;
657  m_btree->m_iterator_map.find(my_bid(), nEl2Move, size(), iterators2fix1);
658  m_btree->m_iterator_map.find(my_bid(), 0, nEl2Move - 1, iterators2fix2);
659 
660  typename std::vector<iterator_base*>::iterator it2fix = iterators2fix1.begin();
661  for ( ; it2fix != iterators2fix1.end(); ++it2fix)
662  {
663  STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
664  " (pos-" << nEl2Move << ")");
665  m_btree->m_iterator_map.unregister_iterator(**it2fix);
666  ((*it2fix)->pos) -= nEl2Move; // fixing iterators
667  m_btree->m_iterator_map.register_iterator(**it2fix);
668  }
669 
670  it2fix = iterators2fix2.begin();
671  for ( ; it2fix != iterators2fix2.end(); ++it2fix)
672  {
673  STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
674  " (pos+" << left.size() << " bid=" << left.my_bid() << ")");
675  m_btree->m_iterator_map.unregister_iterator(**it2fix);
676  ((*it2fix)->bid) = left.my_bid(); // fixing iterators
677  ((*it2fix)->pos) += left.size(); // fixing iterators
678  m_btree->m_iterator_map.register_iterator(**it2fix);
679  }
680  }
681 
682  m_block->info.cur_size = new_right_size; // update size
683  left.m_block->info.cur_size = new_left_size; // update size
684 
685  return left.back().first;
686  }
687 
688  void push_back(const value_type& x)
689  {
690  (*this)[size()] = x;
691  ++(m_block->info.cur_size);
692  }
693 };
694 
695 } // namespace btree
696 
698 
699 #endif // !STXXL_CONTAINERS_BTREE_LEAF_HEADER
std::pair< key_type, data_type > value_type
Definition: leaf.h:37
virtual ~normal_leaf()
Definition: leaf.h:162
normal_leaf< KeyType, DataType, KeyCmp, RawSize, BTreeType > self_type
Definition: leaf.h:30
const_iterator lower_bound(const key_type &k) const
Definition: leaf.h:461
DataType data_type
Definition: leaf.h:35
const_iterator upper_bound(const key_type &k) const
Definition: leaf.h:491
unsigned size() const
Definition: leaf.h:228
const bid_type & pred() const
Definition: leaf.h:199
void push_back(const value_type &x)
Definition: leaf.h:688
typed_block< raw_size, value_type, 0, metainfo_type > block_type
Definition: leaf.h:53
void fuse(const normal_leaf &src)
Definition: leaf.h:535
key_type balance(normal_leaf &left)
Definition: leaf.h:586
const_reference back() const
Definition: leaf.h:285
normal_leaf(btree_type *btree, key_compare cmp)
Definition: leaf.h:167
info_type info
Per block information element.
Definition: typed_block.h:179
bool underflows() const
Definition: leaf.h:181
bid_type & succ()
Definition: leaf.h:186
BID< raw_size > bid_type
Definition: leaf.h:45
reference front()
Definition: leaf.h:280
const_iterator begin() const
Definition: leaf.h:361
iterator find(const key_type &k)
Definition: leaf.h:423
static unsigned max_nelements()
Definition: leaf.h:183
#define STXXL_VERBOSE2(x)
Definition: verbose.h:121
block_type * m_block
Definition: leaf.h:82
const value_type & const_reference
Definition: leaf.h:39
BTreeType btree_type
Definition: leaf.h:60
btree_type::size_type size_type
Definition: leaf.h:61
const bid_type & succ() const
Definition: leaf.h:195
request_ptr load(const bid_type &bid)
Definition: leaf.h:244
iterator begin()
Definition: leaf.h:356
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.
node_cache< normal_leaf, btree_type > leaf_cache_type
Definition: leaf.h:66
void increment_iterator(iterator_base &it) const
Definition: leaf.h:371
void decrement_iterator(iterator_base &it) const
Definition: leaf.h:396
key_compare m_cmp
Definition: leaf.h:85
value_type & reference
Definition: leaf.h:38
btree_iterator< btree_type > iterator
Definition: leaf.h:63
static std::vector< std::string > split(const std::string &str, const std::string &sep, unsigned int min_fields=0, unsigned int limit_fields=std::numeric_limits< unsigned int >::max())
Split a string by given separator string. Returns a vector of strings with at least min_fields and at...
Definition: utils.h:56
const_pointer const_iterator
Definition: typed_block.h:249
bid_type & pred()
Definition: leaf.h:190
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
const_reference front() const
Definition: leaf.h:290
#define STXXL_VERBOSE1(x)
Definition: verbose.h:113
iterator lower_bound(const key_type &k)
Definition: leaf.h:445
bool overflows() const
Definition: leaf.h:180
iterator begin()
Returns iterator pointing to the first element.
Definition: typed_block.h:92
bool valid() const
Definition: bid.h:55
reference back()
Definition: leaf.h:275
btree_type * m_btree
Definition: leaf.h:83
std::pair< iterator, bool > insert(const value_type &x, std::pair< key_type, bid_type > &splitter)
Definition: leaf.h:302
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
size_type erase(const key_type &k)
Definition: leaf.h:506
const bid_type & my_bid() const
Definition: leaf.h:233
void split(std::pair< key_type, bid_type > &splitter)
Definition: leaf.h:88
btree_const_iterator< btree_type > const_iterator
Definition: leaf.h:64
iterator upper_bound(const key_type &k)
Definition: leaf.h:476
static unsigned min_nelements()
Definition: leaf.h:184
btree_iterator_base< btree_type > iterator_base
Definition: leaf.h:62
void init(const bid_type &my_bid_)
Definition: leaf.h:257
request_ptr prefetch(const bid_type &bid)
Definition: leaf.h:252
const_iterator find(const key_type &k) const
Definition: leaf.h:434
value_compare m_vcmp
Definition: leaf.h:86
#define STXXL_END_NAMESPACE
Definition: namespace.h:17