silo/static_unordered_map.h

   1 #ifndef _STATIC_UNORDERED_MAP_H_
   2 #define _STATIC_UNORDERED_MAP_H_
   3
   4 #include "small_unordered_map.h"
   5
   6 /**
   7  * XXX(stephentu): allow custom allocator
   8  */
   9 template <typename Key,
  10           typename T,
  11           size_t StaticSize = SMALL_SIZE_MAP,
  12           typename Hash = private_::myhash<Key>>
  13 class static_unordered_map {
  14 public:
  15   typedef Key key_type;
  16   typedef T mapped_type;
  17   typedef std::pair<const key_type, mapped_type> value_type;
  18   typedef Hash hasher;
  19   typedef T & reference;
  20   typedef const T & const_reference;
  21
  22 private:
  23   typedef std::unordered_map<Key, T, Hash> large_table_type;
  24   typedef std::pair<key_type, mapped_type> bucket_value_type;
  25
  26   static const bool is_trivially_destructible =
  27     private_::is_trivially_destructible<bucket_value_type>::value;
  28
  29   static const size_t TableSize = private_::TableSize(StaticSize);
  30   static_assert(StaticSize >= 1, "XXX");
  31   static_assert(TableSize >= 1, "XXX");
  32
  33   struct bucket {
  34     inline ALWAYS_INLINE bucket_value_type *
  35     ptr()
  36     {
  37       return reinterpret_cast<bucket_value_type *>(&buf[0]);
  38     }
  39
  40     inline ALWAYS_INLINE const bucket_value_type *
  41     ptr() const
  42     {
  43       return reinterpret_cast<const bucket_value_type *>(&buf[0]);
  44     }
  45
  46     inline ALWAYS_INLINE bucket_value_type &
  47     ref()
  48     {
  49       return *ptr();
  50     }
  51
  52     inline ALWAYS_INLINE const bucket_value_type &
  53     ref() const
  54     {
  55       return *ptr();
  56     }
  57
  58     template <class... Args>
  59     inline ALWAYS_INLINE void
  60     construct(size_t hash, Args &&... args)
  61     {
  62       h = hash;
  63       new (&ref()) bucket_value_type(std::forward<Args>(args)...);
  64     }
  65
  66     inline ALWAYS_INLINE void
  67     destroy()
  68     {
  69       if (!is_trivially_destructible)
  70         ref().~bucket_value_type();
  71     }
  72
  73     struct bucket *bnext;
  74     size_t h;
  75     char buf[sizeof(value_type)];
  76   };
  77
  78   // iterators are not stable across mutation
  79   template <typename BucketType, typename ValueType>
  80   class iterator_ : public std::iterator<std::forward_iterator_tag, ValueType> {
  81     friend class static_unordered_map;
  82   public:
  83     inline iterator_() : b(0) {}
  84
  85     template <typename B, typename V>
  86     inline iterator_(const iterator_<B, V> &other)
  87       : b(other.b)
  88     {}
  89
  90     inline ValueType &
  91     operator*() const
  92     {
  93       return reinterpret_cast<ValueType &>(b->ref());
  94     }
  95
  96     inline ValueType *
  97     operator->() const
  98     {
  99       return reinterpret_cast<ValueType *>(b->ptr());
 100     }
 101
 102     inline bool
 103     operator==(const iterator_ &o) const
 104     {
 105       return b == o.b;
 106     }
 107
 108     inline bool
 109     operator!=(const iterator_ &o) const
 110     {
 111       return !operator==(o);
 112     }
 113
 114     inline iterator_ &
 115     operator++()
 116     {
 117       b++;
 118       return *this;
 119     }
 120
 121     inline iterator_
 122     operator++(int)
 123     {
 124       iterator_ cur = *this;
 125       ++(*this);
 126       return cur;
 127     }
 128
 129   protected:
 130     inline iterator_(BucketType *b)
 131       : b(b)
 132     {
 133     }
 134
 135   private:
 136     BucketType *b;
 137   };
 138
 139   static size_t
 140   chain_length(bucket *b)
 141   {
 142     size_t ret = 0;
 143     while (b) {
 144       ret++;
 145       b = b->bnext;
 146     }
 147     return ret;
 148   }
 149
 150 public:
 151
 152   typedef iterator_<bucket, value_type> iterator;
 153   typedef iterator_<const bucket, const value_type> const_iterator;
 154
 155   static_unordered_map()
 156     : n(0)
 157   {
 158     NDB_MEMSET(&table[0], 0, sizeof(table));
 159   }
 160
 161   ~static_unordered_map()
 162   {
 163     for (size_t i = 0; i < n; i++)
 164       elems[i].destroy();
 165 #ifdef ENABLE_EVENT_COUNTERS
 166     size_t ml = 0;
 167     for (size_t i = 0; i < TableSize; i++) {
 168       const size_t l = chain_length(table[i]);
 169       ml = std::max(ml, l);
 170
 171     }
 172     if (ml)
 173       private_::evt_avg_max_unordered_map_chain_length.offer(ml);
 174 #endif
 175   }
 176
 177   static_unordered_map(const static_unordered_map &other)
 178     : n(0)
 179   {
 180     NDB_MEMSET(&table[0], 0, sizeof(table));
 181     assignFrom(other);
 182   }
 183
 184   static_unordered_map &
 185   operator=(const static_unordered_map &other)
 186   {
 187     // self assignment
 188     if (unlikely(this == &other))
 189       return *this;
 190     assignFrom(other);
 191     return *this;
 192   }
 193
 194 private:
 195   bucket *
 196   find_bucket(const key_type &k, size_t *hash_value)
 197   {
 198     const size_t h = Hash()(k);
 199     if (hash_value)
 200       *hash_value = h;
 201     const size_t i = h % TableSize;
 202     bucket *b = table[i];
 203     while (b) {
 204       const bool check_hash = private_::is_eq_expensive<key_type>::value;
 205       if ((!check_hash || b->h == h) && b->ref().first == k)
 206         return b;
 207       b = b->bnext;
 208     }
 209     return 0;
 210   }
 211
 212   inline ALWAYS_INLINE const bucket *
 213   find_bucket(const key_type &k, size_t *hash_value) const
 214   {
 215     return const_cast<static_unordered_map *>(this)->find_bucket(k, hash_value);
 216   }
 217
 218 public:
 219
 220   // XXX(stephentu): template away this stuff
 221
 222   mapped_type &
 223   operator[](const key_type &k)
 224   {
 225     size_t h;
 226     bucket *b = find_bucket(k, &h);
 227     if (b)
 228       return b->ref().second;
 229     INVARIANT(n < StaticSize);
 230     b = &elems[n++];
 231     b->construct(h, k, mapped_type());
 232     const size_t i = h % TableSize;
 233     b->bnext = table[i];
 234     table[i] = b;
 235     return b->ref().second;
 236   }
 237
 238   mapped_type &
 239   operator[](key_type &&k)
 240   {
 241     size_t h;
 242     bucket *b = find_bucket(k, &h);
 243     if (b)
 244       return b->ref().second;
 245     INVARIANT(n < StaticSize);
 246     b = &elems[n++];
 247     b->construct(h, std::move(k), mapped_type());
 248     const size_t i = h % TableSize;
 249     b->bnext = table[i];
 250     table[i] = b;
 251     return b->ref().second;
 252   }
 253
 254   inline size_t
 255   size() const
 256   {
 257     return n;
 258   }
 259
 260   inline bool
 261   empty() const
 262   {
 263     return !n;
 264   }
 265
 266   iterator
 267   begin()
 268   {
 269     return iterator(&elems[0]);
 270   }
 271
 272   const_iterator
 273   begin() const
 274   {
 275     return const_iterator(&elems[0]);
 276   }
 277
 278   inline iterator
 279   end()
 280   {
 281     return iterator(&elems[n]);
 282   }
 283
 284   inline const_iterator
 285   end() const
 286   {
 287     return const_iterator(&elems[n]);
 288   }
 289
 290   iterator
 291   find(const key_type &k)
 292   {
 293     bucket * const b = find_bucket(k, 0);
 294     if (b)
 295       return iterator(b);
 296     return end();
 297   }
 298
 299   const_iterator
 300   find(const key_type &k) const
 301   {
 302     const bucket * const b = find_bucket(k, 0);
 303     if (b)
 304       return const_iterator(b);
 305     return end();
 306   }
 307
 308   void
 309   clear()
 310   {
 311     if (!n)
 312       return;
 313     NDB_MEMSET(&table[0], 0, sizeof(table));
 314     for (size_t i = 0; i < n; i++)
 315       elems[i].destroy();
 316     n = 0;
 317   }
 318
 319 public:
 320   // non-standard API
 321   inline bool is_small_type() const { return true; }
 322
 323 private:
 324
 325   // doesn't check for self assignment
 326   inline void
 327   assignFrom(const static_unordered_map &that)
 328   {
 329     clear();
 330     for (size_t i = 0; i < that.n; i++) {
 331       bucket * const b = &elems[n++];
 332       const bucket * const that_b = &that.elems[i];
 333       b->construct(that_b->h, that_b->ref().first, that_b->ref().second);
 334       const size_t idx = b->h % TableSize;
 335       b->bnext = table[idx];
 336       table[idx] = b;
 337     }
 338   }
 339
 340   size_t n;
 341   bucket elems[StaticSize];
 342   bucket *table[TableSize];
 343 };
 344
 345 #endif /* _STATIC_UNORDERED_MAP_H_ */