root/trunk/containers/include/hash_table.h @ 3142

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <cstring>

#include "boost/mpl/if.hpp"
#include "boost/utility/enable_if.hpp"

namespace iwear
{

template<class T, size_t N>
/*constexpr*/ size_t array_size( T(& )[N] )
{
        return N;
}

#define asize(x) (sizeof(x) / sizeof(x[0]))
/*
 * This class aims to be a quite versatile hashtable, where you can control
 * various parameters of its behaviour via template parameters.
 */

/**
 * These enums control basic behaviours of the hashing functions built in. If
 * you need something else for the trivial types, you need to roll your own
 * structure that does this.
 * @note You can create specializations for various other hashing classes
 * yourself, and specify them at the same point where you instantiate them
 * otherwise. To do that, simply specialize for other numerical values, like
 * hash<T,(hashclass)3> and use that type wherever you want.
 */
enum class hashclass : int
{
        identity, ///< If possible, use the value as the result of the hash, to suppress possible errors we static_cast to size_type
        trivial,  ///< Use a trivial hashing, like multiplication with a large prime
        fnv       ///< Use a hashing scheme similar to fnv (but not quite exactly)
};

/**
 * This is a value metafunction that takes an integer as input and outputs the
 * same value of the type hashclass. Whenever the input could be something
 * convertible to int, this is a wrapper for the case you don't like casts. You
 * can use it like make_hashclass<5>::value instead of (hash_class)5
 */
template<int hc>
struct make_hashclass
{
    static const hashclass value = (hashclass)hc;
};

/**
 * This class is for the actual hashing. The user is supposed to specialize it
 * for his own types in order to get the hashing behaviour he wants. It might
 * be possible though, that for some reasons another hashing is needed for the
 * same datatype. To compensate for this we allow for specifying the type of
 * the hash struct later in the hash_table so that a user can use its own
 * there.
 * @note per default a trivial hashing is used, which is often a good balance
 * between speed and degradation effects.
 * @note We will always use this type without explicitly specifying its
 * namespace. Therefore it could be possible that sometimes something from your
 * namespace is picked up, be aware of that.
 * @warning Various hashes have different degradation properties, like
 * avalanche effects and similar. Consider carefully what you chose here, and
 * in that consideration, think about who controls the data. If you control the
 * data you can usually be much more lax with the requirements as you can make
 * sure that no strange clustering effects can occur.
 */
template<class T, hashclass HC >
struct hash
{
    typedef size_t size_type;
    typedef T item_type;
private:
    /**
     * If you get a compile error here saying that this is private, you need to
     * specialize your own version of hash for your item_type with this
     * function not being private. This generic version is just to communicate
     * a defined interface.
     */
    size_type operator()( const item_type& i );
    size_type operator()( item_type* i );
};

namespace __detail
{

template<class size_type, int N>
struct roundup
{
        static size_type roundup_recurse( size_type v )
        {
                v = roundup<size_type,N/2>::roundup_recurse(v);
                v |= v >> N;
                return v;
    }
};

template<class size_type>
struct roundup<size_type,1>
{
        static size_type roundup_recurse( size_type v )
        {
                v |= v >> 1;
                return v;
        }
};

template<class size_type>
size_type roundup2( size_type v )
{
        v--;
        v = roundup<size_type,sizeof(v)>::roundup_recurse(v);
        v++;
        return v;
}

} // namespace __detail

#if 0  // old shit ;)
/**
 * This class controls how the sizes of the hashtable are selected, as well as
 * how the hash value is actually transformed into an index.
 * @param binary decides whether the hashtable uses power of two sizes only,
 * and then the operator& to determine indices or whether a predefined list of
 * primes is used with the operator%.
 */
template<bool binary >
struct hash_selection
{
    typedef size_t size_type;

    /**
     * With this we control whether the hashtable will automatically resize
     * when it detects after an insert that it is now too small, or whether the
     * user is responsible for calling the corresponding check function.
     * @note that in no case a check for the size is done, when the slot in the
     * hashtable that was found wasn't already occupied.
     */
    static const bool auto_resize;
    /**
     * required helper function that will determine the type of the pointer
     * being used. You can write your own variant, that will use e.g.
     * boost::offset_ptr so all pointers that are permanently stored in memory
     * are of such a type which means you can store things in shared memory or
     * in a memory mapped file you will be able to relocate.
     */
    template<class T>
    struct add_pointer
    {
        typedef T* type;
    };

    /**
     * The default metafunction for creating the slot item type assumes that we
     * are using a singly linked list for our hashtable.
     */
    template<class T>
    struct slot_item
    {
        typedef typename add_pointer<T>::type type;
    };

    /**
     * Transforms the hash into an actual index.
     * @param hash is the hash as gathered from the hash structure
     * @param size is the current size of the hashtable in number of slots
     */

    static size_type index( size_type hash, size_type size );

    /**
     * @returns true if a resize of the hashtable is recommended, making the
     * hashtable actually bigger. If a shrink is possible, this does not mean a
     * resize is recommended, so this function returns false.
     */
    static bool need_resize( size_type size, size_type filled );

    /**
      Do a resize so the size vs filled ratio is optimized in case too much
     * slots are filled. If there are already enough free slots, no change is
     * made.
     * @returns true iff an actual resize was made.
     */
    static bool resize( size_type size, size_type filled );

    /**
     * Shrinks a hashtable to the least minimum necessary for a proper
     * fillratio of the table. This might be significantly slower as the
     * recommended size used in resize() so that you should only ever call this
     * if you think the hashtable will not be filled in the future.
     */
    static bool shrink( size_type size, size_type filled );
};

template<>
struct hash_selection<false>
{
    template<class R>
    struct add_pointer
    {
        typedef R* type;
    };

    template<class R>
    struct slot_item
    {
        typedef typename add_pointer<R>::type type;
    };

    typedef size_t size_type;
    static size_type index( size_type hash, size_type size )
    {
#ifdef DEBUG
        std::cerr << "hash = " << hash << ", size = " << size << "\n";
#endif
        return hash % size;
    }
};
#endif

struct slot_selector_modulo
{
        static size_t mask_from_length( size_t len )
        {
                return len;
        }

        size_t operator()( size_t hsum, size_t mask ) const
        { 
#ifdef DEBUG
                std::cerr << "slot_selector_modulo()(" << hsum << " % " << mask << " == " << (hsum % mask) << "\n";
#endif
                return hsum % mask;
        }
};

struct slot_selector_power2
{
        static size_t mask_from_length( size_t len )
        {
                return len - 1;
        }

