hphp/runtime/base/property-table.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 #ifndef incl_HPHP_PROPERTY_TABLE_H_
  17 #define incl_HPHP_PROPERTY_TABLE_H_
  18
  19 #include "hphp/runtime/base/string-data.h"
  20
  21 #include <cstdint>
  22
  23 namespace HPHP {
  24
  25 // Hash table that preserves insertion order.
  26 struct PropertyTable {
  27   PropertyTable();
  28   PropertyTable(const PropertyTable&);
  29   ~PropertyTable();
  30
  31   PropertyTable& operator=(const PropertyTable&) = delete;
  32
  33   uint32_t add(const StringData*);
  34   uint32_t offsetFor(const StringData*) const;
  35   const StringData* keyForOffset(uint32_t) const;
  36
  37   static constexpr uint32_t kInvalidOffset = UINT_MAX;
  38
  39 private:
  40   struct Entry {
  41     const StringData* key;
  42     uint32_t offset;
  43     strhash_t hash;
  44   };
  45
  46   static uint32_t* baseToOffsets(void* base);
  47   uint32_t* offsets();
  48   const uint32_t* offsets() const;
  49
  50   static Entry* baseToEntries(void* base, size_t capacity);
  51   Entry* entries();
  52   const Entry* entries() const;
  53
  54   enum PropertyTypeTag {
  55     Static,
  56     NotStatic
  57   };
  58
  59   template<PropertyTypeTag>
  60   uint32_t bucketFor(const StringData*);
  61   template<PropertyTypeTag>
  62   uint32_t bucketFor(const StringData*) const;
  63   template<PropertyTypeTag>
  64   uint32_t bucketFor(const StringData*, const Entry*, size_t capacity);
  65   template<PropertyTypeTag>
  66   uint32_t bucketFor(const StringData*, const Entry*, size_t capacity) const;
  67
  68   static size_t bytesForCapacity(size_t capacity);
  69   double loadFactor() const;
  70   bool shouldGrow() const;
  71   void grow();
  72   void rehash(void* oldBase, size_t oldCap, void* newBase, size_t newCap);
  73
  74   // The capacity below which we ignore the load factor. The table
  75   // depends on having at least one free slot to signal the end of a hash
  76   // lookup.  If we always followed the load factor, table sizes below a
  77   // certain limit would be guaranteed to fill completely, violating this
  78   // invariant.
  79   static constexpr size_t kLoadFactorCapacityThreshold = 4;
  80   static constexpr double kMaxLoadFactor =
  81     1.0 - (1.0/static_cast<double>(kLoadFactorCapacityThreshold));
  82
  83   uint32_t m_nextOffset;
  84   size_t m_size;
  85   size_t m_capacity;
  86   void* m_base;
  87 };
  88
  89 inline size_t PropertyTable::bytesForCapacity(size_t capacity) {
  90   return capacity * (sizeof(uint32_t) + sizeof(Entry));
  91 }
  92
  93 inline uint32_t* PropertyTable::baseToOffsets(void* base) {
  94   return static_cast<uint32_t*>(base);
  95 }
  96
  97 inline PropertyTable::Entry* PropertyTable::baseToEntries(
  98   void* base,
  99   size_t capacity
 100 ) {
 101   return reinterpret_cast<Entry*>(baseToOffsets(base) + capacity);
 102 }
 103
 104 inline uint32_t* PropertyTable::offsets() {
 105   return const_cast<uint32_t*>(
 106     const_cast<const PropertyTable*>(this)->baseToOffsets(m_base));
 107 }
 108
 109 inline const uint32_t* PropertyTable::offsets() const {
 110   return baseToOffsets(m_base);
 111 }
 112
 113 inline PropertyTable::Entry* PropertyTable::entries() {
 114   return const_cast<PropertyTable::Entry*>(
 115     const_cast<const PropertyTable*>(this)->entries());
 116 }
 117
 118 inline const PropertyTable::Entry* PropertyTable::entries() const {
 119   return baseToEntries(m_base, m_capacity);
 120 }
 121
 122 inline double PropertyTable::loadFactor() const {
 123   return static_cast<double>(m_size) / static_cast<double>(m_capacity);
 124 }
 125
 126 inline bool PropertyTable::shouldGrow() const {
 127   if (m_capacity >= kLoadFactorCapacityThreshold) {
 128     return loadFactor() >= kMaxLoadFactor;
 129   }
 130   // We have to keep at least one extra slot free so that we're guaranteed to
 131   // eventually hit it when doing the hash lookup.
 132   return (m_size + 1) >= m_capacity;
 133 }
 134
 135 template<PropertyTable::PropertyTypeTag propType>
 136 inline uint32_t PropertyTable::bucketFor(const StringData* property) {
 137   return bucketFor<propType>(property, entries(), m_capacity);
 138 }
 139
 140 template<PropertyTable::PropertyTypeTag propType>
 141 inline uint32_t PropertyTable::bucketFor(const StringData* property) const {
 142   return bucketFor<propType>(property, entries(), m_capacity);
 143 }
 144
 145 inline const StringData* PropertyTable::keyForOffset(uint32_t offset) const {
 146   if (offset >= m_size) return nullptr;
 147   return entries()[offsets()[offset]].key;
 148 }
 149
 150 inline uint32_t PropertyTable::offsetFor(const StringData* property) const {
 151   auto bucketIndex = property->isStatic() ? bucketFor<Static>(property)
 152                                           : bucketFor<NotStatic>(property);
 153   auto& bucket = entries()[bucketIndex];
 154   return bucket.key ? bucket.offset : kInvalidOffset;
 155 }
 156
 157 template<PropertyTable::PropertyTypeTag propType>
 158 inline uint32_t PropertyTable::bucketFor(
 159   const StringData* property,
 160   const Entry* entries,
 161   size_t capacity
 162 ) {
 163   return const_cast<const PropertyTable*>(this)->bucketFor<propType>(
 164     property, entries, capacity);
 165 }
 166
 167 template<PropertyTable::PropertyTypeTag propType>
 168 inline uint32_t PropertyTable::bucketFor(
 169   const StringData* property,
 170   const Entry* entries,
 171   size_t capacity
 172 ) const {
 173   assertx(propType == NotStatic || property->isStatic());
 174   assertx(m_size < m_capacity);
 175   auto hash = property->hash();
 176   auto start = hash & (capacity - 1);
 177   auto current = start;
 178   while (true) {
 179     const auto key = entries[current].key;
 180     if (!key) break;
 181     if (key == property) break;
 182     if (propType == NotStatic) {
 183       if (entries[current].hash == property->hash()) {
 184         if (key->same(property)) break;
 185       }
 186     }
 187     current = (current + 1) & (capacity - 1);
 188   }
 189   return current;
 190 }
 191
 192 }
 193
 194 #endif