hphp/runtime/ext/collections/hash-collection.cpp

   1 #include "hphp/runtime/ext/collections/hash-collection.h"
   2 #include "hphp/runtime/base/array-init.h"
   3 #include "hphp/runtime/base/vanilla-dict.h"
   4 #include "hphp/runtime/ext/collections/ext_collections-map.h"
   5 #include "hphp/runtime/ext/collections/ext_collections-set.h"
   6 #include "hphp/runtime/vm/vm-regs.h"
   7 #include "hphp/util/text-util.h"
   8
   9 namespace HPHP {
  10 /////////////////////////////////////////////////////////////////////////////
  11 // HashCollection
  12
  13 HashCollection::HashCollection(Class* cls, HeaderKind kind, uint32_t cap)
  14   : c_Collection(cls, kind)
  15   , m_unusedAndSize(0)
  16 {
  17   setArrayData(cap > 0
  18     ? VanillaDict::as(VanillaDict::MakeReserveDict(cap))
  19     : CreateDictAsMixed());
  20 }
  21
  22 NEVER_INLINE
  23 void HashCollection::throwTooLarge() {
  24   assertx(getClassName().size() == 6);
  25   auto clsName = getClassName().get()->slice();
  26   String msg(130, ReserveString);
  27   auto buf = msg.bufferSlice();
  28   auto sz = snprintf(buf.data(), buf.size() + 1,
  29     "%s object has reached its maximum capacity of %u element "
  30     "slots and does not have room to add a new element",
  31     clsName.data() + 3, // strip "HH\" prefix
  32     MaxSize
  33   );
  34   msg.setSize(std::min<int>(sz, buf.size()));
  35   SystemLib::throwInvalidOperationExceptionObject(msg);
  36 }
  37
  38 NEVER_INLINE
  39 void HashCollection::throwReserveTooLarge() {
  40   assertx(getClassName().size() == 6);
  41   auto clsName = getClassName().get()->slice();
  42   String msg(80, ReserveString);
  43   auto buf = msg.bufferSlice();
  44   auto sz = snprintf(buf.data(), buf.size() + 1,
  45     "%s does not support reserving room for more than %u elements",
  46     clsName.data() + 3, // strip "HH\" prefix
  47     MaxReserveSize
  48   );
  49   msg.setSize(std::min<int>(sz, buf.size()));
  50   SystemLib::throwInvalidOperationExceptionObject(msg);
  51 }
  52
  53 NEVER_INLINE
  54 int32_t* HashCollection::warnUnbalanced(size_t n, int32_t* ei) const {
  55   if (n > size_t(Cfg::Server::MaxArrayChain)) {
  56     raise_error("%s is too unbalanced (%lu)",
  57                 getClassName().data() + 3, // strip "HH\" prefix
  58                 n);
  59   }
  60   return ei;
  61 }
  62
  63 Array HashCollection::toKeysArray() {
  64   VecInit ai(m_size);
  65   auto* eLimit = elmLimit();
  66   for (auto* e = firstElm(); e != eLimit; e = nextElm(e, eLimit)) {
  67     if (e->hasIntKey()) {
  68       ai.append(int64_t{e->ikey});
  69     } else {
  70       assertx(e->hasStrKey());
  71       ai.append(VarNR(e->skey).tv());
  72     }
  73   }
  74   return ai.toArray();
  75 }
  76
  77 Array HashCollection::toValuesArray() {
  78   if (!m_size) return empty_vec_array();
  79   return Array{arrayData()}.toVec();
  80 }
  81
  82 void HashCollection::remove(int64_t key) {
  83   auto p = findForRemove(key, hash_int64(key));
  84   if (p.valid()) {
  85     mutate();
  86     erase(p);
  87   }
  88 }
  89
  90 void HashCollection::remove(StringData* key) {
  91   auto p = findForRemove(key, key->hash());
  92   if (p.valid()) {
  93     mutate();
  94     erase(p);
  95   }
  96 }
  97
  98 void HashCollection::eraseNoCompact(VanillaDict::RemovePos pos) {
  99   assertx(canMutateBuffer());
 100   assertx(pos.valid() && !isTombstone(pos.elmIdx));
 101   assertx(m_size > 0);
 102   arrayData()->eraseNoCompact(pos);
 103   --m_size;
 104 }
 105
 106 NEVER_INLINE
 107 void HashCollection::makeRoom() {
 108   assertx(isFull());
 109   assertx(!isDensityTooLow());
 110   if (UNLIKELY(cap() == MaxSize)) throwTooLarge();
 111   assertx(scale() > 0);
 112   grow(scale() * 2);
 113   assertx(canMutateBuffer());
 114   assertx(!isFull());
 115 }
 116
 117 NEVER_INLINE
 118 void HashCollection::reserve(int64_t sz) {
 119   assertx(m_size <= posLimit() && posLimit() <= cap());
 120   auto cap = static_cast<int64_t>(this->cap());
 121   if (LIKELY(sz > cap)) {
 122     if (UNLIKELY(sz > int64_t(MaxReserveSize))) {
 123       throwReserveTooLarge();
 124     }
 125     // Fast path: The requested capacity is greater than the current capacity.
 126     // Grow to the smallest allowed capacity that is sufficient.
 127     grow(VanillaDict::computeScaleFromSize(sz));
 128     assertx(canMutateBuffer());
 129     return;
 130   }
 131   if (LIKELY(!hasTombstones())) {
 132     // Fast path: There are no tombstones and the requested capacity is less
 133     // than or equal to the current capacity.
 134     mutate();
 135     return;
 136   }
 137   if (sz + int64_t(posLimit() - m_size) <= cap || isDensityTooLow()) {
 138     // If we reach this case, then either (1) density is too low (this is
 139     // possible because of methods like retain()), in which case we compact
 140     // to make room and return, OR (2) density is not too low and either
 141     // sz < m_size or there's enough room to add sz-m_size elements, in
 142     // which case we do nothing and return.
 143     compactOrShrinkIfDensityTooLow();
 144     assertx(sz + int64_t(posLimit() - m_size) <= cap);
 145     mutate();
 146     return;
 147   }
 148   // If we reach this case, then density is not too low and sz > m_size and
 149   // there is not enough room to add sz-m_size elements. While would could
 150   // compact to make room, it's better for Hysteresis if we grow capacity
 151   // by 2x instead.
 152   assertx(!isDensityTooLow());
 153   assertx(sz + int64_t(posLimit() - m_size) > cap);
 154   assertx(cap < MaxSize && tableMask() != 0);
 155   auto newScale = scale() * 2;
 156   assertx(sz > 0 && VanillaDict::Capacity(newScale) >= sz);
 157   grow(newScale);
 158   assertx(canMutateBuffer());
 159 }
 160
 161 ALWAYS_INLINE
 162 void HashCollection::resizeHelper(uint32_t newCap) {
 163   assertx(newCap >= m_size);
 164   assertx(m_immCopy.isNull());
 165   // Allocate a new ArrayData with the specified capacity and dup
 166   // all the elements (without copying over tombstones).
 167   auto ad = arrayData()->isStatic() && arrayData()->empty() ?
 168     VanillaDict::as(VanillaDict::MakeReserveDict(newCap)) :
 169     VanillaDict::CopyReserve(arrayData(), newCap);
 170   decRefArr(arrayData());
 171   setArrayData(ad);
 172   assertx(canMutateBuffer());
 173 }
 174
 175 void HashCollection::grow(uint32_t newScale) {
 176   auto newCap = VanillaDict::Capacity(newScale);
 177   assertx(m_size <= posLimit() && posLimit() <= cap() && cap() <= newCap);
 178   assertx(SmallSize <= newCap && newCap <= MaxSize);
 179   assertx(m_size <= newCap);
 180   auto oldAd = arrayData();
 181   dropImmCopy();
 182   if (m_size > 0 && !oldAd->cowCheck()) {
 183     setArrayData(VanillaDict::Grow(oldAd, newScale, false));
 184     decRefArr(oldAd);
 185   } else {
 186     // For cases where m_size is zero or the buffer's refcount is
 187     // greater than 1, call resizeHelper().
 188     resizeHelper(newCap);
 189   }
 190   assertx(canMutateBuffer());
 191 }
 192
 193 void HashCollection::compact() {
 194   assertx(isDensityTooLow());
 195   dropImmCopy();
 196   if (!arrayData()->cowCheck()) {
 197     // VanillaDict::compact can only handle cases where the buffer's
 198     // refcount is 1.
 199     arrayData()->compact();
 200   } else {
 201     // For cases where the buffer's refcount is greater than 1, call
 202     // resizeHelper().
 203     resizeHelper(cap());
 204   }
 205   assertx(canMutateBuffer());
 206   assertx(!isDensityTooLow());
 207 }
 208
 209 void HashCollection::shrink(uint32_t oldCap /* = 0 */) {
 210   assertx(isCapacityTooHigh() && (oldCap == 0 || oldCap < cap()));
 211   assertx(m_size <= posLimit() && posLimit() <= cap());
 212   dropImmCopy();
 213   uint32_t newCap;
 214   if (oldCap != 0) {
 215     // If an old capacity was specified, use that
 216     newCap = oldCap;
 217     // .. unless the old capacity is too small, in which case we use the
 218     // smallest capacity that is large enough to hold the current number
 219     // of elements.
 220     for (; newCap < m_size; newCap <<= 1) {}
 221     assertx(newCap == computeMaxElms(folly::nextPowTwo<uint64_t>(newCap) - 1));
 222   } else {
 223     // If no old capacity was provided, we compute the largest capacity
 224     // where m_size/cap() is less than or equal to 0.5 for good hysteresis
 225     size_t doubleSz = size_t(m_size) * 2;
 226     uint32_t capThreshold = (doubleSz < size_t(MaxSize)) ? doubleSz : MaxSize;
 227     for (newCap = SmallSize * 2; newCap < capThreshold; newCap <<= 1) {}
 228   }
 229   assertx(SmallSize <= newCap && newCap <= MaxSize);
 230   assertx(m_size <= newCap);
 231   auto* oldAd = arrayData();
 232   if (!oldAd->cowCheck()) {
 233     // If the buffer's refcount is 1, we can teleport the elements
 234     // to a new buffer
 235     auto oldBuf = data();
 236     auto oldUsed = posLimit();
 237     auto oldNextKI = nextKI();
 238     auto const arr = VanillaDict::as(VanillaDict::MakeReserveDict(newCap));
 239     setArrayData(arr);
 240     arr->m_size = m_size;
 241     arr->mutableKeyTypes()->copyFrom(oldAd->keyTypes(), /*compact=*/true);
 242     auto data = this->data();
 243     auto table = hashTab();
 244     auto table_mask = tableMask();
 245     setPosLimit(m_size);
 246     setNextKI(oldNextKI);
 247     for (uint32_t frPos = 0, toPos = 0; toPos < m_size; ++toPos, ++frPos) {
 248       frPos = skipTombstonesNoBoundsCheck(frPos, oldUsed, oldBuf);
 249       copyElm(oldBuf[frPos], data[toPos]);
 250       *findForNewInsert(table, table_mask, data[toPos].probe()) = toPos;
 251     }
 252     oldAd->setZombie();
 253     decRefArr(oldAd);
 254   } else {
 255     // For cases where the buffer's refcount is greater than 1, call
 256     // resizeHelper()
 257     resizeHelper(newCap);
 258   }
 259   assertx(canMutateBuffer());
 260   assertx(!isCapacityTooHigh() || newCap == oldCap);
 261 }
 262
 263 HashCollection::Elm& HashCollection::allocElmFront(VanillaDict::Inserter ei) {
 264   assertx(VanillaDict::isValidIns(ei) && !VanillaDict::isValidPos(*ei));
 265   assertx(m_size <= posLimit() && posLimit() < cap());
 266   // Move the existing elements to make element slot 0 available.
 267   memmove(data() + 1, data(), posLimit() * sizeof(Elm));
 268   incPosLimit();
 269   // Update the hashtable to reflect the fact that everything was
 270   // moved over one position
 271   auto* hash = hashTab();
 272   auto* hashEnd = hash + arrayData()->hashSize();
 273   for (; hash != hashEnd; ++hash) {
 274     if (validPos(*hash)) {
 275       ++(*hash);
 276     }
 277   }
 278   // Set the hash entry we found to point to element slot 0.
 279   (*ei) = 0;
 280   // Adjust size to reflect that we're adding a new element.
 281   incSize();
 282   // Store the value into element slot 0.
 283   return data()[0];
 284 }
 285
 286 void HashCollection::mutateImpl() {
 287   assertx(arrayData()->hasMultipleRefs());
 288   dropImmCopy();
 289   if (canMutateBuffer()) {
 290     return;
 291   }
 292   auto* oldAd = arrayData();
 293   setArrayData(VanillaDict::as(VanillaDict::Copy(oldAd)));
 294   assertx(oldAd->hasMultipleRefs());
 295   oldAd->decRefCount();
 296 }
 297
 298 /////////////////////////////////////////////////////////////////////////////
 299 }