Listing 1: The BtreeIndex class

namespace Util {

//
//
BtreeIndex --
//
template<typename Key,
         typename Compare = std::less<Key>,
         typename KeyTraits = XDR_Traits<Key>,
         size_t PageSize = 4096>
class BtreeIndex {
public:
    // public types
    class Iterator;
    class StreamposProxy;

    typedef Key                            key_type;
    typedef std::pair<const Key, size_t> value_type;
    typedef Compare                        key_compare;
    typedef Iterator                    iterator;
    typedef size_t                        size_type;
    typedef ptrdiff_t                    difference_type;

    enum DeleteStrategy { None, Compact, Shuffle };
    enum UpdateStrategy { Unsafe, MostlySafe, Safe };
    
    class StreamposProxy;
    class Iterator;
 

    // construct / destroy
    explicit BtreeIndex(Compare comp = Compare());
    explicit BtreeIndex(const std::string& name, 
        std::ios_base::openmode mode = std::ios_base::in|std::ios_base::out,
        Compare comp = Compare()); 
    ~BtreeIndex();

    // open/close/test state
    bool            is_open();
    void            open(const std::string& name, 
                        std::ios_base::openmode mode = std::ios_base::in|std::ios_base::out);
    void            close();
    void            flush();
    operator void*() const; 
    bool operator!() const;

    // iterators
    iterator        begin();
    iterator        end();
 
    // capacity
    bool            empty();
    size_type        size();
 
    // modifiers
    iterator        insert(const value_type& x);
    iterator        insert(const Key& k);
    template<typename InputIterator>
        void        insert(InputIterator first, InputIterator last);
 
    void            erase(iterator pos);
    size_type        erase(const Key& x);
    void            erase(iterator first, iterator last);
    void            clear();
 
    // observers
    key_compare        key_comp() const;
    size_type        page_size() const;
    XDR_Stream&        xdrstream();
         // operations
    iterator        find(const Key& x);
    size_type        count(const Key& x);
 
    iterator        lower_bound(const Key& x);
    iterator        upper_bound(const Key& x);
    std::pair<iterator, iterator>
                    equal_range(const Key& x);
 
    // utilities
    void            reindex();
    DeleteStrategy    set_delete_strategy(DeleteStrategy strategy);
    UpdateStrategy    set_update_strategy(UpdateStrategy strategy);
    int                set_cache_size(int size);
 
private:
    // private types
    class XIODataStreambuf;
    class XInDataBuf;
    class XOutDataBuf;
    class Page;
    class RootPage;
    class PageCache;
 
        // friends
    friend class Iterator;
    friend class StreamposProxy;
    friend class Page;
    friend class RootPage;

    // data
    Compare                    _comp;
    typename KeyTraits::xio_type _xstream; 
    RootPage*                _root;
    PageCache                _pageCache;
    DeleteStrategy            _dStrategy;
    UpdateStrategy            _uStrategy;
 
    // Iterator utility functions - used by friends
    std::pair<const Key, StreamposProxy>
                    get_value(size_t page, size_t slot);
    void            prev_iter(Iterator& it);
    void            next_iter(Iterator& it);
 
    // StreamposProxy utility functions - used by friends
    void            update_link(size_t page, size_t offset, size_t link);
 
    // BtreeIndex utility functions
    Page*            get_page(size_t pageId);
    Page*            get_free_page();
    void            add_free_page(Page* p);
    iterator        lower_bound(Page* p, int depth, const Key& k);
    iterator        upper_bound(Page* p, int depth, const Key& k);
    iterator        insert(Page*, int depth, const value_type& x);
    std::pair<bool,bool> erase(Page* p, int depth, const Key& k, iterator pos);
 
    void            flush(UpdateStrategy s);
}; //> BtreeIndex 


//
// BtreeIndex inline function definitions
//
template<typename Key, typename Compare, typename KeyTraits, size_t PageSize>
inline bool
BtreeIndex<Key,Compare,KeyTraits,PageSize>::is_open()
{
return _xstream.is_open(); }


template<typename Key, typename Compare, typename KeyTraits, size_t PageSize>
inline 
BtreeIndex<Key,Compare,KeyTraits,PageSize>::operator void*() const
{
    if (_xstream.fail()) return null;
    return const_cast<BtreeIndex*>(this);
}


template<typename Key, typename Compare, typename KeyTraits, size_t PageSize>
inline bool
BtreeIndex<Key,Compare,KeyTraits,PageSize>::operator!() const
{ return _xstream.fail(); } 


template<typename Key, typename Compare, typename KeyTraits, size_t PageSize>
inline bool
BtreeIndex<Key,Compare,KeyTraits,PageSize>::empty()
{ return size() == 0; }


template<typename Key, typename Compare, typename KeyTraits, size_t PageSize>
inline size_t
BtreeIndex<Key,Compare,KeyTraits,PageSize>::size()
{ return _root->total_keys(); }


template<typename Key, typename Compare, typename KeyTraits, size_t PageSize>
inline typename BtreeIndex<Key,Compare,KeyTraits,PageSize>::Iterator
BtreeIndex<Key,Compare,KeyTraits,PageSize>::insert(const Key& key)
{ return insert(value_type(key, 0)); }


template<typename Key, typename Compare, typename KeyTraits, size_t PageSize>
inline Compare
BtreeIndex<Key,Compare,KeyTraits,PageSize>::key_comp() const
{ return _comp; }


template<typename Key, typename Compare, typename KeyTraits, size_t PageSize>
inline size_t
BtreeIndex<Key,Compare,KeyTraits,PageSize>::page_size() const
{ return PageSize; }


template<typename Key, typename Compare, typename KeyTraits, size_t PageSize>
inline XDR_Stream&
BtreeIndex<Key,Compare,KeyTraits,PageSize>::xdrstream()
{
return _xstream; }


template<typename Key, typename Compare, typename KeyTraits, size_t PageSize>
inline typename BtreeIndex<Key,Compare,KeyTraits,PageSize>::DeleteStrategy
BtreeIndex<Key,Compare,KeyTraits,PageSize>::set_delete_strategy(DeleteStrategy s)
{
    DeleteStrategy t = _dStrategy;
    _dStrategy = s;
    return t;
}

template<typename Key, typename Compare, typename KeyTraits, size_t PageSize>
inline typename BtreeIndex<Key,Compare,KeyTraits,PageSize>::UpdateStrategy
BtreeIndex<Key,Compare,KeyTraits,PageSize>::set_update_strategy(UpdateStrategy s)
{ 
    UpdateStrategy t = _uStrategy;
    _uStrategy = s;
    return t;
}


template<typename Key, typename Compare, typename KeyTraits, size_t PageSize>
inline int
BtreeIndex<Key,Compare,KeyTraits,PageSize>::set_cache_size(int size)
{ 
    int t = _pageCache.max_size();
    _pageCache.max_size(size);
    return t;
}


} //> namespace