        size_t operator()( size_t hsum, size_t mask ) const 
        {
#ifdef DEBUG
                std::cerr << "slot_selector_power2()(" << hsum << " & " << mask << " == " << (hsum & mask) << "\n";
#endif
                // assert( mask+1 is power of 2 );
                return hsum & mask;
        }
};


// ############################################# # # # # # # # # # # # # # # # # # # # # # # # #
//
// for the factor 1.1
size_t primetable11[] =
{
        2,                              3,                              5,                              7,                              11,                             13,                             
        17,                             19,                             23,                             29,                             31,                             37,                             
        41,                             43,                             53,                             59,                             67,                             73,                             
        83,                             89,                             97,                             107,                    127,                    139,                    
        157,                    167,                    191,                    211,                    223,                    251,                    
        269,                    293,                    331,                    359,                    389,                    431,                    
        479,                    521,                    569,                    631,                    691,                    757,                    
        827,                    911,                    1009,                   1103,                   1213,                   1327,                   
        1459,                   1607,                   1777,                   1949,                   2137,                   2347,                   
        2591,                   2843,                   3137,                   3449,                   3779,                   4157,                   
        4583,                   5039,                   5527,                   6079,                   6689,                   7369,                   
        8089,                   8923,                   9787,                   10771,                  11863,                  13033,                  
        14327,                  15761,                  17333,                  19069,                  20981,                  23071,                  
        25391,                  27917,                  30703,                  33773,                  37159,                  40867,                  
        44953,                  49451,                  54401,                  59833,                  65827,                  72421,                  
        79631,                  87613,                  96353,                  105997,                 116593,                 128257,                 
        141073,                 155191,                 170701,                 187763,                 206543,                 227189,                 
        249911,                 274909,                 302399,                 332641,                 365903,                 402487,                 
        442721,                 487007,                 535697,                 589273,                 648191,                 713021,                 
        784307,                 862739,                 949019,                 1043921,                1148311,                1263133,                
        1389439,                1528399,                1681241,                1849349,                2034283,                2237743,                
        2461477,                2707651,                2978399,                3276241,                3603857,                3964229,                
        4360649,                4796749,                5276387,                5804023,                6384439,                7022867,                
        7725161,                8497681,                9347441,                10282177,               11310413,               12441439,               
        13685579,               15054157,               16559561,               18215501,               20037053,               22040771,               
        24244837,               26669317,               29336243,               32269877,               35496869,               39046541,               
        42951203,               47246359,               51970957,               57168043,               62884859,               69173333,               
        76090681,               83699761,               92069729,               101276699,              111404369,              122544787,              
        134799271,              148279217,              163107157,              179417839,              197359663,              217095589,              
        238805207,              262685693,              288954269,              317849681,              349634651,              384598153,              
        423057949,              465363781,              511900133,              563090189,              619399213,              681339121,              
        749473051,              824420407,              906862427,              997548689,              1097303609,             1207033967,             
        1327737391,             1460511163,             1606562357,             1767218597,             1943940541,             2138334589,             
        2352168083UL,   2587384981UL,   2846123519UL,   3130735931UL,   3443809657UL,   3788190661UL,           
        4167009773UL,           
};

// for the factor 1.5
size_t primetable15[] = 
{
        2,                              5,                              7,                              11,                             17,                             29,                             
        41,                             59,                             89,                             137,                    199,                    307,                    
        449,                    673,                    1009,                   1511,                   2267,                   3391,                   
        5087,                   7639,                   11443,                  17167,                  25741,                  38611,                  
        57917,                  86923,                  130337,                 195469,                 293201,                 439799,                 
        659689,                 989533,                 1484291,                2226431,                3339643,                5009471,                
        7514231,                11271319,               16906949,               25360441,               38040619,               57060931,               
        85591417,               128387137,              192580621,              288870937,              433306427,              649959679,              
        974939417,              1462409083,             2193613607UL,   3290420401UL
};

template<
int grow_load_pm,
int perfect_load_pm,
int shrink_load_pm
>
struct resize_base
{
// XXX one day take some time and think about whether we can safely do all this
// with integer only maths. Or even provide a template parameter for this.
        static const float shrink_load = shrink_load_pm / 1000.0f;
        static const float perfect_load = perfect_load_pm / 1000.0f;
        static const float grow_load = grow_load_pm / 1000.0f;

        /**
         */
//      __attribute__((noinline))
        static bool need_grow( size_t elements, size_t slots )
        {
                // XXX A later design could sacrifice a few bytes to store the actual
                // values in elements for grow and shrink barriers, so that a check
                // against those only needs to compare against them. Of course in case
                // of a real resize event those values will need to be recalculated.
                // Since this is a speed vs space trade-off we will provide template
                // parameters for that with proper defaults.

                // calculate actual load factor
                double lfactor = double(elements)/slots;
#ifdef DEBUG
                std::cerr << "need_grow load factor " << lfactor << "\n";
                std::cerr << "load factor at which to start growing " << grow_load << "\n";
                std::cerr << "returning " << ( lfactor >= grow_load ) << "\n";
#endif
                if( lfactor >= grow_load )
                {
                        return true;
                }
                else
                {
                        return false;
                }
        }

        static bool need_shrink( size_t elements, size_t slots )
        {
                // calculate actual load factor
                // XXX Check whether the compiler can properly inline and elide this
                // calculation in the case need_resize() will be called.
                double lfactor = double(elements)/slots;
#ifdef DEBUG
                std::cerr << "need_shrink load factor " << lfactor << "\n";
                std::cerr << "load factor at which to start shrinking " << shrink_load << "\n";
                std::cerr << "returning " << ( lfactor < shrink_load ) << "\n";
#endif
                if( lfactor < shrink_load )
                {
                        return true;
                }
                else
                {
                        return false;
                }
        }

