hphp/runtime/base/packed-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 #ifndef incl_HPHP_PACKED_ARRAY_H_
  17 #define incl_HPHP_PACKED_ARRAY_H_
  18
  19 #include <cstddef>
  20 #include <cstdint>
  21 #include <sys/types.h>
  22
  23 #include "hphp/runtime/base/array-common.h"
  24 #include "hphp/runtime/base/array-data.h"
  25 #include "hphp/runtime/base/data-walker.h"
  26 #include "hphp/runtime/base/header-kind.h"
  27 #include "hphp/runtime/base/tv-val.h"
  28 #include "hphp/runtime/base/sort-flags.h"
  29 #include "hphp/runtime/base/typed-value.h"
  30
  31 #include "hphp/util/type-scan.h"
  32
  33 namespace HPHP {
  34
  35 //////////////////////////////////////////////////////////////////////
  36
  37 struct Variant;
  38 struct ArrayData;
  39 struct StringData;
  40 struct MixedArray;
  41 struct APCArray;
  42 struct APCHandle;
  43
  44 //////////////////////////////////////////////////////////////////////
  45
  46 /*
  47  * Packed arrays are a specialized array layout for vector-like data.  That is,
  48  * php arrays with zero-based contiguous integer keys, and values of mixed
  49  * types.  The TypedValues are placed right after the array header.
  50  */
  51 struct PackedArray final : type_scan::MarkCollectable<PackedArray> {
  52   static constexpr uint32_t SmallSize = 3;
  53   // the smallest and largest MM size classes we use for allocating PackedArrays
  54   static constexpr size_t SmallSizeIndex = 3;
  55   static constexpr size_t MaxSizeIndex = 121;
  56
  57   // Used in static_asserts near code that will have to change if/when we
  58   // disaggregate the TypedValues in PackedArray.
  59   static constexpr bool stores_typed_values = true;
  60
  61   static_assert(MaxSizeIndex <= std::numeric_limits<uint8_t>::max(),
  62                 "Size index must fit into 8-bits");
  63
  64   static void Release(ArrayData*);
  65   static void ReleaseUncounted(ArrayData*);
  66   static TypedValue NvGetInt(const ArrayData*, int64_t ki);
  67   static TypedValue NvGetStr(const ArrayData*, const StringData*);
  68   static ssize_t NvGetIntPos(const ArrayData*, int64_t k);
  69   static ssize_t NvGetStrPos(const ArrayData*, const StringData* k);
  70   static TypedValue GetPosKey(const ArrayData*, ssize_t pos);
  71   static TypedValue GetPosVal(const ArrayData*, ssize_t pos);
  72   static ArrayData* SetInt(ArrayData*, int64_t k, TypedValue v);
  73   static ArrayData* SetIntMove(ArrayData*, int64_t k, TypedValue v);
  74   static ArrayData* SetStr(ArrayData*, StringData* k, TypedValue v);
  75   static constexpr auto SetStrMove = &SetStr;
  76   static bool IsVectorData(const ArrayData*) { return true; }
  77   static bool ExistsInt(const ArrayData* ad, int64_t k);
  78   static bool ExistsStr(const ArrayData*, const StringData*);
  79   static arr_lval LvalInt(ArrayData*, int64_t k);
  80   static arr_lval LvalStr(ArrayData*, StringData* k);
  81   static ArrayData* RemoveInt(ArrayData*, int64_t k);
  82   static ArrayData* RemoveStr(ArrayData*, const StringData* k);
  83   static ssize_t IterBegin(const ArrayData*);
  84   static ssize_t IterLast(const ArrayData*);
  85   static ssize_t IterEnd(const ArrayData*);
  86   static ssize_t IterAdvance(const ArrayData*, ssize_t pos);
  87   static ssize_t IterRewind(const ArrayData*, ssize_t pos);
  88   static ArrayData* Copy(const ArrayData* ad);
  89   static ArrayData* CopyStatic(const ArrayData*);
  90   static ArrayData* EscalateForSort(ArrayData*, SortFunction);
  91   static void Ksort(ArrayData*, int, bool);
  92   static void Sort(ArrayData*, int, bool);
  93   static void Asort(ArrayData*, int, bool);
  94   static bool Uksort(ArrayData*, const Variant&);
  95   static bool Usort(ArrayData*, const Variant&);
  96   static bool Uasort(ArrayData*, const Variant&);
  97   static ArrayData* Append(ArrayData*, TypedValue v);
  98   static ArrayData* AppendMove(ArrayData*, TypedValue v);
  99   static ArrayData* Merge(ArrayData*, const ArrayData* elems);
 100   static ArrayData* Pop(ArrayData*, Variant& value);
 101   static ArrayData* Dequeue(ArrayData*, Variant& value);
 102   static ArrayData* Prepend(ArrayData*, TypedValue v);
 103   static ArrayData* ToVArray(ArrayData*, bool);
 104   static ArrayData* ToDArray(ArrayData*, bool);
 105   static ArrayData* ToDict(ArrayData*, bool);
 106   static ArrayData* ToVec(ArrayData*, bool);
 107   static ArrayData* Renumber(ArrayData* ad) { return ad; }
 108   static void OnSetEvalScalar(ArrayData*);
 109   static constexpr auto ToKeyset = &ArrayCommon::ToKeyset;
 110
 111   //////////////////////////////////////////////////////////////////////
 112
 113   // Layout-specific helpers that work on PHP and Hack packed arrays.
 114   // We use these helpers in ArrayInit and a few other hot sites where
 115   // we can guarantee the layout of the array.
 116
 117   // Exactly like Append, except that it skips the COW check. May grow.
 118   //  @precondition: !cowCheck
 119   static ArrayData* AppendInPlace(ArrayData*, TypedValue v);
 120
 121   // Exactly like LvalInt, except that it skips the bounds check.
 122   //  @precondition: 0 <= i && i < size
 123   static tv_lval LvalUncheckedInt(ArrayData*, int64_t i);
 124
 125   // Appends a new null element and returns an lval to it.
 126   //  @precondition: !cowCheck
 127   //  @precondition: size < capacity
 128   static tv_lval LvalNewInPlace(ArrayData*);
 129
 130   /////////////////////////////////////////////////////////////////////
 131
 132   static bool checkInvariants(const ArrayData*);
 133
 134   static ptrdiff_t entriesOffset();
 135
 136   static uint32_t capacity(const ArrayData*);
 137   static size_t heapSize(const ArrayData*);
 138   static uint16_t packSizeIndexAndAuxBits(uint8_t, uint8_t);
 139
 140   static void scan(const ArrayData*, type_scan::Scanner&);
 141
 142   static ArrayData* MakeReserveVArray(uint32_t capacity);
 143   static ArrayData* MakeReserveVec(uint32_t capacity);
 144
 145   /*
 146    * Allocate a PackedArray containing `size' values, in the reverse order of
 147    * the `values' array. This can only be used to populate the array with cells,
 148    * not refs.
 149    *
 150    * This function takes ownership of the Cells in `values'.
 151    */
 152   static ArrayData* MakeVArray(uint32_t size, const TypedValue* values);
 153   static ArrayData* MakeVec(uint32_t size, const TypedValue* values);
 154
 155   /*
 156    * Like MakePacked, but with `values' array in natural (not reversed) order.
 157    */
 158   static ArrayData* MakeVArrayNatural(uint32_t size, const TypedValue* values);
 159   static ArrayData* MakeVecNatural(uint32_t size, const TypedValue* values);
 160
 161   static ArrayData* MakeUninitializedVArray(uint32_t size);
 162   static ArrayData* MakeUninitializedVec(uint32_t size);
 163
 164   static ArrayData* MakeUncounted(
 165       ArrayData* array, bool withApcTypedValue = false,
 166       DataWalker::PointerMap* seen = nullptr
 167   );
 168   static ArrayData* MakeUncounted(
 169       ArrayData* array, int, DataWalker::PointerMap* seen = nullptr
 170   ) = delete;
 171   static ArrayData* MakeUncounted(
 172       ArrayData* array, size_t extra, DataWalker::PointerMap* seen = nullptr
 173   ) = delete;
 174   static ArrayData* MakeUncountedHelper(ArrayData* array, size_t extra);
 175
 176   static ArrayData* MakeVecFromAPC(const APCArray* apc, bool isLegacy = false);
 177   static ArrayData* MakeVArrayFromAPC(const APCArray* apc,
 178                                       bool isMarked = false);
 179
 180   static bool VecEqual(const ArrayData* ad1, const ArrayData* ad2);
 181   static bool VecNotEqual(const ArrayData* ad1, const ArrayData* ad2);
 182   static bool VecSame(const ArrayData* ad1, const ArrayData* ad2);
 183   static bool VecNotSame(const ArrayData* ad1, const ArrayData* ad2);
 184
 185   // Fast iteration
 186   template <class F, bool inc = true>
 187   static void IterateV(const ArrayData* arr, F fn);
 188   template <class F, bool inc = true>
 189   static void IterateKV(const ArrayData* arr, F fn);
 190   template <class F>
 191   static void IterateVNoInc(const ArrayData* arr, F fn);
 192
 193   // Return a MixedArray with the same elements as this PackedArray.
 194   // The target type is based on the source: varray -> darray, vec -> dict.
 195   static MixedArray* ToMixed(ArrayData*);
 196   static MixedArray* ToMixedCopy(const ArrayData*);
 197   static MixedArray* ToMixedCopyReserve(const ArrayData*, size_t);
 198
 199   static size_t capacityToSizeIndex(size_t);
 200
 201   static constexpr auto SizeIndexOffset = HeaderAuxOffset + 1;
 202 private:
 203   static uint8_t sizeClass(const ArrayData*);
 204
 205   static MixedArray* ToMixedHeader(const ArrayData*, size_t);
 206
 207   static ArrayData* Grow(ArrayData*, bool);
 208   static ArrayData* PrepareForInsert(ArrayData*, bool);
 209   static SortFlavor preSort(ArrayData*);
 210
 211   static ArrayData* MakeReserveImpl(uint32_t, HeaderKind);
 212
 213   template<bool reverse>
 214   static ArrayData* MakePackedImpl(uint32_t, const TypedValue*, HeaderKind);
 215
 216   static void CopyPackedHelper(const ArrayData* adIn, ArrayData* ad);
 217
 218   static bool VecEqualHelper(const ArrayData*, const ArrayData*, bool);
 219   static int64_t VecCmpHelper(const ArrayData*, const ArrayData*);
 220
 221   // By default, this method will inc-ref the value being inserted. If move is
 222   // true, no refcounting operations will be performed.
 223   static ArrayData* AppendImpl(ArrayData*, TypedValue v, bool copy,
 224                                bool move = false);
 225
 226   struct VecInitializer;
 227   static VecInitializer s_vec_initializer;
 228
 229   struct VArrayInitializer;
 230   static VArrayInitializer s_varr_initializer;
 231
 232   struct MarkedVecInitializer;
 233   static MarkedVecInitializer s_marked_vec_initializer;
 234
 235   struct MarkedVArrayInitializer;
 236   static MarkedVArrayInitializer s_marked_varr_initializer;
 237 };
 238
 239 //////////////////////////////////////////////////////////////////////
 240
 241 }
 242
 243 #endif