Class sparse_hashtable

libCacheSim/dataStructure/sparsepp/spp.h:2506–4323

template <class Value, class Key, class HashFcn,
          class ExtractKey, class SetKey, class EqualKey, class Alloc>
class sparse_hashtable
{
public:
    typedef Key                                        key_type;
    typedef Value                                      value_type;
    typedef HashFcn                                    hasher; // user provided or spp_hash<Key>
    typedef EqualKey                                   key_equal;
    typedef Alloc                                      allocator_type;

    typedef typename allocator_type::size_type         size_type;
    typedef typename allocator_type::difference_type   difference_type;
    typedef value_type&                                reference;
    typedef const value_type&                          const_reference;
    typedef value_type*                                pointer;
    typedef const value_type*                          const_pointer;

    // Table is the main storage class.
    typedef sparsetable<value_type, allocator_type>   Table;
    typedef typename Table::ne_iterator               ne_it;
    typedef typename Table::const_ne_iterator         cne_it;
    typedef typename Table::destructive_iterator      dest_it;
    typedef typename Table::ColIterator               ColIterator;

    typedef ne_it                                     iterator;
    typedef cne_it                                    const_iterator;
    typedef dest_it                                   destructive_iterator;

    // These come from tr1.  For us they're the same as regular iterators.
    // -------------------------------------------------------------------
    typedef iterator                                  local_iterator;
    typedef const_iterator                            const_local_iterator;

    // How full we let the table get before we resize
    // ----------------------------------------------
    static const int HT_OCCUPANCY_PCT; // = 80 (out of 100);

    // How empty we let the table get before we resize lower, by default.
    // (0.0 means never resize lower.)
    // It should be less than OCCUPANCY_PCT / 2 or we thrash resizing
    // ------------------------------------------------------------------
    static const int HT_EMPTY_PCT; // = 0.4 * HT_OCCUPANCY_PCT;

    // Minimum size we're willing to let hashtables be.
    // Must be a power of two, and at least 4.
    // Note, however, that for a given hashtable, the initial size is a
    // function of the first constructor arg, and may be >HT_MIN_BUCKETS.
    // ------------------------------------------------------------------
    static const size_type HT_MIN_BUCKETS = 4;

    // By default, if you don't specify a hashtable size at
    // construction-time, we use this size.  Must be a power of two, and
    // at least HT_MIN_BUCKETS.
    // -----------------------------------------------------------------
    static const size_type HT_DEFAULT_STARTING_BUCKETS = 32;

    // iterators
    // ---------
    iterator       begin()        { return _mk_iterator(table.ne_begin());  }