leaf.h

Go to the documentation of this file.

/***************************************************************************
 *  include/stxxl/bits/containers/btree/leaf.h
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 2006 Roman Dementiev <[email protected]>
 *
 *  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 <stxxl/bits/containers/btree/iterator.h>
#include <stxxl/bits/containers/btree/node_cache.h>


STXXL_BEGIN_NAMESPACE

namespace btree {

template <class NodeType, class BTreeType>
class node_cache;

template <class KeyType_, class DataType_, class KeyCmp_, unsigned RawSize_, class BTreeType>
class normal_leaf : private noncopyable
{
public:
    typedef normal_leaf<KeyType_, DataType_, KeyCmp_, RawSize_, BTreeType> SelfType;

    friend class node_cache<SelfType, BTreeType>;

    typedef KeyType_ key_type;
    typedef DataType_ data_type;
    typedef KeyCmp_ key_compare;
    typedef std::pair<key_type, data_type> value_type;
    typedef value_type& reference;
    typedef const value_type& const_reference;

    enum {
        raw_size = RawSize_
    };
    typedef BID<raw_size> bid_type;
    struct InfoType
    {
        bid_type me, pred, succ;
        unsigned cur_size;
    };

    typedef typed_block<raw_size, value_type, 0, InfoType> 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<btree_type> iterator_base;
    typedef btree_iterator<btree_type> iterator;
    typedef btree_const_iterator<btree_type> const_iterator;

    typedef node_cache<normal_leaf, btree_type> leaf_cache_type;

public:
    struct value_compare : public std::binary_function<value_type, value_type, bool>
    {
        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* block_;
    btree_type* btree_;

    key_compare cmp_;
    value_compare vcmp_;

    void split(std::pair<key_type, bid_type>& splitter)
    {
        bid_type NewBid;
        btree_->leaf_cache_.get_new_node(NewBid);                         // new (left) leaf
        normal_leaf* NewLeaf = btree_->leaf_cache_.get_node(NewBid, true);
        assert(NewLeaf);

        // update links
        NewLeaf->succ() = my_bid();
        normal_leaf* PredLeaf = NULL;
        if (pred().valid())
        {
            NewLeaf->pred() = pred();
            PredLeaf = btree_->leaf_cache_.get_node(pred());
            assert(PredLeaf);
            assert(vcmp_(PredLeaf->back(), front()));
            PredLeaf->succ() = NewBid;
        }
        pred() = NewBid;

        std::vector<iterator_base*> Iterators2Fix;
        btree_->iterator_map_.find(my_bid(), 0, size(), Iterators2Fix);

        const unsigned end_of_smaller_part = size() / 2;

        splitter.first = ((*block_)[end_of_smaller_part - 1]).first;
        splitter.second = NewBid;

        const unsigned old_size = size();
        // copy the smaller part
        std::copy(block_->begin(), block_->begin() + end_of_smaller_part, NewLeaf->block_->begin());
        NewLeaf->block_->info.cur_size = end_of_smaller_part;
        // copy the larger part
        std::copy(block_->begin() + end_of_smaller_part,
                  block_->begin() + old_size, block_->begin());
        block_->info.cur_size = old_size - end_of_smaller_part;
        assert(size() + NewLeaf->size() == old_size);

        // fix iterators
        typename std::vector<iterator_base*>::iterator it2fix = Iterators2Fix.begin();
        for ( ; it2fix != Iterators2Fix.end(); ++it2fix)
        {
            btree_->iterator_map_.unregister_iterator(**it2fix);

            if ((*it2fix)->pos < end_of_smaller_part)     // belongs to the smaller part
                (*it2fix)->bid = NewBid;

            else
                (*it2fix)->pos -= end_of_smaller_part;


            btree_->iterator_map_.register_iterator(**it2fix);
        }


        STXXL_VERBOSE1("btree::normal_leaf split leaf " << this
                                                        << " splitter: " << splitter.first);

#if STXXL_VERBOSE_LEVEL >= 1
        if (PredLeaf)
        {
            STXXL_VERBOSE1("btree::normal_leaf pred_part.smallest    = " << PredLeaf->front().first);
            STXXL_VERBOSE1("btree::normal_leaf pred_part.largest     = " << PredLeaf->back().first);
        }
#endif
        STXXL_VERBOSE1("btree::normal_leaf smaller_part.smallest = " << NewLeaf->front().first);
        STXXL_VERBOSE1("btree::normal_leaf smaller_part.largest  = " << NewLeaf->back().first);
        STXXL_VERBOSE1("btree::normal_leaf larger_part.smallest  = " << front().first);
        STXXL_VERBOSE1("btree::normal_leaf larger_part.largest   = " << back().first);

        btree_->leaf_cache_.unfix_node(NewBid);
    }

public:
    virtual ~normal_leaf()
    {
        delete block_;
    }

    normal_leaf(btree_type* btree__,
                key_compare cmp) :
        block_(new block_type),
        btree_(btree__),
        cmp_(cmp),
        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 block_->info.cur_size > max_nelements(); }
    bool underflows() const { return block_->info.cur_size < min_nelements(); }

    unsigned max_nelements() const { return max_size; }
    unsigned min_nelements() const { return min_size; }


    bid_type & succ()
    {
        return block_->info.succ;
    }
    bid_type & pred()
    {
        return block_->info.pred;
    }

    const bid_type & succ() const
    {
        return block_->info.succ;
    }
    const bid_type & pred() const
    {
        return block_->info.pred;
    }

    /*
       template <class InputIterator>
       normal_leaf(InputIterator begin_, InputIterator end_,
            btree_type * btree__,
            key_compare cmp):
            block_(new block_type),
            btree_(btree__),
            cmp_(cmp),
            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_,block_->begin());
            assert(stxxl::is_sorted(block_->begin(),block_->begin() + new_size, vcmp_));
            block_->info.cur_size = new_size;
       }*/

    unsigned size() const
    {
        return block_->info.cur_size;
    }

    const bid_type & my_bid() const
    {
        return block_->info.me;
    }

    void save()
    {
        request_ptr req = block_->write(my_bid());
        req->wait();
    }

    request_ptr load(const bid_type& bid)
    {
        request_ptr req = block_->read(bid);
        req->wait();
        assert(bid == my_bid());
        return req;
    }

    request_ptr prefetch(const bid_type& bid)
    {
        return block_->read(bid);
    }

    void init(const bid_type& my_bid_)
    {
        block_->info.me = my_bid_;
        block_->info.succ = bid_type();
        block_->info.pred = bid_type();
        block_->info.cur_size = 0;
    }

    reference operator [] (int i)
    {
        return (*block_)[i];
    }

    const_reference operator [] (int i) const
    {
        return (*block_)[i];
    }

    reference back()
    {
        return (*block_)[size() - 1];
    }

    reference front()
    {
        return *(block_->begin());
    }

    const_reference back() const
    {
        return (*block_)[size() - 1];
    }

    const_reference front() const
    {
        return *(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<iterator, bool> insert(
        const value_type& x,
        std::pair<key_type, bid_type>& splitter)
    {
        assert(size() <= max_nelements());
        splitter.first = key_compare::max_value();

        typename block_type::iterator it =
            std::lower_bound(block_->begin(), block_->begin() + size(), x, vcmp_);

        if (!(vcmp_(*it, x) || vcmp_(x, *it)) && it != (block_->begin() + size()))                    // *it == x
        {
            // already exists
            return std::pair<iterator, bool>(
                iterator(btree_, my_bid(), unsigned(it - block_->begin())),
                false);
        }

        typename block_type::iterator cur = block_->begin() + size() - 1;

        for ( ; cur >= it; --cur)
            *(cur + 1) = *cur;
        // move elements to make space for the new element

        *it = x;

        std::vector<iterator_base*> Iterators2Fix;
        btree_->iterator_map_.find(my_bid(), unsigned(it - block_->begin()), size(), Iterators2Fix);
        typename std::vector<iterator_base*>::iterator it2fix = Iterators2Fix.begin();
        for ( ; it2fix != Iterators2Fix.end(); ++it2fix)
        {
            btree_->iterator_map_.unregister_iterator(**it2fix);
            ++((*it2fix)->pos);                            // fixing iterators
            btree_->iterator_map_.register_iterator(**it2fix);
        }

        ++(block_->info.cur_size);

        std::pair<iterator, bool> result(iterator(btree_, my_bid(), unsigned(it - block_->begin())), true);

        if (size() <= max_nelements())
        {
            // no overflow
            dump();
            return result;
        }

        // overflow

        split(splitter);

        return result;
    }

    iterator begin()
    {
        return iterator(btree_, my_bid(), 0);
    }

    const_iterator begin() const
    {
        return const_iterator(btree_, my_bid(), 0);
    }

    iterator end()
    {
        return iterator(btree_, my_bid(), size());
    }

    void increment_iterator(iterator_base& it) const
    {
        assert(it.bid == my_bid());
        assert(it.pos != size());

        btree_->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();
        } else if (it.pos == 1 && btree_->prefetching_enabled_)                        // increment of pos from 0 to 1
        {
            // prefetch the succ leaf
            if (succ().valid())
                btree_->leaf_cache_.prefetch_node(succ());
        }
        btree_->iterator_map_.register_iterator(it);
    }

    void decrement_iterator(iterator_base& it) const
    {
        assert(it.bid == my_bid());

        btree_->iterator_map_.unregister_iterator(it);

        if (it.pos == 0)
        {
            assert(pred().valid());

            it.bid = pred();
            normal_leaf const* PredLeaf = btree_->leaf_cache_.get_const_node(pred(), true);
            assert(PredLeaf);
            it.pos = PredLeaf->size() - 1;

            // prefetch the pred leaf of PredLeaf
            if (btree_->prefetching_enabled_ && PredLeaf->pred().valid())
                btree_->leaf_cache_.prefetch_node(PredLeaf->pred());


            btree_->leaf_cache_.unfix_node(pred());
        }
        else
            --it.pos;


        btree_->iterator_map_.register_iterator(it);
    }

    iterator find(const key_type& k)
    {
        value_type searchVal(k, data_type());
        typename block_type::iterator lb =
            std::lower_bound(block_->begin(), block_->begin() + size(), searchVal, vcmp_);
        if (lb == block_->begin() + size() || lb->first != k)
            return btree_->end();


        return iterator(btree_, my_bid(), unsigned(lb - block_->begin()));
    }

    const_iterator find(const key_type& k) const
    {
        value_type searchVal(k, data_type());
        typename block_type::iterator lb =
            std::lower_bound(block_->begin(), block_->begin() + size(), searchVal, vcmp_);
        if (lb == block_->begin() + size() || lb->first != k)
            return btree_->end();


        return const_iterator(btree_, my_bid(), unsigned(lb - block_->begin()));
    }

    iterator lower_bound(const key_type& k)
    {
        value_type searchVal(k, data_type());

        typename block_type::iterator lb =
            std::lower_bound(block_->begin(), block_->begin() + size(), searchVal, vcmp_);

        // lower_bound is in the succ block
        if (lb == block_->begin() + size() && succ().valid())
        {
            return iterator(btree_, succ(), 0);
        }

        return iterator(btree_, my_bid(), unsigned(lb - block_->begin()));
    }

    const_iterator lower_bound(const key_type& k) const
    {
        value_type searchVal(k, data_type());
        typename block_type::iterator lb =
            std::lower_bound(block_->begin(), block_->begin() + size(), searchVal, vcmp_);

        // lower_bound is in the succ block
        if (lb == block_->begin() + size() && succ().valid())
        {
            return iterator(btree_, succ(), 0);
        }

        return const_iterator(btree_, my_bid(), unsigned(lb - block_->begin()));
    }

    iterator upper_bound(const key_type& k)
    {
        value_type searchVal(k, data_type());
        typename block_type::iterator lb =
            std::upper_bound(block_->begin(), block_->begin() + size(), searchVal, vcmp_);

        // upper_bound is in the succ block
        if (lb == block_->begin() + size() && succ().valid())
        {
            return iterator(btree_, succ(), 0);
        }

        return iterator(btree_, my_bid(), unsigned(lb - block_->begin()));
    }

    const_iterator upper_bound(const key_type& k) const
    {
        value_type searchVal(k, data_type());
        typename block_type::iterator lb =
            std::upper_bound(block_->begin(), block_->begin() + size(), searchVal, vcmp_);

        // upper_bound is in the succ block
        if (lb == block_->begin() + size() && succ().valid())
        {
            return const_iterator(btree_, succ(), 0);
        }

        return const_iterator(btree_, my_bid(), unsigned(lb - block_->begin()));
    }

    size_type erase(const key_type& k)
    {
        value_type searchVal(k, data_type());
        typename block_type::iterator it =
            std::lower_bound(block_->begin(), block_->begin() + size(), searchVal, vcmp_);

        if (it == block_->begin() + size() || it->first != k)
            return 0;
        // no such element

        // move elements one position left
        std::copy(it + 1, block_->begin() + size(), it);

        std::vector<iterator_base*> Iterators2Fix;
        btree_->iterator_map_.find(my_bid(), unsigned(it + 1 - block_->begin()), size(), Iterators2Fix);
        typename std::vector<iterator_base*>::iterator it2fix = Iterators2Fix.begin();
        for ( ; it2fix != Iterators2Fix.end(); ++it2fix)
        {
            STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) << " (pos--)");
            btree_->iterator_map_.unregister_iterator(**it2fix);
            --((*it2fix)->pos);                            // fixing iterators
            btree_->iterator_map_.register_iterator(**it2fix);
        }

        --(block_->info.cur_size);

        return 1;
    }

    void fuse(const normal_leaf& Src)
    {
        STXXL_VERBOSE1("btree::normal_leaf Fusing");
        assert(vcmp_(Src.back(), front()));
        const unsigned SrcSize = Src.size();

        typename block_type::iterator cur = block_->begin() + size() - 1;
        typename block_type::const_iterator begin = block_->begin();

        for ( ; cur >= begin; --cur)
            *(cur + SrcSize) = *cur;
        // move elements to make space for Src elements

        // copy Src to *this leaf
        std::copy(Src.block_->begin(), Src.block_->begin() + SrcSize, block_->begin());


        std::vector<iterator_base*> Iterators2Fix;
        btree_->iterator_map_.find(my_bid(), 0, size(), Iterators2Fix);
        typename std::vector<iterator_base*>::iterator it2fix = Iterators2Fix.begin();
        for ( ; it2fix != Iterators2Fix.end(); ++it2fix)
        {
            STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
                           " (pos+" << SrcSize << ")");
            btree_->iterator_map_.unregister_iterator(**it2fix);
            ((*it2fix)->pos) += SrcSize;                           // fixing iterators
            btree_->iterator_map_.register_iterator(**it2fix);
        }

        Iterators2Fix.clear();
        btree_->iterator_map_.find(Src.my_bid(), 0, SrcSize, Iterators2Fix);
        it2fix = Iterators2Fix.begin();
        for ( ; it2fix != Iterators2Fix.end(); ++it2fix)
        {
            STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
                           " (bid=" << my_bid() << ")");
            btree_->iterator_map_.unregister_iterator(**it2fix);
            ((*it2fix)->bid) = my_bid();                             // fixing iterators
            btree_->iterator_map_.register_iterator(**it2fix);
        }

        block_->info.cur_size += SrcSize;

        // update links
        pred() = Src.pred();
        if (pred().valid())
        {                         // update successor link
            normal_leaf* NewPred = btree_->leaf_cache_.get_node(pred());
            assert(NewPred);
            NewPred->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 TotalSize = Left.size() + size();
        unsigned newLeftSize = TotalSize / 2;
        assert(newLeftSize <= Left.max_nelements());
        assert(newLeftSize >= Left.min_nelements());
        unsigned newRightSize = TotalSize - newLeftSize;
        assert(newRightSize <= max_nelements());
        assert(newRightSize >= min_nelements());

        assert(vcmp_(Left.back(), front()) || size() == 0);

        if (newLeftSize < Left.size())
        {
            const unsigned nEl2Move = Left.size() - newLeftSize;                            // #elements to move from Left to *this

            typename block_type::iterator cur = block_->begin() + size() - 1;
            typename block_type::const_iterator begin = 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.block_->begin() + newLeftSize,
                      Left.block_->begin() + Left.size(), block_->begin());

            std::vector<iterator_base*> Iterators2Fix1;
            std::vector<iterator_base*> Iterators2Fix2;
            btree_->iterator_map_.find(my_bid(), 0, size(), Iterators2Fix1);
            btree_->iterator_map_.find(Left.my_bid(), newLeftSize, Left.size(), Iterators2Fix2);

            typename std::vector<iterator_base*>::iterator it2fix = Iterators2Fix1.begin();
            for ( ; it2fix != Iterators2Fix1.end(); ++it2fix)
            {
                STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
                               " (pos+" << nEl2Move << ")");
                btree_->iterator_map_.unregister_iterator(**it2fix);
                ((*it2fix)->pos) += nEl2Move;                               // fixing iterators
                btree_->iterator_map_.register_iterator(**it2fix);
            }


            it2fix = Iterators2Fix2.begin();
            for ( ; it2fix != Iterators2Fix2.end(); ++it2fix)
            {
                STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
                               " (pos-" << newLeftSize << " bid=" << my_bid() << ")");
                btree_->iterator_map_.unregister_iterator(**it2fix);
                ((*it2fix)->bid) = my_bid();                                     // fixing iterators
                ((*it2fix)->pos) -= newLeftSize;                                 // fixing iterators
                btree_->iterator_map_.register_iterator(**it2fix);
            }
        }
        else
        {
            assert(newRightSize < size());

            const unsigned nEl2Move = size() - newRightSize;                            // #elements to move from *this to Left

            // copy *this to Left
            std::copy(block_->begin(),
                      block_->begin() + nEl2Move, Left.block_->begin() + Left.size());
            // move elements in *this
            std::copy(block_->begin() + nEl2Move,
                      block_->begin() + size(), block_->begin());

            std::vector<iterator_base*> Iterators2Fix1;
            std::vector<iterator_base*> Iterators2Fix2;
            btree_->iterator_map_.find(my_bid(), nEl2Move, size(), Iterators2Fix1);
            btree_->iterator_map_.find(my_bid(), 0, nEl2Move - 1, Iterators2Fix2);

            typename std::vector<iterator_base*>::iterator it2fix = Iterators2Fix1.begin();
            for ( ; it2fix != Iterators2Fix1.end(); ++it2fix)
            {
                STXXL_VERBOSE2("btree::normal_leaf updating iterator " << (*it2fix) <<
                               " (pos-" << nEl2Move << ")");
                btree_->iterator_map_.unregister_iterator(**it2fix);
                ((*it2fix)->pos) -= nEl2Move;                                 // fixing iterators
                btree_->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() << ")");
                btree_->iterator_map_.unregister_iterator(**it2fix);
                ((*it2fix)->bid) = Left.my_bid();                                 // fixing iterators
                ((*it2fix)->pos) += Left.size();                                  // fixing iterators
                btree_->iterator_map_.register_iterator(**it2fix);
            }
        }

        block_->info.cur_size = newRightSize;                             // update size
        Left.block_->info.cur_size = newLeftSize;                         // update size

        return Left.back().first;
    }

    void push_back(const value_type& x)
    {
        (*this)[size()] = x;
        ++(block_->info.cur_size);
    }
};

} // namespace btree


STXXL_END_NAMESPACE

#endif // !STXXL_CONTAINERS_BTREE_LEAF_HEADER