        static bool need_resize( size_t elements, size_t slots )
        {
                return need_grow(elements,slots) || need_shrink(elements,slots);
        }

};

template<
int grow_load_pm,
int perfect_load_pm,
int shrink_load_pm,
size_t* prime_table_start,
size_t prime_table_size
>
struct resize_primetable_template
        : resize_base<grow_load_pm,perfect_load_pm, shrink_load_pm>
{
        typedef resize_base<grow_load_pm,perfect_load_pm, shrink_load_pm> base_type;

        typedef slot_selector_modulo slot_selector;

        static size_t max_size( )
        {
                return prime_table_start[prime_table_size-1];
        }
        /**
         * The optimal size will be calculated in the way that from the desired
         * load factor (per default 0.8*elements) on we will take the next bigger
         * prime from our table. The table was generated using a start number (89)
         * and multiplying this by 1.5 and then choosing the next prime (and so on,
         * taking the previous result and not the prime as input for multiplication
         * by 1.5 so that you can easier determine the numbers).
         * @note the optimal_size function is potentially expensive and should only
         * be called in the case a resize needs to be done. Determining whether a
         * resize is needed should be done purely on the current sizes load factor.
         */
        static size_t optimal_size( size_t elements )
        {
                // First of all we calculate the number of slots for the desired
                // perfect load factor.
                size_t min_slots = elements / base_type::perfect_load;
                // then search in the provided primetable for a proper prime number.
                size_t* i = std::lower_bound(prime_table_start, prime_table_start + prime_table_size , min_slots);
                if( i == (prime_table_start+prime_table_size) )
                {
                        // XXX refine to a more suited exception type one day
                        throw std::runtime_error("Exceeded built in primetable while generating optimal_size");
                }
                return *i;
        }

        static bool need_resize( size_t elements, size_t slots )
        {
                return (base_type::need_grow(elements,slots) || base_type::need_shrink(elements,slots))
                        // actually ask for shrink only if the amount of elements is really
                        // bigger than the smallest size we would ever have.
                        && prime_table_start[0] < elements;
        }


};

template<
int grow_load_pm = 800,
int perfect_load_pm = 700,
int shrink_load_pm = 300
>
struct resize_primetable_15
        : resize_primetable_template<grow_load_pm,perfect_load_pm, shrink_load_pm,primetable15,asize(primetable15)>
{
};


// XXX A good default load factor depends on the collision resolution used
template<
int grow_load_pm = 800,
int perfect_load_pm = 700,
int shrink_load_pm = 300
>
struct resize_power2
        : resize_base<grow_load_pm, perfect_load_pm, shrink_load_pm>
{
        typedef resize_base<grow_load_pm, perfect_load_pm, shrink_load_pm> base_type;

        typedef slot_selector_power2 slot_selector;

        static size_t max_size( )
        {
                return static_cast<size_t>(-1);
        }
        /**
         * 
         */
        static size_t optimal_size( size_t elements )
        {
                // the optimal size is given a certain load factor the next power of
                // two after the amount of slots needed to achieve this load factor.
                size_t min_slots = elements / base_type::perfect_load;
                // Now find the next power of two...
                size_t s = __detail::roundup2(min_slots);
                return s;
        }
};

struct raw_pointer
{
        template<class T>
        struct pointer
        {
                typedef T* type;
        };
};



// generic anchor hierarchy, to be used by all possible containers that might
// want to use them.

template<class T, class PTR_SELECTOR >
struct anchor_single
{
        typedef T item_type;
        typedef typename PTR_SELECTOR::template pointer<item_type>::type pointer_type;
        typedef decltype(*pointer_type()) reference_type;

        static const bool empty = false;
protected:
        pointer_type next;
public:
        anchor_single( )
                : next(0) // not really necessary but gcc warns otherwise
        {
#ifdef DEBUG
                next = reinterpret_cast<pointer_type>(~0UL);
#endif
        }

        const pointer_type get_next() const { return next; }
        pointer_type get_next() { return next; }
        void set_next( pointer_type ptr ) { next = ptr; }
};

template<class T, class PTR_SELECTOR>
struct anchor_double : public anchor_single<T,PTR_SELECTOR>
{
    typedef anchor_single<T,PTR_SELECTOR> base_type;
    typedef typename base_type::item_type item_type;
    typedef typename base_type::pointer_type pointer_type;
    typedef typename base_type::reference_type reference_type;
protected:
    pointer_type prev;
public:
    const pointer_type get_prev() const { return prev; }
    void set_prev( pointer_type ptr ) { prev = ptr; }
};

template<class T, class PTR_SELECTOR>
struct anchor_btree : protected anchor_double<T,PTR_SELECTOR>
{
    typedef anchor_double<T,PTR_SELECTOR> base_type;
    typedef typename base_type::item_type item_type;
    typedef typename base_type::pointer_type pointer_type;
    typedef typename base_type::reference_type reference_type;

    const pointer_type get_left() const { return base_type::prev; }
    const pointer_type get_right() const { return base_type::next; }

    void set_left( pointer_type ptr ) { base_type::set_prev(ptr); }
    void set_right( pointer_type ptr ) { base_type::set_next(ptr); }

    base_type& get_base() { return *this; } 
    const base_type& get_base() const { return *this; } 
};

namespace avl
{
    enum class skew
    {
        none,
        left,
        right
    };
}

/* need to be adapted to new PTR_SELECTOR non-template variant
template<class T, template<class> class PTR>
struct anchor_avltree : public anchor_btree<T,PTR>
{
    avl::skew sk;
    avl::skew get_skew() const { return sk; }
    void set_skew( avl::skew _sk ) { sk = _sk; }
};

template<class T, template<class> class PTR>
struct anchor_compressed_avltree : public anchor_btree<T,PTR>
{
    typedef anchor_btree<T,PTR> base_type;
    typedef typename base_type::item_type item_type;
    typedef typename base_type::pointer_type pointer_type;
    typedef typename base_type::reference_type reference_type;

    // XXX its likely a good idea to have this as a free utility function somewhere
    static ptrdiff_t get_pointer_bits( const void* ptr, ptrdiff_t mask )
    {
        const char* t = reinterpret_cast<const char*>(ptr);
        const char* null = 0;
        ptrdiff_t d = t - null;
        return (d&mask);
    }
    // abuse boost::mpl::print to emit a warning when sizeof(base) != sizeof(*this)
        avl::skew get_skew() const
        {
                // for efficiency reasons, if possible we only use the left pointer
                if( sizeof(*this) >= 4 )
                {
                        // pointer points always to a multiple of 4, meaning that the lower
                        // two bits are reserved for us. Useful compilers will eliminate
                        // this if.
                        return static_cast<avl::skew>( get_pointer_bits(get_left(), 0x3u));
                }
                else
                {
                        const ptrdiff_t mask = 0x1u;
                        assert( sizeof(*this) >= 2 ); // it cannot be lower, we consist of two distinct objects, that is pointers
                        if( get_pointer_bits(get_left(),mask) ) // lowest bit of left is set
                        {
                                assert( !get_pointer_bits(get_right() & mask) ); // both bits are never set by us, so this must be a bug somewhere
                                return avl::skew::left;
                        }
                        else if( get_pointer_bits(get_right(),mask) ) // lowest bit of left is set
                        {
                                assert( !get_pointer_bits(get_left() & mask) ); // both bits are never set by us, so this must be a bug somewhere
                                return avl::skew::right;
                        }
                        // no bit is set, skew is none
                        return avl::skew::none;
                }
        }

    void set_skew( avl::skew _sk );

    // XXX its likely a good idea to have this as a free utility function somewhere
        template<class U>
        U* get_masked_pointer( const void* ptr, ptrdiff_t mask )
        {
                U* ret;
                const char* t = reinterpret_cast<const char*>(ptr);
                const char* null = 0;
                ptrdiff_t d = t - null;
                d &= ~mask; // mask "off" the bits
                ret = static_cast<U*>(null + d);
                return ret;
        }

    const pointer_type get_left() const 
    {
        if( sizeof(*this) >= 4 )
        {
            return get_masked_pointer<const pointer_type>(base_type::get_left(),0x3u);
        }
        else
        {
            return get_masked_pointer<const pointer_type>(base_type::get_left(),0x1u);
        }
    }

    const pointer_type get_right() const 
    { 
        if( sizeof(*this) >= 4 )
        { // in this case, the right pointer is not used for special bits
            return base_type::get_right();
        }
        else
        { // in this case, its the lowest bit, mask it off
            return get_masked_pointer<const pointer_type>(base_type::get_right(),0x1u);
        }
    }

    void set_left( pointer_type ptr )
    {
        // XXX We should make this function act upon the actual skew and
        // sizeof(*this) and maybe change the skew only if affected by the
        // pointer or so.
        avl::skew s = get_skew();
        base_type::set_left(ptr);
        set_skew(s);
    }

    void set_right( pointer_type ptr )
    {
        avl::skew s = get_skew();
        base_type::set_right(ptr);
        set_skew(s);
    }
};
*/

enum class occupancy : unsigned char
{
        free,
        deleted,
        occupied
};

template<bool>
struct anchor_occupancy_storage;

template<>
struct anchor_occupancy_storage<true>
{
        occupancy occupied;
};

template<>
struct anchor_occupancy_storage<false>
{
};

template<bool>
struct anchor_hash_storage;

template<>
struct anchor_hash_storage<true>
{
        size_t hash;
};

template<>
struct anchor_hash_storage<false>
{
};

template<class anchor_type, bool empty>
struct anchor_storage;

template<class anchor_type>
struct anchor_storage<anchor_type,false>
{
        anchor_type anchor;
};

template<class anchor_type>
struct anchor_storage<anchor_type,true>
{
};

template< class anchor_type, bool store_hash, bool store_occupancy>
struct anchor_member_mixer :
        anchor_storage<anchor_type, anchor_type::empty>,
        anchor_occupancy_storage<store_occupancy>,
        anchor_hash_storage<store_hash>

{
};

template<class ANCHOR_ACCESSOR>
struct single_inserter_template
{
        typedef ANCHOR_ACCESSOR anchor_accessor;

