FastHash.h

Go to the documentation of this file.

#ifndef FastHash_HEADER
#define FastHash_HEADER

/***************************************************************************
 * Benoit Hudson (C) 2007.
 ***************************************************************************/

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif

#include <assert.h>
#include <boost/utility.hpp>
#include <string.h> // memset
#include <utility> // for pair
#include "SmallMemoryPool.h"

#include "bit-hacks.h"
#include "hash.h" // namespace hashers
using namespace std;

namespace hudson {

struct FHS_Stats {
  size_t N;
  size_t sumnitems;
  size_t sumcapacity;
  size_t sumnonempty;
  vector<size_t> histogram;
  FHS_Stats() {
    memset(this, 0, sizeof(*this));
  }
  void print();
};
extern FHS_Stats global_stats;

template <typename Key, typename Value> struct KeyValue {
  Key key_;
  Value value_;
  KeyValue(const Key& k): key_(k) { }

  template <typename KeyRef, typename ValueRef> struct Pair {
    KeyRef first;
    ValueRef second;
    Pair(KeyRef f, ValueRef s): first(f), second(s) { }
  };
  typedef Pair<Key&, Value&> ref;
  typedef Pair<const Key&, const Value&> const_ref;
  operator ref () { return ref(key_, value_); }
  operator const_ref() const { return const_ref(key_, value_); }
  operator const Key& () const { return key_; }

  bool operator== (const Key& k) const { return key_ == k; }
  bool operator!= (const Key& k) const { return !(key_ == k); }
};

template <typename Key> struct KeyValue<Key,void> {
  Key key_;
  KeyValue(const Key& k): key_(k) { }

  typedef Key& ref;
  typedef const Key& const_ref;
  operator ref () { return key_; }
  operator const_ref () const { return key_; } // same as const Key&

  bool operator== (const Key& k) const { return key_ == k; }
  bool operator!= (const Key& k) const { return !(key_ == k); }
};

template <typename Key, typename Value, class hasher, bool NeedsDelete, bool collectStats> class FastHashBase
: public boost::noncopyable {
  /***************************************************************************
   ***************************************************************************/
  typedef hudson::KeyValue<Key,Value> KeyValue;

  struct link : public SmallMemoryItem<link> {
    KeyValue key_;
    link *next_;
    link(const Key& key): key_(key), next_(NULL) { }
  };

  public:
  struct iterator {
    typedef typename KeyValue::ref value_type;

    iterator(link *l): l_(l) { }
    iterator(const iterator& it): l_(it.l_) { }
    bool operator== (const iterator& other) const { return l_ == other.l_; }
    bool operator!= (const iterator& other) const { return l_ != other.l_; }
    value_type operator*() const { return value_type(this->l_->key_); }

    private:
    link *l_;
  };
  struct const_iterator {
    typedef typename KeyValue::const_ref value_type;

    const_iterator(const link *l): l_(l) { }
    const_iterator(const const_iterator& it): l_(it.l_) { }
    bool operator== (const const_iterator& other) const { return l_ == other.l_; }
    bool operator!= (const const_iterator& other) const { return l_ != other.l_; }
    value_type operator*() const { return value_type(this->l_->key_); }

    private:
    const link *l_;
  };

  /***************************************************************************
    * \name Allocating the table.
   ***************************************************************************/
  private:
  void allocateTable() {
    if (capacity() == 0) {
      table_ = 0;
      return;
    }
    size_t nbytes = sizeof(*table_) * capacity();
    table_ = (link**)SmallMemoryPool::allocate_n(nbytes);
    memset(table_, 0, nbytes);
  }

  void freeTable(link **tab, size_t capacity) {
    if (tab != 0) {
      size_t nbytes = sizeof(*table_) * capacity;
      SmallMemoryPool::deallocate_n(tab, nbytes);
    }
  }

  public:
  FastHashBase(size_t size_hint) {
    if (size_hint == 0) {
      capacity_ = 0;
    } else {
      capacity_ = bithacks::ceil_pow2(size_hint);
    }
    n_ = 0;
    allocateTable();
  }

  FastHashBase() {
    capacity_ = 0;
    n_ = 0;
    allocateTable();
  }

  void reserve(size_t capacity) {
    capacity = bithacks::ceil_pow2(capacity);
    if (capacity > capacity_) {
      resize(capacity);
    }
  }

  public:
  ~FastHashBase() {
    if(collectStats) { collectstats(global_stats); }
    clear(true);
  }

  void clear(bool free_table = false) {
    for (size_t i = 0; i < capacity(); ++i) {
      link *l = table_[i];
      while(l) {
        link *next = l->next_;
        delete l;
        l = next;
      }
      table_[i] = NULL;
    }
    if (free_table) {
      freeTable(table_, capacity());
      capacity_ = 0;
      table_ = NULL;
    }
    n_ = 0;
  }

  /***************************************************************************
   * Compute some statistics to see if the hash function is good.
   * Helps allay fears at the very least.
   *
   * See FHS_Stats.
   ***************************************************************************/
  public:
  void collectstats(FHS_Stats& s) {
    size_t nbuckets = bithacks::log2(n_) + 1;
    if (s.histogram.size() < nbuckets) {
      s.histogram.resize(nbuckets);
    }

    s.N++;
    s.sumnitems += n_;
    s.sumcapacity += capacity();
    for(size_t i = 0; i < capacity(); ++i) {
      size_t n = 0;
      link *l = table_[i];
      while(l) { l = l->next_; n++; }
      if (n > 0) {
        s.sumnonempty++;
        s.histogram[bithacks::log2(n)]++;
      }
    }
  }

  /***************************************************************************
   ***************************************************************************/
  private:
  size_t mask() const {
    assert(capacity_ != 0);
    return capacity_ - 1;
  }

  size_t index(const Key& key) const {
    hasher h;
    return h(key) & mask();
  }
  /***************************************************************************
   ***************************************************************************/
  private:
  static link *findLink(const Key& key, link *l) {
    while (l && l->key_ != key) {
      l = l->next_;
    }
    return l;
  }
  static const link *findLink(const Key& key, const link *l) {
    while (l && l->key_ != key) {
      l = l->next_;
    }
    return l;
  }

  /***************************************************************************
    * \name find
    * Returns an iterator that points to the element that holds the key.
    * Returns end() if there is no such element.
   ***************************************************************************/
  public:
  const_iterator find(const Key& key) const {
    if (size() == 0) { return end(); }
    size_t i = index(key);
    const link *l = findLink(key, table_[i]);
    return const_iterator(l);
  }
  iterator find(const Key& key)  {
    if (size() == 0) { return end(); }
    size_t i = index(key);
    link *l = findLink(key, table_[i]);
    return iterator(l);
  }

  /***************************************************************************
   * Find-or-insert semantics: either insert the key, or return an iterator
   * to the previous copy.
   ***************************************************************************/
  public:
  pair<iterator,bool> insert(const Key& key) {
    if (capacity() == 0) {
      resize();
    }

    hasher h;
    size_t hashval = h(key);
    size_t i = hashval & mask();
    link *l = findLink(key, table_[i]);
    if (l) {
      // found it; not inserting this version of the key
      return make_pair(iterator(l), false);
    } else {
      // Not found; inserting this key.  Check if it fits.
      if (n_ == capacity()) {
        resize();
        i = hashval & mask(); // mask changed
      }
      link *l = new link(key);
      l->next_ = table_[i];
      table_[i] = l;
      n_++;
      return make_pair(iterator(l), true);
    }
  }

  private:
  void resize(size_t newcap) {
    link **oldtable = table_;
    size_t oldcap = capacity();

    capacity_ = newcap;

    allocateTable();

    // foreach bucket, foreach link, put the link where it belongs.
    for(size_t oldi = 0; oldi < oldcap; ++oldi) {
      link *l = oldtable[oldi];
      while(l) {
        link *next = l->next_;
        size_t i = index(l->key_);
        l->next_ = table_[i];
        table_[i] = l;
        l = next;
      }
    }
    freeTable(oldtable, oldcap);
  }

  void resize() {
    size_t oldcap = capacity();

    if (oldcap == 0) {
      resize(2);
    } else {
      resize(oldcap * 2);
    }
  }

  public:
  template <class key_iterator> void insert(key_iterator begin, const key_iterator& end) {
    while(begin != end) {
      insert(*begin);
      ++begin;
    }
  }

  /***************************************************************************
   * Remove the key.
   *
   * Return whether we removed anything.
   *
   * TODO: resize if we shrink too much?  At the moment, I do not, because
   * in all the applications where I erase, I only erase while growing the
   * overall structure.
   ***************************************************************************/
  public:
  bool erase(const Key& key) {
    if (size() == 0) {
      // this is to handle the zero-capacity case, but might as well optimize
      // for the zero-size case too.
      return false;
    }
    size_t i = index(key);
    link *l = table_[i];
    if (!l) { return false; }
    if (l->key_ == key) {
      table_[i] = l->next_;
      goto remove;
    }

    while(1) {
      link *prev = l;
      l = l->next_;
      if (!l) { return false; }
      if (l->key_ == key) {
        prev->next_ = l->next_;
        goto remove;
      }
    }
remove:
    n_--;
    delete l;
    // TODO: if n falls too low compared to the capacity, resize.
    return true;
  }


  /***************************************************************************
   ***************************************************************************/
  public:
  size_t size() const { return n_; }
  size_t capacity() const { return capacity_; }

  /******************************
   * \name end
   *
   * An iterator corresponding to a failed search.  Note that there is
   * no begin, since the iterator is not a ForwardIterator. */
  iterator end() { return iterator(NULL); }
  const_iterator end() const { return const_iterator(NULL); }


  /***************************************************************************
   ***************************************************************************/
  private:
  size_t capacity_; 
  size_t n_;    
  link **table_;
};



/***************************************************************************
 ***************************************************************************
 ***************************************************************************/

template <typename Key, class hasher = hashers::hash<Key>, bool NeedsDelete = true, bool collectStats = false>
class FastHashSet : public FastHashBase<Key, void, hasher, NeedsDelete, collectStats> {
  private:
    typedef FastHashBase<Key, void, hasher, NeedsDelete, collectStats> super;
  public:
    FastHashSet() : super() { }
    FastHashSet(size_t size_hint) : super(size_hint) { }

