/usr/include/stxxl/bits/containers/btree
Edit: /usr/include/stxxl/bits/containers/btree/leaf.h (23869B)
/***************************************************************************
* include/stxxl/bits/containers/btree/leaf.h
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2006 Roman Dementiev
*
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
**************************************************************************/
#ifndef STXXL_CONTAINERS_BTREE_LEAF_HEADER
#define STXXL_CONTAINERS_BTREE_LEAF_HEADER
#include
#include
STXXL_BEGIN_NAMESPACE
namespace btree {
template
class node_cache;
template
class normal_leaf : private noncopyable
{
public:
typedef normal_leaf self_type;
friend class node_cache;
typedef KeyType key_type;
typedef DataType data_type;
typedef KeyCmp key_compare;
typedef std::pair value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
enum {
raw_size = RawSize
};
typedef BID bid_type;
struct metainfo_type
{
bid_type me, pred, succ;
unsigned cur_size;
};
typedef typed_block block_type;
enum {
nelements = block_type::size - 1,
max_size = nelements,
min_size = nelements / 2
};
typedef BTreeType btree_type;
typedef typename btree_type::size_type size_type;
typedef btree_iterator_base iterator_base;
typedef btree_iterator iterator;
typedef btree_const_iterator const_iterator;
typedef node_cache leaf_cache_type;
public:
struct value_compare : public std::binary_function
{
key_compare comp;
value_compare(key_compare c) : comp(c) { }
bool operator () (const value_type& x, const value_type& y) const
{
return comp(x.first, y.first);
}
};
private:
block_type* m_block;
btree_type* m_btree;
key_compare m_cmp;
value_compare m_vcmp;
void split(std::pair& splitter)
{
bid_type new_bid;
m_btree->m_leaf_cache.get_new_node(new_bid); // new (left) leaf
normal_leaf* new_leaf = m_btree->m_leaf_cache.get_node(new_bid, true);
assert(new_leaf);
// update links
new_leaf->succ() = my_bid();
normal_leaf* pred_leaf = NULL;
if (pred().valid())
{
new_leaf->pred() = pred();
pred_leaf = m_btree->m_leaf_cache.get_node(pred());
assert(pred_leaf);
assert(m_vcmp(pred_leaf->back(), front()));
pred_leaf->succ() = new_bid;
}
pred() = new_bid;
typedef std::vector iterators2fix_type;
iterators2fix_type iterators2fix;
m_btree->m_iterator_map.find(my_bid(), 0, size(), iterators2fix);
const unsigned end_of_smaller_part = size() / 2;
splitter.first = ((*m_block)[end_of_smaller_part - 1]).first;
splitter.second = new_bid;
const unsigned old_size = size();
// copy the smaller part
std::copy(m_block->begin(), m_block->begin() + end_of_smaller_part,
new_leaf->m_block->begin());
new_leaf->m_block->info.cur_size = end_of_smaller_part;
// copy the larger part
std::copy(m_block->begin() + end_of_smaller_part,
m_block->begin() + old_size, m_block->begin());
m_block->info.cur_size = old_size - end_of_smaller_part;
assert(size() + new_leaf->size() == old_size);
// fix iterators
for (typename iterators2fix_type::iterator it2fix = iterators2fix.begin();
it2fix != iterators2fix.end(); ++it2fix)
{
m_btree->m_iterator_map.unregister_iterator(**it2fix);
if ((*it2fix)->pos < end_of_smaller_part) // belongs to the smaller part
(*it2fix)->bid = new_bid;
else
(*it2fix)->pos -= end_of_smaller_part;
m_btree->m_iterator_map.register_iterator(**it2fix);
}
STXXL_VERBOSE1("btree::normal_leaf split leaf " << this
<< " splitter: " << splitter.first);
#if STXXL_VERBOSE_LEVEL >= 1
if (pred_leaf)
{
STXXL_VERBOSE1("btree::normal_leaf pred_part.smallest = " << pred_leaf->front().first);
STXXL_VERBOSE1("btree::normal_leaf pred_part.largest = " << pred_leaf->back().first);
}
#endif
STXXL_VERBOSE1("btree::normal_leaf smaller_part.smallest = " << new_leaf->front().first);
STXXL_VERBOSE1("btree::normal_leaf smaller_part.largest = " << new_leaf->back().first);
STXXL_VERBOSE1("btree::normal_leaf larger_part.smallest = " << front().first);
STXXL_VERBOSE1("btree::normal_leaf larger_part.largest = " << back().first);
m_btree->m_leaf_cache.unfix_node(new_bid);
}
public:
virtual ~normal_leaf()
{
delete m_block;
}
normal_leaf(btree_type* btree,
key_compare cmp)
: m_block(new block_type),
m_btree(btree),
m_cmp(cmp),
m_vcmp(cmp)
{
assert(min_nelements() >= 2);
assert(2 * min_nelements() - 1 <= max_nelements());
assert(max_nelements() <= nelements);
assert(unsigned(block_type::size) >= nelements + 1); // extra space for an overflow
}
bool overflows() const { return m_block->info.cur_size > max_nelements(); }
bool underflows() const { return m_block->info.cur_size < min_nelements(); }
static unsigned max_nelements() { return max_size; }
static unsigned min_nelements() { return min_size; }
bid_type & succ()
{
return m_block->info.succ;
}
bid_type & pred()
{
return m_block->info.pred;
}
const bid_type & succ() const
{
return m_block->info.succ;
}
const bid_type & pred() const
{
return m_block->info.pred;
}
/*
template
normal_leaf(InputIterator begin_, InputIterator end_,
btree_type * btree,
key_compare cmp):
m_block(new block_type),
m_btree(btree),
m_cmp(cmp),
m_vcmp(cmp)
{
assert(min_nelements() >=2);
assert(2*min_nelements() - 1 <= max_nelements());
assert(max_nelements() <= nelements);
assert(unsigned(block_type::size) >= nelements +1); // extra space for an overflow element
unsigned new_size = end_ - begin_;
assert(new_size <= max_nelements());
assert(new_size >= min_nelements());
std::copy(begin_,end_,m_block->begin());
assert(stxxl::is_sorted(m_block->begin(),m_block->begin() + new_size, m_vcmp));
m_block->info.cur_size = new_size;
}*/
unsigned size() const
{
return m_block->info.cur_size;
}
const bid_type & my_bid() const
{
return m_block->info.me;
}
void save()
{
request_ptr req = m_block->write(my_bid());
req->wait();
}
request_ptr load(const bid_type& bid)
{
request_ptr req = m_block->read(bid);
req->wait();
assert(bid == my_bid());
return req;
}
request_ptr prefetch(const bid_type& bid)
{
return m_block->read(bid);
}
void init(const bid_type& my_bid_)
{
m_block->info.me = my_bid_;
m_block->info.succ = bid_type();
m_block->info.pred = bid_type();
m_block->info.cur_size = 0;
}
reference operator [] (unsigned_type i)
{
return (*m_block)[i];
}
const_reference operator [] (unsigned_type i) const
{
return (*m_block)[i];
}
reference back()
{
return (*m_block)[size() - 1];
}
reference front()
{
return *(m_block->begin());
}
const_reference back() const
{
return (*m_block)[size() - 1];
}
const_reference front() const
{
return *(m_block->begin());
}
void dump()
{
STXXL_VERBOSE2("Dump of leaf " << this);
for (unsigned i = 0; i < size(); ++i)
STXXL_VERBOSE2((*this)[i].first << " " << (*this)[i].second);
}
std::pair insert(
const value_type& x,
std::pair& splitter)
{
assert(size() <= max_nelements());
splitter.first = key_compare::max_value();
typename block_type::iterator it =
std::lower_bound(m_block->begin(), m_block->begin() + size(), x, m_vcmp);
if (!(m_vcmp(*it, x) || m_vcmp(x, *it)) && it != (m_block->begin() + size())) // *it == x
{
// already exists
return std::pair(
iterator(m_btree, my_bid(), unsigned(it - m_block->begin())),
false);
}
typename block_type::iterator cur = m_block->begin() + size() - 1;
for ( ; cur >= it; --cur)
*(cur + 1) = *cur;
// move elements to make space for the new element
*it = x;
std::vector iterators2fix;
m_btree->m_iterator_map.find(my_bid(), unsigned(it - m_block->begin()), size(), iterators2fix);
typename std::vector::iterator it2fix = iterators2fix.begin();
for ( ; it2fix != iterators2fix.end(); ++it2fix)
{
m_btree->m_iterator_map.unregister_iterator(**it2fix);
++((*it2fix)->pos); // fixing iterators
m_btree->m_iterator_map.register_iterator(**it2fix);
}
++(m_block->info.cur_size);
std::pair result(iterator(m_btree, my_bid(), unsigned(it - m_block->begin())), true);
if (size() <= max_nelements())
{
// no overflow
dump();
return result;
}
// overflow
split(splitter);
return result;
}
iterator begin()
{
return iterator(m_btree, my_bid(), 0);
}
const_iterator begin() const
{
return const_iterator(m_btree, my_bid(), 0);
}
iterator end()
{
return iterator(m_btree, my_bid(), size());
}
void increment_iterator(iterator_base& it) const
{
assert(it.bid == my_bid());
assert(it.pos != size());
m_btree->m_iterator_map.unregister_iterator(it);
++(it.pos);
if (it.pos == size() && succ().valid())
{
// run to the end of the leaf
STXXL_VERBOSE1("btree::normal_leaf jumping to the next block");
it.pos = 0;
it.bid = succ();
}
// increment of pos from 0 to 1
else if (it.pos == 1 && m_btree->m_prefetching_enabled)
{
// prefetch the succ leaf
if (succ().valid())
m_btree->m_leaf_cache.prefetch_node(succ());
}
m_btree->m_iterator_map.register_iterator(it);
}
void decrement_iterator(iterator_base& it) const
{
assert(it.bid == my_bid());
m_btree->m_iterator_map.unregister_iterator(it);
if (it.pos == 0)
{
assert(pred().valid());
it.bid = pred();
normal_leaf const* pred_leaf = m_btree->m_leaf_cache.get_const_node(pred(), true);
assert(pred_leaf);
it.pos = pred_leaf->size() - 1;
// prefetch the pred leaf of pred_leaf
if (m_btree->m_prefetching_enabled && pred_leaf->pred().valid())
m_btree->m_leaf_cache.prefetch_node(pred_leaf->pred());
m_btree->m_leaf_cache.unfix_node(pred());
}
else
--it.pos;
m_btree->m_iterator_map.register_iterator(it);
}
iterator find(const key_type& k)
{
value_type search_val(k, data_type());
typename block_type::iterator lb =
std::lower_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
if (lb == m_block->begin() + size() || lb->first != k)
return m_btree->end();
return iterator(m_btree, my_bid(), unsigned(lb - m_block->begin()));
}
const_iterator find(const key_type& k) const
{
value_type search_val(k, data_type());
typename block_type::iterator lb =
std::lower_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
if (lb == m_block->begin() + size() || lb->first != k)
return m_btree->end();
return const_iterator(m_btree, my_bid(), unsigned(lb - m_block->begin()));
}
iterator lower_bound(const key_type& k)
{
value_type search_val(k, data_type());
typename block_type::iterator lb =
std::lower_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
// lower_bound is in the succ block
if (lb == m_block->begin() + size() && succ().valid())
{
return iterator(m_btree, succ(), 0);
}
return iterator(m_btree, my_bid(), unsigned(lb - m_block->begin()));
}
const_iterator lower_bound(const key_type& k) const
{
value_type search_val(k, data_type());
typename block_type::iterator lb =
std::lower_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
// lower_bound is in the succ block
if (lb == m_block->begin() + size() && succ().valid())
{
return iterator(m_btree, succ(), 0);
}
return const_iterator(m_btree, my_bid(), unsigned(lb - m_block->begin()));
}
iterator upper_bound(const key_type& k)
{
value_type search_val(k, data_type());
typename block_type::iterator lb =
std::upper_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
// upper_bound is in the succ block
if (lb == m_block->begin() + size() && succ().valid())
{
return iterator(m_btree, succ(), 0);
}
return iterator(m_btree, my_bid(), unsigned(lb - m_block->begin()));
}
const_iterator upper_bound(const key_type& k) const
{
value_type search_val(k, data_type());
typename block_type::iterator lb =
std::upper_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
// upper_bound is in the succ block
if (lb == m_block->begin() + size() && succ().valid())
{
return const_iterator(m_btree, succ(), 0);
}
return const_iterator(m_btree, my_bid(), unsigned(lb - m_block->begin()));
}
size_type erase(const key_type& k)
{
value_type search_val(k, data_type());
typename block_type::iterator it =
std::lower_bound(m_block->begin(), m_block->begin() + size(), search_val, m_vcmp);
if (it == m_block->begin() + size() || it->first != k)
return 0;
// no such element
// move elements one position left
std::copy(it + 1, m_block->begin() + size(), it);
std::vector iterators2fix;
m_btree->m_iterator_map.find(my_bid(), unsigned(it + 1 - m_block->begin()), size(), iterators2fix);
typename std::vector::iterator it2fix = iterators2fix.begin();
for ( ; it2fix != iterators2fix.end(); ++it2fix)
{
STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) << " (pos--)");
m_btree->m_iterator_map.unregister_iterator(**it2fix);
--((*it2fix)->pos); // fixing iterators
m_btree->m_iterator_map.register_iterator(**it2fix);
}
--(m_block->info.cur_size);
return 1;
}
void fuse(const normal_leaf& src)
{
STXXL_VERBOSE1("btree::normal_leaf Fusing");
assert(m_vcmp(src.back(), front()));
const unsigned src_size = src.size();
typename block_type::iterator cur = m_block->begin() + size() - 1;
typename block_type::const_iterator begin = m_block->begin();
for ( ; cur >= begin; --cur)
*(cur + src_size) = *cur;
// move elements to make space for Src elements
// copy Src to *this leaf
std::copy(src.m_block->begin(), src.m_block->begin() + src_size, m_block->begin());
std::vector iterators2fix;
m_btree->m_iterator_map.find(my_bid(), 0, size(), iterators2fix);
typename std::vector::iterator it2fix = iterators2fix.begin();
for ( ; it2fix != iterators2fix.end(); ++it2fix)
{
STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
" (pos+" << src_size << ")");
m_btree->m_iterator_map.unregister_iterator(**it2fix);
((*it2fix)->pos) += src_size; // fixing iterators
m_btree->m_iterator_map.register_iterator(**it2fix);
}
iterators2fix.clear();
m_btree->m_iterator_map.find(src.my_bid(), 0, src_size, iterators2fix);
for (it2fix = iterators2fix.begin(); it2fix != iterators2fix.end(); ++it2fix)
{
STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
" (bid=" << my_bid() << ")");
m_btree->m_iterator_map.unregister_iterator(**it2fix);
((*it2fix)->bid) = my_bid(); // fixing iterators
m_btree->m_iterator_map.register_iterator(**it2fix);
}
m_block->info.cur_size += src_size;
// update links
pred() = src.pred();
if (pred().valid())
{ // update successor link
normal_leaf* new_pred = m_btree->m_leaf_cache.get_node(pred());
assert(new_pred);
new_pred->succ() = my_bid();
}
}
key_type balance(normal_leaf& left)
{
STXXL_VERBOSE1("btree::normal_leaf Balancing leaves with bids " <<
left.my_bid() << " and " << my_bid());
const unsigned total_size = left.size() + size();
unsigned new_left_size = total_size / 2;
assert(new_left_size <= left.max_nelements());
assert(new_left_size >= left.min_nelements());
unsigned new_right_size = total_size - new_left_size;
assert(new_right_size <= max_nelements());
assert(new_right_size >= min_nelements());
assert(m_vcmp(left.back(), front()) || size() == 0);
if (new_left_size < left.size())
{
// #elements to move from left to *this
const unsigned nEl2Move = left.size() - new_left_size;
typename block_type::iterator cur = m_block->begin() + size() - 1;
typename block_type::const_iterator begin = m_block->begin();
for ( ; cur >= begin; --cur)
*(cur + nEl2Move) = *cur;
// move elements to make space for Src elements
// copy Left to *this leaf
std::copy(left.m_block->begin() + new_left_size,
left.m_block->begin() + left.size(), m_block->begin());
std::vector iterators2fix1;
std::vector iterators2fix2;
m_btree->m_iterator_map.find(my_bid(), 0, size(), iterators2fix1);
m_btree->m_iterator_map.find(left.my_bid(), new_left_size, left.size(), iterators2fix2);
typename std::vector::iterator it2fix = iterators2fix1.begin();
for ( ; it2fix != iterators2fix1.end(); ++it2fix)
{
STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
" (pos+" << nEl2Move << ")");
m_btree->m_iterator_map.unregister_iterator(**it2fix);
((*it2fix)->pos) += nEl2Move; // fixing iterators
m_btree->m_iterator_map.register_iterator(**it2fix);
}
it2fix = iterators2fix2.begin();
for ( ; it2fix != iterators2fix2.end(); ++it2fix)
{
STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
" (pos-" << new_left_size << " bid=" << my_bid() << ")");
m_btree->m_iterator_map.unregister_iterator(**it2fix);
((*it2fix)->bid) = my_bid(); // fixing iterators
((*it2fix)->pos) -= new_left_size; // fixing iterators
m_btree->m_iterator_map.register_iterator(**it2fix);
}
}
else
{
assert(new_right_size < size());
const unsigned nEl2Move = size() - new_right_size; // #elements to move from *this to Left
// copy *this to Left
std::copy(m_block->begin(),
m_block->begin() + nEl2Move, left.m_block->begin() + left.size());
// move elements in *this
std::copy(m_block->begin() + nEl2Move,
m_block->begin() + size(), m_block->begin());
std::vector iterators2fix1;
std::vector iterators2fix2;
m_btree->m_iterator_map.find(my_bid(), nEl2Move, size(), iterators2fix1);
m_btree->m_iterator_map.find(my_bid(), 0, nEl2Move - 1, iterators2fix2);
typename std::vector::iterator it2fix = iterators2fix1.begin();
for ( ; it2fix != iterators2fix1.end(); ++it2fix)
{
STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
" (pos-" << nEl2Move << ")");
m_btree->m_iterator_map.unregister_iterator(**it2fix);
((*it2fix)->pos) -= nEl2Move; // fixing iterators
m_btree->m_iterator_map.register_iterator(**it2fix);
}
it2fix = iterators2fix2.begin();
for ( ; it2fix != iterators2fix2.end(); ++it2fix)
{
STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
" (pos+" << left.size() << " bid=" << left.my_bid() << ")");
m_btree->m_iterator_map.unregister_iterator(**it2fix);
((*it2fix)->bid) = left.my_bid(); // fixing iterators
((*it2fix)->pos) += left.size(); // fixing iterators
m_btree->m_iterator_map.register_iterator(**it2fix);
}
}
m_block->info.cur_size = new_right_size; // update size
left.m_block->info.cur_size = new_left_size; // update size
return left.back().first;
}
void push_back(const value_type& x)
{
(*this)[size()] = x;
++(m_block->info.cur_size);
}
};
} // namespace btree
STXXL_END_NAMESPACE
#endif // !STXXL_CONTAINERS_BTREE_LEAF_HEADER