        template<class AA>
        struct rebind
        {
                typedef single_inserter_template<AA> other;
        };

        // XXX choose per template parameter whether to put things at the beginning
        // or the end of the list
        template<
                class IT,
                class SZ,
                class SLA
                >
        static bool insert( IT* i, SZ idx, SLA** sa )
        {
                SLA*& slot = sa[idx];
#ifdef DEBUG
                std::cerr << "Chosen slot = " << (void*)slot << "\n";
#endif
                anchor_accessor aa;
                aa(i)->anchor.set_next(0);
                // XXX if is_occupied(slot) for others
                if( slot )
                {
                        IT* next = slot;
                        while( aa(next)->anchor.get_next() )
                        {
#ifdef DEBUG
                                std::cerr << "Accessing slot/item " << (void*)slot << " and next being ";
#endif
                                next = aa(next)->anchor.get_next();
#ifdef DEBUG
                                std::cerr << (void*)next << "\n";
#endif
                        }
                        assert( next != NULL );
                        // next now contains the last item in the list
                        // XXX singly linked list collision resolution
                        aa(next)->anchor.set_next(i);
                }
                else // its free, just set it
                {
                        slot = i;
                }
                return true;
        }

        template<
                class IT,
                class SZ,
                class SLA
                >
        static bool remove( IT* it, SZ idx, SLA** sa )
        {
                SLA*& slot = sa[idx];
                anchor_accessor aa;
                if( slot == it )
                {
                        // If it is directly sitting at the slot remove it there.
                        slot = aa(it)->anchor.get_next();
#ifdef DEBUG
                        aa(it)->anchor.set_next( reinterpret_cast<IT*>(~0UL) );
#endif
                        return true;
                }
                else if( slot )
                {
                        // It is not the first in the slot but there is something
                        IT* next = slot;
                        while( aa(next)->anchor.get_next() )
                        {
                                IT* prev = next;
                                next = aa(next)->anchor.get_next();
                                if( next == it )
                                {
                                        aa(prev)->anchor.set_next( aa(next)->anchor.get_next() );
#ifdef DEBUG
                                        aa(next)->anchor.set_next( reinterpret_cast<IT*>(~0UL) );
#endif
                                        return true;
                                }
                        }

                }
                return false;
        }

};

template<class ANCHOR_ACCESSOR>
struct double_inserter_template
{
        typedef ANCHOR_ACCESSOR anchor_accessor;

        template<class AA>
        struct rebind
        {
                typedef double_inserter_template<AA> other;
        };

