static_unordered_map.h

#ifndef _STATIC_UNORDERED_MAP_H_
#define _STATIC_UNORDERED_MAP_H_

#include "small_unordered_map.h"

/**
 * XXX(stephentu): allow custom allocator
 */
template <typename Key,
          typename T,
          size_t StaticSize = SMALL_SIZE_MAP,
          typename Hash = private_::myhash<Key>>
class static_unordered_map {
public:
  typedef Key key_type;
  typedef T mapped_type;
  typedef std::pair<const key_type, mapped_type> value_type;
  typedef Hash hasher;
  typedef T & reference;
  typedef const T & const_reference;

private:
  typedef std::unordered_map<Key, T, Hash> large_table_type;
  typedef std::pair<key_type, mapped_type> bucket_value_type;

  static const bool is_trivially_destructible =
    private_::is_trivially_destructible<bucket_value_type>::value;

  static const size_t TableSize = private_::TableSize(StaticSize);
  static_assert(StaticSize >= 1, "XXX");
  static_assert(TableSize >= 1, "XXX");

  struct bucket {
    inline ALWAYS_INLINE bucket_value_type *
    ptr()
    {
      return reinterpret_cast<bucket_value_type *>(&buf[0]);
    }

    inline ALWAYS_INLINE const bucket_value_type *
    ptr() const
    {
      return reinterpret_cast<const bucket_value_type *>(&buf[0]);
    }

    inline ALWAYS_INLINE bucket_value_type &
    ref()
    {
      return *ptr();
    }

    inline ALWAYS_INLINE const bucket_value_type &
    ref() const
    {
      return *ptr();
    }

    template <class... Args>
    inline ALWAYS_INLINE void
    construct(size_t hash, Args &&... args)
    {
      h = hash;
      new (&ref()) bucket_value_type(std::forward<Args>(args)...);
    }

    inline ALWAYS_INLINE void
    destroy()
    {
      if (!is_trivially_destructible)
        ref().~bucket_value_type();
    }

    struct bucket *bnext;
    size_t h;
    char buf[sizeof(value_type)];
  };

  // iterators are not stable across mutation
  template <typename BucketType, typename ValueType>
  class iterator_ : public std::iterator<std::forward_iterator_tag, ValueType> {
    friend class static_unordered_map;
  public:
    inline iterator_() : b(0) {}

    template <typename B, typename V>
    inline iterator_(const iterator_<B, V> &other)
      : b(other.b)
    {}

    inline ValueType &
    operator*() const
    {
      return reinterpret_cast<ValueType &>(b->ref());
    }

    inline ValueType *
    operator->() const
    {
      return reinterpret_cast<ValueType *>(b->ptr());
    }

    inline bool
    operator==(const iterator_ &o) const
    {
      return b == o.b;
    }

    inline bool
    operator!=(const iterator_ &o) const
    {
      return !operator==(o);
    }

    inline iterator_ &
    operator++()
    {
      b++;
      return *this;
    }

    inline iterator_
    operator++(int)
    {
      iterator_ cur = *this;
      ++(*this);
      return cur;
    }

  protected:
    inline iterator_(BucketType *b)
      : b(b)
    {
    }

  private:
    BucketType *b;
  };

  static size_t
  chain_length(bucket *b)
  {
    size_t ret = 0;
    while (b) {
      ret++;
      b = b->bnext;
    }
    return ret;
  }

public:

  typedef iterator_<bucket, value_type> iterator;
  typedef iterator_<const bucket, const value_type> const_iterator;

  static_unordered_map()
    : n(0)
  {
    NDB_MEMSET(&table[0], 0, sizeof(table));
  }

  ~static_unordered_map()
  {
    for (size_t i = 0; i < n; i++)
      elems[i].destroy();
#ifdef ENABLE_EVENT_COUNTERS
    size_t ml = 0;
    for (size_t i = 0; i < TableSize; i++) {
      const size_t l = chain_length(table[i]);
      ml = std::max(ml, l);

    }
    if (ml)
      private_::evt_avg_max_unordered_map_chain_length.offer(ml);
#endif
  }

  static_unordered_map(const static_unordered_map &other)
    : n(0)
  {
    NDB_MEMSET(&table[0], 0, sizeof(table));
    assignFrom(other);
  }

  static_unordered_map &
  operator=(const static_unordered_map &other)
  {
    // self assignment
    if (unlikely(this == &other))
      return *this;
    assignFrom(other);
    return *this;
  }

private:
  bucket *
  find_bucket(const key_type &k, size_t *hash_value)
  {
    const size_t h = Hash()(k);
    if (hash_value)
      *hash_value = h;
    const size_t i = h % TableSize;
    bucket *b = table[i];
    while (b) {
      const bool check_hash = private_::is_eq_expensive<key_type>::value;
      if ((!check_hash || b->h == h) && b->ref().first == k)
        return b;
      b = b->bnext;
    }
    return 0;
  }

  inline ALWAYS_INLINE const bucket *
  find_bucket(const key_type &k, size_t *hash_value) const
  {
    return const_cast<static_unordered_map *>(this)->find_bucket(k, hash_value);
  }

public:

  // XXX(stephentu): template away this stuff

  mapped_type &
  operator[](const key_type &k)
  {
    size_t h;
    bucket *b = find_bucket(k, &h);
    if (b)
      return b->ref().second;
    INVARIANT(n < StaticSize);
    b = &elems[n++];
    b->construct(h, k, mapped_type());
    const size_t i = h % TableSize;
    b->bnext = table[i];
    table[i] = b;
    return b->ref().second;
  }

  mapped_type &
  operator[](key_type &&k)
  {
    size_t h;
    bucket *b = find_bucket(k, &h);
    if (b)
      return b->ref().second;
    INVARIANT(n < StaticSize);
    b = &elems[n++];
    b->construct(h, std::move(k), mapped_type());
    const size_t i = h % TableSize;
    b->bnext = table[i];
    table[i] = b;
    return b->ref().second;
  }

  inline size_t
  size() const
  {
    return n;
  }

  inline bool
  empty() const
  {
    return !n;
  }

  iterator
  begin()
  {
    return iterator(&elems[0]);
  }

  const_iterator
  begin() const
  {
    return const_iterator(&elems[0]);
  }

  inline iterator
  end()
  {
    return iterator(&elems[n]);
  }

  inline const_iterator
  end() const
  {
    return const_iterator(&elems[n]);
  }

  iterator
  find(const key_type &k)
  {
    bucket * const b = find_bucket(k, 0);
    if (b)
      return iterator(b);
    return end();
  }

  const_iterator
  find(const key_type &k) const
  {
    const bucket * const b = find_bucket(k, 0);
    if (b)
      return const_iterator(b);
    return end();
  }

  void
  clear()
  {
    if (!n)
      return;
    NDB_MEMSET(&table[0], 0, sizeof(table));
    for (size_t i = 0; i < n; i++)
      elems[i].destroy();
    n = 0;
  }

public:
  // non-standard API
  inline bool is_small_type() const { return true; }

private:

  // doesn't check for self assignment
  inline void
  assignFrom(const static_unordered_map &that)
  {
    clear();
    for (size_t i = 0; i < that.n; i++) {
      bucket * const b = &elems[n++];
      const bucket * const that_b = &that.elems[i];
      b->construct(that_b->h, that_b->ref().first, that_b->ref().second);
      const size_t idx = b->h % TableSize;
      b->bnext = table[idx];
      table[idx] = b;
    }
  }

  size_t n;
  bucket elems[StaticSize];
  bucket *table[TableSize];
};

#endif /* _STATIC_UNORDERED_MAP_H_ */