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   /*
 191    * Safe downcast helpers.
 192    */
 193   static SetArray* asSet(ArrayData* ad);
 194   static const SetArray* asSet(const ArrayData* ad);
 195
 196   static ArrayData* MakeSetFromAPC(const APCArray*);
 197
 198   /*
 199    * For array initialization using KeysetInit.
 200    */
 201   static ArrayData* AddToSet(ArrayData*, int64_t);
 202   static ArrayData* AddToSetInPlace(ArrayData*, int64_t);
 203   static ArrayData* AddToSet(ArrayData*, StringData*);
 204   static ArrayData* AddToSetInPlace(ArrayData*, StringData*);
 205
 206 private:
 207   static bool ClearElms(Elm* elms, uint32_t count);
 208
 209   enum class AllocMode : bool { Request, Static };
 210
 211   static SetArray* CopySet(const SetArray& other, AllocMode);
 212   SetArray* copySet() const { return CopySet(*this, AllocMode::Request); }
 213
 214   static ArrayData* ToDArrayImpl(const SetArray*);
 215
 216 private:
 217   SetArray() = delete;
 218   SetArray(const SetArray&) = delete;
 219   SetArray& operator=(const SetArray&) = delete;
 220   ~SetArray() = delete;
 221
 222 //////////////////////////////////////////////////////////////////////
 223 // Iteration
 224
 225 private:
 226   TypedValue getElm(ssize_t ei) const;
 227
 228 public:
 229   const TypedValue* tvOfPos(uint32_t) const;
 230
 231   template <class F, bool inc = true>
 232   static void Iterate(const SetArray* a, F fn) {
 233     if (inc) a->incRefCount();
 234     SCOPE_EXIT { if (inc) decRefArr(const_cast<SetArray*>(a)); };
 235     auto const* elm = a->data();
 236     for (auto i = a->m_used; i--; elm++) {
 237       if (LIKELY(!elm->isTombstone())) {
 238         if (ArrayData::call_helper(fn, elm->tv)) break;
 239       }
 240     }
 241   }
 242
 243 //////////////////////////////////////////////////////////////////////
 244 // Sorting
 245
 246 public:
 247   static ArrayData* EscalateForSort(ArrayData* ad, SortFunction);
 248
 249   static void Sort(ArrayData*, int, bool);
 250   static void Ksort(ArrayData*, int, bool);
 251   static constexpr auto Asort = &Ksort;
 252
 253   static bool Usort(ArrayData*, const Variant&);
 254   static bool Uksort(ArrayData*, const Variant&);
 255   static constexpr auto Uasort = &Uksort;
 256
 257 private:
 258   template <typename AccessorT>
 259   SortFlavor preSort(const AccessorT& acc, bool checkTypes);
 260   void postSort(bool);
 261
 262 //////////////////////////////////////////////////////////////////////
 263 // Set Internals
 264
 265 private:
 266   bool checkInvariants() const;
 267
 268   /*
 269    * These functions require !isFull().  The index of the position
 270    * where the element was inserted is returned.
 271    */
 272   void insert(int64_t k, inthash_t h);
 273   void insert(int64_t k);
 274   void insert(StringData* k, strhash_t h);
 275   void insert(StringData* k);
 276
 277   ssize_t findElm(const Elm& e) const;
 278
 279   void erase(RemovePos);
 280
 281   /*
 282    * Append idx at the end of the linked list containing the set
 283    * insertion order.
 284    */
 285   void linkLast(uint32_t idx);
 286
 287   /*
 288    * Helper routine for inserting elements into a new array
 289    * when grow()ing the array, that also checks for potentially
 290    * unbalanced entries because of hash collision.
 291    */
 292   SetArray* insertCheckUnbalanced(SetArray* ad, Elm* table,
 293                                   uint32_t mask,
 294                                   Elm* iter, Elm* stop);
 295
 296
 297   /*
 298    * Returns a copy of the set with twice the scale of the original. It
 299    * rebuilds the hash table, but it does not compact the elements. If copy is
 300    * true, it will copy elements instead of taking ownership of them.
 301    */
 302   SetArray* grow(bool copy);
 303
 304   /*
 305    * prepareForInsert ensures that the set has room to insert an element and
 306    * has a refcount of 1, copying if requested and growing if needed.
 307    */
 308   SetArray* prepareForInsert(bool copy);
 309
 310   /*
 311    * compact() removes all tombstones from the hash table by going
 312    * through the inner linked list.
 313    */
 314   void compact();
 315
 316   /*
 317    * Zombie arrays!
 318    */
 319   bool isZombie() const { return m_used + 1 == 0; }
 320   void setZombie() { m_used = -uint32_t{1}; }
 321
 322   /*
 323    * Comparison helper.
 324    */
 325   static bool EqualHelper(const ArrayData*, const ArrayData*, bool);
 326
 327 //////////////////////////////////////////////////////////////////////
 328 // Elements
 329
 330 public:
 331
 332 //////////////////////////////////////////////////////////////////////
 333 // JIT Supporting Routines
 334
 335   static constexpr ptrdiff_t tvOff() {
 336     return offsetof(Elm, tv);
 337   }
 338
 339 //////////////////////////////////////////////////////////////////////
 340 // Reference Counting
 341
 342 public:
 343   using ArrayData::decRefCount;
 344   using ArrayData::hasMultipleRefs;
 345   using ArrayData::hasExactlyOneRef;
 346   using ArrayData::decWillRelease;
 347   using ArrayData::incRefCount;
 348
 349 //////////////////////////////////////////////////////////////////////
 350 // Misc ArrayData Methods
 351
 352   /*
 353    * These using directives ensure the full set of overloaded functions
 354    * are visible in this class, to avoid triggering implicit conversions
 355    * from a const Variant& key to int64.
 356    */
 357 private:
 358   using ArrayData::exists;
 359   using ArrayData::at;
 360   using ArrayData::lval;
 361   using ArrayData::set;
 362   using ArrayData::remove;
 363   using ArrayData::release;
 364
 365 //////////////////////////////////////////////////////////////////////
 366 // Friends
 367
 368 private:
 369   friend struct array::HashTable<SetArray, SetArrayElm>;
 370   friend struct MemoryProfile;
 371   friend struct jit::ArrayAccessProfile;
 372   friend struct PackedArray;
 373   friend struct MixedArray;
 374   friend struct HashCollection;
 375   friend struct BaseMap;
 376   friend struct c_Map;
 377   friend struct c_ImmMap;
 378   friend struct BaseSet;
 379   friend struct c_Set;
 380   friend struct c_ImmSet;
 381   friend struct c_AwaitAllWaitHandle;
 382
 383   friend size_t getMemSize(const ArrayData*, bool);
 384   template <typename AccessorT, class ArrayT>
 385   friend SortFlavor genericPreSort(ArrayT&, const AccessorT&, bool);
 386
 387 //////////////////////////////////////////////////////////////////////
 388 // ArrayData API
 389
 390 public:
 391   static TypedValue GetPosVal(const ArrayData*, ssize_t);
 392   static bool IsVectorData(const ArrayData*);
 393   static bool ExistsInt(const ArrayData*, int64_t);
 394   static bool ExistsStr(const ArrayData*, const StringData*);
 395   static arr_lval LvalInt(ArrayData*, int64_t);
 396   static arr_lval LvalStr(ArrayData*, StringData*);
 397   static ArrayData* SetInt(ArrayData*, int64_t, TypedValue);
 398   static constexpr auto SetIntMove = &SetInt;
 399   static ArrayData* SetStr(ArrayData*, StringData*, TypedValue);
 400   static constexpr auto SetStrMove = &SetStr;
 401   static ArrayData* RemoveInt(ArrayData*, int64_t);
 402   static ArrayData* RemoveStr(ArrayData*, const StringData*);
 403   static ArrayData* Copy(const ArrayData*);
 404   static ArrayData* CopyStatic(const ArrayData*);
 405   static ArrayData* Append(ArrayData*, TypedValue);
 406   static ArrayData* Merge(ArrayData*, const ArrayData*);
 407   static ArrayData* Pop(ArrayData*, Variant&);
 408   static ArrayData* Dequeue(ArrayData*, Variant&);
 409   static ArrayData* Prepend(ArrayData*, TypedValue);
 410   static ArrayData* Renumber(ArrayData*);
 411   static void OnSetEvalScalar(ArrayData*);
 412   static constexpr auto ToDict = &ArrayCommon::ToDict;
 413   static constexpr auto ToVec = &ArrayCommon::ToVec;
 414   static ArrayData* ToKeyset(ArrayData*, bool);
 415   static constexpr auto ToVArray = &ArrayCommon::ToVArray;
 416   static ArrayData* ToDArray(ArrayData*, bool);
 417   static bool Equal(const ArrayData*, const ArrayData*);
 418   static bool NotEqual(const ArrayData*, const ArrayData*);
 419   static bool Same(const ArrayData*, const ArrayData*);
 420   static bool NotSame(const ArrayData*, const ArrayData*);
 421
 422 //////////////////////////////////////////////////////////////////////
 423
 424 private:
 425   template<class K>
 426   static ArrayData* RemoveImpl(ArrayData*, K key, bool, SetArrayElm::hash_t);
 427   static ArrayData* AppendImpl(ArrayData*, TypedValue, bool);
 428
 429 private:
 430   struct Initializer;
 431   static Initializer s_initializer;
 432
 433   uint64_t m_padding;
 434 };
 435
 436 HASH_TABLE_CHECK_OFFSETS(SetArray, SetArrayElm)
 437 //////////////////////////////////////////////////////////////////////
 438
 439 }
 440
 441 #endif // incl_HPHP_SET_ARRAY_H_