        template<
                class IT,
                class SZ,
                class SLA
                >
        bool operator()( IT* i, SZ idx, SLA** sa )
        {
                SLA*& slot = sa[idx];
#ifdef DEBUG
                std::cerr << "Chosen slot = " << (void*)slot << "\n";
#endif
                // XXX if is_occupied(slot) for others
                if( slot )
                {
                        anchor_accessor aa;
                        IT* next = slot;
                        while( aa(next)->get_next() )
                        {
#ifdef DEBUG
                                std::cerr << "Accessing slot/item " << (void*)slot << " and next being ";
#endif
                                next = aa(next)->get_next();
#ifdef DEBUG
                                std::cerr << (void*)next << "\n";
#endif
                        }
                        // next now contains the last item in the list
                        // XXX singly linked list collision resolution
                        aa(next)->set_next(i);
                        aa(i)->set_next(0);
//                      ++elem_size;
                }
                else // its free, just set it
                {
                        slot = i;
//                      ++elem_size;
                }
                return true;
        }
};

struct double_inserter
{
        template<class AA>
        struct rebind
        {
                typedef double_inserter_template<AA> other;
        };
};

struct single_inserter
{
        template<class AA>
        struct rebind
        {
                typedef single_inserter_template<AA> other;
        };
};


struct resolution_single_linked_list
{
        template<class T, class PTR_SELECTOR>
        struct anchor_member_type
        {
                typedef anchor_single<T,PTR_SELECTOR> type;
        };
        typedef single_inserter inserter;
};


/**
 * This is a metafunction that provides the proper type for an anchor, given
 * certain parameters.
 * @tparam COLLISION_RESOLUTION is the metafunction that provides the way
 * collisions are resolved. Depending on that the anchor may contain pointers
 * (e.g. for linked list resolves) or also simply nothing.
 * @tparam PTR_SELECTOR is the selector metafunction that transforms types into
 * pointers to that type. We use it everywhere so that we can use special
 * pointer types (shared pointers, relative pointers etc.)
 * @tparam store_occupancy tells us whether we should provide storage for
 * whether this item is occupied or not. This makes only sense if you want to
 * use an open addressing hashtable, as such the collision resolution should be
 * chosen in an appropriate way.
 * @tparam store_hash tells us whether the hash value is ever stored or not. If
 * it is stored, then it will be in a member of type size_t.
 */
template<
class T,
class COLLISION_RESOLUTION = resolution_single_linked_list ,
class PTR_SELECTOR = raw_pointer,
bool store_hash = false,
bool store_occupancy = false
>
struct anchor_member_chooser
{
        typedef 
                anchor_member_mixer<
                typename COLLISION_RESOLUTION::template anchor_member_type<T,PTR_SELECTOR>::type,
                store_hash,
                store_occupancy>
                type;
};

// ############################################# # # # # # # # # # # # # # # # # # # # # # # # #
// 
// We do not want the user to manually chose (however he of course can do so)
// the necessary anchor for his hash table, but we want to provide a
// metafunction that can do so. Therefore we create here something that
// collects all the properties for the future hashtable that will not depend on
// the type of data being stored. Within that embedded will be a metafunction
// that chooses the anchor type.
// Those marked with * influence the anchor type
//
// Not all of these things may be combined
//*- collision resolution scheme
//   - single linked list
//   - double linked list
//   - jumping (various weird kinds)
//   - rehashing (various ways, including one with alternative hashers)
//   - cookoo hashing
// - allocator storage
//   - whether to store the allocator passed to the ctor in a member variable or not
// - comparator storage
//   - whether to store the comparator passed to the ctor in a member variable or not
//*- data storage
//   - in the table (OA like), item will be copied (precludes linked list et al collision resolution)
//   - as pointers, items will be "linked" into the datastructure
//*- pointer type
//   - default is a raw pointer
//   - metafunction that will lead to a pointer type when fed with T
//*- store hash
//   - storing the hash (without the upper bit) set might be necessary in case
//     the hashing is so expensive that its worth it
// - ownership
//   - data structure owns data (on destruction, all items are destroyed)
//   - the user owns the data. On destruction, items will not be touched at all
// - size and access
//   - size is always multiple of 2, access to slots is done by masking of bits
//   - size is an arbitrary number (likely prime). slots will be chosen by
//     taking the remainder of division modulo the size
// - table storage
//   - default is std::vector
//   - a metafunction or template can be provided that will determine the type
//     of the underlying table storage.
// - the size_type
//   - type that is used to store various underlying values
// - automatic resize on insert/remove.
//   - enable per template
//   - disable per template
//   - have a runtime changeable flag with templated default
// - duplicate entries
//   - allow/disallow per template parameter
// - compare hash
//   - if store hash is enabled, before comparing the elements themselves, the hash is compared
// - allocator and storage
//   - an allocator must be specified which can be stored optionally, have a param that tells us
// - same for a comparator
// - also for the hasher we might want to store it (or not)
// The result must be in the hash_config passed to the hash_table
// ############################################# # # # # # # # # # # # # # # # # # # # # # # # #
// For the following things, we need to have T available in some way.
// - hashing
//   - user provides a functor or metafunction or whatever that can hash T into
//     an integer
//   - We provide means for hashing standard datastructures and arbitrary byte
//     buffers in three categories, among the user could chose for his datatypes too.
//       - identity. Do not hash things, useful for those cases where the key
//         is known to be distributed properly
//       - trivial is a very simple way to determine the hash
//       - fnv uses a bit more complex hashing, similar to fnv
// - anchor access
//   - the user provides a mean for accessing the appropriate anchor for this
//     hashtable when having a T* at hand
//   - for OA-like hashtables that store copies in the table itself, the anchor
//     shall provide a way to mark items as occupied, free or deleted. Each
//     element *must* be default constructible and *must* be initially marked
//     as free. Failure to do so will lead to undefined behaviour
// The result must be in the hash_accessor passed to the hash_table
namespace collision_resolution
{

/**
 * This shall resolve collisions by putting things in a singly linked list.
 * We gonna need functionality for specifying the type of the anchor and a
 * function to resolve things in case of a collision. Lets start with simple
 * ones and adapt the interface for every of them.
 */
#if 0
template<
class T,
class POINTER_TYPE,
class ANCHOR_ACCESSOR
>
struct resolve_single_linked
{
        typedef T item_type;
        typedef POINTER_TYPE<item_type>::type pointer_type;
        typedef anchor_single<T,POINTER_TYPE> anchor_type;
        typedef ANCHOR_ACCESSOR<anchor_type> anchor_accessor;

        /**
         * @param colliding is the element at the slot where the collision has been detected.
         * @param added is the element that shall be added to the hashtable. After
         * returning, this element is a successful member of the hashtable.
         */
        static void resolve( T* colliding, T* added )
        {
                T* nx = colliding;
                T* tmp;
                while(tmp = anchor_accessor::get(nx).get_next())
                {
                        nx = tmp;
                }
                anchor_accessor::get(nx).set_next(added);
                anchor_accessor::get(added).set_next(0);
        }

        struct iterator
        {
                pointer_type* slot_position;
                pointer_type item;
                iterator& operator++(int);
                iterator& operator++();
        };
};
#endif

}

#if 0
template<
class T,
template<class,class> class COLLISION_RESOLUTION,
template<class,class> class DATA_ACCESS,
template<class> class POINTER_TYPE
      >
struct hash_intrusion_config // weird name but for OA style we don't have any anchor...
{
        /**
         * Just define the type of the object that shall be stored
         */
        typedef T item_type;

        /**
         * Metafunction that transforms any item type into the pointer type
         * We leave this as a metafunction and do not directly use a pointer type
         * since maybe at other places we need pointers too but have some different
         * item type. Just be flexible.
         */
        template<class IT>
        struct pointer_type
        {
                typedef typename POINTER_TYPE<IT>::type type;
        };

        /**
         * This should somehow resemble the slot type. It will depend on the actual
         * planned collision resolution and also on where to store what, usually
         * its though either the element itself or a pointer to it.
         */
        template<class IT>
        struct slot_type
        {
        };

