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