    bool has(const Key& k) const { return this->find(k) != this->end(); }
};

/***************************************************************************
 ***************************************************************************/

template <typename Key, typename Value, class hasher = hashers::hash<Key>, bool NeedsDelete = true, bool collectStats = false>
class FastHashMap : public FastHashBase<Key, Value, hasher, NeedsDelete, collectStats> {
  private:
    typedef FastHashBase<Key, Value, hasher, NeedsDelete, collectStats> super;
  public:
    FastHashMap() : super() { }
    FastHashMap(size_t size_hint) : super(size_hint) { }

    Value& operator[] (const Key& k) {
      // Insert k; take the iterator; deref; get the value.
      // All-in-one to avoid temporaries.
      return (*(super::insert(k).first)).second;
    }

    Value& findOrDie (const Key& k) {
      typename super::iterator it = this->find(k);
      assert(it != this->end());
      return (*it).second;
    }

    const Value& findOrDie (const Key& k) const {
      typename super::const_iterator it = this->find(k);
      assert(it != this->end());
      return (*it).second;
    }

    pair<typename super::iterator,bool> insert(const Key& key, const Value& val) {
      pair<typename super::iterator, bool> p = super::insert(key);
      if (p.second) {
        (*(p.first)).second = val;
      }
      return p;
    }

    pair<typename super::iterator,bool> insert(const Key& key) {
      return super::insert(key);
    }
};

} // namespace hudson

#endif

---