stx/btree.h

Go to the documentation of this file.

// $Id: btree.h 113 2008-09-07 15:25:51Z tb $
/*
 * STX B+ Tree Template Classes v0.8.3
 * Copyright (C) 2008 Timo Bingmann
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
 * for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

#ifndef _STX_BTREE_H_
#define _STX_BTREE_H_

// *** Required Headers from the STL

#include <algorithm>
#include <functional>
#include <istream>
#include <ostream>
#include <assert.h>

// *** Debugging Macros

#ifdef BTREE_DEBUG

#include <iostream>

#define BTREE_PRINT(x)          do { if (debug) (std::cout << x); } while(0)

#define BTREE_ASSERT(x)         do { assert(x); } while(0)

#else

#define BTREE_PRINT(x)          do { } while(0)

#define BTREE_ASSERT(x)         do { } while(0)

#endif

#define BTREE_MAX(a,b)          ((a) < (b) ? (b) : (a))

#ifndef BTREE_FRIENDS
#define BTREE_FRIENDS           friend class btree_friend;
#endif

namespace stx {

template <typename _Key>
struct btree_default_set_traits
{
    static const bool   selfverify = false;

    static const bool   debug = false;

    static const int    leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key)) );

    static const int    innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
};

template <typename _Key, typename _Data>
struct btree_default_map_traits
{
    static const bool   selfverify = false;

    static const bool   debug = false;

    static const int    leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(_Data)) );

    static const int    innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
};

template <typename _Key, typename _Data,
          typename _Value = std::pair<_Key, _Data>,
          typename _Compare = std::less<_Key>,
          typename _Traits = btree_default_map_traits<_Key, _Data>,
          bool _Duplicates = false>
class btree
{
public:
    // *** Template Parameter Types

    typedef _Key                        key_type;

    typedef _Data                       data_type;

    typedef _Value                      value_type;

    typedef _Compare                    key_compare;

    typedef _Traits                     traits;

    static const bool                   allow_duplicates = _Duplicates;

    // The macro BTREE_FRIENDS can be used by outside class to access the B+
    // tree internals. This was added for wxBTreeDemo to be able to draw the
    // tree.
    BTREE_FRIENDS

public:
    // *** Constructed Types

    typedef btree<key_type, data_type, value_type,
                  key_compare, traits, allow_duplicates>        btree_self;

    typedef size_t                              size_type;

    typedef std::pair<key_type, data_type>      pair_type;

public:
    // *** Static Constant Options and Values of the B+ Tree

    static const unsigned short         leafslotmax =  traits::leafslots;

    static const unsigned short         innerslotmax =  traits::innerslots;

    static const unsigned short minleafslots = (leafslotmax / 2);

    static const unsigned short mininnerslots = (innerslotmax / 2);

    static const bool                   selfverify = traits::selfverify;

    static const bool                   debug = traits::debug;

private:
    // *** Node Classes for In-Memory Nodes

    struct node
    {
        unsigned short  level;

        unsigned short  slotuse;

        inline void initialize(const unsigned short l)
        {
            level = l;
            slotuse = 0;
        }

        inline bool isleafnode() const
        {
            return (level == 0);
        }
    };

    struct inner_node : public node
    {
        key_type        slotkey[innerslotmax];

        node*           childid[innerslotmax+1];

        inline void initialize(const unsigned short l)
        {
            node::initialize(l);
        }

        inline bool isfull() const
        {
            return (node::slotuse == innerslotmax);
        }

        inline bool isfew() const
        {
            return (node::slotuse <= mininnerslots);
        }

        inline bool isunderflow() const
        {
            return (node::slotuse < mininnerslots);
        }
    };

    struct leaf_node : public node
    {
        leaf_node       *prevleaf;

        leaf_node       *nextleaf;

        key_type        slotkey[leafslotmax];

        data_type       slotdata[leafslotmax];

        inline void initialize()
        {
            node::initialize(0);
            prevleaf = nextleaf = NULL;
        }

        inline bool isfull() const
        {
            return (node::slotuse == leafslotmax);
        }

        inline bool isfew() const
        {
            return (node::slotuse <= minleafslots);
        }

        inline bool isunderflow() const
        {
            return (node::slotuse < minleafslots);
        }
    };

private:
    // *** Template Magic to Convert a pair or key/data types to a value_type

    template <typename value_type, typename pair_type>
    struct btree_pair_to_value
    {
        inline value_type operator()(pair_type& p) const {
            return p.first;
        }
        inline value_type operator()(const pair_type& p) const {
            return p.first;
        }
    };

    template <typename value_type>
    struct btree_pair_to_value<value_type, value_type>
    {
        inline value_type operator()(pair_type& p) const {
            return p;
        }
        inline value_type operator()(const pair_type& p) const {
            return p;
        }
    };

    typedef btree_pair_to_value<value_type, pair_type> pair_to_value_type;

public:
    // *** Iterators and Reverse Iterators

    class iterator;
    class const_iterator;
    class reverse_iterator;
    class const_reverse_iterator;

    class iterator
    {
    public:
        // *** Types

        typedef typename btree::key_type                key_type;

        typedef typename btree::data_type               data_type;

        typedef typename btree::value_type              value_type;

        typedef typename btree::pair_type               pair_type;

        typedef value_type&             reference;

        typedef value_type*             pointer;

        typedef std::bidirectional_iterator_tag iterator_category;

        typedef ptrdiff_t               difference_type;

        typedef iterator                self;

    private:
        // *** Members

        typename btree::leaf_node*      currnode;

        unsigned short          currslot;

        friend class const_iterator;

        friend class reverse_iterator;

        friend class const_reverse_iterator;

        mutable value_type              temp_value;

        // The macro BTREE_FRIENDS can be used by outside class to access the B+
        // tree internals. This was added for wxBTreeDemo to be able to draw the
        // tree.
        BTREE_FRIENDS

    public:
        // *** Methods

        inline iterator()
            : currnode(NULL), currslot(0)
        { }

        inline iterator(typename btree::leaf_node *l, unsigned short s)
            : currnode(l), currslot(s)
        { }

        inline iterator(const reverse_iterator &it)
            : currnode(it.currnode), currslot(it.currslot)
        { }

        inline reference operator*() const
        {
            temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
                                                         currnode->slotdata[currslot]) );
            return temp_value;
        }

        inline pointer operator->() const
        {
            temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
                                                         currnode->slotdata[currslot]) );
            return &temp_value;
        }

        inline const key_type& key() const
        {
            return currnode->slotkey[currslot];
        }

        inline data_type& data() const
        {
            return currnode->slotdata[currslot];
        }

        inline self& operator++()
        {
            if (currslot + 1 < currnode->slotuse) {
                ++currslot;
            }
            else if (currnode->nextleaf != NULL) {
                currnode = currnode->nextleaf;
                currslot = 0;
            }
            else {
                // this is end()
                currslot = currnode->slotuse;
            }

            return *this;
        }

        inline self operator++(int)
        {
            self tmp = *this;   // copy ourselves

            if (currslot + 1 < currnode->slotuse) {
                ++currslot;
            }
            else if (currnode->nextleaf != NULL) {
                currnode = currnode->nextleaf;
                currslot = 0;
            }
            else {
                // this is end()
                currslot = currnode->slotuse;
            }

            return tmp;
        }

        inline self& operator--()
        {
            if (currslot > 0) {
                --currslot;
            }
            else if (currnode->prevleaf != NULL) {
                currnode = currnode->prevleaf;
                currslot = currnode->slotuse - 1;
            }
            else {
                // this is begin()
                currslot = 0;
            }

            return *this;
        }

        inline self operator--(int)
        {
            self tmp = *this;   // copy ourselves

            if (currslot > 0) {
                --currslot;
            }
            else if (currnode->prevleaf != NULL) {
                currnode = currnode->prevleaf;
                currslot = currnode->slotuse - 1;
            }
            else {
                // this is begin()
                currslot = 0;
            }

            return tmp;
        }

        inline bool operator==(const self& x) const
        {
            return (x.currnode == currnode) && (x.currslot == currslot);
        }

        inline bool operator!=(const self& x) const
        {
            return (x.currnode != currnode) || (x.currslot != currslot);
        }
    };

    class const_iterator
    {
    public:
        // *** Types

        typedef typename btree::key_type                key_type;

        typedef typename btree::data_type               data_type;

        typedef typename btree::value_type              value_type;

        typedef typename btree::pair_type               pair_type;

        typedef const value_type&               reference;

        typedef const value_type*               pointer;

        typedef std::bidirectional_iterator_tag         iterator_category;

        typedef ptrdiff_t               difference_type;

        typedef const_iterator          self;

    private:
        // *** Members

        const typename btree::leaf_node*        currnode;

        unsigned short                  currslot;

        friend class const_reverse_iterator;

        mutable value_type              temp_value;

        // The macro BTREE_FRIENDS can be used by outside class to access the B+
        // tree internals. This was added for wxBTreeDemo to be able to draw the
        // tree.
        BTREE_FRIENDS

    public:
        // *** Methods

        inline const_iterator()
            : currnode(NULL), currslot(0)
        { }

        inline const_iterator(const typename btree::leaf_node *l, unsigned short s)
            : currnode(l), currslot(s)
        { }

        inline const_iterator(const iterator &it)
            : currnode(it.currnode), currslot(it.currslot)
        { }

        inline const_iterator(const reverse_iterator &it)
            : currnode(it.currnode), currslot(it.currslot)
        { }

        inline const_iterator(const const_reverse_iterator &it)
            : currnode(it.currnode), currslot(it.currslot)
        { }

        inline reference operator*() const
        {
            temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
                                                         currnode->slotdata[currslot]) );
            return temp_value;
        }

        inline pointer operator->() const
        {
            temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
                                                         currnode->slotdata[currslot]) );
            return &temp_value;
        }

        inline const key_type& key() const
        {
            return currnode->slotkey[currslot];
        }

        inline const data_type& data() const
        {
            return currnode->slotdata[currslot];
        }

        inline self& operator++()
        {
            if (currslot + 1 < currnode->slotuse) {
                ++currslot;
            }
            else if (currnode->nextleaf != NULL) {
                currnode = currnode->nextleaf;
                currslot = 0;
            }
            else {
                // this is end()
                currslot = currnode->slotuse;
            }

            return *this;
        }

        inline self operator++(int)
        {
            self tmp = *this;   // copy ourselves

            if (currslot + 1 < currnode->slotuse) {
                ++currslot;
            }
            else if (currnode->nextleaf != NULL) {
                currnode = currnode->nextleaf;
                currslot = 0;
            }
            else {
                // this is end()
                currslot = currnode->slotuse;
            }

            return tmp;
        }

        inline self& operator--()
        {
            if (currslot > 0) {
                --currslot;
            }
            else if (currnode->prevleaf != NULL) {
                currnode = currnode->prevleaf;
                currslot = currnode->slotuse - 1;
            }
            else {
                // this is begin()
                currslot = 0;
            }

            return *this;
        }

        inline self operator--(int)
        {
            self tmp = *this;   // copy ourselves

            if (currslot > 0) {
                --currslot;
            }
            else if (currnode->prevleaf != NULL) {
                currnode = currnode->prevleaf;
                currslot = currnode->slotuse - 1;
            }
            else {
                // this is begin()
                currslot = 0;
            }

            return tmp;
        }

        inline bool operator==(const self& x) const
        {
            return (x.currnode == currnode) && (x.currslot == currslot);
        }

        inline bool operator!=(const self& x) const
        {
            return (x.currnode != currnode) || (x.currslot != currslot);
        }
    };

    class reverse_iterator
    {
    public:
        // *** Types

        typedef typename btree::key_type                key_type;

        typedef typename btree::data_type               data_type;

        typedef typename btree::value_type              value_type;

        typedef typename btree::pair_type               pair_type;

        typedef value_type&             reference;

        typedef value_type*             pointer;

        typedef std::bidirectional_iterator_tag iterator_category;

        typedef ptrdiff_t               difference_type;

        typedef reverse_iterator        self;

    private:
        // *** Members

        typename btree::leaf_node*      currnode;

        unsigned short          currslot;

        friend class iterator;

        friend class const_iterator;

        friend class const_reverse_iterator;

        mutable value_type              temp_value;

        // The macro BTREE_FRIENDS can be used by outside class to access the B+
        // tree internals. This was added for wxBTreeDemo to be able to draw the
        // tree.
        BTREE_FRIENDS

    public:
        // *** Methods

        inline reverse_iterator()
            : currnode(NULL), currslot(0)
        { }

        inline reverse_iterator(typename btree::leaf_node *l, unsigned short s)
            : currnode(l), currslot(s)
        { }

        inline reverse_iterator(const iterator &it)
            : currnode(it.currnode), currslot(it.currslot)
        { }

        inline reference operator*() const
        {
            BTREE_ASSERT(currslot > 0);
            temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot - 1],
                                                         currnode->slotdata[currslot - 1]) );
            return temp_value;
        }

        inline pointer operator->() const
        {
            BTREE_ASSERT(currslot > 0);
            temp_value = pair_to_value_type()( pair_type(currnode->