13 #ifndef STXXL_CONTAINERS_BTREE__NODE_H
14 #define STXXL_CONTAINERS_BTREE__NODE_H
16 #include <stxxl/bits/containers/btree/iterator.h>
17 #include <stxxl/bits/containers/btree/node_cache.h>
20 __STXXL_BEGIN_NAMESPACE
24 template <
class NodeType,
class BTreeType>
27 template <
class KeyType_,
class KeyCmp_,
unsigned RawSize_,
class BTreeType>
28 class normal_node :
private noncopyable
31 typedef normal_node<KeyType_, KeyCmp_, RawSize_, BTreeType> SelfType;
33 friend class node_cache<SelfType, BTreeType>;
35 typedef KeyType_ key_type;
36 typedef KeyCmp_ key_compare;
42 typedef bid_type node_bid_type;
43 typedef SelfType node_type;
44 typedef std::pair<key_type, bid_type> value_type;
45 typedef value_type & reference;
46 typedef const value_type & const_reference;
59 min_size = nelements / 2
61 typedef typename block_type::iterator block_iterator;
62 typedef typename block_type::const_iterator block_const_iterator;
64 typedef BTreeType btree_type;
65 typedef typename btree_type::size_type size_type;
66 typedef typename btree_type::iterator iterator;
67 typedef typename btree_type::const_iterator const_iterator;
69 typedef typename btree_type::value_type btree_value_type;
70 typedef typename btree_type::leaf_bid_type leaf_bid_type;
71 typedef typename btree_type::leaf_type leaf_type;
73 typedef node_cache<normal_node, btree_type> node_cache_type;
76 struct value_compare :
public std::binary_function<value_type, bid_type, bool>
80 value_compare(key_compare c) : comp(c) { }
82 bool operator () (
const value_type & x,
const value_type & y)
const
84 return comp(x.first, y.first);
94 template <
class BIDType>
95 std::pair<key_type, bid_type> insert(
const std::pair<key_type, BIDType> & splitter,
96 const block_iterator & place2insert)
98 std::pair<key_type, bid_type> result(key_compare::max_value(), bid_type());
101 assert(vcmp_(*place2insert, splitter) || vcmp_(splitter, *place2insert));
103 block_iterator cur = block_->begin() + size() - 1;
104 for ( ; cur >= place2insert; --cur)
108 *place2insert = splitter;
110 ++(block_->info.cur_size);
112 if (size() > max_nelements())
114 STXXL_VERBOSE1(
"btree::normal_node::insert overflow happened, splitting");
117 btree_->node_cache_.get_new_node(NewBid);
118 normal_node * NewNode = btree_->node_cache_.get_node(NewBid,
true);
121 const unsigned end_of_smaller_part = size() / 2;
123 result.first = ((*block_)[end_of_smaller_part - 1]).first;
124 result.second = NewBid;
127 const unsigned old_size = size();
129 std::copy(block_->begin(), block_->begin() + end_of_smaller_part, NewNode->block_->begin());
130 NewNode->block_->info.cur_size = end_of_smaller_part;
132 std::copy(block_->begin() + end_of_smaller_part,
133 block_->begin() + old_size, block_->begin());
134 block_->info.cur_size = old_size - end_of_smaller_part;
135 assert(size() + NewNode->size() == old_size);
137 btree_->node_cache_.unfix_node(NewBid);
139 STXXL_VERBOSE1(
"btree::normal_node split leaf " <<
this
140 <<
" splitter: " << result.first);
146 template <
class CacheType>
147 void fuse_or_balance(block_iterator UIt, CacheType & cache_)
149 typedef typename CacheType::node_type local_node_type;
150 typedef typename local_node_type::bid_type local_bid_type;
152 block_iterator leftIt, rightIt;
153 if (UIt == (block_->begin() + size() - 1))
155 assert(UIt != block_->begin());
163 assert(rightIt != (block_->begin() + size()));
167 local_bid_type LeftBid = (local_bid_type)leftIt->second;
168 local_bid_type RightBid = (local_bid_type)rightIt->second;
169 local_node_type * LeftNode = cache_.get_node(LeftBid,
true);
170 local_node_type * RightNode = cache_.get_node(RightBid,
true);
172 const unsigned TotalSize = LeftNode->size() + RightNode->size();
173 if (TotalSize <= RightNode->max_nelements())
176 RightNode->fuse(*LeftNode);
178 cache_.unfix_node(RightBid);
179 cache_.delete_node(LeftBid);
181 std::copy(leftIt + 1, block_->begin() + size(), leftIt);
182 --(block_->info.cur_size);
188 key_type NewSplitter = RightNode->balance(*LeftNode);
191 leftIt->first = NewSplitter;
192 assert(vcmp_(*leftIt, *rightIt));
194 cache_.unfix_node(LeftBid);
195 cache_.unfix_node(RightBid);
200 virtual ~normal_node()
205 normal_node(btree_type * btree__,
207 block_(new block_type),
212 assert(min_nelements() >= 2);
213 assert(2 * min_nelements() - 1 <= max_nelements());
214 assert(max_nelements() <= nelements);
223 bool overflows()
const {
return block_->info.cur_size > max_nelements(); }
224 bool underflows()
const {
return block_->info.cur_size < min_nelements(); }
226 unsigned max_nelements()
const {
return max_size; }
227 unsigned min_nelements()
const {
return min_size; }
253 unsigned size()
const
255 return block_->info.cur_size;
258 bid_type my_bid()
const
260 return block_->info.me;
273 assert(bid == my_bid());
279 return block_->read(bid);
282 void init(
const bid_type & my_bid_)
284 block_->info.me = my_bid_;
285 block_->info.cur_size = 0;
288 reference operator [] (
int i)
293 const_reference operator [] (
int i)
const
300 return (*block_)[size() - 1];
305 return *(block_->begin());
308 const_reference back()
const
310 return (*block_)[size() - 1];
313 const_reference front()
const
315 return *(block_->begin());
319 std::pair<iterator, bool> insert(
320 const btree_value_type & x,
322 std::pair<key_type, bid_type> & splitter)
324 assert(size() <= max_nelements());
325 splitter.first = key_compare::max_value();
327 value_type Key2Search(x.first, bid_type());
329 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
331 assert(it != (block_->begin() + size()));
333 bid_type found_bid = it->second;
337 STXXL_VERBOSE1(
"btree::normal_node Inserting new value into a leaf");
338 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)it->second,
true);
340 std::pair<key_type, leaf_bid_type> BotSplitter;
341 std::pair<iterator, bool> result = Leaf->insert(x, BotSplitter);
342 btree_->leaf_cache_.unfix_node((leaf_bid_type)it->second);
344 if (!(cmp_(key_compare::max_value(), BotSplitter.first) ||
345 cmp_(BotSplitter.first, key_compare::max_value())))
349 STXXL_VERBOSE1(
"btree::normal_node Inserting new value in *this");
351 splitter = insert(BotSplitter, it);
357 STXXL_VERBOSE1(
"btree::normal_node Inserting new value into a node");
358 node_type * Node = btree_->node_cache_.get_node((node_bid_type)it->second,
true);
360 std::pair<key_type, node_bid_type> BotSplitter;
361 std::pair<iterator, bool> result = Node->insert(x, height - 1, BotSplitter);
362 btree_->node_cache_.unfix_node((node_bid_type)it->second);
364 if (!(cmp_(key_compare::max_value(), BotSplitter.first) ||
365 cmp_(BotSplitter.first, key_compare::max_value())))
369 STXXL_VERBOSE1(
"btree::normal_node Inserting new value in *this");
371 splitter = insert(BotSplitter, it);
377 iterator begin(
unsigned height)
379 bid_type FirstBid = block_->begin()->second;
383 STXXL_VERBOSE1(
"btree::node retrieveing begin() from the first leaf");
384 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)FirstBid);
386 return Leaf->begin();
390 STXXL_VERBOSE1(
"btree: retrieveing begin() from the first node");
391 node_type * Node = btree_->node_cache_.get_node((node_bid_type)FirstBid,
true);
393 iterator result = Node->begin(height - 1);
394 btree_->node_cache_.unfix_node((node_bid_type)FirstBid);
399 const_iterator begin(
unsigned height)
const
401 bid_type FirstBid = block_->begin()->second;
405 STXXL_VERBOSE1(
"btree::node retrieveing begin() from the first leaf");
406 leaf_type
const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)FirstBid);
408 return Leaf->begin();
412 STXXL_VERBOSE1(
"btree: retrieveing begin() from the first node");
413 node_type
const * Node = btree_->node_cache_.get_const_node((node_bid_type)FirstBid,
true);
415 const_iterator result = Node->begin(height - 1);
416 btree_->node_cache_.unfix_node((node_bid_type)FirstBid);
421 iterator
find(
const key_type & k,
unsigned height)
423 value_type Key2Search(k, bid_type());
426 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
428 assert(it != (block_->begin() + size()));
430 bid_type found_bid = it->second;
434 STXXL_VERBOSE1(
"Searching in a leaf");
435 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid,
true);
437 iterator result = Leaf->find(k);
438 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid);
444 STXXL_VERBOSE1(
"Searching in a node");
445 node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid,
true);
447 iterator result = Node->find(k, height - 1);
448 btree_->node_cache_.unfix_node((node_bid_type)found_bid);
453 const_iterator
find(
const key_type & k,
unsigned height)
const
455 value_type Key2Search(k, bid_type());
458 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
460 assert(it != (block_->begin() + size()));
462 bid_type found_bid = it->second;
466 STXXL_VERBOSE1(
"Searching in a leaf");
467 leaf_type
const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)found_bid,
true);
469 const_iterator result = Leaf->find(k);
470 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid);
476 STXXL_VERBOSE1(
"Searching in a node");
477 node_type
const * Node = btree_->node_cache_.get_const_node((node_bid_type)found_bid,
true);
479 const_iterator result = Node->find(k, height - 1);
480 btree_->node_cache_.unfix_node((node_bid_type)found_bid);
485 iterator lower_bound(
const key_type & k,
unsigned height)
487 value_type Key2Search(k, bid_type());
488 assert(!vcmp_(back(), Key2Search));
490 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
492 assert(it != (block_->begin() + size()));
494 bid_type found_bid = it->second;
498 STXXL_VERBOSE1(
"Searching lower bound in a leaf");
499 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid,
true);
501 iterator result = Leaf->lower_bound(k);
502 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid);
508 STXXL_VERBOSE1(
"Searching lower bound in a node");
509 node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid,
true);
511 iterator result = Node->lower_bound(k, height - 1);
512 btree_->node_cache_.unfix_node((node_bid_type)found_bid);
517 const_iterator lower_bound(
const key_type & k,
unsigned height)
const
519 value_type Key2Search(k, bid_type());
520 assert(!vcmp_(back(), Key2Search));
522 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
524 assert(it != (block_->begin() + size()));
526 bid_type found_bid = it->second;
530 STXXL_VERBOSE1(
"Searching lower bound in a leaf");
531 leaf_type
const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)found_bid,
true);
533 const_iterator result = Leaf->lower_bound(k);
534 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid);
540 STXXL_VERBOSE1(
"Searching lower bound in a node");
541 node_type
const * Node = btree_->node_cache_.get_const_node((node_bid_type)found_bid,
true);
543 const_iterator result = Node->lower_bound(k, height - 1);
544 btree_->node_cache_.unfix_node((node_bid_type)found_bid);
549 iterator upper_bound(
const key_type & k,
unsigned height)
551 value_type Key2Search(k, bid_type());
552 assert(vcmp_(Key2Search, back()));
554 std::upper_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
556 assert(it != (block_->begin() + size()));
558 bid_type found_bid = it->second;
562 STXXL_VERBOSE1(
"Searching upper bound in a leaf");
563 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid,
true);
565 iterator result = Leaf->upper_bound(k);
566 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid);
572 STXXL_VERBOSE1(
"Searching upper bound in a node");
573 node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid,
true);
575 iterator result = Node->upper_bound(k, height - 1);
576 btree_->node_cache_.unfix_node((node_bid_type)found_bid);
581 const_iterator upper_bound(
const key_type & k,
unsigned height)
const
583 value_type Key2Search(k, bid_type());
584 assert(vcmp_(Key2Search, back()));
586 std::upper_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
588 assert(it != (block_->begin() + size()));
590 bid_type found_bid = it->second;
594 STXXL_VERBOSE1(
"Searching upper bound in a leaf");
595 leaf_type
const * Leaf = btree_->leaf_cache_.get_const_node((leaf_bid_type)found_bid,
true);
597 const_iterator result = Leaf->upper_bound(k);
598 btree_->leaf_cache_.unfix_node((leaf_bid_type)found_bid);
604 STXXL_VERBOSE1(
"Searching upper bound in a node");
605 node_type
const * Node = btree_->node_cache_.get_const_node((node_bid_type)found_bid,
true);
607 const_iterator result = Node->upper_bound(k, height - 1);
608 btree_->node_cache_.unfix_node((node_bid_type)found_bid);
613 void fuse(
const normal_node & Src)
615 assert(vcmp_(Src.back(), front()));
616 const unsigned SrcSize = Src.size();
618 block_iterator cur = block_->begin() + size() - 1;
619 block_const_iterator begin = block_->begin();
621 for ( ; cur >= begin; --cur)
622 *(cur + SrcSize) = *cur;
626 std::copy(Src.block_->begin(), Src.block_->begin() + SrcSize, block_->begin());
628 block_->info.cur_size += SrcSize;
632 key_type balance(normal_node & Left)
634 const unsigned TotalSize = Left.size() + size();
635 unsigned newLeftSize = TotalSize / 2;
636 assert(newLeftSize <= Left.max_nelements());
637 assert(newLeftSize >= Left.min_nelements());
638 unsigned newRightSize = TotalSize - newLeftSize;
639 assert(newRightSize <= max_nelements());
640 assert(newRightSize >= min_nelements());
642 assert(vcmp_(Left.back(), front()) || size() == 0);
644 if (newLeftSize < Left.size())
646 const unsigned nEl2Move = Left.size() - newLeftSize;
648 block_iterator cur = block_->begin() + size() - 1;
649 block_const_iterator begin = block_->begin();
651 for ( ; cur >= begin; --cur)
652 *(cur + nEl2Move) = *cur;
656 std::copy(Left.block_->begin() + newLeftSize,
657 Left.block_->begin() + Left.size(), block_->begin());
661 assert(newRightSize < size());
663 const unsigned nEl2Move = size() - newRightSize;
666 std::copy(block_->begin(),
667 block_->begin() + nEl2Move, Left.block_->begin() + Left.size());
669 std::copy(block_->begin() + nEl2Move,
670 block_->begin() + size(), block_->begin());
673 block_->info.cur_size = newRightSize;
674 Left.block_->info.cur_size = newLeftSize;
676 return Left.back().first;
679 size_type erase(
const key_type & k,
unsigned height)
681 value_type Key2Search(k, bid_type());
684 std::lower_bound(block_->begin(), block_->begin() + size(), Key2Search, vcmp_);
686 assert(it != (block_->begin() + size()));
688 bid_type found_bid = it->second;
694 STXXL_VERBOSE1(
"btree::normal_node Deleting key from a leaf");
695 leaf_type * Leaf = btree_->leaf_cache_.get_node((leaf_bid_type)found_bid,
true);
697 size_type result = Leaf->erase(k);
698 btree_->leaf_cache_.unfix_node((leaf_bid_type)it->second);
699 if (!Leaf->underflows())
703 STXXL_VERBOSE1(
"btree::normal_node Fusing or rebalancing a leaf");
704 fuse_or_balance(it, btree_->leaf_cache_);
710 STXXL_VERBOSE1(
"btree::normal_node Deleting key from a node");
711 node_type * Node = btree_->node_cache_.get_node((node_bid_type)found_bid,
true);
713 size_type result = Node->erase(k, height - 1);
714 btree_->node_cache_.unfix_node((node_bid_type)found_bid);
715 if (!Node->underflows())
719 STXXL_VERBOSE1(
"btree::normal_node Fusing or rebalancing a node");
720 fuse_or_balance(it, btree_->node_cache_);
725 void deallocate_children(
unsigned height)
730 block_const_iterator it = block().begin();
731 for ( ; it != block().begin() + size(); ++it)
734 btree_->leaf_cache_.delete_node((leaf_bid_type)it->second);
739 block_const_iterator it = block().begin();
740 for ( ; it != block().begin() + size(); ++it)
742 node_type * Node = btree_->node_cache_.get_node((node_bid_type)it->second);
744 Node->deallocate_children(height - 1);
746 btree_->node_cache_.delete_node((node_bid_type)it->second);
751 void push_back(
const value_type & x)
754 ++(block_->info.cur_size);
760 __STXXL_END_NAMESPACE