        /*
         * anchor type depends on collision resolution. If its single/double linked
         * list then we have anchors, if its some re-hashing or OA we just have
         * nothing. Ideally the anchor would not eixst then giving us compile time
         * errors.
         */
        typedef typename COLLISION_RESOLUTION<T,
                        STORE_HASH,
                        POINTER_TYPE
                        >::anchor_type anchor_type;
};
#endif

template<
class T0,
class T1,
class T2,
class T3,
class T4,
class T5
      >
struct hash_config
{
};

// Here we wrap the storage type that the user wants us to use in a hashtable 
template<class T>
struct storage_wrapper
{
};

template<class A>
struct anchor_accessor_single
{
    typedef typename A::item_type item_type;
    A* operator()( item_type* i )
    {
        // XXX This all is total mockup, we really need a way to
        // flexibly accessing the proper member (possible via member
        // pointers). This interface must be suitable for the
        // generated item types from UDTs.
        return &(i->anchor); // XXX make this a refernece
    }
};

#if 0
template<class T>
struct hash_anchor_oa
{
    /**
     * To mark this element as occupied/free/deleted
     */
    unsigned char status;
};

template<class T>
struct hash_item_double
{
    typedef T item_type;
    hash_anchor_double<T> anchor;
    T item;
};

/**
 * There is no real anchor for OA based items. Either we have just a plain
 * pointer to them or they are already fully in the table.
 */
template<class T>
struct hash_item_oa
{
    typedef T item_type;
};

template<class T>
struct hash_item_single
{
    typedef T item_type;
    hash_anchor_single<T> anchor;
    T item;
};

/**
 * For open addressing based hashtables there is the possibility of using this
 * only as collision resolution, and just store the pointers in there, or to
 * store the whole object in there. This is the variant of the item thats just
 * for the pointers.
 */
template<class T>
struct hash_item_oa_pointer
{
    typedef T item_type;
    item_type* item;
};

template<class T>
struct hash_item_oa_item
{
    typedef T item_type;
    item_type item;
};
#endif
/**
 * This class controls how the single items that are being stored in the table
 * are accessed.
 * If there is no special accessor that uses anchors embedded in the usertype,
 * then this will generate nodes containing the users type in them and all
 * inserts will be copies instead of "hanging" the node into the table.
 */
template<class T>
struct hash_accessor
{
    typedef typename T::item_type item_type;

};

template<bool store_per_instance, class H>
struct hasher_storage_base;

template<class H>
struct hasher_storage_base<true,H>
{
        H hasher_instance;
};

template<class H>
struct hasher_storage_base<false,H>
{
        static H hasher_instance;
};

template<class H>
H hasher_storage_base<false,H>::hasher_instance;

template<bool store_per_instance, class H>
struct allocator_storage_base;

template<class H>
struct allocator_storage_base<true,H>
{
        H allocator_instance;
};

template<class H>
struct allocator_storage_base<false,H>
{
        static H allocator_instance;
};

template<class H>
H allocator_storage_base<false,H>::allocator_instance;

template<
class T,
class ATYPE,
ATYPE T::* AMEMBER
>
struct anchor_member_accessor
{
        ATYPE* operator()( T& t ) { return &( t.*AMEMBER); }
        ATYPE* operator()( T* t ) { return &( t->*AMEMBER); }
};

template<class T>
struct item_compare
{
        bool operator()( const T& l, const T& r ) const
        {
                return l == r;
        }
};

template< class T , class K , K T::* M >
struct member_compare
{
        template<class R>
        bool operator()( const T& l, const R& r ) const
        {
                return l.*M == r;
        }

        bool operator()( const T& l, const T& r ) const
        {
                return l.*M == r.*M;
        }

};
struct auto_size_always
{
        bool auto_size( ) const { return true; }
};

struct auto_size_never
{
        bool auto_size( ) const { return false; }
};

struct empty_base_owns
{
};

struct empty_base_size
{
};


enum class storage_levels
{
        storage_level_auto_size,
        storage_level_owns_items
};

struct auto_size_bool_storage
{
        bool a_size;

        template<int>
        void store( bool b )
        {
                a_size = b;
        }

        template<int>
        bool load( void ) const
        {
                return a_size;
        }
};

struct owns_items_bool_storage
{
        bool o_items;

        template<int>
        void store( bool b )
        {
                o_items = b;
        }

        template<int>
        bool load( void ) const
        {
                return o_items;
        }
};
/**
 * important: This must always go at least once through rebind to make the
 * mpl::if_c call so the use_bitset_storage parameter is reflected correctly.
 */
template<bool def = true, bool use_bitset_storage = true, class T = void >
struct auto_size_runtime
        : public boost::mpl::if_c<use_bitset_storage,empty_base_size,auto_size_bool_storage>::type
{
        auto_size_runtime( )
        {
                set_auto_size(def);
        }

        static const storage_levels storage_level = storage_levels::storage_level_auto_size;

        static const bool needs_bitset_storage = use_bitset_storage;

        void set_auto_size( bool en = true)
        {
                static_cast<T*>(this)->template store<storage_level>(en);
        }

        bool auto_size( ) const
        {
                return static_cast<const T*>(this)->template load<storage_level>();
        }

        template<class U>
        struct rebind
        {
                typedef auto_size_runtime<def,use_bitset_storage,
                        typename boost::mpl::if_c<use_bitset_storage, U, auto_size_bool_storage>::type > other;
        };
};

template<bool def = true, bool use_bitset_storage = true, class T = void >
struct owns_items_runtime
        : public boost::mpl::if_c<use_bitset_storage,empty_base_owns,owns_items_bool_storage>::type
{
        owns_items_runtime( )
        {
                set_owns_items(def);
        }

        static const storage_levels storage_level = storage_levels::storage_level_owns_items;

        static const bool needs_bitset_storage = use_bitset_storage;

        void set_owns_items( bool en = true)
        {
                static_cast<T*>(this)->template store<storage_level>(en);
        }

        bool owns_items( ) const
        {
                return static_cast<const T*>(this)->template load<storage_level>();
        }

        template<class U>
        struct rebind
        {
                typedef owns_items_runtime<def,use_bitset_storage,
                        typename boost::mpl::if_c<use_bitset_storage, U, owns_items_bool_storage>::type > other;
        };
};



template<class T0, class T1>
struct policy_bool_storage :
        T0::template rebind<policy_bool_storage<T0,T1> >::other,
        T1::template rebind<policy_bool_storage<T0,T1> >::other
{
        bool b0 : 1;
        bool b1 : 1;

        template<unsigned N>
        void store( bool b )
        {
                switch(N)
                {
                        case 0:
                                b0 = b;
                                break;
                        case 1:
                                b1 = b;
                                break;
                        // intentionally no default case, anything else here is UB
                }
        }

        template<unsigned N>
        bool load( void ) const
        {
                switch(N)
                {
                        case 0:
                                return b0;
                        case 1:
                                return b1;
                }
        }
};

struct three_bytes_test
{
        char c0;
        char c1;
        char c2;
};
#if 0
// planned final class interface something like:
hash_table<T,ACCESSOR,HASHER,
        store_hasher<true>,
        equal_comparator<COMPARE>,
        size_type<int>,
        auto_size<auto_size_runtime<false> >,

#endif

template<bool STORE_MASK, class SIZE_TYPE, class SLOT_RESIZER>
struct mask_storage_base;

template<class SIZE_TYPE, class SLOT_RESIZER>
struct mask_storage_base<true,SIZE_TYPE,SLOT_RESIZER>
{
        typedef SLOT_RESIZER slot_resizer;
        typedef typename slot_resizer::slot_selector hash_slot_selector;
        typedef SIZE_TYPE size_type;

        size_type h_mask;

        void reset_mask( size_t len )
        {
                h_mask = hash_slot_selector::mask_from_length(len);
        }

        size_type hash_mask( size_t /*len*/ ) const
        {
                return h_mask;
        }
};

template<class SIZE_TYPE, class SLOT_RESIZER>
struct mask_storage_base<false,SIZE_TYPE,SLOT_RESIZER>
{
        typedef SLOT_RESIZER slot_resizer;
        typedef typename slot_resizer::slot_selector hash_slot_selector;
        typedef SIZE_TYPE size_type;

        void reset_mask( size_t /*len*/ )
        {
        }

