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