hphp/runtime/vm/indexed-string-map.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2014 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_VM_INDEXED_STRING_MAP_H_
  18 #define incl_HPHP_VM_INDEXED_STRING_MAP_H_
  19
  20 #include <boost/mpl/if.hpp>
  21 #include <boost/utility/enable_if.hpp>
  22
  23 #include "hphp/runtime/base/string-data.h"
  24 #include "hphp/runtime/vm/fixed-string-map.h"
  25
  26 namespace HPHP {
  27
  28 //////////////////////////////////////////////////////////////////////
  29
  30 /*
  31  * Several VM data structures can be accessed with both a string-based
  32  * lookup and by an index.  This map supports both types of lookup.
  33  * (The index type is a template parameter in order to allow different
  34  * uses of this map to have different sized indexes).
  35  *
  36  * The number of elements must be fixed after initialization time
  37  * (since we use a FixedStringMap internally).
  38  */
  39 template<class T,
  40          bool CaseSensitive,
  41          class Index,
  42          Index InvalidIndex = Index(-1)>
  43 struct IndexedStringMap {
  44   struct Builder;
  45
  46   explicit IndexedStringMap() {
  47     setSize(0);
  48   }
  49
  50   ~IndexedStringMap() {
  51     clear();
  52   }
  53
  54   IndexedStringMap(const IndexedStringMap&) = delete;
  55   IndexedStringMap& operator=(const IndexedStringMap&) = delete;
  56
  57   void clear() {
  58     m_map.clear();
  59     setSize(0);
  60   }
  61
  62   /*
  63    * Create an IndexedStringMap from the supplied builder.  See
  64    * builder below.
  65    */
  66   void create(const Builder& b) {
  67     assert(!size() && "IndexedStringMap::create called more than once");
  68     setSize(b.size());
  69     m_map.init(b.size(), size() * sizeof(T));
  70     if (!b.size()) {
  71       // note that we have to initialize m_map even though its zero
  72       // sized (an empty FixedStringMap isn't quite empty - see
  73       // FixedStringMap::init).
  74       return;
  75     }
  76
  77     std::copy(b.m_list.begin(), b.m_list.end(), mutableAccessList());
  78     for (typename Builder::const_iterator it = b.begin();
  79         it != b.end();
  80         ++it) {
  81       m_map.add(it->first, it->second);
  82     }
  83   }
  84
  85   const T* accessList() const {
  86     return static_cast<const T*>(m_map.extraData());
  87   }
  88   T* mutableAccessList() { return const_cast<T*>(accessList()); }
  89
  90   bool contains(const StringData* k) const { return m_map.find(k); }
  91   Index size() const { return m_map.extra(); }
  92   bool empty() const { return size() != 0; }
  93
  94   // Find the index for an entry by name.  Returns InvalidIndex if
  95   // there is no entry with this name.
  96   Index findIndex(const StringData* k) const {
  97     Index* i = m_map.find(k);
  98     if (!i) return InvalidIndex;
  99     return *i;
 100   }
 101
 102   // Lookup entries in the map by string.  Returns the entry or the
 103   // supplied default value if it doesn't exist.
 104   T lookupDefault(const StringData* k, T def) const {
 105     Index* i = m_map.find(k);
 106     if (!i) return def;
 107     return accessList()[*i];
 108   }
 109
 110   // Lookup entries by index.  Index must be in range or you get
 111   // undefined behavior.
 112   T& operator[](Index index) {
 113     assert(index < size());
 114     return mutableAccessList()[index];
 115   }
 116   const T& operator[](Index index) const {
 117     return (*const_cast<IndexedStringMap*>(this))[index];
 118   }
 119
 120   static ptrdiff_t vecOff() {
 121     return offsetof(IndexedStringMap, m_map) +
 122       FixedStringMap<Index,CaseSensitive,Index>::tableOff();
 123   }
 124 private:
 125   uint32_t byteSize() const { return size() * sizeof(T); }
 126   void setSize(Index size) { m_map.extra() = size; }
 127
 128   FixedStringMap<Index,CaseSensitive,Index> m_map;
 129 };
 130
 131 //////////////////////////////////////////////////////////////////////
 132
 133 /*
 134  * Builder object for creating IndexedStringMaps.  Fill one of these
 135  * up, and then pass it to IndexedStringMap::create.
 136  */
 137 template<class T, bool CaseSensitive, class Index, Index InvalidIndex>
 138 class IndexedStringMap<T,CaseSensitive,Index,InvalidIndex>::Builder {
 139   typedef typename boost::mpl::if_c<
 140     CaseSensitive,
 141     string_data_same,
 142     string_data_isame
 143   >::type EqObject;
 144   typedef hphp_hash_map<const StringData*,Index,
 145     string_data_hash,EqObject> Map;
 146
 147 public:
 148   typedef typename Map::const_iterator const_iterator;
 149   typedef typename Map::iterator iterator;
 150
 151   iterator find(const StringData* key) { return m_map.find(key); }
 152   iterator begin()                     { return m_map.begin(); }
 153   iterator end()                       { return m_map.end(); }
 154   Index    size() const                { return m_list.size(); }
 155
 156   const_iterator find(const StringData* key) const {
 157     return m_map.find(key);
 158   }
 159   const_iterator begin() const { return m_map.begin(); }
 160   const_iterator end()   const { return m_map.end(); }
 161
 162   T& operator[](Index idx) {
 163     assert(idx >= 0);
 164     assert(size_t(idx) < m_list.size());
 165     return m_list[idx];
 166   }
 167
 168   const T& operator[](Index idx) const {
 169     return (*const_cast<Builder*>(this))[idx];
 170   }
 171
 172   /*
 173    * Add an object to the position on the end, and allow lookup by
 174    * `name'.
 175    */
 176   void add(const StringData* name, const T& t) {
 177     if (m_list.size() >= size_t(std::numeric_limits<Index>::max())) {
 178       assert(false && "IndexedStringMap::Builder overflowed");
 179       abort();
 180     }
 181
 182     m_map[name] = m_list.size();
 183     m_list.push_back(t);
 184   }
 185
 186   /*
 187    * Adds objects that occupy indexes but can't be located by name.
 188    */
 189   void addUnnamed(const T& t) {
 190     m_list.push_back(t);
 191   }
 192
 193   /*
 194    * Implement custom separate versions of (de)serialization code to
 195    * be more compact about what we put on disk.  (Instead of just
 196    * pumping through our m_list and m_map.)
 197    */
 198
 199   // Deserialization version.
 200   template<class SerDe>
 201   typename std::enable_if<SerDe::deserializing>::type serde(SerDe& sd) {
 202     uint32_t size;
 203     sd(size);
 204     for (uint32_t i = 0; i < size; ++i) {
 205       const StringData* name;
 206       T t;
 207       sd(name)(t);
 208
 209       if (name) {
 210         add(name, t);
 211       } else {
 212         addUnnamed(t);
 213       }
 214     }
 215   }
 216
 217   // Serialization version.
 218   template<class SerDe>
 219   typename std::enable_if<!SerDe::deserializing>::type serde(SerDe& sd) {
 220     std::vector<const StringData*> names(m_list.size());
 221     for (typename Map::const_iterator it = m_map.begin();
 222         it != m_map.end();
 223         ++it) {
 224       names[it->second] = it->first;
 225     }
 226
 227     sd(uint32_t(m_list.size()));
 228     for (uint32_t i = 0; i < m_list.size(); ++i) {
 229       sd(names[i])(m_list[i]);
 230     }
 231   }
 232
 233 private:
 234   friend class IndexedStringMap;
 235   std::vector<T> m_list;
 236   Map m_map;
 237 };
 238
 239 //////////////////////////////////////////////////////////////////////
 240
 241 }
 242
 243 #endif