stx/btree.h

Go to the documentation of this file.

// $Id: btree.h 37 2007-04-27 12:13:27Z tb $
/*
 * STX B+ Tree Template Classes v0.7
 * Copyright (C) 2007 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 <functional>
#include <algorithm>
#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))

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;

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 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 btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates>::const_iterator;
        
        mutable value_type              temp_value;

    public:
        // *** Methods

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

        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;
    
        mutable value_type              temp_value;

    public:
        // *** Methods

        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 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);
        }    
    };

    typedef std::reverse_iterator<iterator>       reverse_iterator;

    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

public:
    // *** Small Statistics Structure

    struct tree_stats
    {
        size_type       itemcount;

        size_type       leaves;

        size_type       innernodes;

        static const unsigned short     leafslots = btree_self::leafslotmax;

        static const unsigned short     innerslots = btree_self::innerslotmax;

        inline tree_stats()
            : itemcount(0),
              leaves(0), innernodes(0)
        {
        }

        inline size_type nodes() const
        {
            return innernodes + leaves;
        }

        inline double avgfill_leaves() const
        {
            return static_cast<double>(itemcount) / (leaves * leafslots);
        }
    };

private:
    // *** Tree Object Data Members

    node*       root;

    leaf_node   *headleaf;

    leaf_node   *tailleaf;

    tree_stats  stats;

    key_compare key_less;

public:
    // *** Constructors and Destructor

    inline btree()
        : root(NULL), headleaf(NULL), tailleaf(NULL)
    {
    }

    inline btree(const key_compare &kcf)
        : root(NULL), headleaf(NULL), tailleaf(NULL),
          key_less(kcf)
    {
    }

    template <class InputIterator>
    inline btree(InputIterator first, InputIterator last)
        : root(NULL), headleaf(NULL), tailleaf(NULL)
    {
        insert(first, last);
    }

    template <class InputIterator>
    inline btree(InputIterator first, InputIterator last, const key_compare &kcf)
        : root(NULL), headleaf(NULL), tailleaf(NULL),
          key_less(kcf)
    {
        insert(first, last);
    }

    inline ~btree()
    {
        clear();
    }

    void swap(btree_self& from)
    {
        std::swap(root, from.root);
        std::swap(headleaf, from.headleaf);
        std::swap(tailleaf, from.tailleaf);
        std::swap(stats, from.stats);
        std::swap(key_less, from.key_less);
    }

public:
    // *** Key and Value Comparison Function Objects

    class value_compare
    {
    protected:
        key_compare     key_comp;
 
        inline value_compare(key_compare kc)
            : key_comp(kc)
        { }

        friend class btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates>;
 
    public:
        inline bool operator()(const value_type& x, const value_type& y) const
        {
            return key_comp(x.first, y.first);
        }
    };

    inline key_compare key_comp() const
    {
        return key_less;
    }

    inline value_compare value_comp() const
    {
        return value_compare(key_less);
    }

private:
    // *** Convenient Key Comparison Functions Generated From key_less

    inline bool key_lessequal(const key_type &a, const key_type b) const
    {
        return !key_less(b, a);
    }

    inline bool key_greater(const key_type &a, const key_type &b) const
    {
        return key_less(b, a);
    }

    inline bool key_greaterequal(const key_type &a, const key_type b) const
    {
        return !key_less(a, b);
    }

    inline bool key_equal(const key_type &a, const key_type &b) const
    {
        return !key_less(a, b) && !key_less(b, a);
    }

private:
    // *** Node Object Allocation and Deallocation Functions

    inline leaf_node* allocate_leaf()
    {
        leaf_node* n = new leaf_node;
        n->initialize();
        stats.leaves++;
        return n;
    }

    inline inner_node* allocate_inner(unsigned short l)
    {
        inner_node* n = new inner_node;
        n->initialize(l);
        stats.innernodes++;
        return n;
    }
    
    inline void free_node(node *n)
    {
        if (n->isleafnode()) {
            delete static_cast<leaf_node*>(n);
            stats.leaves--;
        }
        else {
            delete static_cast<inner_node*>(n);
            stats.innernodes--;
        }
    }

public:
    // *** Fast Destruction of the B+ Tree

    void clear()
    {
        if (root)
        {
            clear_recursive(root);
            free_node(root);

            root = NULL;
            headleaf = tailleaf = NULL;

            stats = tree_stats();
        }

        BTREE_ASSERT(stats.itemcount == 0);
    }

private:
    void clear_recursive(node *n)
    {
        if (n->isleafnode())
        {
            leaf_node *leafnode = static_cast<leaf_node*>(n);

            for (unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
            {
                // data objects are deleted by leaf_node's destructor
            }
        }
        else
        {
            inner_node *innernode = static_cast<inner_node*>(n);

            for (unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
            {
                clear_recursive(innernode->childid[slot]);
                free_node(innernode->childid[slot]);
            }
        }
    }

public:
    // *** STL Iterator Construction Functions

    inline iterator begin()
    {
        return iterator(headleaf, 0);
    }

    inline iterator end()
    {
        return iterator(tailleaf, tailleaf->slotuse);
    }

    inline const_iterator begin() const
    {
        return const_iterator(headleaf, 0);
    }

    inline const_iterator end() const
    {
        return const_iterator(tailleaf, tailleaf->slotuse);
    }

    inline reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }

    inline reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }

    inline const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(end());
    }

    inline const_reverse_iterator rend() const
    {
        return const_reverse_iterator(begin());
    }

private:
    // *** B+ Tree Node Binary Search Functions

    template <typename node_type>
    inline int find_lower(const node_type *n, const key_type& key) const
    {
        if (n->slotuse == 0) return 0;

        int lo = 0,
            hi = n->slotuse - 1;

        while(lo < hi)
        {
            int mid = (lo + hi) / 2;

            if (key_lessequal(key, n->slotkey[mid])) {
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }

        if (hi < 0 || key_less(n->slotkey[hi], key))
            hi++;

        BTREE_PRINT("btree::find_lower: on " << n << " key " << key << " -> (" << lo << ") " << hi << ", ");

        // verify result using simple linear search
        if (selfverify)
        {
            int i = n->slotuse - 1;
            while(i >= 0 && key_lessequal(key, n->slotkey[i]))
                i--;
            i++;

            BTREE_PRINT("testfind: " << i << std::endl);
            BTREE_ASSERT(i == hi);
        }
        else {
            BTREE_PRINT(std::endl);
        }
        
        return hi;
    }

    template <typename node_type>
    inline int find_upper(const node_type *n, const key_type& key) const
    {
        if (n->slotuse == 0) return 0;

        int lo = 0,
            hi = n->slotuse - 1;

        while(lo < hi)
        {
            int mid = (lo + hi) / 2;

            if (key_less(key, n->slotkey[mid])) {
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }

        if (hi < 0 || key_lessequal(n->slotkey[hi], key))
            hi++;

        BTREE_PRINT("btree::find_upper: on " << n << " key " << key << " -> (" << lo << ") " << hi << ", ");

        // verify result using simple linear search
        if (selfverify)
        {
            int i = n->slotuse - 1;
            while(i >= 0 && key_less(key, n->slotkey[i]))
                i--;
            i++;

            BTREE_PRINT("btree::find_upper testfind: " << i << std::endl);
            BTREE_ASSERT(i == hi);
        }
        else {
            BTREE_PRINT(std::endl);
        }
        
        return hi;
    }

public:
    // *** Access Functions to the Item Count

    inline size_type size() const
    {
        return stats.itemcount;
    }

    inline bool empty() const
    {
        return (size() == size_type(0));
    }
    
    inline size_type max_size() const
    {
        return size_type(-1);
    }

    inline const struct tree_stats& get_stats() const
    {
        return stats;
    }

public:
    // *** Standard Access Functions Querying the Tree by Descending to a Leaf

    bool exists(const key_type &key) const
    {
        const node *n = root;

        if (!n) return false;

        while(!n->isleafnode())
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            int slot = find_lower(inner, key);

            n = inner->childid[slot];
        }

        const leaf_node *leaf = static_cast<const leaf_node*>(n);

        int slot = find_lower(leaf, key);
        return key_equal(key, leaf->slotkey[slot]);
    }

    iterator find(const key_type &key)
    {
        node *n = root;
        if (!n) return end();

        while(!n->isleafnode())
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            int slot = find_lower(inner, key);

            n = inner->childid[slot];
        }

        leaf_node *leaf = static_cast<leaf_node*>(n);

        int slot = find_lower(leaf, key);
        return key_equal(key, leaf->slotkey[slot]) ? iterator(leaf, slot) : end();
    }

    const_iterator find(const key_type &key) const
    {
        const node *n = root;
        if (!n) return end();

        while(!n->isleafnode())
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            int slot = find_lower(inner, key);

            n = inner->childid[slot];
        }

        const leaf_node *leaf = static_cast<const leaf_node*>(n);

        int slot = find_lower(leaf, key);
        return key_equal(key, leaf->slotkey[slot]) ? const_iterator(leaf, slot) : end();
    }

    size_type count(const key_type &key) const
    {
        const node *n = root;
        if (!n) return 0;

        while(!n->isleafnode())
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            int slot = find_lower(inner, key);

            n = inner->childid[slot];
        }

        const leaf_node *leaf = static_cast<const leaf_node*>(n);

        int slot = find_lower(leaf, key);
        size_type num = 0;

        while (leaf && key_equal(key, leaf->slotkey[slot]))