silo/small_unordered_map.h

   1 #ifndef _SMALL_UNORDERED_MAP_H_
   2 #define _SMALL_UNORDERED_MAP_H_
   3
   4 #include <algorithm>
   5 #include <iterator>
   6 #include <stdint.h>
   7 #include <unordered_map>
   8 #include <type_traits>
   9
  10 #include "macros.h"
  11 #include "counter.h"
  12 #include "log2.hh"
  13 #include "ndb_type_traits.h"
  14
  15 namespace private_ {
  16
  17   template <typename T>
  18   struct is_eq_expensive { static const bool value = true; };
  19
  20   struct cheap_eq { static const bool value = false; };
  21
  22   // equals is cheap for integer types
  23   template <> struct is_eq_expensive<bool>     : public cheap_eq {};
  24   template <> struct is_eq_expensive<uint8_t>  : public cheap_eq {};
  25   template <> struct is_eq_expensive<int8_t>   : public cheap_eq {};
  26   template <> struct is_eq_expensive<uint16_t> : public cheap_eq {};
  27   template <> struct is_eq_expensive<int16_t>  : public cheap_eq {};
  28   template <> struct is_eq_expensive<uint32_t> : public cheap_eq {};
  29   template <> struct is_eq_expensive<int32_t>  : public cheap_eq {};
  30   template <> struct is_eq_expensive<uint64_t> : public cheap_eq {};
  31   template <> struct is_eq_expensive<int64_t>  : public cheap_eq {};
  32
  33   static event_avg_counter evt_avg_max_unordered_map_chain_length CACHE_ALIGNED
  34     ("avg_max_unordered_map_chain_length");
  35
  36   template <typename T>
  37   struct fast_func_param {
  38     typedef typename std::conditional<std::is_scalar<T>::value, T, const T &>::type type;
  39   };
  40
  41   template <typename T>
  42   struct myhash {
  43     inline ALWAYS_INLINE size_t
  44     operator()(typename fast_func_param<T>::type t) const
  45     {
  46       return std::hash<T>()(t);
  47     }
  48   };
  49
  50   template <typename Tp>
  51   struct myhash<Tp *> {
  52     inline ALWAYS_INLINE size_t
  53     operator()(Tp *t) const
  54     {
  55       // std::hash for ptrs is bad
  56       // tommyhash: http://tommyds.sourceforge.net/doc/tommyhash_8h_source.html
  57       size_t key = reinterpret_cast<size_t>(t) >> 3; // shift out 8-byte pointer alignment
  58 #ifdef USE_TOMMY_HASH
  59       key = (~key) + (key << 21); // key = (key << 21) - key - 1;
  60       key = key ^ (key >> 24);
  61       key = (key + (key << 3)) + (key << 8); // key * 265
  62       key = key ^ (key >> 14);
  63       key = (key + (key << 2)) + (key << 4); // key * 21
  64       key = key ^ (key >> 28);
  65       key = key + (key << 31);
  66 #else
  67       key = (~key) + (key << 21); // key = (key << 21) - key - 1;
  68       key = key ^ (key >> 24);
  69 #endif
  70       return key;
  71     }
  72   };
  73
  74   static inline constexpr size_t
  75   TableSize(size_t small_size)
  76   {
  77     return round_up_to_pow2_const(small_size);
  78   }
  79 }
  80
  81 /**
  82  * For under SmallSize, uses linear probing on a fixed size array. Otherwise,
  83  * delegates to a regular std::unordered_map
  84  *
  85  * XXX(stephentu): allow custom allocator
  86  */
  87 template <typename Key,
  88           typename T,
  89           size_t SmallSize = SMALL_SIZE_MAP,
  90           typename Hash = private_::myhash<Key>>
  91 class small_unordered_map {
  92 public:
  93   typedef Key key_type;
  94   typedef T mapped_type;
  95   typedef std::pair<const key_type, mapped_type> value_type;
  96   typedef Hash hasher;
  97   typedef T & reference;
  98   typedef const T & const_reference;
  99
 100 private:
 101   typedef std::unordered_map<Key, T, Hash> large_table_type;
 102   typedef std::pair<key_type, mapped_type> bucket_value_type;
 103
 104   typedef typename large_table_type::iterator large_table_iterator;
 105   typedef typename large_table_type::const_iterator large_table_const_iterator;
 106
 107   static const bool is_trivially_destructible =
 108     private_::is_trivially_destructible<bucket_value_type>::value;
 109
 110   static const size_t TableSize = private_::TableSize(SmallSize);
 111   static_assert(SmallSize >= 1, "XXX");
 112   static_assert(TableSize >= 1, "XXX");
 113
 114   struct bucket {
 115     inline ALWAYS_INLINE bucket_value_type *
 116     ptr()
 117     {
 118       return reinterpret_cast<bucket_value_type *>(&buf[0]);
 119     }
 120
 121     inline ALWAYS_INLINE const bucket_value_type *
 122     ptr() const
 123     {
 124       return reinterpret_cast<const bucket_value_type *>(&buf[0]);
 125     }
 126
 127     inline ALWAYS_INLINE bucket_value_type &
 128     ref()
 129     {
 130       return *ptr();
 131     }
 132
 133     inline ALWAYS_INLINE const bucket_value_type &
 134     ref() const
 135     {
 136       return *ptr();
 137     }
 138
 139     template <class... Args>
 140     inline ALWAYS_INLINE void
 141     construct(size_t hash, Args &&... args)
 142     {
 143       h = hash;
 144       new (&ref()) bucket_value_type(std::forward<Args>(args)...);
 145     }
 146
 147     inline ALWAYS_INLINE void
 148     destroy()
 149     {
 150       if (!is_trivially_destructible)
 151         ref().~bucket_value_type();
 152     }
 153
 154     struct bucket *bnext;
 155     size_t h;
 156     char buf[sizeof(value_type)];
 157   };
 158
 159   // iterators are not stable across mutation
 160   template <typename SmallIterType,
 161             typename LargeIterType,
 162             typename ValueType>
 163   class iterator_ : public std::iterator<std::forward_iterator_tag, ValueType> {
 164     friend class small_unordered_map;
 165   public:
 166     inline iterator_() : large(false), b(0) {}
 167
 168     template <typename S, typename L, typename V>
 169     inline iterator_(const iterator_<S, L, V> &other)
 170       : large(other.large), b(other.b)
 171     {}
 172
 173     inline ValueType &
 174     operator*() const
 175     {
 176       if (unlikely(large))
 177         return *large_it;
 178       return reinterpret_cast<ValueType &>(b->ref());
 179     }
 180
 181     inline ValueType *
 182     operator->() const
 183     {
 184       if (unlikely(large))
 185         return &(*large_it);
 186       return reinterpret_cast<ValueType *>(b->ptr());
 187     }
 188
 189     inline bool
 190     operator==(const iterator_ &o) const
 191     {
 192       INVARIANT(large == o.large);
 193       if (likely(!large))
 194         return b == o.b;
 195       return large_it == o.large_it;
 196     }
 197
 198     inline bool
 199     operator!=(const iterator_ &o) const
 200     {
 201       return !operator==(o);
 202     }
 203
 204     inline iterator_ &
 205     operator++()
 206     {
 207       if (unlikely(large)) {
 208         ++large_it;
 209         return *this;
 210       }
 211       b++;
 212       return *this;
 213     }
 214
 215     inline iterator_
 216     operator++(int)
 217     {
 218       iterator_ cur = *this;
 219       ++(*this);
 220       return cur;
 221     }
 222
 223   protected:
 224     inline iterator_(SmallIterType *b)
 225       : large(false), b(b)
 226     {
 227     }
 228     inline iterator_(LargeIterType large_it)
 229       : large(true), large_it(large_it) {}
 230
 231   private:
 232     bool large;
 233     SmallIterType *b;
 234     LargeIterType large_it;
 235   };
 236
 237   static size_t
 238   chain_length(bucket *b)
 239   {
 240     size_t ret = 0;
 241     while (b) {
 242       ret++;
 243       b = b->bnext;
 244     }
 245     return ret;
 246   }
 247
 248 public:
 249
 250   typedef
 251     iterator_<
 252       bucket,
 253       large_table_iterator,
 254       value_type>
 255     iterator;
 256
 257   typedef
 258     iterator_<
 259       const bucket,
 260       large_table_const_iterator,
 261       const value_type>
 262     const_iterator;
 263
 264   small_unordered_map()
 265     : n(0), large_elems(0)
 266   {
 267     NDB_MEMSET(&table[0], 0, sizeof(table));
 268   }
 269
 270   ~small_unordered_map()
 271   {
 272     if (unlikely(large_elems)) {
 273       delete large_elems;
 274       return;
 275     }
 276     for (size_t i = 0; i < n; i++)
 277       small_elems[i].destroy();
 278   }
 279
 280   small_unordered_map(const small_unordered_map &other)
 281     : n(0), large_elems(0)
 282   {
 283     NDB_MEMSET(&table[0], 0, sizeof(table));
 284     assignFrom(other);
 285   }
 286
 287   small_unordered_map &
 288   operator=(const small_unordered_map &other)
 289   {
 290     // self assignment
 291     if (unlikely(this == &other))
 292       return *this;
 293     assignFrom(other);
 294     return *this;
 295   }
 296
 297 private:
 298   bucket *
 299   find_bucket(const key_type &k, size_t *hash_value)
 300   {
 301     INVARIANT(!large_elems);
 302     const size_t h = Hash()(k);
 303     if (hash_value)
 304       *hash_value = h;
 305     const size_t i = h % TableSize;
 306     bucket *b = table[i];
 307     while (b) {
 308       const bool check_hash = private_::is_eq_expensive<key_type>::value;
 309       if ((!check_hash || b->h == h) && b->ref().first == k)
 310         return b;
 311       b = b->bnext;
 312     }
 313     return 0;
 314   }
 315
 316   inline ALWAYS_INLINE const bucket *
 317   find_bucket(const key_type &k, size_t *hash_value) const
 318   {
 319     return const_cast<small_unordered_map *>(this)->find_bucket(k, hash_value);
 320   }
 321
 322 public:
 323
 324   // XXX(stephentu): template away this stuff
 325
 326   mapped_type &
 327   operator[](const key_type &k)
 328   {
 329     if (unlikely(large_elems))
 330       return large_elems->operator[](k);
 331     size_t h;
 332     bucket *b = find_bucket(k, &h);
 333     if (b)
 334       return b->ref().second;
 335     if (unlikely(n == SmallSize)) {
 336       large_elems = new large_table_type;
 337       for (size_t n = 0; n < SmallSize; n++) {
 338         bucket &b = small_elems[n];
 339 #if GCC_AT_LEAST_47
 340         large_elems->emplace(std::move(b.ref()));
 341 #else
 342         large_elems->operator[](std::move(b.ref().first)) = std::move(b.ref().second);
 343 #endif
 344         b.destroy();
 345       }
 346       n = 0;
 347       return large_elems->operator[](k);
 348     }
 349     INVARIANT(n < SmallSize);
 350     b = &small_elems[n++];
 351     b->construct(h, k, mapped_type());
 352     const size_t i = h % TableSize;
 353     b->bnext = table[i];
 354     table[i] = b;
 355     return b->ref().second;
 356   }
 357
 358   mapped_type &
 359   operator[](key_type &&k)
 360   {
 361     if (unlikely(large_elems))
 362       return large_elems->operator[](std::move(k));
 363     size_t h;
 364     bucket *b = find_bucket(k, &h);
 365     if (b)
 366       return b->ref().second;
 367     if (unlikely(n == SmallSize)) {
 368       large_elems = new large_table_type;
 369       for (size_t n = 0; n < SmallSize; n++) {
 370         bucket &b = small_elems[n];
 371 #if GCC_AT_LEAST_47
 372         large_elems->emplace(std::move(b.ref()));
 373 #else
 374         large_elems->operator[](std::move(b.ref().first)) = std::move(b.ref().second);
 375 #endif
 376         b.destroy();
 377       }
 378       n = 0;
 379       return large_elems->operator[](std::move(k));
 380     }
 381     INVARIANT(n < SmallSize);
 382     b = &small_elems[n++];
 383     b->construct(h, std::move(k), mapped_type());
 384     const size_t i = h % TableSize;
 385     b->bnext = table[i];
 386     table[i] = b;
 387     return b->ref().second;
 388   }
 389
 390   inline size_t
 391   size() const
 392   {
 393     if (unlikely(large_elems))
 394       return large_elems->size();
 395     return n;
 396   }
 397
 398   inline bool
 399   empty() const
 400   {
 401     return size() == 0;
 402   }
 403
 404   iterator
 405   begin()
 406   {
 407     if (unlikely(large_elems))
 408       return iterator(large_elems->begin());
 409     return iterator(&small_elems[0]);
 410   }
 411
 412   const_iterator
 413   begin() const
 414   {
 415     if (unlikely(large_elems))
 416       return const_iterator(large_elems->begin());
 417     return const_iterator(&small_elems[0]);
 418   }
 419
 420   inline iterator
 421   end()
 422   {
 423     if (unlikely(large_elems))
 424       return iterator(large_elems->end());
 425     return iterator(&small_elems[n]);
 426   }
 427
 428   inline const_iterator
 429   end() const
 430   {
 431     if (unlikely(large_elems))
 432       return const_iterator(large_elems->end());
 433     return const_iterator(&small_elems[n]);
 434   }
 435
 436   iterator
 437   find(const key_type &k)
 438   {
 439     if (unlikely(large_elems))
 440       return iterator(large_elems->find(k));
 441     bucket * const b = find_bucket(k, 0);
 442     if (b)
 443       return iterator(b);
 444     return end();
 445   }
 446
 447   const_iterator
 448   find(const key_type &k) const
 449   {
 450     if (unlikely(large_elems))
 451       return const_iterator(large_elems->find(k));
 452     const bucket * const b = find_bucket(k, 0);
 453     if (b)
 454       return const_iterator(b);
 455     return end();
 456   }
 457
 458   void
 459   clear()
 460   {
 461     if (unlikely(large_elems)) {
 462       INVARIANT(!n);
 463       delete large_elems;
 464       large_elems = NULL;
 465       return;
 466     }
 467     if (!n)
 468       return;
 469     NDB_MEMSET(&table[0], 0, sizeof(table));
 470     for (size_t i = 0; i < n; i++)
 471       small_elems[i].destroy();
 472     n = 0;
 473   }
 474
 475 public:
 476   // non-standard API
 477   inline bool is_small_type() const { return !large_elems; }
 478
 479 private:
 480
 481   // doesn't check for self assignment
 482   inline void
 483   assignFrom(const small_unordered_map &that)
 484   {
 485     clear();
 486     if (that.large_elems) {
 487       INVARIANT(!that.n);
 488       INVARIANT(!n);
 489       large_elems = new large_table_type(*that.large_elems);
 490       return;
 491     }
 492     INVARIANT(!large_elems);
 493     for (size_t i = 0; i < that.n; i++) {
 494       bucket * const b = &small_elems[n++];
 495       const bucket * const that_b = &that.small_elems[i];
 496       b->construct(that_b->h, that_b->ref().first, that_b->ref().second);
 497       const size_t idx = b->h % TableSize;
 498       b->bnext = table[idx];
 499       table[idx] = b;
 500     }
 501   }
 502
 503   size_t n;
 504
 505   bucket small_elems[SmallSize];
 506   bucket *table[TableSize];
 507
 508   large_table_type *large_elems;
 509 };
 510
 511 #endif /* _SMALL_UNORDERED_MAP_H_ */