hphp/runtime/base/req-hash-map.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #ifndef incl_HPHP_RUNTIME_BASE_REQ_HASH_MAP_H_
  18 #define incl_HPHP_RUNTIME_BASE_REQ_HASH_MAP_H_
  19
  20 #include "hphp/runtime/base/req-malloc.h"
  21 #include <folly/container/F14Map.h>
  22
  23 namespace HPHP { namespace req {
  24
  25 /*
  26  * hash_map wraps F14NodeMap, which allocates key+value indirectly,
  27  * without moving them during rehash. Use when you need similar reference
  28  * stability to std::unordered_map.
  29  */
  30 template <class T,
  31           class U,
  32           class V = std::hash<T>,
  33           class W = std::equal_to<T>>
  34 struct hash_map : folly::F14NodeMap<
  35   T, U, V, W,
  36   Allocator<std::pair<const T,U>>
  37 > {
  38   using Base = folly::F14NodeMap<
  39     T, U, V, W, Allocator<std::pair<const T, U>>
  40   >;
  41   hash_map() : Base() {}
  42
  43   TYPE_SCAN_IGNORE_BASES(Base);
  44   TYPE_SCAN_CUSTOM(T, U) {
  45     for (const auto& pair : *this) scanner.scan(pair);
  46   }
  47 };
  48
  49 /*
  50  * value_map Wraps F14ValueMap. Only safe when you don't care when values move
  51  * on rehash or erase, and don't care about having contiguous values, like
  52  * F14VectorMap (below). This map favors hash lookups over iteration, and
  53  * small cheap-to-move elements. Over-reserving in this table can potentially
  54  * waste memory proportional to the value size, since values are stored in
  55  * hashtable chunks with no indirection.
  56  */
  57 template <class T,
  58           class U,
  59           class V = std::hash<T>,
  60           class W = std::equal_to<T>>
  61 struct value_map : folly::F14ValueMap<
  62   T, U, V, W,
  63   ConservativeAllocator<std::pair<const T,U>>
  64 > {
  65   using Base = folly::F14ValueMap<
  66     T, U, V, W, ConservativeAllocator<std::pair<const T, U>>
  67   >;
  68   using value_type = typename Base::value_type;
  69   value_map() : Base() {}
  70
  71   TYPE_SCAN_IGNORE_BASES(Base);
  72   TYPE_SCAN_CUSTOM(T, U) {
  73     Base::visitContiguousRanges(
  74       [&](value_type const* start, value_type const* end) {
  75         scanner.scan(*start, (const char*)end - (const char*)start);
  76       });
  77   }
  78 };
  79
  80 /*
  81  * vector_map Wraps F14VectorMap, which store key+value contiguously,
  82  * and maintains insertion order, providing erase() is not called.
  83  * iterator walks in LIFO order, reverse_iterator walks in FIFO order.
  84  * The LIFO order of iterator is efficient when using this pattern:
  85  *   while (!m.empty()) {
  86  *     auto it = map.begin();
  87  *     ...
  88  *     map.erase(it);
  89  *   }
  90  *
  91  * This map favors iteration and value locality at the cost of some
  92  * indirection on hash lookups.
  93  */
  94 template <class T,
  95           class U,
  96           class V = std::hash<T>,
  97           class W = std::equal_to<T>>
  98 struct vector_map : folly::F14VectorMap<
  99   T, U, V, W,
 100   ConservativeAllocator<std::pair<const T,U>>
 101 > {
 102   using Base = folly::F14VectorMap<
 103     T, U, V, W, ConservativeAllocator<std::pair<const T, U>>
 104   >;
 105   using value_type = typename Base::value_type;
 106   vector_map() : Base() {}
 107
 108   TYPE_SCAN_IGNORE_BASES(Base);
 109   TYPE_SCAN_CUSTOM(T, U) {
 110     Base::visitContiguousRanges(
 111       [&](value_type const* start, value_type const* end) {
 112         scanner.scan(*start, (const char*)end - (const char*)start);
 113       });
 114   }
 115 };
 116
 117 /*
 118  * fast_map chooses either value_map or vector_map, depending on value size,
 119  * using the same policy as F14FastMap
 120  *
 121  * Not using F14FastMap directly allows us to further customize req::value_map
 122  * and req::vector_map above without re-implementing the same customizations
 123  * in our own wrapper for F14FastMap.
 124  */
 125 template <class Key, class Mapped,
 126           class Hasher = std::hash<Key>,
 127           class KeyEqual = std::equal_to<Key>>
 128 struct fast_map : std::conditional_t<
 129                        sizeof(std::pair<Key const, Mapped>) < 24,
 130                        value_map<Key, Mapped, Hasher, KeyEqual>,
 131                        vector_map<Key, Mapped, Hasher, KeyEqual>> {
 132   using Super = std::conditional_t<
 133       sizeof(std::pair<Key const, Mapped>) < 24,
 134       value_map<Key, Mapped, Hasher, KeyEqual>,
 135       vector_map<Key, Mapped, Hasher, KeyEqual>>;
 136
 137   using Super::Super;
 138   fast_map() : Super() {}
 139 };
 140
 141 }}
 142 #endif