        size_type hash_mask( size_t len ) const
        {
                return hash_slot_selector::mask_from_length(len);
        }
};

/**
 */
template<class T
, class SIZE_TYPE
, class HASHER
, bool STORE_HASHER
, bool STORE_MASK
, class SLOT_RESIZER
, class ANCHOR_ACCESSOR
, class COMPARE
, class INSERTER
, class AUTOSIZE
, class OWNAGE
    >
class hash_table :
        protected hasher_storage_base<STORE_HASHER,HASHER>,
        protected mask_storage_base<STORE_MASK,SIZE_TYPE,SLOT_RESIZER>,
//      protected allocator_storage_base<STORE_ALLOCATOR,ALLOCATOR>
        // XXX MPL check for whether we do not better derive from empty base
        public policy_bool_storage<AUTOSIZE, OWNAGE>
        // XXX later check how many size_type members we have at most and at least.
        // If this differs much, and they are also shattered around then it could
        // make sense to do something like the policy_bool_storage for size_type so
        // that alignment issues due to derivation do not play any role.
{
public:
        typedef policy_bool_storage<AUTOSIZE, OWNAGE> pbstorage;
    /**
     * This is the selector type that will give us many mayn informations about
     * other types.
     */
//    typedef S hash_selector;

    /**
     * This is the type of the items or "nodes" that the user will put into our
     * hashtable. Depending on the selector, our array will contain those items
     * explicitly, or pointers to them, that then will either resemble singly
     * linked or doubly linked lists.
     */
    typedef T item_type;

        typedef SIZE_TYPE size_type;
        typedef item_type* slot_item_type;
//      typedef std::vector<slot_item_type> table_type;
        typedef slot_item_type* table_type;

        typedef SLOT_RESIZER slot_resizer;
        typedef typename slot_resizer::slot_selector hash_slot_selector;
        typedef ANCHOR_ACCESSOR anchor_accessor;

        typedef COMPARE compare;

//      typedef INSERTER inserter;
        typedef typename INSERTER::template rebind<ANCHOR_ACCESSOR>::other inserter;


//    typedef typename hash_selector::size_type size_type;
//    typedef K key_type;
//    typedef typename hash_selector::template slot_item<item_type>::type slot_item_type;
//    typedef typename hash_selector::template add_pointer<slot_item_type>::type table_type;

    /**
     * We are a nullary metafunction returning ourselves. Who knows what this
     * is good for...
     */
    typedef hash_table type;
//    typedef V<slot_item_type> sequence_type;
//    typedef IT iterator;
//    typedef IT const_iterator;
 /*   template<class T,...>
    struct 
    {
        typedef hash_table<T,...> type;
    } helper_type;
    */
private:
        table_type data;

        /**
         * Amount of elements actually contained within the hashtable.
         */
        size_type elem_size;

        /**
         * The length of the slots array/vector.
         */
        size_type h_length;

protected:
public:
        hash_table( size_type i_s ) :
                elem_size(0)
        {
                h_length = slot_resizer::optimal_size(i_s);
                data = new slot_item_type[h_length];
                // XXX This fill is redundant if the slot item type is a UDT. It makes
                // only sense if it is a pointer type.
                std::fill_n( data, h_length, slot_item_type());
                this->reset_mask(table_size());
#ifdef DEBUG
                std::cerr << "i_s = " << i_s << ", h_length " << h_length << ", h_mask = " << this->hash_mask(table_size()) << "\n";
#endif
        }

        /* currently broken, recreate as soon as the above ctor is stable and we
         * can provide useful defaults here.
         * XXX Make sure empty hashtables work well with no dynamic storage
         * allocated. (especially iterators etc. will have to work properly)
        hash_table( ) :
                data(0),
                elem_size(0),
                h_mask(0)
        {
        }
        */

        ~hash_table( )
        {
                // XXX allocation and deallocation should be routed through a policy so
                // we can use policies that allocate in e.g. memory mapped files using
                // relative pointers.
                clear();
                delete[] data;
        }

        hash_table( const hash_table& ) = delete;
        hash_table& operator=( const hash_table& ) = delete;

    // insert variant that allows duplicates and uses single linked lists for
    // collision resolution.
    /**
     * @returns true if the insert was successfully, the item should be removed
     * from the structure prior to deletion, as removing will likely need
     * access to the item. If false is returned, this means that the item has
     * not been inserted. In this case the user is always responsible for
     * handling this item, e.g. delete it.
     */
//    IWEAR_WARN_UNUSED_RESULT
        bool insert( item_type* i )
        {
                // XXX note: a shrink on insert doesn't really make sense. If the table
                // is bigger then it is because someone has removed something without
                // having the table shrink, or its being constructed to hold many
                // elements.
                if( maybe_grow() )
                {
#ifdef DEBUG
                        std::cerr << "Hashtable changed its size\n";
#endif
                }
                return insert_direct( i );
        }

        /*private*/
        bool insert_direct( item_type* i )
        {
#ifdef DEBUG
//              std::cerr << "sizeof(pbstorage) " << sizeof(pbstorage) << "\n";
#endif
#ifdef DEBUG
                std::cerr << "Inserting " << i << "\n";
#endif
                // generate hash
                size_type hvalue = hasher_instance(i);
#ifdef DEBUG
                std::cerr << "hvalue = " << hvalue << "\n";
#endif
                // generate slot position
                size_type idx = hash_slot_selector()(hvalue,this->hash_mask(table_size()));
#ifdef DEBUG
                std::cerr << "idx = " << idx << ", data is " << (void*)data  << "\n";
#endif

                // get the slot at hands...
                // although the table_type might be some relative pointer thingie, we
                // use a plain pointer here since this is for internal purposes only
                // and any compatible pointer should have conversions to/from us

                bool ret = inserter::insert(i,idx,&data[0]);
                if( ret )
                {
                        elem_size++;
                }
                // XXX check whether duplicates are allowed
                // do collision prevention
                // set slot and/or do list linking, if not already done by
                // collision prevention
                return false;
        }

        void resize_slots( size_t nslots )
        {
#ifdef DEBUG
                std::cerr << "resize_slots(" << nslots << ")\n";
#endif
                assert( nslots >= size() );
                // XXX Invent some smart pointer like things to make this all exception
                // safe.

                // Save a bunch of useful old values
                table_type odata = data;
                size_type olen = h_length;
                size_type omask = this->hash_mask(h_length);
#ifdef DEBUG
                size_type oelem = elem_size;
#endif

                // now set the new wanted values
                h_length = nslots;
                data = new slot_item_type[h_length];
                std::fill_n( data, h_length, slot_item_type());
                this->reset_mask(h_length);

                // Since for inserting we pretend to be an empty hashtable currently we
                // set our size to 0
                elem_size = 0;

#ifdef DEBUG
#ifdef DEBUG
                std::cerr << "re-inserting " << oelem << " elements \n";
#endif
#endif
                for( size_t i = 0; i < olen; ++i )
                {
                        slot_item_type it = odata[i];
                        while(it)
                        {
#ifdef DEBUG
                                std::cerr << "re-inserting item chain starting at " << (void*)it << "\n";
#endif
                                // do an erase() on the old data (needs to be kept in sync with
                                // erase()
                                size_type hvalue = hasher_instance(it);
                                size_type idx = hash_slot_selector()(hvalue,omask);
                                inserter::remove(it,idx,&odata[0]);

                                // this will insert into the new storage, not checking and/or
                                // triggering any resizes.
                                insert_direct(it);
                                it = odata[i];
                        }
                }
#ifdef DEBUG
                assert( oelem == elem_size );
#endif
                // data has been transferred, dispose of the slots storage
                delete[] odata;
        }

        // XXX when we have a "never resize" or "never shrink" policy, make this
        // function not remove the internal storage table. Otherwise pretend that
        // "shrink to fit" was called.
        /**
         * @returns true if a resize of the underlying table storage has been done.
         */
        bool clear ( )
        {
#ifdef DEBUG
                std::cerr << "Clearing hashtable of " << size() << " elements \n";
#endif
                for( size_t i = 0; i < h_length; ++i )
                {
                        slot_item_type it = data[i];
                        while(it)
                        {
                                // do an erase() on the old data (needs to be kept in sync with
                                // erase()
                                size_type hvalue = hasher_instance(it);
                                size_type idx = hash_slot_selector()(hvalue,this->hash_mask(this->table_size()));
                                inserter::remove(it,idx,&data[0]);
                                if( this->owns_items() )
                                {
                                        delete it;
                                }
                                it = data[i];
                        }
                }
                return shrink_to_fit();
        }

        /**
         * @returns true if a table resize has been done
         */
        bool shrink_to_fit( )
        {
                // XXX unimplemented
                return false;
        }

        bool empty( ) const
        {
                return elem_size == 0;
        }

        size_type max_size( ) const
        {
                return slot_resizer::max_size();
        }
        /**
         * @param num is the number of elements to prepare the hashtable for being
         * stored. If this is bigger than what the current size of the hashtable is
         * optimal for, then a resize will be triggered.
         * @returns true if the size of the hashtable was actually changed.
         */
        bool reserve( size_t num )
        {
                size_type sz = slot_resizer::optimal_size(num);
                if( sz > table_size() )
                {
                        resize_slots( sz );
                        return true;
                }
                return false;
        }

    /**
     * Checks if the table needs to be resized according to our
     * resize policy and returns true if it was done, false
     * otherwise.
     */
        /*private*/
//      __attribute__((noinline))
        bool maybe_grow( void )
        {
                // XXX split auto resize policy into "auto grow" and "auto shrink".
                // Some people might never want the table to shrink automatically but
                // to grow. We will then also have to make the actual calculations for
                // grow/shrink depending on those values as they are now are done
                // together.

                // check if we do auto size at all
                if( this->auto_size() )
                {
#ifdef DEBUG
                        std::cerr << "auto_resize check\n";
#endif
                        if( __builtin_expect(slot_resizer::need_grow( size(), table_size() ),0) )
                        {
#ifdef DEBUG
                                std::cerr << "auto resize triggered\n";
#endif
                                resize_slots( slot_resizer::optimal_size(size()) );
                        }
                }
                return false;
        }

        bool maybe_shrink( void )
        {
                // check if we do auto size at all
                if( this->auto_size() )
                {
#ifdef DEBUG
                        std::cerr << "auto_resize check\n";
#endif
                        if( slot_resizer::need_shrink( size(), table_size() ) )
                        {
#ifdef DEBUG
                                std::cerr << "auto resize triggered\n";
#endif
                                resize_slots( slot_resizer::optimal_size(size()) );
                        }
                }
                return false;
        }
        /*
        iterator erase( iterator i )
        {
                iterator tmp(i);
                ++tmp;
                erase(&*i);
                return tmp;
        }
*/

        bool erase( item_type* it )
        {
                // XXX Make sure that for elements caching their hash values we reset
                // the hash value to "unstored"
                size_type hvalue = hasher_instance(it);
                size_type idx = hash_slot_selector()(hvalue,this->hash_mask(table_size()));
                bool ret = inserter::remove(it,idx,&data[0]);

                if( ret )
                {
                        maybe_shrink();
                }

                return ret;
        }

    /**
     *
     */
    item_type* find( ) { return const_cast<item_type*>(const_cast<const type*>(this)->find()); }

    /**
     * Find something.
     * @param k is the key to search in the hashtable for. There must exist an
     * operator() in the hash template parameter that takes such a type, and
     * also this must be comparable via operator== to the item_type.
         * XXX Think about whether it makes sense to return an iterator instead.
         * Most of the cases we don't want anything besides the item, and for
         * iterating any position is as good as the one from find, since after all
         * we cannot expect to know anything about where things went.
     */
        template<class K>
        const item_type* find( const K& k ) const
        {
                // XXX Try to figure out if we do the exact same sequence of operations
                // for find/insert too, and if yes lets have a look if we can put it
                // into one single function, so that we only have one place to maintain
                // it.
                size_type hvalue = hasher_instance(k);
#ifdef DEBUG
                std::cerr << "Trying to find a K \"" << k << "\" with hash " << hvalue << "\n";
#endif

                size_type idx = hash_slot_selector()(hvalue,this->hash_mask(table_size()));
#ifdef DEBUG
                std::cerr << "First trying at index idx = " << idx << ", data is " << (void*)data  << "\n";
#endif

                slot_item_type* slot = data + idx;
#ifdef DEBUG
                std::cerr << "Chosen slot = " << (void*)slot << "\n";
#endif
                if( *slot )
                {
                        anchor_accessor aa;
                        item_type* next = *slot;
                        while( next && !compare()(*next,k) )
                        {
                                next = aa(next)->anchor.get_next();
                        }
#ifdef DEBUG
                        std::cerr << "Returning element at " << (void*)next << "\n";
#endif
                        return next;
                }
                else
                {
#ifdef DEBUG
                        std::cerr << "Chosen slot is empty\n";
#endif
                        return 0;
                }
        }


    /**
     * Returns the amount of occupied elements.
     */
        size_type size() const { return elem_size; }

        size_type table_size() const
        {
                return h_length;
        }
};

// below come some convenience wrapper templates that behave more or less like the stdlib alternatives.
/*
   template<class T, class HT<T> = hash_table >
hash_set
{
public:
    typedef size_t size_type;
    typedef T item_type;
    typedef typename HT::accesor_type accessor_type;
private:
protected:
public:
    bool insert( item_type& );
    bool insert( item_type* );
    bool erase( item_type& );
    bool erase( item_type* );
    iterator find( item_type* );
    iterator find( item_type& );
    iterator find( key_type& );
    iterator find( size_type );
    void reserve( size_type );
    size_type capacity( void ) const;
    bool resize( size_type );

    const_iterator begin( void ) const;
    iterator begin( void );
    const_iterator end( void ) const;
    iterator end( void );

};

template<class T, class HT<...> = hash_table >
hash_map
{
};
*/
} // namespace iwear


/*
 * Future improvements
 * - make the load ratios optionally configurable at runtime.
 */
// vim: tabstop=4 shiftwidth=4 noexpandtab