STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
btree.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/btree/btree.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2006, 2008 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_BTREE_HEADER
14 #define STXXL_CONTAINERS_BTREE_BTREE_HEADER
15 
16 #include <limits>
17 #include <stxxl/bits/namespace.h>
24 #include <stxxl/vector>
25 
27 
28 namespace btree {
29 
30 template <class KeyType,
31  class DataType,
32  class CompareType,
33  unsigned RawNodeSize,
34  unsigned RawLeafSize,
35  class PDAllocStrategy
36  >
37 class btree : private noncopyable
38 {
39 public:
40  typedef KeyType key_type;
41  typedef DataType data_type;
42  typedef CompareType key_compare;
43 
44  typedef btree<KeyType, DataType, CompareType,
45  RawNodeSize, RawLeafSize, PDAllocStrategy> self_type;
46 
47  typedef PDAllocStrategy alloc_strategy_type;
48 
51  typedef std::pair<const key_type, data_type> value_type;
53  typedef const value_type& const_reference;
54  typedef value_type* pointer;
55  typedef value_type const* const_pointer;
56 
57  // leaf type declarations
59  friend class normal_leaf<key_type, data_type, key_compare, RawLeafSize, self_type>;
63  friend class node_cache<leaf_type, self_type>;
64  // iterator types
68  // iterator map type
70  // node type declarations
73  friend class normal_node<key_type, key_compare, RawNodeSize, self_type>;
76  friend class node_cache<node_type, self_type>;
77 
79 
80  enum {
81  min_node_size = node_type::min_size,
82  max_node_size = node_type::max_size,
83  min_leaf_size = leaf_type::min_size,
84  max_leaf_size = leaf_type::max_size
85  };
86 
87 private:
93  unsigned int m_height;
97 
98  typedef std::map<key_type, node_bid_type, key_compare> root_node_type;
99  typedef typename root_node_type::iterator root_node_iterator_type;
100  typedef typename root_node_type::const_iterator root_node_const_iterator_type;
101  typedef std::pair<key_type, node_bid_type> root_node_pair_type;
102 
105 
106  void insert_into_root(const std::pair<key_type, node_bid_type>& splitter)
107  {
108  std::pair<root_node_iterator_type, bool> result =
109  m_root_node.insert(splitter);
110  STXXL_ASSERT(result.second == true);
111 
112  if (m_root_node.size() > max_node_size) // root overflow
113  {
114  STXXL_VERBOSE1("btree::insert_into_root, overflow happened, splitting");
115 
116  node_bid_type left_bid;
117  node_type* left_node = m_node_cache.get_new_node(left_bid);
118  assert(left_node);
119  node_bid_type right_bid;
120  node_type* right_node = m_node_cache.get_new_node(right_bid);
121  assert(right_node);
122 
123  const unsigned_type old_size = m_root_node.size();
124  const unsigned_type half = m_root_node.size() / 2;
125  unsigned_type i = 0;
126  root_node_iterator_type it = m_root_node.begin();
127  typename node_block_type::iterator block_it = left_node->block().begin();
128  while (i < half) // copy smaller part
129  {
130  *block_it = *it;
131  ++i;
132  ++block_it;
133  ++it;
134  }
135  left_node->block().info.cur_size = (unsigned int)half;
136  key_type left_key = (left_node->block()[half - 1]).first;
137 
138  block_it = right_node->block().begin();
139  while (i < old_size) // copy larger part
140  {
141  *block_it = *it;
142  ++i;
143  ++block_it;
144  ++it;
145  }
146  unsigned_type right_size = right_node->block().info.cur_size = (unsigned int)(old_size - half);
147  key_type right_key = (right_node->block()[right_size - 1]).first;
148 
149  assert(old_size == right_node->size() + left_node->size());
150 
151  // create new root node
152  m_root_node.clear();
153  m_root_node.insert(root_node_pair_type(left_key, left_bid));
154  m_root_node.insert(root_node_pair_type(right_key, right_bid));
155 
156  ++m_height;
157  STXXL_VERBOSE1("btree Increasing height to " << m_height);
158  if (m_node_cache.size() < (m_height - 1))
159  {
160  STXXL_THROW2(std::runtime_error, "btree::bulk_construction",
161  "The height of the tree (" << m_height << ") has exceeded the required capacity (" << (m_node_cache.size() + 1) << ") of the node cache. Increase the node cache size.");
162  }
163  }
164  }
165 
166  template <class CacheType>
167  void fuse_or_balance(root_node_iterator_type uit, CacheType& cache)
168  {
169  typedef typename CacheType::node_type local_node_type;
170  typedef typename local_node_type::bid_type local_bid_type;
171 
172  root_node_iterator_type left_it, right_it;
173  if (uit->first == key_compare::max_value())
174  {
175  // uit is the last entry in the root
176  assert(uit != m_root_node.begin());
177  right_it = uit;
178  left_it = --uit;
179  }
180  else
181  {
182  left_it = uit;
183  right_it = ++uit;
184  assert(right_it != m_root_node.end());
185  }
186 
187  // now fuse or balance nodes pointed by leftIt and rightIt
188  local_bid_type left_bid = (local_bid_type)left_it->second;
189  local_bid_type right_bid = (local_bid_type)right_it->second;
190  local_node_type* left_node = cache.get_node(left_bid, true);
191  local_node_type* right_node = cache.get_node(right_bid, true);
192 
193  const unsigned_type total_size = left_node->size() + right_node->size();
194  if (total_size <= right_node->max_nelements())
195  {
196  // --- fuse ---
197 
198  // add the content of left_node to right_node
199  right_node->fuse(*left_node);
200 
201  cache.unfix_node(right_bid);
202  // 'delete_node' unfixes left_bid also
203  cache.delete_node(left_bid);
204 
205  // delete left BID from the root
206  m_root_node.erase(left_it);
207  }
208  else
209  {
210  // --- balance ---
211 
212  key_type new_splitter = right_node->balance(*left_node);
213 
214  // delete left BID from the root
215  m_root_node.erase(left_it);
216 
217  // reinsert with the new key
218  m_root_node.insert(root_node_pair_type(new_splitter, (node_bid_type)left_bid));
219 
220  cache.unfix_node(left_bid);
221  cache.unfix_node(right_bid);
222  }
223  }
224 
226  {
227  leaf_bid_type new_bid;
228  leaf_type* new_leaf = m_leaf_cache.get_new_node(new_bid);
229  assert(new_leaf);
230  m_end_iterator = new_leaf->end(); // initialize end() iterator
231  m_root_node.insert(
232  root_node_pair_type(key_compare::max_value(), (node_bid_type)new_bid)
233  );
234  }
235 
237  {
238  if (m_height == 2)
239  {
240  // we have children leaves here
241  for (root_node_const_iterator_type it = m_root_node.begin();
242  it != m_root_node.end(); ++it)
243  {
244  // delete from leaf cache and deallocate bid
245  m_leaf_cache.delete_node((leaf_bid_type)it->second);
246  }
247  }
248  else
249  {
250  for (root_node_const_iterator_type it = m_root_node.begin();
251  it != m_root_node.end(); ++it)
252  {
253  node_type* node = m_node_cache.get_node((node_bid_type)it->second);
254  assert(node);
255  node->deallocate_children(m_height - 1);
256  // delete from node cache and deallocate bid
257  m_node_cache.delete_node((node_bid_type)it->second);
258  }
259  }
260  }
261 
262  template <class InputIterator>
263  void bulk_construction(InputIterator begin, InputIterator end,
264  double node_fill_factor, double leaf_fill_factor)
265  {
266  assert(node_fill_factor >= 0.5);
267  assert(leaf_fill_factor >= 0.5);
268  key_type last_key = key_compare::max_value();
269 
270  typedef std::pair<key_type, node_bid_type> key_bid_pair;
271  typedef typename stxxl::VECTOR_GENERATOR<
272  key_bid_pair, 1, 1, node_block_type::raw_size
273  >::result key_bid_vector_type;
274 
275  key_bid_vector_type bids;
276 
277  leaf_bid_type new_bid;
278  leaf_type* leaf = m_leaf_cache.get_new_node(new_bid);
279  const unsigned_type max_leaf_elements = unsigned_type(
280  (double)leaf->max_nelements() * leaf_fill_factor
281  );
282 
283  while (begin != end)
284  {
285  // write data in leaves
286 
287  // if *b not equal to the last element
288  if (m_key_compare(begin->first, last_key) || m_key_compare(last_key, begin->first))
289  {
290  ++m_size;
291  if (leaf->size() == max_leaf_elements)
292  {
293  // overflow, need a new block
294  bids.push_back(key_bid_pair(leaf->back().first, (node_bid_type)new_bid));
295 
296  leaf_type* new_leaf = m_leaf_cache.get_new_node(new_bid);
297  assert(new_leaf);
298  // Setting links
299  leaf->succ() = new_leaf->my_bid();
300  new_leaf->pred() = leaf->my_bid();
301 
302  leaf = new_leaf;
303  }
304  leaf->push_back(*begin);
305  last_key = begin->first;
306  }
307  ++begin;
308  }
309 
310  // rebalance the last leaf
311  if (leaf->underflows() && !bids.empty())
312  {
313  leaf_type* left_leaf = m_leaf_cache.get_node((leaf_bid_type)(bids.back().second));
314  assert(left_leaf);
315  if (left_leaf->size() + leaf->size() <= leaf->max_nelements())
316  {
317  // can fuse
318  leaf->fuse(*left_leaf);
319  m_leaf_cache.delete_node((leaf_bid_type)(bids.back().second));
320  bids.pop_back();
321  assert(!leaf->overflows() && !leaf->underflows());
322  }
323  else
324  {
325  // need to rebalance
326  const key_type new_splitter = leaf->balance(*left_leaf);
327  bids.back().first = new_splitter;
328  assert(!left_leaf->overflows() && !left_leaf->underflows());
329  }
330  }
331 
332  assert(!leaf->overflows() && (!leaf->underflows() || m_size <= max_leaf_size));
333 
334  m_end_iterator = leaf->end(); // initialize end() iterator
335 
336  bids.push_back(key_bid_pair(key_compare::max_value(), (node_bid_type)new_bid));
337 
338  const unsigned_type max_node_elements = unsigned_type(
339  double(max_node_size) * node_fill_factor
340  );
341 
342  //-tb fixes bug with only one child remaining in m_root_node
343  while (bids.size() > node_type::max_nelements())
344  {
345  key_bid_vector_type parent_bids;
346 
347  stxxl::uint64 nparents = div_ceil(bids.size(), max_node_elements);
348  assert(nparents >= 2);
349  STXXL_VERBOSE1("btree bulk construct"
350  << " bids.size=" << bids.size()
351  << " nparents=" << nparents
352  << " max_node_elements=" << max_node_elements
353  << " node_type::max_nelements=" << node_type::max_nelements());
354 
355  for (typename key_bid_vector_type::const_iterator it = bids.begin();
356  it != bids.end(); )
357  {
358  node_bid_type new_bid;
359  node_type* node = m_node_cache.get_new_node(new_bid);
360  assert(node);
361 
362  for (unsigned_type cnt = 0;
363  cnt < max_node_elements && it != bids.end(); ++cnt, ++it)
364  {
365  node->push_back(*it);
366  }
367 
368  STXXL_VERBOSE1("btree bulk construct node size : " << node->size() << " limits: " << node->min_nelements() << " " << node->max_nelements() << " max_node_elements: " << max_node_elements);
369 
370  if (node->underflows())
371  {
372  // this can happen only at the end
373  assert(it == bids.end());
374  assert(!parent_bids.empty());
375 
376  node_type* left_node = m_node_cache.get_node(parent_bids.back().second);
377  assert(left_node);
378  if (left_node->size() + node->size() <= node->max_nelements())
379  {
380  // can fuse
381  STXXL_VERBOSE1("btree bulk construct fuse last nodes:"
382  << " left_node.size=" << left_node->size()
383  << " node.size=" << node->size());
384 
385  node->fuse(*left_node);
386  m_node_cache.delete_node(parent_bids.back().second);
387  parent_bids.pop_back();
388  }
389  else
390  {
391  // need to rebalance
392  STXXL_VERBOSE1("btree bulk construct rebalance last nodes:"
393  << " left_node.size=" << left_node->size()
394  << " node.size=" << node->size());
395 
396  const key_type new_splitter = node->balance(*left_node, false);
397  parent_bids.back().first = new_splitter;
398 
399  STXXL_VERBOSE1("btree bulk construct after rebalance:"
400  << " left_node.size=" << left_node->size()
401  << " node.size=" << node->size());
402 
403  assert(!left_node->overflows() && !left_node->underflows());
404  }
405  }
406  assert(!node->overflows() && !node->underflows());
407 
408  parent_bids.push_back(key_bid_pair(node->back().first, new_bid));
409  }
410 
411  STXXL_VERBOSE1("btree parent_bids.size()=" << parent_bids.size()
412  << " bids.size()=" << bids.size());
413 
414  std::swap(parent_bids, bids);
415 
416  assert(nparents == bids.size() || (nparents - 1) == bids.size());
417 
418  ++m_height;
419  STXXL_VERBOSE1("Increasing height to " << m_height);
420  if (m_node_cache.size() < (m_height - 1))
421  {
422  STXXL_THROW2(std::runtime_error, "btree::bulk_construction",
423  "The height of the tree (" << m_height << ") has exceeded the required capacity (" << (m_node_cache.size() + 1) << ") of the node cache. Increase the node cache size.");
424  }
425  }
426 
427  m_root_node.insert(bids.begin(), bids.end());
428 
429  STXXL_VERBOSE1("btree bulk root_node_.size()=" << m_root_node.size());
430  }
431 
432 public:
433  btree(unsigned_type node_cache_size_in_bytes,
434  unsigned_type leaf_cache_size_in_bytes)
435  : m_node_cache(node_cache_size_in_bytes, this, m_key_compare),
436  m_leaf_cache(leaf_cache_size_in_bytes, this, m_key_compare),
437  m_iterator_map(this),
438  m_size(0),
439  m_height(2),
440  m_prefetching_enabled(true),
441  m_bm(block_manager::get_instance())
442  {
443  STXXL_VERBOSE1("Creating a btree, addr=" << this);
444  STXXL_VERBOSE1(" bytes in a node: " << node_bid_type::size);
445  STXXL_VERBOSE1(" bytes in a leaf: " << leaf_bid_type::size);
446  STXXL_VERBOSE1(" elements in a node: " << node_block_type::size);
447  STXXL_VERBOSE1(" elements in a leaf: " << leaf_block_type::size);
448  STXXL_VERBOSE1(" size of a node element: " << sizeof(typename node_block_type::value_type));
449  STXXL_VERBOSE1(" size of a leaf element: " << sizeof(typename leaf_block_type::value_type));
450 
451  create_empty_leaf();
452  }
453 
455  unsigned_type node_cache_size_in_bytes,
456  unsigned_type leaf_cache_size_in_bytes)
457  : m_key_compare(key_compare),
458  m_node_cache(node_cache_size_in_bytes, this, m_key_compare),
459  m_leaf_cache(leaf_cache_size_in_bytes, this, m_key_compare),
460  m_iterator_map(this),
461  m_size(0),
462  m_height(2),
463  m_prefetching_enabled(true),
464  m_bm(block_manager::get_instance())
465  {
466  STXXL_VERBOSE1("Creating a btree, addr=" << this);
467  STXXL_VERBOSE1(" bytes in a node: " << node_bid_type::size);
468  STXXL_VERBOSE1(" bytes in a leaf: " << leaf_bid_type::size);
469 
470  create_empty_leaf();
471  }
472 
473  virtual ~btree()
474  {
475  try
476  {
477  deallocate_children();
478  }
479  catch (...)
480  {
481  // no exceptions in destructor
482  }
483  }
484 
485  size_type size() const
486  {
487  return m_size;
488  }
489 
491  {
493  }
494 
495  bool empty() const
496  {
497  return !m_size;
498  }
499 
500  std::pair<iterator, bool> insert(const value_type& x)
501  {
502  root_node_iterator_type it = m_root_node.lower_bound(x.first);
503  assert(!m_root_node.empty());
504  assert(it != m_root_node.end());
505 
506  if (m_height == 2) // 'it' points to a leaf
507  {
508  STXXL_VERBOSE1("Inserting new value into a leaf");
509  leaf_type* leaf = m_leaf_cache.get_node((leaf_bid_type)it->second, true);
510  assert(leaf);
511  std::pair<key_type, leaf_bid_type> splitter;
512  std::pair<iterator, bool> result = leaf->insert(x, splitter);
513  if (result.second)
514  ++m_size;
515 
516  m_leaf_cache.unfix_node((leaf_bid_type)it->second);
517  //if(key_compare::max_value() == Splitter.first)
518  if (!(m_key_compare(key_compare::max_value(), splitter.first) ||
519  m_key_compare(splitter.first, key_compare::max_value())))
520  return result;
521  // no overflow/splitting happened
522 
523  STXXL_VERBOSE1("Inserting new value into root node");
524 
525  insert_into_root(std::make_pair(splitter.first, node_bid_type(splitter.second)));
526 
527  assert(m_leaf_cache.nfixed() == 0);
528  assert(m_node_cache.nfixed() == 0);
529  return result;
530  }
531 
532  // 'it' points to a node
533  STXXL_VERBOSE1("Inserting new value into a node");
534  node_type* node = m_node_cache.get_node((node_bid_type)it->second, true);
535  assert(node);
536  std::pair<key_type, node_bid_type> splitter;
537  std::pair<iterator, bool> result = node->insert(x, m_height - 1, splitter);
538  if (result.second)
539  ++m_size;
540 
541  m_node_cache.unfix_node((node_bid_type)it->second);
542  //if(key_compare::max_value() == Splitter.first)
543  if (!(m_key_compare(key_compare::max_value(), splitter.first) ||
544  m_key_compare(splitter.first, key_compare::max_value())))
545  return result;
546  // no overflow/splitting happened
547 
548  STXXL_VERBOSE1("Inserting new value into root node");
549 
550  insert_into_root(splitter);
551 
552  assert(m_leaf_cache.nfixed() == 0);
553  assert(m_node_cache.nfixed() == 0);
554 
555  return result;
556  }
557 
559  {
560  root_node_iterator_type it = m_root_node.begin();
561  assert(it != m_root_node.end());
562 
563  if (m_height == 2) // 'it' points to a leaf
564  {
565  STXXL_VERBOSE1("btree: retrieving begin() from the first leaf");
566  leaf_type* leaf = m_leaf_cache.get_node((leaf_bid_type)it->second);
567  assert(leaf);
568 
569  assert(m_leaf_cache.nfixed() == 0);
570  assert(m_node_cache.nfixed() == 0);
571  return leaf->begin();
572  }
573 
574  // 'it' points to a node
575  STXXL_VERBOSE1("btree: retrieving begin() from the first node");
576  node_type* node = m_node_cache.get_node((node_bid_type)it->second, true);
577  assert(node);
578  iterator result = node->begin(m_height - 1);
579  m_node_cache.unfix_node((node_bid_type)it->second);
580 
581  assert(m_leaf_cache.nfixed() == 0);
582  assert(m_node_cache.nfixed() == 0);
583 
584  return result;
585  }
586 
588  {
589  root_node_const_iterator_type it = m_root_node.begin();
590  assert(it != m_root_node.end());
591 
592  if (m_height == 2) // 'it' points to a leaf
593  {
594  STXXL_VERBOSE1("btree: retrieving begin() from the first leaf");
595  const leaf_type* leaf = m_leaf_cache.get_const_node((leaf_bid_type)it->second);
596  assert(leaf);
597  assert(m_leaf_cache.nfixed() == 0);
598  assert(m_node_cache.nfixed() == 0);
599  return leaf->begin();
600  }
601 
602  // 'it' points to a node
603  STXXL_VERBOSE1("btree: retrieving begin() from the first node");
604  const node_type* node = m_node_cache.get_const_node((node_bid_type)it->second, true);
605  assert(node);
606  const_iterator result = node->begin(m_height - 1);
607  m_node_cache.unfix_node((node_bid_type)it->second);
608  assert(m_leaf_cache.nfixed() == 0);
609  assert(m_node_cache.nfixed() == 0);
610  return result;
611  }
612 
614  {
615  return m_end_iterator;
616  }
617 
619  {
620  return m_end_iterator;
621  }
622 
623  data_type& operator [] (const key_type& k)
624  {
625  return (*((insert(value_type(k, data_type()))).first)).second;
626  }
627 
629  {
630  root_node_iterator_type it = m_root_node.lower_bound(k);
631  assert(it != m_root_node.end());
632 
633  if (m_height == 2) // 'it' points to a leaf
634  {
635  STXXL_VERBOSE1("Searching in a leaf");
636  leaf_type* leaf = m_leaf_cache.get_node((leaf_bid_type)it->second, true);
637  assert(leaf);
638  iterator result = leaf->find(k);
639  m_leaf_cache.unfix_node((leaf_bid_type)it->second);
640  assert(result == end() || result->first == k);
641  assert(m_leaf_cache.nfixed() == 0);
642  assert(m_node_cache.nfixed() == 0);
643  return result;
644  }
645 
646  // 'it' points to a node
647  STXXL_VERBOSE1("Searching in a node");
648  node_type* node = m_node_cache.get_node((node_bid_type)it->second, true);
649  assert(node);
650  iterator result = node->find(k, m_height - 1);
651  m_node_cache.unfix_node((node_bid_type)it->second);
652 
653  assert(result == end() || result->first == k);
654  assert(m_leaf_cache.nfixed() == 0);
655  assert(m_node_cache.nfixed() == 0);
656  return result;
657  }
658 
659  const_iterator find(const key_type& k) const
660  {
661  root_node_const_iterator_type it = m_root_node.lower_bound(k);
662  assert(it != m_root_node.end());
663 
664  if (m_height == 2) // 'it' points to a leaf
665  {
666  STXXL_VERBOSE1("Searching in a leaf");
667  const leaf_type* leaf = m_leaf_cache.get_const_node((leaf_bid_type)it->second, true);
668  assert(leaf);
669  const_iterator result = leaf->find(k);
670  m_leaf_cache.unfix_node((leaf_bid_type)it->second);
671  assert(result == end() || result->first == k);
672  assert(m_leaf_cache.nfixed() == 0);
673  assert(m_node_cache.nfixed() == 0);
674  return result;
675  }
676 
677  // 'it' points to a node
678  STXXL_VERBOSE1("Searching in a node");
679  const node_type* node = m_node_cache.get_const_node((node_bid_type)it->second, true);
680  assert(node);
681  const_iterator result = node->find(k, m_height - 1);
682  m_node_cache.unfix_node((node_bid_type)it->second);
683 
684  assert(result == end() || result->first == k);
685  assert(m_leaf_cache.nfixed() == 0);
686  assert(m_node_cache.nfixed() == 0);
687  return result;
688  }
689 
691  {
692  root_node_iterator_type it = m_root_node.lower_bound(k);
693  assert(it != m_root_node.end());
694 
695  if (m_height == 2) // 'it' points to a leaf
696  {
697  STXXL_VERBOSE1("Searching lower bound in a leaf");
698  leaf_type* leaf = m_leaf_cache.get_node((leaf_bid_type)it->second, true);
699  assert(leaf);
700  iterator result = leaf->lower_bound(k);
701  m_leaf_cache.unfix_node((leaf_bid_type)it->second);
702  assert(m_leaf_cache.nfixed() == 0);
703  assert(m_node_cache.nfixed() == 0);
704  return result;
705  }
706 
707  // 'it' points to a node
708  STXXL_VERBOSE1("Searching lower bound in a node");
709  node_type* node = m_node_cache.get_node((node_bid_type)it->second, true);
710  assert(node);
711  iterator result = node->lower_bound(k, m_height - 1);
712  m_node_cache.unfix_node((node_bid_type)it->second);
713 
714  assert(m_leaf_cache.nfixed() == 0);
715  assert(m_node_cache.nfixed() == 0);
716  return result;
717  }
718 
720  {
721  root_node_const_iterator_type it = m_root_node.lower_bound(k);
722  assert(it != m_root_node.end());
723 
724  if (m_height == 2) // 'it' points to a leaf
725  {
726  STXXL_VERBOSE1("Searching lower bound in a leaf");
727  const leaf_type* leaf = m_leaf_cache.get_const_node((leaf_bid_type)it->second, true);
728  assert(leaf);
729  const_iterator result = leaf->lower_bound(k);
730  m_leaf_cache.unfix_node((leaf_bid_type)it->second);
731 
732  assert(m_leaf_cache.nfixed() == 0);
733  assert(m_node_cache.nfixed() == 0);
734  return result;
735  }
736 
737  // 'it' points to a node
738  STXXL_VERBOSE1("Searching lower bound in a node");
739  const node_type* node = m_node_cache.get_const_node((node_bid_type)it->second, true);
740  assert(node);
741  const_iterator result = node->lower_bound(k, m_height - 1);
742  m_node_cache.unfix_node((node_bid_type)it->second);
743 
744  assert(m_leaf_cache.nfixed() == 0);
745  assert(m_node_cache.nfixed() == 0);
746  return result;
747  }
748 
750  {
751  root_node_iterator_type it = m_root_node.upper_bound(k);
752  assert(it != m_root_node.end());
753 
754  if (m_height == 2) // 'it' points to a leaf
755  {
756  STXXL_VERBOSE1("Searching upper bound in a leaf");
757  leaf_type* Leaf = m_leaf_cache.get_node((leaf_bid_type)it->second, true);
758  assert(Leaf);
759  iterator result = Leaf->upper_bound(k);
760  m_leaf_cache.unfix_node((leaf_bid_type)it->second);
761 
762  assert(m_leaf_cache.nfixed() == 0);
763  assert(m_node_cache.nfixed() == 0);
764  return result;
765  }
766 
767  // 'it' points to a node
768  STXXL_VERBOSE1("Searching upper bound in a node");
769  node_type* Node = m_node_cache.get_node((node_bid_type)it->second, true);
770  assert(Node);
771  iterator result = Node->upper_bound(k, m_height - 1);
772  m_node_cache.unfix_node((node_bid_type)it->second);
773 
774  assert(m_leaf_cache.nfixed() == 0);
775  assert(m_node_cache.nfixed() == 0);
776  return result;
777  }
778 
780  {
781  root_node_const_iterator_type it = m_root_node.upper_bound(k);
782  assert(it != m_root_node.end());
783 
784  if (m_height == 2) // 'it' points to a leaf
785  {
786  STXXL_VERBOSE1("Searching upper bound in a leaf");
787  const leaf_type* leaf = m_leaf_cache.get_const_node((leaf_bid_type)it->second, true);
788  assert(leaf);
789  const_iterator result = leaf->upper_bound(k);
790  m_leaf_cache.unfix_node((leaf_bid_type)it->second);
791 
792  assert(m_leaf_cache.nfixed() == 0);
793  assert(m_node_cache.nfixed() == 0);
794  return result;
795  }
796 
797  // 'it' points to a node
798  STXXL_VERBOSE1("Searching upper bound in a node");
799  const node_type* node = m_node_cache.get_const_node((node_bid_type)it->second, true);
800  assert(node);
801  const_iterator result = node->upper_bound(k, m_height - 1);
802  m_node_cache.unfix_node((node_bid_type)it->second);
803 
804  assert(m_leaf_cache.nfixed() == 0);
805  assert(m_node_cache.nfixed() == 0);
806  return result;
807  }
808 
809  std::pair<iterator, iterator> equal_range(const key_type& k)
810  {
811  // l->first >= k
812  iterator l = lower_bound(k);
813 
814  // if (k < l->first)
815  if (l == end() || m_key_compare(k, l->first))
816  // then upper_bound == lower_bound
817  return std::pair<iterator, iterator>(l, l);
818 
819  iterator u = l;
820  // only one element ==k can exist
821  ++u;
822 
823  assert(m_leaf_cache.nfixed() == 0);
824  assert(m_node_cache.nfixed() == 0);
825 
826  // then upper_bound == (lower_bound+1)
827  return std::pair<iterator, iterator>(l, u);
828  }
829 
830  std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
831  {
832  // l->first >= k
833  const_iterator l = lower_bound(k);
834 
835  // if (k < l->first)
836  if (l == end() || m_key_compare(k, l->first))
837  // then upper_bound == lower_bound
838  return std::pair<const_iterator, const_iterator>(l, l);
839 
840  const_iterator u = l;
841  // only one element ==k can exist
842  ++u;
843 
844  assert(m_leaf_cache.nfixed() == 0);
845  assert(m_node_cache.nfixed() == 0);
846  // then upper_bound == (lower_bound+1)
847  return std::pair<const_iterator, const_iterator>(l, u);
848  }
849 
851  {
852  root_node_iterator_type it = m_root_node.lower_bound(k);
853  assert(it != m_root_node.end());
854 
855  if (m_height == 2) // 'it' points to a leaf
856  {
857  STXXL_VERBOSE1("Deleting key from a leaf");
858  leaf_type* Leaf = m_leaf_cache.get_node((leaf_bid_type)it->second, true);
859  assert(Leaf);
860  size_type result = Leaf->erase(k);
861  m_size -= result;
862  m_leaf_cache.unfix_node((leaf_bid_type)it->second);
863  assert(m_leaf_cache.nfixed() == 0);
864  assert(m_node_cache.nfixed() == 0);
865 
866  if ((!Leaf->underflows()) || m_root_node.size() == 1)
867  return result;
868  // no underflow or root has a special degree 1 (too few elements)
869 
870  STXXL_VERBOSE1("btree: Fusing or rebalancing a leaf");
871  fuse_or_balance(it, m_leaf_cache);
872 
873  assert(m_leaf_cache.nfixed() == 0);
874  assert(m_node_cache.nfixed() == 0);
875 
876  return result;
877  }
878 
879  // 'it' points to a node
880  STXXL_VERBOSE1("Deleting key from a node");
881  assert(m_root_node.size() >= 2);
882  node_type* node = m_node_cache.get_node((node_bid_type)it->second, true);
883  assert(node);
884  size_type result = node->erase(k, m_height - 1);
885  m_size -= result;
886  m_node_cache.unfix_node((node_bid_type)it->second);
887  assert(m_leaf_cache.nfixed() == 0);
888  assert(m_node_cache.nfixed() == 0);
889  if (!node->underflows())
890  return result;
891  // no underflow happened
892 
893  STXXL_VERBOSE1("Fusing or rebalancing a node");
894  fuse_or_balance(it, m_node_cache);
895 
896  if (m_root_node.size() == 1)
897  {
898  STXXL_VERBOSE1("btree Root has size 1 and height > 2");
899  STXXL_VERBOSE1("btree Deallocate root and decrease height");
900  it = m_root_node.begin();
901  node_bid_type root_bid = it->second;
902  assert(it->first == key_compare::max_value());
903  node_type* root_node = m_node_cache.get_node(root_bid);
904  assert(root_node);
905  assert(root_node->back().first == key_compare::max_value());
906  m_root_node.clear();
907  m_root_node.insert(root_node->block().begin(),
908  root_node->block().begin() + root_node->size());
909 
910  m_node_cache.delete_node(root_bid);
911  --m_height;
912  STXXL_VERBOSE1("btree Decreasing height to " << m_height);
913  }
914 
915  assert(m_leaf_cache.nfixed() == 0);
916  assert(m_node_cache.nfixed() == 0);
917 
918  return result;
919  }
920 
922  {
923  if (find(k) == end())
924  return 0;
925 
926  return 1;
927  }
928 
929  void erase(iterator pos)
930  {
931  assert(pos != end());
932 #ifndef NDEBUG
933  size_type old_size = size();
934 #endif
935 
936  erase(pos->first);
937 
938  assert(size() == old_size - 1);
939  }
940 
941  iterator insert(iterator /*pos*/, const value_type& x)
942  {
943  // pos ignored in the current version
944  return insert(x).first;
945  }
946 
947  void clear()
948  {
949  deallocate_children();
950 
951  m_root_node.clear();
952 
953  m_size = 0;
954  m_height = 2,
955 
956  create_empty_leaf();
957  assert(m_leaf_cache.nfixed() == 0);
958  assert(m_node_cache.nfixed() == 0);
959  }
960 
961  template <class InputIterator>
962  void insert(InputIterator b, InputIterator e)
963  {
964  while (b != e)
965  {
966  insert(*(b++));
967  }
968  }
969 
970  template <class InputIterator>
971  btree(InputIterator begin,
972  InputIterator end,
973  const key_compare& c_,
974  unsigned_type node_cache_size_in_bytes,
975  unsigned_type leaf_cache_size_in_bytes,
976  bool range_sorted = false,
977  double node_fill_factor = 0.75,
978  double leaf_fill_factor = 0.6)
979  : m_key_compare(c_),
980  m_node_cache(node_cache_size_in_bytes, this, m_key_compare),
981  m_leaf_cache(leaf_cache_size_in_bytes, this, m_key_compare),
982  m_iterator_map(this),
983  m_size(0),
984  m_height(2),
985  m_prefetching_enabled(true),
986  m_bm(block_manager::get_instance())
987  {
988  STXXL_VERBOSE1("Creating a btree, addr=" << this);
989  STXXL_VERBOSE1(" bytes in a node: " << node_bid_type::size);
990  STXXL_VERBOSE1(" bytes in a leaf: " << leaf_bid_type::size);
991 
992  if (range_sorted == false)
993  {
994  create_empty_leaf();
995  insert(begin, end);
996  assert(m_leaf_cache.nfixed() == 0);
997  assert(m_node_cache.nfixed() == 0);
998  return;
999  }
1000 
1001  bulk_construction(begin, end, node_fill_factor, leaf_fill_factor);
1002  assert(m_leaf_cache.nfixed() == 0);
1003  assert(m_node_cache.nfixed() == 0);
1004  }
1005 
1006  template <class InputIterator>
1007  btree(InputIterator begin,
1008  InputIterator end,
1009  unsigned_type node_cache_size_in_bytes,
1010  unsigned_type leaf_cache_size_in_bytes,
1011  bool range_sorted = false,
1012  double node_fill_factor = 0.75,
1013  double leaf_fill_factor = 0.6)
1014  : m_node_cache(node_cache_size_in_bytes, this, m_key_compare),
1015  m_leaf_cache(leaf_cache_size_in_bytes, this, m_key_compare),
1016  m_iterator_map(this),
1017  m_size(0),
1018  m_height(2),
1019  m_prefetching_enabled(true),
1020  m_bm(block_manager::get_instance())
1021  {
1022  STXXL_VERBOSE1("Creating a btree, addr=" << this);
1023  STXXL_VERBOSE1(" bytes in a node: " << node_bid_type::size);
1024  STXXL_VERBOSE1(" bytes in a leaf: " << leaf_bid_type::size);
1025 
1026  if (range_sorted == false)
1027  {
1028  create_empty_leaf();
1029  insert(begin, end);
1030  assert(m_leaf_cache.nfixed() == 0);
1031  assert(m_node_cache.nfixed() == 0);
1032  return;
1033  }
1034 
1035  bulk_construction(begin, end, node_fill_factor, leaf_fill_factor);
1036  assert(m_leaf_cache.nfixed() == 0);
1037  assert(m_node_cache.nfixed() == 0);
1038  }
1039 
1040  void erase(iterator first, iterator last)
1041  {
1042  if (first == begin() && last == end())
1043  clear();
1044  else
1045  while (first != last)
1046  erase(first++);
1047  }
1048 
1050  {
1051  return m_key_compare;
1052  }
1054  {
1055  return value_compare(m_key_compare);
1056  }
1057 
1058  void swap(btree& obj)
1059  {
1060  std::swap(m_key_compare, obj.m_key_compare); // OK
1061 
1062  std::swap(m_node_cache, obj.m_node_cache); // OK
1063  std::swap(m_leaf_cache, obj.m_leaf_cache); // OK
1064 
1065  std::swap(m_iterator_map, obj.m_iterator_map); // must update all iterators
1066 
1067  std::swap(m_end_iterator, obj.m_end_iterator);
1068  std::swap(m_size, obj.m_size);
1069  std::swap(m_height, obj.m_height);
1070  std::swap(m_alloc_strategy, obj.m_alloc_strategy);
1071  std::swap(m_root_node, obj.m_root_node);
1072  }
1073 
1075  {
1076  m_prefetching_enabled = true;
1077  }
1079  {
1080  m_prefetching_enabled = false;
1081  }
1083  {
1084  return m_prefetching_enabled;
1085  }
1086 
1087  void print_statistics(std::ostream& o) const
1088  {
1089  o << "Node cache statistics:" << std::endl;
1090  m_node_cache.print_statistics(o);
1091  o << "Leaf cache statistics:" << std::endl;
1092  m_leaf_cache.print_statistics(o);
1093  }
1095  {
1096  m_node_cache.reset_statistics();
1097  m_leaf_cache.reset_statistics();
1098  }
1099 };
1100 
1101 template <class KeyType,
1102  class DataType,
1103  class CompareType,
1104  unsigned LogNodeSize,
1105  unsigned LogLeafSize,
1106  class PDAllocStrategy
1107  >
1108 inline bool operator ==
1109  (const btree<KeyType, DataType, CompareType,
1110  LogNodeSize, LogLeafSize, PDAllocStrategy>& a,
1111  const btree<KeyType, DataType, CompareType,
1112  LogNodeSize, LogLeafSize, PDAllocStrategy>& b)
1113 {
1114  return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
1115 }
1116 
1117 template <class KeyType,
1118  class DataType,
1119  class CompareType,
1120  unsigned LogNodeSize,
1121  unsigned LogLeafSize,
1122  class PDAllocStrategy
1123  >
1124 inline bool operator !=
1125  (const btree<KeyType, DataType, CompareType,
1126  LogNodeSize, LogLeafSize, PDAllocStrategy>& a,
1127  const btree<KeyType, DataType, CompareType,
1128  LogNodeSize, LogLeafSize, PDAllocStrategy>& b)
1129 {
1130  return !(a == b);
1131 }
1132 
1133 template <class KeyType,
1134  class DataType,
1135  class CompareType,
1136  unsigned LogNodeSize,
1137  unsigned LogLeafSize,
1138  class PDAllocStrategy
1139  >
1140 inline bool operator <
1141  (const btree<KeyType, DataType, CompareType,
1142  LogNodeSize, LogLeafSize, PDAllocStrategy>& a,
1143  const btree<KeyType, DataType, CompareType,
1144  LogNodeSize, LogLeafSize, PDAllocStrategy>& b)
1145 {
1146  return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
1147 }
1148 
1149 template <class KeyType,
1150  class DataType,
1151  class CompareType,
1152  unsigned LogNodeSize,
1153  unsigned LogLeafSize,
1154  class PDAllocStrategy
1155  >
1156 inline bool operator >
1157  (const btree<KeyType, DataType, CompareType,
1158  LogNodeSize, LogLeafSize, PDAllocStrategy>& a,
1159  const btree<KeyType, DataType, CompareType,
1160  LogNodeSize, LogLeafSize, PDAllocStrategy>& b)
1161 {
1162  return b < a;
1163 }
1164 
1165 template <class KeyType,
1166  class DataType,
1167  class CompareType,
1168  unsigned LogNodeSize,
1169  unsigned LogLeafSize,
1170  class PDAllocStrategy
1171  >
1172 inline bool operator <=
1173  (const btree<KeyType, DataType, CompareType,
1174  LogNodeSize, LogLeafSize, PDAllocStrategy>& a,
1175  const btree<KeyType, DataType, CompareType,
1176  LogNodeSize, LogLeafSize, PDAllocStrategy>& b)
1177 {
1178  return !(b < a);
1179 }
1180 
1181 template <class KeyType,
1182  class DataType,
1183  class CompareType,
1184  unsigned LogNodeSize,
1185  unsigned LogLeafSize,
1186  class PDAllocStrategy
1187  >
1188 inline bool operator >=
1189  (const btree<KeyType, DataType, CompareType,
1190  LogNodeSize, LogLeafSize, PDAllocStrategy>& a,
1191  const btree<KeyType, DataType, CompareType,
1192  LogNodeSize, LogLeafSize, PDAllocStrategy>& b)
1193 {
1194  return !(a < b);
1195 }
1196 
1197 } // namespace btree
1198 
1200 
1201 namespace std {
1202 
1203 template <class KeyType,
1204  class DataType,
1205  class CompareType,
1206  unsigned LogNodeSize,
1207  unsigned LogLeafSize,
1208  class PDAllocStrategy
1209  >
1210 void swap(stxxl::btree::btree<KeyType, DataType, CompareType,
1211  LogNodeSize, LogLeafSize, PDAllocStrategy>& a,
1212  stxxl::btree::btree<KeyType, DataType, CompareType,
1213  LogNodeSize, LogLeafSize, PDAllocStrategy>& b)
1214 {
1215  if (&a != &b)
1216  a.swap(b);
1217 }
1218 
1219 } // namespace std
1220 
1221 #endif // !STXXL_CONTAINERS_BTREE_BTREE_HEADER
bool underflows() const
Definition: node.h:224
#define STXXL_ASSERT(condition)
Definition: verbose.h:220
stxxl::uint64 size_type
Definition: btree.h:49
compat::remove_const< Integral >::type div_ceil(Integral n, Integral2 d)
Definition: utils.h:199
unsigned int m_height
Definition: btree.h:93
size_type size() const
Definition: btree.h:485
btree_const_iterator< self_type > const_iterator
Definition: btree.h:66
iterator_map_type m_iterator_map
Definition: btree.h:91
Block manager class.
Definition: block_manager.h:61
void insert(InputIterator b, InputIterator e)
Definition: btree.h:962
long long int int64
Definition: types.h:38
std::pair< iterator, iterator > equal_range(const key_type &k)
Definition: btree.h:809
unsigned size() const
Definition: leaf.h:228
leaf_cache_type m_leaf_cache
Definition: btree.h:90
void push_back(const value_type &x)
Definition: leaf.h:688
value_type & reference
Definition: btree.h:52
unsigned long long int uint64
Definition: types.h:39
void fuse(const normal_leaf &src)
Definition: leaf.h:535
key_type balance(normal_leaf &left)
Definition: leaf.h:586
iterator m_end_iterator
Definition: btree.h:104
std::pair< const_iterator, const_iterator > equal_range(const key_type &k) const
Definition: btree.h:830
std::map< key_type, node_bid_type, key_compare > root_node_type
Definition: btree.h:98
virtual ~btree()
Definition: btree.h:473
const_iterator end() const
Definition: btree.h:618
info_type info
Per block information element.
Definition: typed_block.h:179
static unsigned max_nelements()
Definition: node.h:226
key_compare m_key_compare
Definition: btree.h:88
btree(InputIterator begin, InputIterator end, unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes, bool range_sorted=false, double node_fill_factor=0.75, double leaf_fill_factor=0.6)
Definition: btree.h:1007
bool underflows() const
Definition: leaf.h:181
bool m_prefetching_enabled
Definition: btree.h:94
void deallocate_children()
Definition: btree.h:236
bid_type & succ()
Definition: leaf.h:186
iterator begin()
Definition: btree.h:558
node_type::block_type node_block_type
Definition: btree.h:72
iterator find(const key_type &k)
Definition: leaf.h:423
block_type & block()
Definition: node.h:218
iterator end()
Definition: btree.h:613
static unsigned max_nelements()
Definition: leaf.h:183
btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy > self_type
Definition: btree.h:45
btree(InputIterator begin, InputIterator end, const key_compare &c_, unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes, bool range_sorted=false, double node_fill_factor=0.75, double leaf_fill_factor=0.6)
Definition: btree.h:971
PDAllocStrategy alloc_strategy_type
Definition: btree.h:47
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
const_iterator lower_bound(const key_type &k) const
Definition: btree.h:719
normal_leaf< key_type, data_type, key_compare, RawLeafSize, self_type > leaf_type
Definition: btree.h:58
node_cache< node_type, self_type > node_cache_type
Definition: btree.h:75
btree(const key_compare &key_compare, unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes)
Definition: btree.h:454
void insert_into_root(const std::pair< key_type, node_bid_type > &splitter)
Definition: btree.h:106
void erase(iterator first, iterator last)
Definition: btree.h:1040
size_type erase(const key_type &k)
Definition: btree.h:850
btree(unsigned_type node_cache_size_in_bytes, unsigned_type leaf_cache_size_in_bytes)
Definition: btree.h:433
iterator lower_bound(const key_type &k)
Definition: btree.h:690
std::pair< iterator, bool > insert(const value_type &x)
Definition: btree.h:500
iterator_map< self_type > iterator_map_type
Definition: btree.h:69
leaf_type::block_type leaf_block_type
Definition: btree.h:60
void fuse_or_balance(root_node_iterator_type uit, CacheType &cache)
Definition: btree.h:167
iterator find(const key_type &k)
Definition: btree.h:628
iterator begin()
Definition: leaf.h:356
std::pair< const key_type, data_type > value_type
Definition: btree.h:51
bool overflows() const
Definition: node.h:223
iterator insert(iterator, const value_type &x)
Definition: btree.h:941
reference back()
Definition: node.h:298
node_cache< leaf_type, self_type > leaf_cache_type
Definition: btree.h:62
root_node_type::const_iterator root_node_const_iterator_type
Definition: btree.h:100
Block containing elements of fixed length.
Definition: typed_block.h:237
void bulk_construction(InputIterator begin, InputIterator end, double node_fill_factor, double leaf_fill_factor)
Definition: btree.h:263
stxxl::int64 difference_type
Definition: btree.h:50
bool prefetching_enabled()
Definition: btree.h:1082
void erase(iterator pos)
Definition: btree.h:929
CompareType key_compare
Definition: btree.h:42
node_cache_type m_node_cache
Definition: btree.h:89
const value_type & const_reference
Definition: btree.h:53
btree_iterator< self_type > iterator
Definition: btree.h:65
void swap(btree &obj)
Definition: btree.h:1058
void enable_prefetching()
Definition: btree.h:1074
block_manager * m_bm
Definition: btree.h:95
void push_back(const value_type &x)
Definition: node.h:750
const_iterator upper_bound(const key_type &k) const
Definition: btree.h:779
bid_type & pred()
Definition: leaf.h:190
root_node_type m_root_node
Definition: btree.h:103
void reset_statistics()
Definition: btree.h:1094
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
size_type count(const key_type &k)
Definition: btree.h:921
void fuse(const normal_node &src)
Definition: node.h:611
#define STXXL_VERBOSE1(x)
Definition: verbose.h:113
value_compare value_comp() const
Definition: btree.h:1053
iterator lower_bound(const key_type &k)
Definition: leaf.h:445
KeyType key_type
Definition: btree.h:40
#define STXXL_THROW2(exception_type, location, error_message)
Throws exception_type with &quot;Error in [location] : [error_message]&quot;.
void deallocate_children(unsigned height)
Definition: node.h:724
static uint_pair max()
return an uint_pair instance containing the largest value possible
Definition: uint_types.h:241
bool overflows() const
Definition: leaf.h:180
iterator begin()
Returns iterator pointing to the first element.
Definition: typed_block.h:92
alloc_strategy_type m_alloc_strategy
Definition: btree.h:96
value_type const * const_pointer
Definition: btree.h:55
normal_node< key_type, key_compare, RawNodeSize, self_type > node_type
Definition: btree.h:71
reference back()
Definition: leaf.h:275
key_type balance(normal_node &left, bool check_constraints=true)
Definition: node.h:629
std::pair< iterator, bool > insert(const value_type &x, std::pair< key_type, bid_type > &splitter)
Definition: leaf.h:302
iterator upper_bound(const key_type &k)
Definition: btree.h:749
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
iterator lower_bound(const key_type &k, unsigned height)
Definition: node.h:483
value_type * pointer
Definition: btree.h:54
size_type erase(const key_type &k)
Definition: leaf.h:506
void print_statistics(std::ostream &o) const
Definition: btree.h:1087
const bid_type & my_bid() const
Definition: leaf.h:233
unsigned size() const
Definition: node.h:253
iterator upper_bound(const key_type &k)
Definition: leaf.h:476
DataType data_type
Definition: btree.h:41
iterator find(const key_type &k, unsigned height)
Definition: node.h:419
size_type max_size() const
Definition: btree.h:490
root_node_type::iterator root_node_iterator_type
Definition: btree.h:99
node_type::bid_type node_bid_type
Definition: btree.h:74
leaf_type::bid_type leaf_bid_type
Definition: btree.h:61
iterator begin(unsigned height)
Definition: node.h:375
const_iterator find(const key_type &k) const
Definition: btree.h:659
ExtIterator find(ExtIterator begin, ExtIterator end, const EqualityComparable &value, int_type nbuffers=0)
External equivalent of std::find, see stxxl::find.
Definition: scan.h:289
void disable_prefetching()
Definition: btree.h:1078
leaf_type::value_compare value_compare
Definition: btree.h:78
External vector type generator.
Definition: vector.h:2602
size_type m_size
Definition: btree.h:92
const_iterator begin() const
Definition: btree.h:587
std::pair< key_type, node_bid_type > root_node_pair_type
Definition: btree.h:101
key_compare key_comp() const
Definition: btree.h:1049
void create_empty_leaf()
Definition: btree.h:225
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
bool empty() const
Definition: btree.h:495
iterator upper_bound(const key_type &k, unsigned height)
Definition: node.h:547