hphp/runtime/base/array/hphp_array.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010- 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/types.h"
  21 #include "hphp/runtime/base/array/array_data.h"
  22 #include "hphp/runtime/base/memory/smart_allocator.h"
  23 #include "hphp/runtime/base/complex_types.h"
  24
  25 namespace HPHP {
  26 ///////////////////////////////////////////////////////////////////////////////
  27
  28 class ArrayInit;
  29
  30 class HphpArray : public ArrayData {
  31   enum CopyMode { kSmartCopy, kNonSmartCopy };
  32   enum SortFlavor { IntegerSort, StringSort, GenericSort };
  33 public:
  34   friend class ArrayInit;
  35
  36   // Load factor scaler.  If S is the # of elements, C is the
  37   // power-of-2 capacity, and L=LoadScale, we grow when S > C-C/L.
  38   // So 2 gives 0.5 load factor, 4 gives 0.75 load factor, 8 gives
  39   // 0.125 load factor.  Use powers of 2 to enable shift-divide.
  40   static const uint LoadScale = 4;
  41
  42 public:
  43   static HphpArray* GetStaticEmptyArray() {
  44     return &s_theEmptyArray;
  45   }
  46
  47 private:
  48   // for copy-on-write escalation
  49   HphpArray(CopyMode);
  50
  51 public:
  52   // Create an empty array with enough capacity for nSize elements.
  53   HphpArray(uint nSize);
  54
  55   // Create and initialize an array with size elements, populated by
  56   // moving (without refcounting) and reversing vals.
  57   HphpArray(uint size, const TypedValue* vals); // make tuple
  58
  59   virtual ~HphpArray();
  60
  61   // unlike ArrayData::size(), this functions doesn't delegate
  62   // to the virtual vsize() functions, so its more efficient to
  63   // use this when you know you have an HphpArray.
  64   ssize_t getSize() const {
  65     return m_size;
  66   }
  67
  68   // This behaves the same as iter_begin except that it assumes
  69   // this array is not empty and its not virtual.
  70   ssize_t getIterBegin() const {
  71     assert(!empty());
  72     if (LIKELY((m_data[0].data.m_type < KindOfTombstone))) {
  73       return 0;
  74     }
  75     return nextElm(m_data, 0);
  76   }
  77
  78   // override/implement ArrayData api's
  79
  80   // these using directives ensure the full set of overloaded functions
  81   // are visible in this class, to avoid triggering implicit conversions
  82   // from a CVarRef key to int64.
  83   using ArrayData::exists;
  84   using ArrayData::get;
  85   using ArrayData::getIndex;
  86   using ArrayData::lval;
  87   using ArrayData::lvalNew;
  88   using ArrayData::lvalPtr;
  89   using ArrayData::set;
  90   using ArrayData::setRef;
  91   using ArrayData::add;
  92   using ArrayData::addLval;
  93   using ArrayData::remove;
  94
  95   // implements ArrayData
  96   ssize_t vsize() const;
  97   Variant getKey(ssize_t pos) const;
  98   Variant getValue(ssize_t pos) const;
  99   CVarRef getValueRef(ssize_t pos) const;
 100
 101   // overrides ArrayData
 102   bool isVectorData() const;
 103   ssize_t iter_begin() const;
 104   ssize_t iter_end() const;
 105   ssize_t iter_advance(ssize_t prev) const;
 106   ssize_t iter_rewind(ssize_t prev) const;
 107
 108   // overrides ArrayData
 109   Variant reset();
 110   Variant prev();
 111   Variant current() const;
 112   Variant next();
 113   Variant end();
 114   Variant key() const;
 115   Variant value(ssize_t& pos) const;
 116   Variant each();
 117
 118   // implements ArrayData
 119   bool exists(int64_t k) const;
 120   bool exists(const StringData* k) const;
 121
 122   // implements ArrayData
 123   CVarRef get(int64_t k, bool error=false) const FLATTEN;
 124   CVarRef get(const StringData* k, bool error=false) const FLATTEN;
 125
 126   // implements ArrayData
 127   ssize_t getIndex(int64_t k) const;
 128   ssize_t getIndex(const StringData* k) const;
 129
 130   // implements ArrayData
 131   ArrayData* lval(int64_t k, Variant*& ret, bool copy, bool checkExist=false);
 132   ArrayData* lval(StringData* k, Variant*& ret, bool copy,
 133                   bool checkExist=false);
 134   ArrayData* lvalNew(Variant*& ret, bool copy);
 135
 136   // overrides ArrayData
 137   ArrayData* lvalPtr(StringData* k, Variant*& ret, bool copy,
 138                      bool create);
 139
 140   // implements ArrayData
 141   ArrayData* set(int64_t k, CVarRef v, bool copy);
 142   ArrayData* set(StringData* k, CVarRef v, bool copy);
 143
 144   // implements ArrayData
 145   ArrayData* setRef(int64_t k, CVarRef v, bool copy);
 146   ArrayData* setRef(StringData* k, CVarRef v, bool copy);
 147
 148   // overrides ArrayData
 149   ArrayData *add(int64_t k, CVarRef v, bool copy);
 150   ArrayData *add(StringData* k, CVarRef v, bool copy);
 151   ArrayData *addLval(int64_t k, Variant*& ret, bool copy);
 152   ArrayData *addLval(StringData* k, Variant*& ret, bool copy);
 153
 154   // implements ArrayData
 155   ArrayData* remove(int64_t k, bool copy);
 156   ArrayData* remove(const StringData* k, bool copy);
 157
 158   // overrides/implements ArrayData
 159   ArrayData* copy() const;
 160   ArrayData* copyWithStrongIterators() const;
 161   ArrayData* nonSmartCopy() const;
 162   ArrayData* append(CVarRef v, bool copy);
 163   ArrayData* appendRef(CVarRef v, bool copy);
 164   ArrayData* appendWithRef(CVarRef v, bool copy);
 165   ArrayData* append(const ArrayData* elems, ArrayOp op, bool copy);
 166   ArrayData* pop(Variant& value);
 167   ArrayData* dequeue(Variant& value);
 168   ArrayData* prepend(CVarRef v, bool copy);
 169   void renumber();
 170   void onSetEvalScalar();
 171
 172   // overrides ArrayData
 173   bool validFullPos(const FullPos &fp) const;
 174   bool advanceFullPos(FullPos& fp);
 175   CVarRef currentRef();
 176   CVarRef endRef();
 177
 178   // END overide/implements section
 179
 180   // nvGet and friends.
 181   // "nv" stands for non-variant. If we know the types of keys and values
 182   // through runtime and compile-time chicanery, we can directly call these
 183   // methods.
 184
 185   // nvGet returns a pointer to the value if the specified key is in the
 186   // array, NULL otherwise.
 187   TypedValue* nvGet(int64_t ki) const;
 188   TypedValue* nvGet(const StringData* k) const;
 189
 190   // nvGetCell is a variation of get, however it unwraps a KindOfRef,
 191   // returns KindOfNull if the key doesn't exist, and always warns.
 192   TypedValue* nvGetCell(int64_t ki) const;
 193   TypedValue* nvGetCell(const StringData* k) const;
 194
 195   void nvBind(int64_t ki, const TypedValue* v) {
 196     updateRef(ki, tvAsCVarRef(v));
 197   }
 198   void nvBind(StringData* k, const TypedValue* v) {
 199     updateRef(k, tvAsCVarRef(v));
 200   }
 201   void nvAppend(const TypedValue* v) {
 202     nextInsert(tvAsCVarRef(v));
 203   }
 204   ArrayData* nvNew(TypedValue*& v, bool copy);
 205   TypedValue* nvGetValueRef(ssize_t pos);
 206   void nvGetKey(TypedValue* out, ssize_t pos);
 207   bool nvInsert(StringData* k, TypedValue *v);
 208
 209   /**
 210    * Main helper for AddNewElemC.  The semantics are slightly different from
 211    * other helpers, but tuned for the opcode.  The value to set is passed by
 212    * value; the caller has incref'd it if necessary, and this call *moves* it
 213    * to its location in the array (caller must not decref).  If the value cannot
 214    * be stored in the array, this helper decref's it.
 215    */
 216   static ArrayData* AddNewElemC(ArrayData* a, TypedValue value);
 217
 218 private:
 219   template <typename AccessorT>
 220   SortFlavor preSort(const AccessorT& acc, bool checkTypes);
 221
 222   void postSort(bool resetKeys);
 223
 224 public:
 225   ArrayData* escalateForSort();
 226   void ksort(int sort_flags, bool ascending);
 227   void sort(int sort_flags, bool ascending);
 228   void asort(int sort_flags, bool ascending);
 229   void uksort(CVarRef cmp_function);
 230   void usort(CVarRef cmp_function);
 231   void uasort(CVarRef cmp_function);
 232   void dumpDebugInfo() const;
 233
 234   // Used in Elm's data.m_type field to denote an invalid Elm.
 235   static const HPHP::DataType KindOfTombstone = MaxNumDataTypes;
 236
 237   // Array element.
 238   struct Elm {
 239     /* The key is either a string pointer or an int value, and the _count
 240      * field in data is used to discriminate the key type. _count = 0 means
 241      * int, nonzero values contain 32 bits of a string's hashcode.
 242      * It is critical that when we return &data to clients, that they not
 243      * read or write the _count field! */
 244     union {
 245       int64_t ikey;
 246       StringData* key;
 247     };
 248     // We store values here, but also some information local to this array:
 249     // data.m_aux.u_hash contains either 0 (for an int key) or a string
 250     // hashcode; the high bit is the int/string key descriminator.
 251     // data.m_type == KindOfTombstone if this is an empty slot in the
 252     // array (e.g. after a key is deleted).
 253     TypedValueAux data;
 254     bool hasStrKey() const {
 255       return data.hash() != 0;
 256     }
 257     bool hasIntKey() const {
 258       return data.hash() == 0;
 259     }
 260     int32_t hash() const {
 261       return data.hash();
 262     }
 263     void setStrKey(StringData* k, strhash_t h) {
 264       key = k;
 265       data.hash() = int32_t(h) | 0x80000000;
 266     }
 267     void setIntKey(int64_t k) {
 268       ikey = k;
 269       data.hash() = 0;
 270     }
 271   };
 272
 273   struct ElmKey {
 274     ElmKey() {}
 275     ElmKey(int32_t hash, StringData* key) {
 276       this->hash = hash;
 277       this->key = key;
 278     }
 279     int32_t hash;
 280     union {
 281       StringData* key;
 282       int64_t ikey;
 283     };
 284   };
 285
 286   // Element index, with special values < 0 used for hash tables.
 287   // NOTE: Unfortunately, g++ on x64 tends to generate worse machine code for
 288   // 32-bit ints than it does for 64-bit ints. As such, we have deliberately
 289   // chosen to use ssize_t in some places where ideally we *should* have used
 290   // ElmInd.
 291   typedef int32_t ElmInd;
 292   static const ElmInd ElmIndEmpty      = -1; // == ArrayData::invalid_index
 293   static const ElmInd ElmIndTombstone  = -2;
 294
 295   // Use a minimum of an 4-element hash table.  Valid range: [2..32]
 296   static const uint32_t MinLgTableSize = 2;
 297   static const uint32_t SmallHashSize = 1 << MinLgTableSize;
 298   static const uint32_t SmallSize = SmallHashSize - SmallHashSize / LoadScale;
 299
 300   struct InlineSlots {
 301     Elm slots[SmallSize];
 302     ElmInd hash[SmallHashSize];
 303   };
 304
 305   ElmInd getLastE() const { return m_lastE; }
 306   Elm*   getElm(ssize_t pos)  const {
 307     assert(unsigned(pos) <= unsigned(m_lastE));
 308     return &m_data[pos];
 309   }
 310   static void getElmKey(Elm* e, TypedValue* out) {
 311     if (e->hasIntKey()) {
 312       out->m_data.num = e->ikey;
 313       out->m_type = KindOfInt64;
 314       return;
 315     }
 316     out->m_data.pstr = e->key;
 317     out->m_type = KindOfString;
 318     e->key->incRefCount();
 319   }
 320 private:
 321   // Small: Array elements and the hash table are allocated inline.
 322   //
 323   //            +--------------------+
 324   // this -->   | HphpArray fields   |
 325   //            +--------------------+
 326   // m_data --> | slot 0 ...         | SmallSize slots for elements.
 327   //            | slot SmallSize-1   |
 328   //            +--------------------+
 329   // m_hash --> |                    | 2^MinLgTableSize hash table entries.
 330   //            +--------------------+
 331   //
 332   // Medium: Just the hash table is allocated inline, array elements
 333   // are allocated from malloc.
 334   //
 335   //            +--------------------+
 336   // this -->   | HphpArray fields   |
 337   //            +--------------------+
 338   // m_hash --> |                    | 2^K hash table entries
 339   //            +--------------------+
 340   //
 341   //            +--------------------+
 342   // m_data --> | slot 0             | 0.75 * 2^K slots for elements.
 343   //            | slot 1             |
 344   //            | ...                |
 345   //            +--------------------+
 346   //
 347   // Big: Array elements and the hash table are contiguously allocated, and
 348   // elements are pointer aligned.
 349   //
 350   //            +--------------------+
 351   // m_data --> | slot 0             | 0.75 * 2^K slots for elements.
 352   //            | slot 1             |
 353   //            | ...                |
 354   //            +--------------------+
 355   // m_hash --> |                    | 2^K hash table entries.
 356   //            +--------------------+
 357
 358   ElmInd  m_lastE;       // Index of last used element.
 359   Elm*    m_data;        // Contains elements and hash table.
 360   ElmInd* m_hash;        // Hash table.
 361   int64_t   m_nextKI;      // Next integer key to use for append.
 362   uint32_t  m_tableMask;   // Bitmask used when indexing into the hash table.
 363   uint32_t  m_hLoad;       // Hash table load (# of non-empty slots).
 364   union {
 365     InlineSlots m_inline_data;
 366     ElmInd m_inline_hash[sizeof(m_inline_data) / sizeof(ElmInd)];
 367   };
 368
 369   ssize_t /*ElmInd*/ nextElm(Elm* elms, ssize_t /*ElmInd*/ ei) const {
 370     assert(ei >= -1);
 371     ssize_t lastE = m_lastE;
 372     while (ei < lastE) {
 373       ++ei;
 374       if (elms[ei].data.m_type < KindOfTombstone) {
 375         return ei;
 376       }
 377     }
 378     return (ssize_t)ElmIndEmpty;
 379   }
 380   ssize_t /*ElmInd*/ prevElm(Elm* elms, ssize_t /*ElmInd*/ ei) const;
 381
 382   ssize_t /*ElmInd*/ find(int64_t ki) const;
 383   ssize_t /*ElmInd*/ find(const StringData* s, strhash_t prehash) const;
 384   ElmInd* findForInsert(int64_t ki) const;
 385   ElmInd* findForInsert(const StringData* k, strhash_t prehash) const;
 386
 387   ssize_t iter_advance_helper(ssize_t prev) const ATTRIBUTE_COLD;
 388
 389   /**
 390    * findForNewInsert() CANNOT be used unless the caller can guarantee that
 391    * the relevant key is not already present in the array. Otherwise this can
 392    * put the array into a bad state; use with caution.
 393    */
 394   ElmInd* findForNewInsertLoop(size_t tableMask, size_t h0) const;
 395
 396   inline ALWAYS_INLINE
 397   ElmInd* findForNewInsert(size_t h0) const {
 398     size_t tableMask = m_tableMask;
 399     size_t probeIndex = h0 & tableMask;
 400     ElmInd* ei = &m_hash[probeIndex];
 401     return !validElmInd(*ei) ? ei :
 402            findForNewInsertLoop(tableMask, h0);
 403   }
 404
 405   bool nextInsert(CVarRef data);
 406   ArrayData* nextInsertRef(CVarRef data);
 407   ArrayData* nextInsertWithRef(CVarRef data);
 408   ArrayData* addLvalImpl(int64_t ki, Variant** pDest);
 409   ArrayData* addLvalImpl(StringData* key, strhash_t h, Variant** pDest);
 410   ArrayData* addVal(int64_t ki, CVarRef data);
 411   ArrayData* addVal(StringData* key, CVarRef data);
 412   ArrayData* addValWithRef(int64_t ki, CVarRef data);
 413   ArrayData* addValWithRef(StringData* key, CVarRef data);
 414
 415   ArrayData* update(int64_t ki, CVarRef data);
 416   ArrayData* update(StringData* key, CVarRef data);
 417   ArrayData* updateRef(int64_t ki, CVarRef data);
 418   ArrayData* updateRef(StringData* key, CVarRef data);
 419
 420   ArrayData* erase(ElmInd* ei, bool updateNext = false);
 421
 422   HphpArray* copyImpl(HphpArray* target) const;
 423   HphpArray* copyImpl() const;
 424
 425   bool isFull() const;
 426   Elm* newElm(ElmInd* e, size_t h0);
 427   Elm* newElmGrow(size_t h0);
 428   Elm* allocElm(ElmInd* ei);
 429   Elm* allocElmFast(ElmInd* ei);
 430   void initElmInt(Elm* e, int64_t ki, CVarRef data, bool byRef=false);
 431   void initElmStr(Elm* e, strhash_t h, StringData* key, CVarRef data,
 432                   bool byRef=false);
 433   void newElmInt(ElmInd* ei, int64_t ki, CVarRef data,
 434                       bool byRef=false);
 435   void newElmStr(ElmInd* ei, strhash_t h, StringData* key, CVarRef data,
 436                       bool byRef=false);
 437   void allocData(size_t maxElms, size_t tableSize);
 438   void reallocData(size_t maxElms, size_t tableSize, uint oldMask);
 439
 440   /**
 441    * init(size) allocates space for size elements but initializes
 442    * as an empty array
 443    */
 444   void init(uint size);
 445
 446   /**
 447    * grow() increases the hash table size and the number of slots for
 448    * elements by a factor of 2. grow() rebuilds the hash table, but it
 449    * does not compact the elements.
 450    */
 451   void grow() ATTRIBUTE_COLD;
 452
 453   /**
 454    * compact() does not change the hash table size or the number of slots
 455    * for elements. compact() rebuilds the hash table and compacts the
 456    * elements into the slots with lower addresses.
 457    */
 458   void compact(bool renumber=false) ATTRIBUTE_COLD;
 459
 460   /**
 461    * resize() and resizeIfNeeded() will grow or compact the array as
 462    * necessary to ensure that there is room for a new element and a
 463    * new hash entry.
 464    *
 465    * resize() assumes that the array does not have room for a new element
 466    * or a new hash entry. resizeIfNeeded() will first check if there is room
 467    * for a new element and hash entry before growing or compacting the array.
 468    */
 469   void resize();
 470   void resizeIfNeeded();
 471
 472   // Memory allocator methods.
 473   DECLARE_SMART_ALLOCATION(HphpArray);
 474
 475 private:
 476   enum EmptyMode { StaticEmptyArray };
 477   HphpArray(EmptyMode);
 478   // static singleton empty array.  Not a subclass because we want a fast
 479   // isHphpArray implementation; HphpArray should be effectively final.
 480   static HphpArray s_theEmptyArray;
 481
 482   static void initHash(HphpArray::ElmInd* hash, size_t tableSize) {
 483     assert(HphpArray::ElmIndEmpty == -1);
 484     memset(hash, 0xffU, tableSize * sizeof(HphpArray::ElmInd));
 485   }
 486
 487 public:
 488   static bool validElmInd(ssize_t /*HphpArray::ElmInd*/ ei) {
 489     return (ei > ssize_t(HphpArray::ElmIndEmpty));
 490   }
 491
 492   static size_t computeTableSize(uint32_t tableMask) {
 493     return size_t(tableMask) + size_t(1U);
 494   }
 495
 496   static size_t computeMaxElms(uint32_t tableMask) {
 497     return size_t(tableMask) - size_t(tableMask) / HphpArray::LoadScale;
 498   }
 499
 500   static size_t computeDataSize(uint32_t tableMask) {
 501     return computeTableSize(tableMask) * sizeof(HphpArray::ElmInd) +
 502       computeMaxElms(tableMask) * sizeof(HphpArray::Elm);
 503   }
 504 };
 505
 506 //=============================================================================
 507 // VM runtime support functions.
 508
 509 enum ArrayGetFlags {
 510   DecRefKey = 1,
 511   CheckInts = 2
 512 };
 513
 514 ArrayData* array_setm_ik1_v(RefData* ref, ArrayData* ad, int64_t key,
 515                             TypedValue* value);
 516 ArrayData* array_setm_ik1_v0(RefData* ref, ArrayData* ad, int64_t key,
 517                              TypedValue* value);
 518 ArrayData* array_setm_sk1_v(RefData* ref, ArrayData* ad, StringData* key,
 519                             TypedValue* value);
 520 ArrayData* array_setm_sk1_v0(RefData* ref, ArrayData* ad, StringData* key,
 521                              TypedValue* value);
 522 ArrayData* array_setm_s0k1_v(RefData* ref, ArrayData* ad, StringData* key,
 523                              TypedValue* value);
 524 ArrayData* array_setm_s0k1_v0(RefData* ref, ArrayData* ad, StringData* key,
 525                               TypedValue* value);
 526 ArrayData* array_setm_s0k1nc_v(RefData* ref, ArrayData* ad, StringData* key,
 527                                TypedValue* value);
 528 ArrayData* array_setm_s0k1nc_v0(RefData* ref, ArrayData* ad,
 529                                 StringData* key, TypedValue* value);
 530 ArrayData* array_setm_wk1_v0(ArrayData* ad, TypedValue* value);
 531 ArrayData* array_getm_i(void* hphpArray, int64_t key, TypedValue* out);
 532
 533 ArrayData* array_getm_s(ArrayData* a, StringData* key, TypedValue* out,
 534                         int flags);
 535 uint64_t array_issetm_s(const void* hphpArray, StringData* sd)
 536   FLATTEN;
 537 uint64_t array_issetm_s0(const void* hphpArray, StringData* sd)
 538   FLATTEN;
 539 uint64_t array_issetm_s_fast(const void* hphpArray, StringData* sd)
 540   FLATTEN;
 541 uint64_t array_issetm_s0_fast(const void* hphpArray, StringData* sd)
 542   FLATTEN;
 543 uint64_t array_issetm_i(const void* hphpArray, int64_t key)
 544   FLATTEN;
 545 ArrayData* array_add(ArrayData* a1, ArrayData* a2);
 546
 547 //=============================================================================
 548
 549 ///////////////////////////////////////////////////////////////////////////////
 550 }
 551
 552 #endif // incl_HPHP_HPHP_ARRAY_H_