hphp/runtime/base/mixed-array.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_HPHP_ARRAY_H_
  18 #define incl_HPHP_HPHP_ARRAY_H_
  19
  20 #include "hphp/runtime/base/array-common.h"
  21 #include "hphp/runtime/base/array-data.h"
  22 #include "hphp/runtime/base/data-walker.h"
  23 #include "hphp/runtime/base/hash-table.h"
  24 #include "hphp/runtime/base/mixed-array-keys.h"
  25 #include "hphp/runtime/base/tv-val.h"
  26 #include "hphp/runtime/base/string-data.h"
  27 #include "hphp/runtime/base/typed-value.h"
  28
  29 #include <folly/portability/Constexpr.h>
  30
  31 namespace HPHP {
  32
  33 //////////////////////////////////////////////////////////////////////
  34
  35 struct APCArray;
  36 struct APCHandle;
  37 struct MemoryProfile;
  38
  39 //////////////////////////////////////////////////////////////////////
  40 struct MixedArrayElm {
  41   using hash_t = strhash_t;
  42
  43   // We store values here, but also some information local to this array:
  44   // data.m_aux.u_hash contains either a negative number (for an int key) or
  45   // a string hashcode (31-bit and thus non-negative); the high bit is the
  46   // int/string key descriminator. data.m_type == kInvalidDataType if this is
  47   // an empty slot in the array (e.g. after a key is deleted).  It is
  48   // critical that when we return &data to clients, that they not read or
  49   // write the m_aux field!
  50   TypedValueAux data;
  51
  52   // Putting the key second lets us cast MixedArrayElm* to TypedValue*, which
  53   // we can use to simplify the Lval sublattice in the JIT type system.
  54   union {
  55     int64_t ikey;
  56     StringData* skey;
  57   };
  58
  59   void setStaticKey(StringData* k, strhash_t h) {
  60     assertx(k->isStatic());
  61     setStrKeyNoIncRef(k, h);
  62   }
  63
  64   void setStrKeyNoIncRef(StringData* k, strhash_t h) {
  65     skey = k;
  66     data.hash() = h;
  67   }
  68
  69   void setStrKey(StringData* k, strhash_t h) {
  70     skey = k;
  71     data.hash() = h;
  72     k->incRefCount();
  73   }
  74
  75   void setIntKey(int64_t k, inthash_t h) {
  76     ikey = k;
  77     data.hash() = static_cast<int32_t>(h) | STRHASH_MSB;
  78     assertx(hasIntKey());
  79     static_assert(static_cast<int32_t>(STRHASH_MSB) < 0,
  80                   "high bit indicates int key");
  81   }
  82
  83   void setTombstone() {
  84     // We don't explicitly check for tombstones in MixedArray::release(),
  85     // instead make the deleted element appear to contain uncounted values.
  86     data.m_type = kInvalidDataType;
  87     static_assert(!isRefcountedType(kInvalidDataType), "");
  88     data.hash() = -1;
  89     assertx(hasIntKey());
  90   }
  91
  92   hash_t probe() const {
  93     return hash();
  94   }
  95
  96   TYPE_SCAN_CUSTOM() {
  97     static_assert(!isRefcountedType(kInvalidDataType), "");
  98     // if data is a Tombstone, key should have been set to int type.
  99     if (hasStrKey()) scanner.scan(skey);
 100     if (isRefcountedType(data.m_type)) scanner.scan(data.m_data.pcnt);
 101   }
 102
 103   // Members below here are required for HashTable implemenation.
 104   ALWAYS_INLINE const TypedValue* datatv() const {
 105     return &data;
 106   }
 107
 108   ALWAYS_INLINE bool hasStrKey() const {
 109     // Currently string hash is 31-bit, thus it saves us some instructions to
 110     // encode int keys as a negative hash, so that we don't have to care about
 111     // the MSB when working with strhash_t.
 112     return data.hash() >= 0;
 113   }
 114
 115   ALWAYS_INLINE StringData* strKey() const {
 116     assertx(hasStrKey());
 117     return skey;
 118   }
 119
 120   ALWAYS_INLINE bool hasIntKey() const {
 121     return data.hash() < 0;
 122   }
 123
 124   ALWAYS_INLINE int64_t intKey() const {
 125     return ikey;
 126   }
 127
 128   ALWAYS_INLINE TypedValue getKey() const {
 129     if (hasIntKey()) {
 130       return make_tv<KindOfInt64>(ikey);
 131     }
 132     return skey->isRefCounted() ? make_tv<KindOfString>(skey)
 133                                 : make_tv<KindOfPersistentString>(skey);
 134   }
 135
 136   ALWAYS_INLINE hash_t hash() const {
 137     return data.hash();
 138   }
 139
 140   ALWAYS_INLINE bool isInvalid() const {
 141     return isTombstone();
 142   }
 143
 144   // Elm's data.m_type == kInvalidDataType for deleted slots.
 145   ALWAYS_INLINE bool isTombstone() const {
 146     assertx(isRealType(data.m_type) || data.m_type == kInvalidDataType);
 147     return data.m_type == kInvalidDataType;
 148   }
 149
 150   static constexpr ptrdiff_t keyOff() {
 151     return offsetof(MixedArrayElm, ikey);
 152   }
 153   static constexpr ptrdiff_t dataOff() {
 154     return offsetof(MixedArrayElm, data) + offsetof(TypedValue, m_data);
 155   }
 156   static constexpr ptrdiff_t typeOff() {
 157     return offsetof(MixedArrayElm, data) + offsetof(TypedValue, m_type);
 158   }
 159   static constexpr ptrdiff_t hashOff() {
 160     return offsetof(MixedArrayElm, data) + offsetof(TypedValue, m_aux);
 161   }
 162 };
 163
 164 struct MixedArray final : ArrayData,
 165                           array::HashTable<MixedArray, MixedArrayElm>,
 166                           type_scan::MarkCollectable<MixedArray> {
 167   struct ElmKey {
 168     ElmKey() {}
 169     ElmKey(strhash_t hash, StringData* key)
 170         : skey(key), hash(hash)
 171       {}
 172     union {
 173       StringData* skey;
 174       int64_t ikey;
 175     };
 176     int32_t hash;
 177
 178     TYPE_SCAN_CUSTOM_FIELD(skey) {
 179       if (hash >= 0) scanner.scan(skey);
 180     }
 181   };
 182
 183   /*
 184    * Initialize an empty small mixed array with given field. This should be
 185    * inlined.
 186    */
 187   static void InitSmall(MixedArray* a, uint32_t size, int64_t nextIntKey);
 188
 189   /*
 190    * Allocate a new, empty, request-local array in (mixed|dict) mode, with
 191    * enough space reserved for `capacity' members.
 192    *
 193    * The returned array is already incref'd.
 194    */
 195   static ArrayData* MakeReserveMixed(uint32_t size);
 196   static ArrayData* MakeReserveDArray(uint32_t size);
 197   static ArrayData* MakeReserveDict(uint32_t size);
 198   static constexpr auto MakeReserve = &MakeReserveMixed;
 199
 200   /*
 201    * Convert mixed-layout array to dict in-place. This function doesn't check
 202    * whether the input array contains references or not, so only use this when
 203    * you already know that they do not.
 204    */
 205   static MixedArray* ToDictInPlace(ArrayData*);
 206
 207   /*
 208    * MakeReserveLike will return a PHP array with a memory representation
 209    * similar to the one used by `other'.
 210    *
 211    * The returned array is already incref'd.
 212    */
 213   static ArrayData* MakeReserveLike(const ArrayData* other, uint32_t capacity);
 214
 215   /*
 216    * Allocates a new request-local array with given key,value,key,value,... in
 217    * natural order. Returns nullptr if there are duplicate keys. Does not check
 218    * for integer-like keys. Takes ownership of keys and values iff successful.
 219    */
 220   static MixedArray* MakeMixed(uint32_t size, const TypedValue* kvs);
 221   static MixedArray* MakeDArray(uint32_t size, const TypedValue* kvs);
 222   static MixedArray* MakeDict(uint32_t size, const TypedValue* kvs);
 223 private:
 224   template<HeaderKind hdr, ArrayData::DVArray dv>
 225   static MixedArray* MakeMixedImpl(uint32_t size, const TypedValue* kvs);
 226
 227 public:
 228   static constexpr size_t kKeyTypesOffset = 7;
 229
 230   const MixedArrayKeys& keyTypes() const {
 231     auto const pointer = uintptr_t(this) + kKeyTypesOffset;
 232     return *reinterpret_cast<MixedArrayKeys*>(pointer);
 233   }
 234
 235   MixedArrayKeys* mutableKeyTypes() {
 236     auto const pointer = uintptr_t(this) + kKeyTypesOffset;
 237     return reinterpret_cast<MixedArrayKeys*>(pointer);
 238   }
 239
 240 public:
 241   /*
 242    * Same semantics as PackedArray::MakeNatural().
 243    */
 244   static MixedArray* MakeDArrayNatural(uint32_t size, const TypedValue* vals);
 245
 246   /*
 247    * Like MakePacked, but given static strings, make a struct-like array.
 248    * Also requires size > 0.
 249    */
 250   static MixedArray* MakeStruct(uint32_t size, const StringData* const* keys,
 251                                const TypedValue* values);
 252   static MixedArray* MakeStructDict(uint32_t size,
 253                                     const StringData* const* keys,
 254                                     const TypedValue* values);
 255   static MixedArray* MakeStructDArray(uint32_t size,
 256                                       const StringData* const* keys,
 257                                       const TypedValue* values);
 258
 259   /*
 260    * Allocate a struct-like array (with string literal keys), but only init
 261    * the hash table and the header, leaving elms uninit. Requires size > 0.
 262    */
 263   static MixedArray* AllocStruct(uint32_t size, const int32_t* hash);
 264   static MixedArray* AllocStructDict(uint32_t size, const int32_t* hash);
 265   static MixedArray* AllocStructDArray(uint32_t size, const int32_t* hash);
 266
 267   /*
 268    * Allocate an uncounted MixedArray and copy the values from the
 269    * input 'array' into the uncounted one. All values copied are made
 270    * uncounted as well.  An uncounted array can only contain uncounted
 271    * values (primitive values, uncounted or static strings and
 272    * uncounted or static arrays).  The Packed version does the same
 273    * when the array has a kPackedKind.
 274    *
 275    * If withApcTypedValue is true, space for an APCTypedValue will be
 276    * allocated in front of the returned pointer.
 277    */
 278   static ArrayData* MakeUncounted(
 279       ArrayData* array, bool withApcTypedValue,
 280       DataWalker::PointerMap* seen = nullptr
 281   );
 282   static ArrayData* MakeUncounted(
 283       ArrayData* array, int, DataWalker::PointerMap* seen = nullptr
 284   ) = delete;
 285   static ArrayData* MakeUncounted(
 286       ArrayData* array, size_t extra, DataWalker::PointerMap* seen = nullptr
 287   ) = delete;
 288
 289   static ArrayData* MakeDictFromAPC(const APCArray* apc);
 290   static ArrayData* MakeDArrayFromAPC(const APCArray* apc);
 291
 292   static bool DictEqual(const ArrayData*, const ArrayData*);
 293   static bool DictNotEqual(const ArrayData*, const ArrayData*);
 294   static bool DictSame(const ArrayData*, const ArrayData*);
 295   static bool DictNotSame(const ArrayData*, const ArrayData*);
 296
 297   using ArrayData::decRefCount;
 298   using ArrayData::hasMultipleRefs;
 299   using ArrayData::hasExactlyOneRef;
 300   using ArrayData::decWillRelease;
 301   using ArrayData::incRefCount;
 302
 303   /*
 304    * MixedArray is convertible to ArrayData*, but not implicitly.
 305    * This is to avoid accidentally using virtual dispatch when you
 306    * already know something is Mixed.
 307    *
 308    * I.e., instead of doing things like mixed->nvGet(...) you want to
 309    * do MixedArray::NvGetInt(adYouKnowIsMixed, ...).  This means using
 310    * MixedArray*'s directly shouldn't really happen very often.
 311    */
 312   ArrayData* asArrayData() { return this; }
 313   const ArrayData* asArrayData() const { return this; }
 314
 315   // These using directives ensure the full set of overloaded functions
 316   // are visible in this class, to avoid triggering implicit conversions
 317   // from a const Variant& key to int64.
 318 private:
 319   using ArrayData::exists;
 320   using ArrayData::at;
 321   using ArrayData::rval;
 322   using ArrayData::lval;
 323   using ArrayData::set;
 324   using ArrayData::remove;
 325   using ArrayData::release;
 326
 327 public:
 328   static size_t Vsize(const ArrayData*);
 329   static TypedValue GetPosVal(const ArrayData*, ssize_t pos);
 330   static bool IsVectorData(const ArrayData*);
 331   static bool IsStrictVector(const ArrayData* ad) {
 332     return ad->m_size == asMixed(ad)->m_nextKI && IsVectorData(ad);
 333   }
 334   static bool ExistsInt(const ArrayData*, int64_t k);
 335   static bool ExistsStr(const ArrayData*, const StringData* k);
 336   static arr_lval LvalInt(ArrayData* ad, int64_t k, bool copy);
 337   static arr_lval LvalStr(ArrayData* ad, StringData* k, bool copy);
 338   static ArrayData* SetInt(ArrayData*, int64_t k, TypedValue v);
 339   static ArrayData* SetIntMove(ArrayData*, int64_t k, TypedValue v);
 340   static ArrayData* SetStr(ArrayData*, StringData* k, TypedValue v);
 341   static ArrayData* SetStrMove(ArrayData*, StringData* k, TypedValue v);
 342   static ArrayData* AddInt(ArrayData*, int64_t k, TypedValue v, bool copy);
 343   static ArrayData* AddStr(ArrayData*, StringData* k, TypedValue v, bool copy);
 344   static ArrayData* RemoveInt(ArrayData*, int64_t k);
 345   static ArrayData* RemoveStr(ArrayData*, const StringData* k);
 346   static ArrayData* Copy(const ArrayData*);
 347   static ArrayData* CopyStatic(const ArrayData*);
 348   static ArrayData* Append(ArrayData*, TypedValue v);
 349   static ArrayData* PlusEq(ArrayData*, const ArrayData* elems);
 350   static ArrayData* Merge(ArrayData*, const ArrayData* elems);
 351   static ArrayData* Pop(ArrayData*, Variant& value);
 352   static ArrayData* Dequeue(ArrayData*, Variant& value);
 353   static ArrayData* Prepend(ArrayData*, TypedValue v);
 354   static ArrayData* ToPHPArray(ArrayData*, bool);
 355   static ArrayData* ToPHPArrayIntishCast(ArrayData*, bool);
 356   static ArrayData* ToDict(ArrayData*, bool);
 357   static constexpr auto ToVec = &ArrayCommon::ToVec;
 358   static constexpr auto ToKeyset = &ArrayCommon::ToKeyset;
 359   static constexpr auto ToVArray = &ArrayCommon::ToVArray;
 360   static ArrayData* ToDArray(ArrayData*, bool);
 361
 362   static void Renumber(ArrayData*);
 363   static void OnSetEvalScalar(ArrayData*);
 364   static void Release(ArrayData*);
 365   // Recursively register {allocation, rootAPCHandle} with APCGCManager
 366   static void RegisterUncountedAllocations(ArrayData* ad,
 367                                            APCHandle* rootAPCHandle);
 368   static void ReleaseUncounted(ArrayData*);
 369
 370   static ArrayData* EscalateForSort(ArrayData* ad, SortFunction sf);
 371   static void Ksort(ArrayData*, int sort_flags, bool ascending);
 372   static void Sort(ArrayData*, int sort_flags, bool ascending);
 373   static void Asort(ArrayData*, int sort_flags, bool ascending);
 374   static bool Uksort(ArrayData*, const Variant& cmp_function);
 375   static bool Usort(ArrayData*, const Variant& cmp_function);
 376   static bool Uasort(ArrayData*, const Variant& cmp_function);
 377
 378   static constexpr auto NvGetIntDict = &NvGetInt;
 379   static constexpr auto NvGetStrDict = &NvGetStr;
 380   static constexpr auto NvGetIntPosDict = &NvGetIntPos;
 381   static constexpr auto NvGetStrPosDict = &NvGetStrPos;
 382   static constexpr auto ReleaseDict = &Release;
 383   static constexpr auto GetPosKeyDict = &GetPosKey;
 384   static constexpr auto GetPosValDict = &GetPosVal;
 385   static constexpr auto SetIntDict = &SetInt;
 386   static constexpr auto SetIntMoveDict = &SetIntMove;
 387   static constexpr auto SetStrDict = &SetStr;
 388   static constexpr auto SetStrMoveDict = &SetStrMove;
 389   static constexpr auto AddIntDict = &AddInt;
 390   static constexpr auto AddStrDict = &AddStr;
 391   static constexpr auto VsizeDict = &Vsize;
 392   static constexpr auto IsVectorDataDict = &IsVectorData;
 393   static constexpr auto ExistsIntDict = &ExistsInt;
 394   static constexpr auto ExistsStrDict = &ExistsStr;
 395   static constexpr auto LvalIntDict = &LvalInt;
 396   static constexpr auto LvalStrDict = &LvalStr;
 397   static constexpr auto RemoveIntDict = &RemoveInt;
 398   static constexpr auto RemoveStrDict = &RemoveStr;
 399   static constexpr auto IterBeginDict = &IterBegin;
 400   static constexpr auto IterLastDict = &IterLast;
 401   static constexpr auto IterEndDict = &IterEnd;
 402   static constexpr auto IterAdvanceDict = &IterAdvance;
 403   static constexpr auto IterRewindDict = &IterRewind;
 404   static constexpr auto EscalateForSortDict = &EscalateForSort;
 405   static constexpr auto KsortDict = &Ksort;
 406   static constexpr auto SortDict = &Sort;
 407   static constexpr auto AsortDict = &Asort;
 408   static constexpr auto UksortDict = &Uksort;
 409   static constexpr auto UsortDict = &Usort;
 410   static constexpr auto UasortDict = &Uasort;
 411   static constexpr auto CopyDict = &Copy;
 412   static constexpr auto CopyStaticDict = &CopyStatic;
 413   static constexpr auto AppendDict = &Append;
 414   static constexpr auto PlusEqDict = &PlusEq;
 415   static constexpr auto MergeDict = &Merge;
 416   static constexpr auto PopDict = &Pop;
 417   static constexpr auto DequeueDict = &Dequeue;
 418   static constexpr auto PrependDict = &Prepend;
 419   static constexpr auto RenumberDict = &Renumber;
 420   static constexpr auto OnSetEvalScalarDict = &OnSetEvalScalar;
 421   static ArrayData* ToPHPArrayDict(ArrayData*, bool);
 422   static ArrayData* ToPHPArrayIntishCastDict(ArrayData*, bool);
 423   static ArrayData* ToDictDict(ArrayData*, bool);
 424   static constexpr auto ToVecDict = &ArrayCommon::ToVec;
 425   static constexpr auto ToKeysetDict = &ArrayCommon::ToKeyset;
 426   static constexpr auto ToVArrayDict = &ArrayCommon::ToVArray;
 427   static ArrayData* ToDArrayDict(ArrayData*, bool);
 428
 429   //////////////////////////////////////////////////////////////////////
 430
 431   // Helpers used by ArrayInit to update MixedArrays without refcount ops.
 432   // These helpers work for both mixed PHP arrays and dicts.
 433   static ArrayData* SetIntInPlace(ArrayData*, int64_t k, TypedValue v);
 434   static ArrayData* SetStrInPlace(ArrayData*, StringData* k, TypedValue v);
 435
 436   // Return an lval to the value at the given key. If `k` is not present,
 437   // this method will insert a null value for it and return it.
 438   //  @precondition: !isFull
 439   //  @precondition: !cowCheck
 440   static tv_lval LvalInPlace(ArrayData* ad, const Variant& k);
 441
 442   // If the key is not present in the array, return a null lval; else,
 443   // COW the array if necessary and return an lval into the new array.
 444   static arr_lval LvalSilentInt(ArrayData* ad, int64_t k);
 445   static arr_lval LvalSilentStr(ArrayData* ad, StringData* k);
 446
 447   //////////////////////////////////////////////////////////////////////
 448
 449 private:
 450   MixedArray* copyMixed() const;
 451   static ArrayData* MakeReserveImpl(uint32_t capacity, HeaderKind hk,
 452                                     ArrayData::DVArray);
 453   static MixedArray* MakeStructImpl(uint32_t, const StringData* const*,
 454                                     const TypedValue*, HeaderKind,
 455                                     ArrayData::DVArray);
 456   static MixedArray* AllocStructImpl(uint32_t, const int32_t*,
 457                                     HeaderKind, ArrayData::DVArray);
 458
 459   template <IntishCast IC>
 460   static ArrayData* FromDictImpl(ArrayData*, bool, bool);
 461
 462   static bool DictEqualHelper(const ArrayData*, const ArrayData*, bool);
 463
 464 public:
 465
 466   uint32_t iterLimit() const { return m_used; }
 467
 468   // Fetch a value and optional key (if keyPos != nullptr), given an
 469   // iterator pos.  Get the value cell, and initialize keyOut.
 470   void getArrayElm(ssize_t pos, TypedValue* out, TypedValue* keyOut) const;
 471   void getArrayElm(ssize_t pos, TypedValue* out) const;
 472
 473   const TypedValue* getArrayElmPtr(ssize_t pos) const;
 474   TypedValue getArrayElmKey(ssize_t pos) const;
 475
 476   bool isTombstone(ssize_t pos) const;
 477   // Elm's data.m_type == kInvalidDataType for deleted slots.
 478   static bool isTombstone(DataType t) {
 479     return t == kInvalidDataType;
 480   }
 481
 482 private:
 483   friend struct array::HashTable<MixedArray, MixedArrayElm>;
 484   friend struct MemoryProfile;
 485   friend struct EmptyArray;
 486   friend struct PackedArray;
 487   friend struct RecordArray;
 488   friend struct HashCollection;
 489   friend struct BaseMap;
 490   friend struct c_Map;
 491   friend struct c_ImmMap;
 492   friend struct BaseSet;
 493   friend struct c_Set;
 494   friend struct c_ImmSet;
 495   friend struct c_AwaitAllWaitHandle;
 496
 497   friend size_t getMemSize(const ArrayData*, bool);
 498   template <typename AccessorT, class ArrayT>
 499   friend SortFlavor genericPreSort(ArrayT&, const AccessorT&, bool);
 500
 501 public:
 502   // Safe downcast helpers
 503   static MixedArray* asMixed(ArrayData* ad) {
 504     assertx(ad->hasVanillaMixedLayout());
 505     auto a = static_cast<MixedArray*>(ad);
 506     assertx(a->checkInvariants());
 507     return a;
 508   }
 509   static const MixedArray* asMixed(const ArrayData* ad) {
 510     assertx(ad->hasVanillaMixedLayout());
 511     auto a = static_cast<const MixedArray*>(ad);
 512     assertx(a->checkInvariants());
 513     return a;
 514   }
 515
 516   // Fast iteration
 517   template <class F, bool inc = true>
 518   static void IterateV(const MixedArray* arr, F fn) {
 519     assertx(arr->hasVanillaMixedLayout());
 520     auto elm = arr->data();
 521     if (inc) arr->incRefCount();
 522     SCOPE_EXIT { if (inc) decRefArr(const_cast<MixedArray*>(arr)); };
 523     for (auto i = arr->m_used; i--; elm++) {
 524       if (LIKELY(!elm->isTombstone())) {
 525         if (ArrayData::call_helper(fn, elm->data)) break;
 526       }
 527     }
 528   }
 529   template <class F, bool inc = true>
 530   static void IterateKV(const MixedArray* arr, F fn) {
 531     assertx(arr->hasVanillaMixedLayout());
 532     auto elm = arr->data();
 533     if (inc) arr->incRefCount();
 534     SCOPE_EXIT { if (inc) decRefArr(const_cast<MixedArray*>(arr)); };
 535     for (auto i = arr->m_used; i--; elm++) {
 536       if (LIKELY(!elm->isTombstone())) {
 537         TypedValue key;
 538         key.m_data.num = elm->ikey;
 539         key.m_type = elm->hasIntKey() ? KindOfInt64 : KindOfString;
 540         if (ArrayData::call_helper(fn, key, elm->data)) break;
 541       }
 542     }
 543   }
 544
 545 private:
 546   static TypedValue getElmKey(const Elm& e);
 547
 548 private:
 549   enum class AllocMode : bool { Request, Static };
 550
 551   static MixedArray* CopyMixed(const MixedArray& other, AllocMode,
 552                                HeaderKind, ArrayData::DVArray);
 553   static MixedArray* CopyReserve(const MixedArray* src, size_t expectedSize);
 554
 555   // Slow paths used for MixedArrays with references or counted string keys.
 556   // We fall back to SlowCopy and SlowGrow in the middle of iteration when we
 557   // encounter a reference, so we take an (elm, end) pair as arguments.
 558   static MixedArray* SlowCopy(MixedArray*, const ArrayData& old,
 559                               MixedArrayElm* elm, MixedArrayElm* end);
 560   static MixedArray* SlowGrow(MixedArray*, const ArrayData& old,
 561                               MixedArrayElm* elm, MixedArrayElm* end);
 562   static void SlowRelease(MixedArray*);
 563
 564   MixedArray() = delete;
 565   MixedArray(const MixedArray&) = delete;
 566   MixedArray& operator=(const MixedArray&) = delete;
 567   ~MixedArray() = delete;
 568
 569 private:
 570   // Copy elements as well as `m_nextKI' from one MixedArray to another.
 571   // Warning: it could copy up to 24 bytes beyond the array and thus overwrite
 572   // the hashtable, but it never reads/writes beyond the end of the hash
 573   // table.  If you use this function, make sure you copy/write the correct
 574   // data on the hash table afterwards.
 575   static void copyElmsNextUnsafe(MixedArray* to, const MixedArray* from,
 576                                  uint32_t nElems);
 577
 578   /*
 579    * Copy this from adIn, intish casting all the intish string keys in
 580    * accordance with the value of the intishCast template parameter
 581    */
 582   template <IntishCast IC>
 583   static ArrayData* copyWithIntishCast(MixedArray* adIn, bool asDArray = false);
 584
 585   template <typename AccessorT>
 586   SortFlavor preSort(const AccessorT& acc, bool checkTypes);
 587   void postSort(bool resetKeys);
 588
 589   static ArrayData* ArrayPlusEqGeneric(ArrayData*, MixedArray*,
 590                                        const ArrayData*, size_t);
 591   static ArrayData* ArrayMergeGeneric(MixedArray*, const ArrayData*);
 592
 593   // Assert a bunch of invariants about this array then return true.
 594   // usage:  assertx(checkInvariants());
 595   bool checkInvariants() const;
 596
 597 private:
 598   // The array should already be sized for the new insertion before
 599   // calling these methods.
 600   struct InsertPos {
 601     InsertPos(bool found, TypedValue& tv) : found(found), tv(tv) {}
 602     bool found;
 603     TypedValue& tv;
 604   };
 605   InsertPos insert(int64_t k);
 606   InsertPos insert(StringData* k);
 607
 608   using HashTable<MixedArray, MixedArrayElm>::findForRemove;
 609   int32_t findForRemove(int64_t ki, inthash_t h, bool updateNext);
 610   int32_t findForRemove(const StringData* s, strhash_t h);
 611
 612   static ArrayData* RemoveIntImpl(ArrayData*, int64_t, bool);
 613   static ArrayData* RemoveStrImpl(ArrayData*, const StringData*, bool);
 614   static ArrayData* AppendImpl(ArrayData*, TypedValue v, bool copy);
 615
 616   void nextInsert(TypedValue);
 617   ArrayData* addVal(int64_t ki, TypedValue data);
 618   ArrayData* addVal(StringData* key, TypedValue data);
 619   ArrayData* addValNoAsserts(StringData* key, TypedValue data);
 620
 621   template <bool warn, class K> arr_lval addLvalImpl(K k);
 622   // If "move" is false, this method will inc-ref data.
 623   template <class K, bool move = false> ArrayData* update(K k, TypedValue data);
 624
 625   void eraseNoCompact(ssize_t pos);
 626   void erase(ssize_t pos) {
 627     eraseNoCompact(pos);
 628     if (m_size <= m_used / 2) {
 629       // Compact in order to keep elms from being overly sparse.
 630       compact(false);
 631     }
 632   }
 633
 634   MixedArray* copyImpl(MixedArray* target) const;
 635
 636   bool hasIntishKeys() const;
 637
 638   MixedArray* moveVal(TypedValue& tv, TypedValue v);
 639
 640   /*
 641    * Helper routine for inserting elements into a new array
 642    * when Grow()ing the array, that also checks for potentially
 643    * unbalanced entries because of hash collision.
 644    */
 645   static MixedArray* InsertCheckUnbalanced(MixedArray* ad, int32_t* table,
 646                                            uint32_t mask,
 647                                            Elm* iter, Elm* stop);
 648   /*
 649    * Grow makes a copy of the array with scale = newScale. Grow rebuilds the
 650    * hash table, but it does not compact the elements. If copy is true, it
 651    * will copy elements instead of taking ownership of them.
 652    */
 653   static MixedArray* Grow(MixedArray* old, uint32_t newScale, bool copy);
 654
 655   /*
 656    * prepareForInsert ensures that the array has room to insert an element and
 657    * has a refcount of 1, copying if requested and growing if needed.
 658    */
 659   MixedArray* prepareForInsert(bool copy);
 660
 661   /**
 662    * compact() does not change the hash table size or the number of slots
 663    * for elements. compact() rebuilds the hash table and compacts the
 664    * elements into the slots with lower addresses.
 665    */
 666   void compact(bool renumber);
 667
 668   bool isZombie() const { return m_used + 1 == 0; }
 669   void setZombie() { m_used = -uint32_t{1}; }
 670
 671 public:
 672   void scan(type_scan::Scanner&) const; // in mixed-array-defs.h
 673
 674 private:
 675   struct Initializer;
 676   static Initializer s_initializer;
 677
 678   struct DArrayInitializer;
 679   static DArrayInitializer s_darr_initializer;
 680
 681   int64_t  m_nextKI;        // Next integer key to use for append.
 682 };
 683
 684 HASH_TABLE_CHECK_OFFSETS(MixedArray, MixedArrayElm)
 685 //////////////////////////////////////////////////////////////////////
 686
 687 }
 688
 689 #endif // incl_HPHP_HPHP_ARRAY_H_