hphp/runtime/base/set-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_SET_ARRAY_H_
  18 #define incl_HPHP_SET_ARRAY_H_
  19
  20 #include "hphp/runtime/base/array-data.h"
  21 #include "hphp/runtime/base/array-common.h"
  22 #include "hphp/runtime/base/data-walker.h"
  23 #include "hphp/runtime/base/hash-table.h"
  24 #include "hphp/runtime/base/tv-val.h"
  25 #include "hphp/runtime/base/string-data.h"
  26 #include "hphp/runtime/base/tv-mutate.h"
  27 #include "hphp/runtime/base/typed-value.h"
  28
  29 #include <folly/portability/Constexpr.h>
  30
  31 namespace HPHP {
  32
  33 //////////////////////////////////////////////////////////////////////
  34
  35 namespace jit {
  36 struct ArrayAccessProfile;
  37 }
  38 struct APCArray;
  39 struct APCHandle;
  40
  41 struct SetArrayElm {
  42   using hash_t = strhash_t;
  43   /*
  44    * We store elements of the set here, but also some information
  45    * local to this array: tv.m_aux.u_hash contains either a negative
  46    * number (for an int key) or a string hashcode (31-bit and thus
  47    * non-negative).  The field tv.m_type == kInvalidDataType is used
  48    * to mark a deleted element (tombstone); tv.m_type == KindOfUninit
  49    * is used for debugging to mark empty elements.
  50    */
  51   TypedValueAux tv;
  52
  53   static auto constexpr kTombstone = kInvalidDataType;
  54   static auto constexpr kEmpty = KindOfUninit;
  55
  56   void setStrKey(StringData* k, strhash_t h) {
  57     assertx(isEmpty());
  58     k->incRefCount();
  59     tv.m_type = KindOfString;
  60     tv.m_data.pstr = k;
  61     tv.hash() = h;
  62     assertx(!isInvalid());
  63   }
  64
  65   void setIntKey(int64_t k, inthash_t h) {
  66     assertx(isEmpty());
  67     tv.m_type = KindOfInt64;
  68     tv.m_data.num = k;
  69     tv.hash() = h | STRHASH_MSB;
  70     assertx(!isInvalid());
  71     assertx(hasIntKey());
  72   }
  73
  74   void setTombstone() {
  75     tv.m_type = kTombstone;
  76     static_assert(!isRefcountedType(kTombstone), "");
  77   }
  78
  79   bool isEmpty() const {
  80     return tv.m_type == kEmpty;
  81   }
  82
  83   // Members below here are required for HashTable implemenation.
  84   ALWAYS_INLINE const TypedValue* datatv() const {
  85     return &tv;
  86   }
  87
  88   ALWAYS_INLINE bool hasStrKey() const {
  89     /*
  90      * Currently string hash is 31-bit, thus it saves us some
  91      * instructions to encode int keys as a negative hash, so
  92      * that we don't have to care about the MSB when working
  93      * with strhash_t.
  94      */
  95     assertx(!isInvalid());
  96     return tv.hash() >= 0;
  97   }
  98
  99   ALWAYS_INLINE StringData* strKey() const {
 100     assertx(hasStrKey());
 101     return tv.m_data.pstr;
 102   }
 103
 104   ALWAYS_INLINE bool hasIntKey() const {
 105     assertx(!isInvalid());
 106     return tv.hash() < 0;
 107   }
 108
 109   ALWAYS_INLINE int64_t intKey() const {
 110     return tv.m_data.num;
 111   }
 112
 113   ALWAYS_INLINE TypedValue getKey() const {
 114     assertx(!isInvalid());
 115     return tv;
 116   }
 117
 118   ALWAYS_INLINE hash_t hash() const {
 119     return tv.hash();
 120   }
 121
 122   ALWAYS_INLINE bool isTombstone() const {
 123     return tv.m_type == kTombstone;
 124   }
 125
 126   ALWAYS_INLINE bool isInvalid() const {
 127     return tv.m_type == kEmpty || isTombstone();
 128   }
 129
 130   static constexpr ptrdiff_t keyOff() {
 131     return offsetof(SetArrayElm, tv) + offsetof(TypedValue, m_data.pstr);
 132   }
 133   static constexpr ptrdiff_t dataOff() {
 134     return offsetof(SetArrayElm, tv) + offsetof(TypedValue, m_data);
 135   }
 136   static constexpr ptrdiff_t typeOff() {
 137     return offsetof(SetArrayElm, tv) + offsetof(TypedValue, m_type);
 138   }
 139   static constexpr ptrdiff_t hashOff() {
 140     return offsetof(SetArrayElm, tv) + offsetof(TypedValue, m_aux);
 141   }
 142 };
 143
 144 //////////////////////////////////////////////////////////////////////
 145
 146 struct SetArray final : ArrayData,
 147                         array::HashTable<SetArray, SetArrayElm>,
 148                         type_scan::MarkCollectable<SetArray> {
 149
 150 //////////////////////////////////////////////////////////////////////
 151 // Set Layout
 152
 153 public:
 154   void scan(type_scan::Scanner& scanner) const {
 155     auto const elms = data();
 156     scanner.scan(*elms, m_used * sizeof(*elms));
 157   }
 158
 159 //////////////////////////////////////////////////////////////////////
 160 // Initialization, Copies, and Conversions
 161
 162 public:
 163   /*
 164    * Allocate a new, empty, request-local set array, with enough space
 165    * reserved for `size' members.
 166    *
 167    * The returned array is already incref'd.
 168    */
 169   static ArrayData* MakeReserveSet(uint32_t size);
 170   static constexpr auto MakeReserve = &MakeReserveSet;
 171
 172   static ArrayData* MakeSet(uint32_t size, const TypedValue* values);
 173
 174   /*
 175    * Allocate an uncounted SetArray and copy the values from the
 176    * input 'array' into the uncounted one.
 177    *
 178    * If withApcTypedValue is true, space for an APCTypedValue will be
 179    * allocated in front of the returned pointer.
 180    */
 181   static ArrayData* MakeUncounted(ArrayData* array,
 182                                   bool withApcTypedValue = false,
 183                                   DataWalker::PointerMap* m = nullptr);
 184   static ArrayData* MakeUncounted(ArrayData* array, int) = delete;
 185   static ArrayData* MakeUncounted(ArrayData* array, size_t) = delete;
 186
 187   static void Release(ArrayData*);
 188   static void ReleaseUncounted(ArrayData*);
 189   /*
 190    * Recursively register {allocation, rootAPCHandle} with APCGCManager
 191    */
 192   static void RegisterUncountedAllocations(ArrayData* ad,
 193                                            APCHandle* rootAPCHandle);
 194
 195   /*
 196    * Safe downcast helpers.
 197    */
 198   static SetArray* asSet(ArrayData* ad);
 199   static const SetArray* asSet(const ArrayData* ad);
 200
 201   static ArrayData* MakeSetFromAPC(const APCArray*);
 202
 203   /*
 204    * For array initialization using KeysetInit.
 205    */
 206   static ArrayData* AddToSet(ArrayData*, int64_t);
 207   static ArrayData* AddToSetInPlace(ArrayData*, int64_t);
 208   static ArrayData* AddToSet(ArrayData*, StringData*);
 209   static ArrayData* AddToSetInPlace(ArrayData*, StringData*);
 210
 211 private:
 212   static bool ClearElms(Elm* elms, uint32_t count);
 213
 214   enum class AllocMode : bool { Request, Static };
 215
 216   static SetArray* CopySet(const SetArray& other, AllocMode);
 217   SetArray* copySet() const { return CopySet(*this, AllocMode::Request); }
 218
 219   template <typename Init, IntishCast IC>
 220   static ArrayData* ToArrayImpl(ArrayData*, bool);
 221
 222 private:
 223   SetArray() = delete;
 224   SetArray(const SetArray&) = delete;
 225   SetArray& operator=(const SetArray&) = delete;
 226   ~SetArray() = delete;
 227
 228 //////////////////////////////////////////////////////////////////////
 229 // Iteration
 230
 231 private:
 232   TypedValue getElm(ssize_t ei) const;
 233
 234 public:
 235   const TypedValue* tvOfPos(uint32_t) const;
 236
 237   template <class F, bool inc = true>
 238   static void Iterate(const SetArray* a, F fn) {
 239     if (inc) a->incRefCount();
 240     SCOPE_EXIT { if (inc) decRefArr(const_cast<SetArray*>(a)); };
 241     auto const* elm = a->data();
 242     for (auto i = a->m_used; i--; elm++) {
 243       if (LIKELY(!elm->isTombstone())) {
 244         if (ArrayData::call_helper(fn, elm->tv)) break;
 245       }
 246     }
 247   }
 248
 249 //////////////////////////////////////////////////////////////////////
 250 // Sorting
 251
 252 public:
 253   static ArrayData* EscalateForSort(ArrayData* ad, SortFunction);
 254
 255   static void Sort(ArrayData*, int, bool);
 256   static void Ksort(ArrayData*, int, bool);
 257   static constexpr auto Asort = &Ksort;
 258
 259   static bool Usort(ArrayData*, const Variant&);
 260   static bool Uksort(ArrayData*, const Variant&);
 261   static constexpr auto Uasort = &Uksort;
 262
 263 private:
 264   template <typename AccessorT>
 265   SortFlavor preSort(const AccessorT& acc, bool checkTypes);
 266   void postSort(bool);
 267
 268 //////////////////////////////////////////////////////////////////////
 269 // Set Internals
 270
 271 private:
 272   bool checkInvariants() const;
 273
 274   /*
 275    * These functions require !isFull().  The index of the position
 276    * where the element was inserted is returned.
 277    */
 278   void insert(int64_t k, inthash_t h);
 279   void insert(int64_t k);
 280   void insert(StringData* k, strhash_t h);
 281   void insert(StringData* k);
 282
 283   ssize_t findElm(const Elm& e) const;
 284
 285   void erase(int32_t);
 286
 287   /*
 288    * Append idx at the end of the linked list containing the set
 289    * insertion order.
 290    */
 291   void linkLast(uint32_t idx);
 292
 293   /*
 294    * Helper routine for inserting elements into a new array
 295    * when grow()ing the array, that also checks for potentially
 296    * unbalanced entries because of hash collision.
 297    */
 298   SetArray* insertCheckUnbalanced(SetArray* ad, Elm* table,
 299                                   uint32_t mask,
 300                                   Elm* iter, Elm* stop);
 301
 302
 303   /*
 304    * Returns a copy of the set with twice the scale of the original. It
 305    * rebuilds the hash table, but it does not compact the elements. If copy is
 306    * true, it will copy elements instead of taking ownership of them.
 307    */
 308   SetArray* grow(bool copy);
 309
 310   /*
 311    * prepareForInsert ensures that the set has room to insert an element and
 312    * has a refcount of 1, copying if requested and growing if needed.
 313    */
 314   SetArray* prepareForInsert(bool copy);
 315
 316   /*
 317    * compact() removes all tombstones from the hash table by going
 318    * through the inner linked list.
 319    */
 320   void compact();
 321
 322   /*
 323    * Zombie arrays!
 324    */
 325   bool isZombie() const { return m_used + 1 == 0; }
 326   void setZombie() { m_used = -uint32_t{1}; }
 327
 328   /*
 329    * Comparison helper.
 330    */
 331   static bool EqualHelper(const ArrayData*, const ArrayData*, bool);
 332
 333 //////////////////////////////////////////////////////////////////////
 334 // Elements
 335
 336 public:
 337
 338 //////////////////////////////////////////////////////////////////////
 339 // JIT Supporting Routines
 340
 341   static constexpr ptrdiff_t tvOff(uint32_t pos) {
 342     return dataOff() + pos * sizeof(Elm) + offsetof(Elm, tv);
 343   }
 344
 345 //////////////////////////////////////////////////////////////////////
 346 // Reference Counting
 347
 348 public:
 349   using ArrayData::decRefCount;
 350   using ArrayData::hasMultipleRefs;
 351   using ArrayData::hasExactlyOneRef;
 352   using ArrayData::decWillRelease;
 353   using ArrayData::incRefCount;
 354
 355 //////////////////////////////////////////////////////////////////////
 356 // Misc ArrayData Methods
 357
 358   /*
 359    * These using directives ensure the full set of overloaded functions
 360    * are visible in this class, to avoid triggering implicit conversions
 361    * from a const Variant& key to int64.
 362    */
 363 private:
 364   using ArrayData::exists;
 365   using ArrayData::at;
 366   using ArrayData::rval;
 367   using ArrayData::lval;
 368   using ArrayData::set;
 369   using ArrayData::remove;
 370   using ArrayData::release;
 371
 372 //////////////////////////////////////////////////////////////////////
 373 // Friends
 374
 375 private:
 376   friend struct array::HashTable<SetArray, SetArrayElm>;
 377   friend struct MemoryProfile;
 378   friend struct jit::ArrayAccessProfile;
 379   friend struct EmptyArray;
 380   friend struct PackedArray;
 381   friend struct StructArray;
 382   friend struct MixedArray;
 383   friend struct HashCollection;
 384   friend struct BaseMap;
 385   friend struct c_Map;
 386   friend struct c_ImmMap;
 387   friend struct BaseSet;
 388   friend struct c_Set;
 389   friend struct c_ImmSet;
 390   friend struct c_AwaitAllWaitHandle;
 391
 392   friend size_t getMemSize(const ArrayData*, bool);
 393   template <typename AccessorT, class ArrayT>
 394   friend SortFlavor genericPreSort(ArrayT&, const AccessorT&, bool);
 395
 396 //////////////////////////////////////////////////////////////////////
 397 // ArrayData API
 398
 399 public:
 400   static size_t Vsize(const ArrayData*);
 401   static TypedValue GetPosVal(const ArrayData*, ssize_t);
 402   static bool IsVectorData(const ArrayData*);
 403   static bool ExistsInt(const ArrayData*, int64_t);
 404   static bool ExistsStr(const ArrayData*, const StringData*);
 405   static arr_lval LvalInt(ArrayData*, int64_t, bool);
 406   static arr_lval LvalStr(ArrayData*, StringData*, bool);
 407   static ArrayData* SetInt(ArrayData*, int64_t, TypedValue);
 408   static constexpr auto SetIntMove = &SetInt;
 409   static ArrayData* SetStr(ArrayData*, StringData*, TypedValue);
 410   static constexpr auto SetStrMove = &SetStr;
 411   static ArrayData* RemoveInt(ArrayData*, int64_t);
 412   static ArrayData* RemoveStr(ArrayData*, const StringData*);
 413   static ArrayData* Copy(const ArrayData*);
 414   static ArrayData* CopyStatic(const ArrayData*);
 415   static ArrayData* Append(ArrayData*, TypedValue);
 416   static ArrayData* PlusEq(ArrayData*, const ArrayData*);
 417   static ArrayData* Merge(ArrayData*, const ArrayData*);
 418   static ArrayData* Pop(ArrayData*, Variant&);
 419   static ArrayData* Dequeue(ArrayData*, Variant&);
 420   static ArrayData* Prepend(ArrayData*, TypedValue);
 421   static void Renumber(ArrayData*);
 422   static void OnSetEvalScalar(ArrayData*);
 423   static constexpr auto ToDict = &ArrayCommon::ToDict;
 424   static constexpr auto ToVec = &ArrayCommon::ToVec;
 425   static ArrayData* ToPHPArray(ArrayData*, bool);
 426   static ArrayData* ToPHPArrayIntishCast(ArrayData*, bool);
 427   static ArrayData* ToKeyset(ArrayData*, bool);
 428   static constexpr auto ToVArray = &ArrayCommon::ToVArray;
 429   static ArrayData* ToDArray(ArrayData*, bool);
 430   static bool Equal(const ArrayData*, const ArrayData*);
 431   static bool NotEqual(const ArrayData*, const ArrayData*);
 432   static bool Same(const ArrayData*, const ArrayData*);
 433   static bool NotSame(const ArrayData*, const ArrayData*);
 434
 435 //////////////////////////////////////////////////////////////////////
 436
 437 private:
 438   template<class K>
 439   static ArrayData* RemoveImpl(ArrayData*, K key, bool, SetArrayElm::hash_t);
 440   static ArrayData* AppendImpl(ArrayData*, TypedValue, bool);
 441
 442 private:
 443   struct Initializer;
 444   static Initializer s_initializer;
 445
 446   uint64_t m_padding;
 447 };
 448
 449 HASH_TABLE_CHECK_OFFSETS(SetArray, SetArrayElm)
 450 //////////////////////////////////////////////////////////////////////
 451
 452 }
 453
 454 #endif // incl_HPHP_SET_ARRAY_H_