hphp/runtime/ext/ext_collections.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2013 Facebook, Inc. (http://www.facebook.com)     |
   6    | Copyright (c) 1997-2010 The PHP Group                                |
   7    +----------------------------------------------------------------------+
   8    | This source file is subject to version 3.01 of the PHP license,      |
   9    | that is bundled with this package in the file LICENSE, and is        |
  10    | available through the world-wide-web at the following url:           |
  11    | http://www.php.net/license/3_01.txt                                  |
  12    | If you did not receive a copy of the PHP license and are unable to   |
  13    | obtain it through the world-wide-web, please send a note to          |
  14    | license@php.net so we can mail you a copy immediately.               |
  15    +----------------------------------------------------------------------+
  16 */
  17
  18 #ifndef incl_HPHP_EXT_COLLECTION_H_
  19 #define incl_HPHP_EXT_COLLECTION_H_
  20
  21 #include "hphp/runtime/base/base-includes.h"
  22 #include "hphp/system/systemlib.h"
  23
  24 namespace HPHP {
  25 ///////////////////////////////////////////////////////////////////////////////
  26
  27 ///////////////////////////////////////////////////////////////////////////////
  28 // class Vector
  29
  30 FORWARD_DECLARE_CLASS_BUILTIN(Vector);
  31 class c_Vector : public ExtObjectDataFlags<ObjectData::VectorAttrInit|
  32                                            ObjectData::UseGet|
  33                                            ObjectData::UseSet|
  34                                            ObjectData::UseIsset|
  35                                            ObjectData::UseUnset> {
  36  public:
  37   DECLARE_CLASS(Vector, Vector, ObjectData)
  38
  39  public:
  40   explicit c_Vector(Class* cls = c_Vector::s_cls);
  41   ~c_Vector();
  42   void freeData();
  43   void t___construct(CVarRef iterable = null_variant);
  44   Object t_add(CVarRef val);
  45   Object t_addall(CVarRef val);
  46   Object t_append(CVarRef val); // deprecated
  47   Variant t_pop();
  48   void t_resize(CVarRef sz, CVarRef value);
  49   void t_reserve(CVarRef sz);
  50   Object t_clear();
  51   bool t_isempty();
  52   int64_t t_count();
  53   Object t_items();
  54   Object t_keys();
  55   Object t_view();
  56   Object t_kvzip();
  57   Variant t_at(CVarRef key);
  58   Variant t_get(CVarRef key);
  59   Object t_set(CVarRef key, CVarRef value);
  60   Object t_setall(CVarRef iterable);
  61   Object t_put(CVarRef key, CVarRef value); // deprecated
  62   bool t_contains(CVarRef key); // deprecated
  63   bool t_containskey(CVarRef key);
  64   Object t_removekey(CVarRef key);
  65   Array t_toarray();
  66   void t_sort(CVarRef col = uninit_null()); // deprecated
  67   void t_reverse();
  68   void t_splice(CVarRef offset, CVarRef len = uninit_null(),
  69                 CVarRef replacement = uninit_null());
  70   int64_t t_linearsearch(CVarRef search_value);
  71   void t_shuffle();
  72   Object t_getiterator();
  73   Object t_map(CVarRef callback);
  74   Object t_filter(CVarRef callback);
  75   Object t_zip(CVarRef iterable);
  76   String t___tostring();
  77   Variant t___get(Variant name);
  78   Variant t___set(Variant name, Variant value);
  79   bool t___isset(Variant name);
  80   Variant t___unset(Variant name);
  81   static Object ti_fromitems(CVarRef iterable);
  82   static Object ti_fromarray(CVarRef arr); // deprecated
  83   static Variant ti_slice(CVarRef vec, CVarRef offset,
  84                           CVarRef len = uninit_null());
  85   static Variant t_slice(CVarRef vec, CVarRef offset,
  86                          CVarRef len = uninit_null()) {
  87     return ti_slice(vec, offset, len);
  88   }
  89
  90   static void throwOOB(int64_t key) ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
  91
  92   TypedValue* at(int64_t key) {
  93     if (UNLIKELY((uint64_t)key >= (uint64_t)m_size)) {
  94       throwOOB(key);
  95       return NULL;
  96     }
  97     return &m_data[key];
  98   }
  99   TypedValue* get(int64_t key) {
 100     if ((uint64_t)key >= (uint64_t)m_size) {
 101       return NULL;
 102     }
 103     return &m_data[key];
 104   }
 105   void set(int64_t key, TypedValue* val) {
 106     assert(val->m_type != KindOfRef);
 107     if (UNLIKELY((uint64_t)key >= (uint64_t)m_size)) {
 108       throwOOB(key);
 109       return;
 110     }
 111     tvRefcountedIncRef(val);
 112     TypedValue* tv = &m_data[key];
 113     tvRefcountedDecRef(tv);
 114     tv->m_data.num = val->m_data.num;
 115     tv->m_type = val->m_type;
 116   }
 117   void add(TypedValue* val) {
 118     assert(val->m_type != KindOfRef);
 119     ++m_version;
 120     if (m_capacity <= m_size) {
 121       grow();
 122     }
 123     tvRefcountedIncRef(val);
 124     TypedValue* tv = &m_data[m_size];
 125     tv->m_data.num = val->m_data.num;
 126     tv->m_type = val->m_type;
 127     ++m_size;
 128   }
 129   void resize(int64_t sz, TypedValue* val);
 130   bool contains(int64_t key) {
 131     return ((uint64_t)key < (uint64_t)m_size);
 132   }
 133   void reserve(int64_t sz);
 134   int getVersion() const {
 135     return m_version;
 136   }
 137   int64_t size() const {
 138     return m_size;
 139   }
 140
 141
 142   Array toArrayImpl() const;
 143
 144   Array o_toArray() const;
 145   c_Vector* clone();
 146
 147   enum SortFlavor { IntegerSort, StringSort, GenericSort };
 148
 149  private:
 150   template <typename AccessorT>
 151   SortFlavor preSort(const AccessorT& acc);
 152
 153  public:
 154   void sort(int sort_flags, bool ascending);
 155   void usort(CVarRef cmp_function);
 156
 157   static TypedValue* OffsetGet(ObjectData* obj, TypedValue* key);
 158   static void OffsetSet(ObjectData* obj, TypedValue* key, TypedValue* val);
 159   static bool OffsetIsset(ObjectData* obj, TypedValue* key);
 160   static bool OffsetEmpty(ObjectData* obj, TypedValue* key);
 161   static bool OffsetContains(ObjectData* obj, TypedValue* key);
 162   static void OffsetUnset(ObjectData* obj, TypedValue* key);
 163   static void OffsetAppend(ObjectData* obj, TypedValue* val);
 164   static bool Equals(const ObjectData* obj1, const ObjectData* obj2);
 165   static void Unserialize(ObjectData* obj, VariableUnserializer* uns,
 166                           int64_t sz, char type);
 167
 168  private:
 169   void grow();
 170   static void throwBadKeyType() ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
 171
 172   TypedValue* m_data;
 173   uint m_size;
 174   uint m_capacity;
 175   int32_t m_version;
 176
 177   friend class c_VectorIterator;
 178   friend class c_Map;
 179   friend class c_StableMap;
 180   friend class c_Pair;
 181   friend class ArrayIter;
 182   friend ObjectData* collectionDeepCopyVector(c_Vector* vec);
 183 };
 184
 185 ///////////////////////////////////////////////////////////////////////////////
 186 // class VectorIterator
 187
 188 FORWARD_DECLARE_CLASS_BUILTIN(VectorIterator);
 189 class c_VectorIterator : public ExtObjectData {
 190  public:
 191   DECLARE_CLASS(VectorIterator, VectorIterator, ObjectData)
 192
 193  public:
 194   explicit c_VectorIterator(Class* cls = c_VectorIterator::s_cls);
 195   ~c_VectorIterator();
 196   void t___construct();
 197   Variant t_current();
 198   Variant t_key();
 199   bool t_valid();
 200   void t_next();
 201   void t_rewind();
 202
 203  private:
 204   SmartPtr<c_Vector> m_obj;
 205   ssize_t m_pos;
 206   int32_t m_version;
 207
 208   friend class c_Vector;
 209 };
 210
 211 ///////////////////////////////////////////////////////////////////////////////
 212 // class Map
 213
 214 FORWARD_DECLARE_CLASS_BUILTIN(Map);
 215 class c_Map : public ExtObjectDataFlags<ObjectData::MapAttrInit|
 216                                         ObjectData::UseGet|
 217                                         ObjectData::UseSet|
 218                                         ObjectData::UseIsset|
 219                                         ObjectData::UseUnset> {
 220  public:
 221   DECLARE_CLASS(Map, Map, ObjectData)
 222
 223  public:
 224   explicit c_Map(Class* cls = c_Map::s_cls);
 225   ~c_Map();
 226   void freeData();
 227   void t___construct(CVarRef iterable = null_variant);
 228   Object t_add(CVarRef val);
 229   Object t_addall(CVarRef val);
 230   Object t_clear();
 231   bool t_isempty();
 232   int64_t t_count();
 233   Object t_items();
 234   Object t_keys();
 235   Object t_view();
 236   Object t_kvzip();
 237   Variant t_at(CVarRef key);
 238   Variant t_get(CVarRef key);
 239   Object t_set(CVarRef key, CVarRef value);
 240   Object t_setall(CVarRef iterable);
 241   Object t_put(CVarRef key, CVarRef value); // deprecated
 242   bool t_contains(CVarRef key);
 243   bool t_containskey(CVarRef key);
 244   Object t_remove(CVarRef key);
 245   Object t_removekey(CVarRef key);
 246   Array t_toarray();
 247   Array t_copyasarray(); // deprecated
 248   Array t_tokeysarray(); // deprecated
 249   Object t_values(); // deprecated
 250   Array t_tovaluesarray(); // deprecated
 251   Object t_differencebykey(CVarRef it);
 252   Object t_getiterator();
 253   Object t_map(CVarRef callback);
 254   Object t_filter(CVarRef callback);
 255   Object t_zip(CVarRef iterable);
 256   String t___tostring();
 257   Variant t___get(Variant name);
 258   Variant t___set(Variant name, Variant value);
 259   bool t___isset(Variant name);
 260   Variant t___unset(Variant name);
 261   static Object ti_fromitems(CVarRef iterable);
 262   static Object ti_fromarray(CVarRef arr); // deprecated
 263
 264   static void throwOOB(int64_t key) ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
 265   static void throwOOB(StringData* key) ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
 266
 267   TypedValue* at(int64_t key) const {
 268     Bucket* p = find(key);
 269     if (LIKELY(p != NULL)) return &p->data;
 270     throwOOB(key);
 271     return NULL;
 272   }
 273   TypedValue* get(int64_t key) const {
 274     Bucket* p = find(key);
 275     if (p) return &p->data;
 276     return NULL;
 277   }
 278   TypedValue* at(StringData* key) const {
 279     Bucket* p = find(key->data(), key->size(), key->hash());
 280     if (LIKELY(p != NULL)) return &p->data;
 281     throwOOB(key);
 282     return NULL;
 283   }
 284   TypedValue* get(StringData* key) const {
 285     Bucket* p = find(key->data(), key->size(), key->hash());
 286     if (p) return &p->data;
 287     return NULL;
 288   }
 289   void set(int64_t key, TypedValue* val) {
 290     assert(val->m_type != KindOfRef);
 291     update(key, val);
 292   }
 293   void set(StringData* key, TypedValue* val) {
 294     assert(val->m_type != KindOfRef);
 295     update(key, val);
 296   }
 297   void add(TypedValue* val);
 298   void remove(int64_t key) {
 299     ++m_version;
 300     erase(find(key));
 301   }
 302   void remove(StringData* key) {
 303     ++m_version;
 304     erase(find(key->data(), key->size(), key->hash()));
 305   }
 306   bool contains(int64_t key) const {
 307     return find(key);
 308   }
 309   bool contains(StringData* key) const {
 310     return find(key->data(), key->size(), key->hash());
 311   }
 312   void reserve(int64_t sz) {
 313     if (int64_t(m_load) + sz - int64_t(m_size) >= computeMaxLoad()) {
 314       adjustCapacityImpl(sz);
 315     }
 316   }
 317   int getVersion() const {
 318     return m_version;
 319   }
 320   int64_t size() const {
 321     return m_size;
 322   }
 323   Array toArrayImpl() const;
 324
 325   Array o_toArray() const;
 326   c_Map* clone();
 327
 328   static TypedValue* OffsetGet(ObjectData* obj, TypedValue* key);
 329   static void OffsetSet(ObjectData* obj, TypedValue* key, TypedValue* val);
 330   static bool OffsetIsset(ObjectData* obj, TypedValue* key);
 331   static bool OffsetEmpty(ObjectData* obj, TypedValue* key);
 332   static bool OffsetContains(ObjectData* obj, TypedValue* key);
 333   static void OffsetUnset(ObjectData* obj, TypedValue* key);
 334   static void OffsetAppend(ObjectData* obj, TypedValue* val);
 335   static bool Equals(const ObjectData* obj1, const ObjectData* obj2);
 336   static void Unserialize(ObjectData* obj, VariableUnserializer* uns,
 337                           int64_t sz, char type);
 338
 339   static const int32_t KindOfTombstone = -1;
 340
 341   struct Bucket {
 342     /**
 343      * Buckets are 24 bytes and we allocate Buckets continguously in memory
 344      * without any padding, so some Buckets span multiple cache lines. We
 345      * access data.m_aux, data.m_type, and ikey/skey during hash lookup, so we
 346      * intentionally put the data field first so that the accessed fields are
 347      * all next to each other, which means that they will be on the same cache
 348      * line for 87.5% of the buckets.
 349      *
 350      * The key is either a string pointer or an int value, and the
 351      * m_aux.u_hash field in data is used to discriminate the key type.
 352      * u_hash = 0 means int, nonzero values contain 31 bits of a string's
 353      * hashcode. It is critical that when we return &data to clients, that
 354      * they not read or write the m_aux field.
 355      */
 356     TypedValueAux data;
 357     union {
 358       int64_t ikey;
 359       StringData *skey;
 360     };
 361     inline bool hasStrKey() const { return data.hash() != 0; }
 362     inline bool hasIntKey() const { return data.hash() == 0; }
 363     inline void setStrKey(StringData* k, strhash_t h) {
 364       skey = k;
 365       skey->incRefCount();
 366       data.hash() = int32_t(h) | 0x80000000;
 367     }
 368     inline void setIntKey(int64_t k) {
 369       ikey = k;
 370       data.hash() = 0;
 371     }
 372     inline int64_t hashKey() const {
 373       return data.hash() == 0 ? ikey : data.hash();
 374     }
 375     inline int32_t hash() const {
 376       return data.hash();
 377     }
 378     bool validValue() const {
 379       return (intptr_t(data.m_type) > 0);
 380     }
 381     bool empty() const {
 382       return data.m_type == KindOfUninit;
 383     }
 384     bool tombstone() const {
 385       return data.m_type == KindOfTombstone;
 386     }
 387     void dump();
 388   };
 389
 390  private:
 391   /**
 392    * Map uses a power of two for the table size and quadratic probing to
 393    * resolve hash collisions.
 394    *
 395    * When an element is removed from the table, a marker called a "tombstone"
 396    * is left behind in the slot that the element used to occupy. The tombstone
 397    * will remain in that slot until either (a) the table is resized, or (b) a
 398    * new element is inserted into that slot.
 399    *
 400    * To ensure that hash lookups are efficient, Map keeps the load factor
 401    * of the table below 75%. If adding a new element causes the load to
 402    * increase to 75% or greater, we grow the table to lower the load. Note
 403    * that tombstones count towards load.
 404    *
 405    * To ensure that iteration performance is efficient, Map keeps the ratio
 406    * of # elements / # slots to be at least 18.75%. If removing an element
 407    * causes the ratio to drop below 18.75%, we shrink the table to increase
 408    * the ratio.
 409    *
 410    * When a Map has never had any removals performed, the load factor is
 411    * guaranteed to be between 37.5% and 75% (as long as the Map has at least
 412    * 2 elements).
 413    */
 414
 415   Bucket* m_data;
 416   uint m_size;
 417   uint m_load;
 418   uint m_nLastSlot;
 419   int32_t m_version;
 420
 421   size_t numSlots() const {
 422     return m_nLastSlot + 1;
 423   }
 424
 425   // The maximum load factor is 75%.
 426   size_t computeMaxLoad() const {
 427     size_t n = numSlots();
 428     return (n - (n >> 2));
 429   }
 430
 431   // When the map is not empty, the minimum allowed ratio
 432   // of # elements / # slots is 18.75%.
 433   size_t computeMinElements() const {
 434     size_t n = numSlots();
 435     return ((n >> 3) + ((n+8) >> 4));
 436   }
 437
 438   // We use this funny-looking helper to make g++ use lea and shl
 439   // instructions instead of imul when indexing into m_data
 440   Bucket* fetchBucket(Bucket* data, intptr_t slot) const {
 441     assert(sizeof(Bucket) == 24);
 442     assert(sizeof(int64_t) == 8);
 443     assert(slot >= 0 && slot <= m_nLastSlot);
 444     intptr_t index = slot + (slot<<1);
 445     int64_t* ptr = (int64_t*)data;
 446     return (Bucket*)(&ptr[index]);
 447   }
 448
 449   Bucket* fetchBucket(intptr_t slot) const {
 450     return fetchBucket(m_data, slot);
 451   }
 452
 453   Bucket* find(int64_t h) const;
 454   Bucket* find(const char* k, int len, strhash_t prehash) const;
 455   Bucket* findForInsert(int64_t h) const;
 456   Bucket* findForInsert(const char* k, int len, strhash_t prehash) const;
 457   Bucket* findForNewInsert(size_t h0) const;
 458
 459   bool update(int64_t h, TypedValue* data);
 460   bool update(StringData* key, TypedValue* data);
 461   void erase(Bucket* prev);
 462
 463   void adjustCapacityImpl(int64_t sz);
 464   void adjustCapacity() {
 465     adjustCapacityImpl(m_size);
 466   }
 467
 468   void deleteBuckets();
 469
 470   ssize_t iter_begin() const;
 471   ssize_t iter_next(ssize_t prev) const;
 472   ssize_t iter_prev(ssize_t prev) const;
 473   Variant iter_key(ssize_t pos) const;
 474   TypedValue* iter_value(ssize_t pos) const;
 475
 476   static void throwBadKeyType() ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
 477
 478   friend ObjectData* collectionDeepCopyMap(c_Map* mp);
 479   friend class c_MapIterator;
 480   friend class c_Vector;
 481   friend class c_StableMap;
 482   friend class ArrayIter;
 483   friend class c_GenMapWaitHandle;
 484 };
 485
 486 ///////////////////////////////////////////////////////////////////////////////
 487 // class MapIterator
 488
 489 FORWARD_DECLARE_CLASS_BUILTIN(MapIterator);
 490 class c_MapIterator : public ExtObjectData {
 491  public:
 492   DECLARE_CLASS(MapIterator, MapIterator, ObjectData)
 493
 494  public:
 495   explicit c_MapIterator(Class* cls = c_MapIterator::s_cls);
 496   ~c_MapIterator();
 497   void t___construct();
 498   Variant t_current();
 499   Variant t_key();
 500   bool t_valid();
 501   void t_next();
 502   void t_rewind();
 503
 504  private:
 505   SmartPtr<c_Map> m_obj;
 506   ssize_t m_pos;
 507   int32_t m_version;
 508
 509   friend class c_Map;
 510 };
 511
 512 ///////////////////////////////////////////////////////////////////////////////
 513 // class StableMap
 514
 515 FORWARD_DECLARE_CLASS_BUILTIN(StableMap);
 516 class c_StableMap : public ExtObjectDataFlags<ObjectData::StableMapAttrInit|
 517                                               ObjectData::UseGet|
 518                                               ObjectData::UseSet|
 519                                               ObjectData::UseIsset|
 520                                               ObjectData::UseUnset> {
 521  public:
 522   DECLARE_CLASS(StableMap, StableMap, ObjectData)
 523
 524  public:
 525   explicit c_StableMap(Class* cls = c_StableMap::s_cls);
 526   ~c_StableMap();
 527   void freeData();
 528   void t___construct(CVarRef iterable = null_variant);
 529   Object t_add(CVarRef val);
 530   Object t_addall(CVarRef val);
 531   Object t_clear();
 532   bool t_isempty();
 533   int64_t t_count();
 534   Object t_items();
 535   Object t_keys();
 536   Object t_view();
 537   Object t_kvzip();
 538   Variant t_at(CVarRef key);
 539   Variant t_get(CVarRef key);
 540   Object t_set(CVarRef key, CVarRef value);
 541   Object t_setall(CVarRef iterable);
 542   Object t_put(CVarRef key, CVarRef value); // deprecated
 543   bool t_contains(CVarRef key);
 544   bool t_containskey(CVarRef key);
 545   Object t_remove(CVarRef key);
 546   Object t_removekey(CVarRef key);
 547   Array t_toarray();
 548   Array t_copyasarray(); // deprecated
 549   Array t_tokeysarray(); // deprecated
 550   Object t_values(); // deprecated
 551   Array t_tovaluesarray(); // deprecated
 552   Object t_differencebykey(CVarRef it);
 553   Object t_getiterator();
 554   Object t_map(CVarRef callback);
 555   Object t_filter(CVarRef callback);
 556   Object t_zip(CVarRef iterable);
 557   String t___tostring();
 558   Variant t___get(Variant name);
 559   Variant t___set(Variant name, Variant value);
 560   bool t___isset(Variant name);
 561   Variant t___unset(Variant name);
 562   static Object ti_fromitems(CVarRef iterable);
 563   static Object ti_fromarray(CVarRef arr); // deprecated
 564
 565   static void throwOOB(int64_t key) ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
 566   static void throwOOB(StringData* key) ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
 567
 568   TypedValue* at(int64_t key) {
 569     Bucket* p = find(key);
 570     if (LIKELY(p != NULL)) return &p->data;
 571     throwOOB(key);
 572     return NULL;
 573   }
 574   TypedValue* at(StringData* key) {
 575     Bucket* p = find(key->data(), key->size(), key->hash());
 576     if (LIKELY(p != NULL)) return &p->data;
 577     throwOOB(key);
 578     return NULL;
 579   }
 580   TypedValue* get(int64_t key) {
 581     Bucket* p = find(key);
 582     if (p != NULL) return &p->data;
 583     return NULL;
 584   }
 585   TypedValue* get(StringData* key) {
 586     Bucket* p = find(key->data(), key->size(), key->hash());
 587     if (p != NULL) return &p->data;
 588     return NULL;
 589   }
 590   void set(int64_t key, TypedValue* val) {
 591     update(key, val);
 592   }
 593   void set(StringData* key, TypedValue* val) {
 594     update(key, val);
 595   }
 596   void add(TypedValue* val);
 597   void remove(int64_t key) {
 598     ++m_version;
 599     erase(findForErase(key));
 600   }
 601   void remove(StringData* key) {
 602     ++m_version;
 603     erase(findForErase(key->data(), key->size(), key->hash()));
 604   }
 605   bool contains(int64_t key) {
 606     return find(key);
 607   }
 608   bool contains(StringData* key) {
 609     return find(key->data(), key->size(), key->hash());
 610   }
 611   void reserve(int64_t sz) {
 612     if (sz > int64_t(m_nTableSize)) {
 613       adjustCapacityImpl(sz);
 614     }
 615   }
 616   int getVersion() const {
 617     return m_version;
 618   }
 619   int64_t size() const {
 620     return m_size;
 621   }
 622   Array toArrayImpl() const;
 623
 624   Array o_toArray() const;
 625   c_StableMap* clone();
 626
 627   static TypedValue* OffsetGet(ObjectData* obj, TypedValue* key);
 628   static void OffsetSet(ObjectData* obj, TypedValue* key, TypedValue* val);
 629   static bool OffsetIsset(ObjectData* obj, TypedValue* key);
 630   static bool OffsetEmpty(ObjectData* obj, TypedValue* key);
 631   static bool OffsetContains(ObjectData* obj, TypedValue* key);
 632   static void OffsetUnset(ObjectData* obj, TypedValue* key);
 633   static void OffsetAppend(ObjectData* obj, TypedValue* val);
 634   static bool Equals(const ObjectData* obj1, const ObjectData* obj2);
 635   static void Unserialize(ObjectData* obj, VariableUnserializer* uns,
 636                           int64_t sz, char type);
 637
 638   struct Bucket {
 639     Bucket() : ikey(0), pListNext(nullptr), pListLast(nullptr), pNext(nullptr) {
 640       data.hash() = 0;
 641     }
 642     explicit Bucket(TypedValue* tv) : ikey(0), pListNext(nullptr),
 643         pListLast(nullptr), pNext(nullptr) {
 644       tvDup(*tv, data);
 645       data.hash() = 0;
 646     }
 647     ~Bucket();
 648     // set the top bit for string hashes to make sure the hash
 649     // value is never zero. hash value 0 corresponds to integer key.
 650     static inline int32_t encodeHash(strhash_t h) {
 651       return int32_t(h) | 0x80000000;
 652     }
 653
 654     /* The key is either a string pointer or an int value, and the m_aux.u_hash
 655      * field in data is used to discriminate the key type. u_hash = 0 means
 656      * int, nonzero values contain 31 bits of a string's hashcode.
 657      * It is critical that when we return &data to clients, that they not
 658      * read or write the m_aux field! */
 659     TypedValueAux data;
 660     union {
 661       int64_t ikey;
 662       StringData* skey;
 663     };
 664     Bucket* pListNext;
 665     Bucket* pListLast;
 666     Bucket* pNext;
 667
 668     inline bool hasStrKey() const { return data.hash() != 0; }
 669     inline bool hasIntKey() const { return data.hash() == 0; }
 670     inline void setStrKey(StringData* k, strhash_t h) {
 671       skey = k;
 672       skey->incRefCount();
 673       data.hash() = encodeHash(h);
 674     }
 675     inline void setIntKey(int64_t k) {
 676       ikey = k;
 677       data.hash() = 0;
 678     }
 679     inline int64_t hashKey() const {
 680       return data.hash() == 0 ? ikey : data.hash();
 681     }
 682     inline int32_t hash() const {
 683       return data.hash();
 684     }
 685
 686     /**
 687      * Memory allocator methods.
 688      */
 689     DECLARE_SMART_ALLOCATION(Bucket);
 690     void dump();
 691   };
 692
 693   enum SortFlavor { IntegerSort, StringSort, GenericSort };
 694
 695  private:
 696   template <typename AccessorT>
 697   SortFlavor preSort(Bucket** buffer, const AccessorT& acc, bool checkTypes);
 698
 699   void postSort(Bucket** buffer);
 700
 701  public:
 702   void asort(int sort_flags, bool ascending);
 703   void ksort(int sort_flags, bool ascending);
 704   void uasort(CVarRef cmp_function);
 705   void uksort(CVarRef cmp_function);
 706
 707  private:
 708   uint m_size;
 709   uint m_nTableSize;
 710   uint m_nTableMask;
 711   int32_t m_version;
 712   Bucket* m_pListHead;
 713   Bucket* m_pListTail;
 714   Bucket** m_arBuckets;
 715
 716   Bucket* find(int64_t h) const;
 717   Bucket* find(const char* k, int len, strhash_t prehash) const;
 718   Bucket** findForErase(int64_t h) const;
 719   Bucket** findForErase(const char* k, int len, strhash_t prehash) const;
 720
 721   bool update(int64_t h, TypedValue* data);
 722   bool update(StringData* key, TypedValue* data);
 723   void erase(Bucket** prev);
 724
 725   void adjustCapacityImpl(int64_t sz);
 726   void adjustCapacity() {
 727     adjustCapacityImpl(m_size);
 728   }
 729
 730   void deleteBuckets();
 731
 732   ssize_t iter_begin() const;
 733   ssize_t iter_next(ssize_t prev) const;
 734   ssize_t iter_prev(ssize_t prev) const;
 735   Variant iter_key(ssize_t pos) const;
 736   TypedValue* iter_value(ssize_t pos) const;
 737
 738   static void throwBadKeyType() ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
 739
 740   friend ObjectData* collectionDeepCopyStableMap(c_StableMap* smp);
 741   friend class c_StableMapIterator;
 742   friend class c_Vector;
 743   friend class c_Map;
 744   friend class ArrayIter;
 745 };
 746
 747 ///////////////////////////////////////////////////////////////////////////////
 748 // class StableMapIterator
 749
 750 FORWARD_DECLARE_CLASS_BUILTIN(StableMapIterator);
 751 class c_StableMapIterator : public ExtObjectData {
 752  public:
 753   DECLARE_CLASS(StableMapIterator, StableMapIterator, ObjectData)
 754
 755  public:
 756   explicit c_StableMapIterator(Class* cls = c_StableMapIterator::s_cls);
 757   ~c_StableMapIterator();
 758   void t___construct();
 759   Variant t_current();
 760   Variant t_key();
 761   bool t_valid();
 762   void t_next();
 763   void t_rewind();
 764
 765  private:
 766   SmartPtr<c_StableMap> m_obj;
 767   ssize_t m_pos;
 768   int32_t m_version;
 769
 770   friend class c_StableMap;
 771 };
 772
 773 ///////////////////////////////////////////////////////////////////////////////
 774 // class Set
 775
 776 FORWARD_DECLARE_CLASS_BUILTIN(Set);
 777 class c_Set : public ExtObjectDataFlags<ObjectData::SetAttrInit|
 778                                         ObjectData::UseGet|
 779                                         ObjectData::UseSet|
 780                                         ObjectData::UseIsset|
 781                                         ObjectData::UseUnset> {
 782  public:
 783   DECLARE_CLASS(Set, Set, ObjectData)
 784
 785  public:
 786   static const int32_t KindOfTombstone = -1;
 787
 788   explicit c_Set(Class* cls = c_Set::s_cls);
 789   ~c_Set();
 790   void freeData();
 791   void t___construct(CVarRef iterable = null_variant);
 792   Object t_add(CVarRef val);
 793   Object t_addall(CVarRef val);
 794   Object t_clear();
 795   bool t_isempty();
 796   int64_t t_count();
 797   Object t_items();
 798   Object t_view();
 799   bool t_contains(CVarRef key);
 800   Object t_remove(CVarRef key);
 801   Array t_toarray();
 802   Object t_getiterator();
 803   Object t_map(CVarRef callback);
 804   Object t_filter(CVarRef callback);
 805   Object t_zip(CVarRef iterable);
 806   Object t_difference(CVarRef iterable);
 807   String t___tostring();
 808   Variant t___get(Variant name);
 809   Variant t___set(Variant name, Variant value);
 810   bool t___isset(Variant name);
 811   Variant t___unset(Variant name);
 812   static Object ti_fromitems(CVarRef iterable);
 813   static Object ti_fromarray(CVarRef arr);
 814   static Object ti_fromarrays(int _argc,
 815                               CArrRef _argv = null_array);
 816
 817   static void throwOOB(int64_t key) ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
 818   static void throwOOB(StringData* key) ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
 819   static void throwNoIndexAccess() ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
 820
 821   void add(TypedValue* val);
 822   void remove(int64_t key) {
 823     ++m_version;
 824     erase(find(key));
 825   }
 826   void remove(StringData* key) {
 827     ++m_version;
 828     erase(find(key->data(), key->size(), key->hash()));
 829   }
 830   bool contains(int64_t key) {
 831     return find(key);
 832   }
 833   bool contains(StringData* key) {
 834     return find(key->data(), key->size(), key->hash());
 835   }
 836   void reserve(int64_t sz) {
 837     if (int64_t(m_load) + sz - int64_t(m_size) >= computeMaxLoad()) {
 838       adjustCapacityImpl(sz);
 839     }
 840   }
 841   int getVersion() const {
 842     return m_version;
 843   }
 844   int64_t size() const {
 845     return m_size;
 846   }
 847   Array toArrayImpl() const;
 848
 849   Array o_toArray() const;
 850   c_Set* clone();
 851
 852   static TypedValue* OffsetGet(ObjectData* obj, TypedValue* key);
 853   static void OffsetSet(ObjectData* obj, TypedValue* key, TypedValue* val);
 854   static bool OffsetIsset(ObjectData* obj, TypedValue* key);
 855   static bool OffsetEmpty(ObjectData* obj, TypedValue* key);
 856   static bool OffsetContains(ObjectData* obj, TypedValue* key);
 857   static void OffsetUnset(ObjectData* obj, TypedValue* key);
 858   static void OffsetAppend(ObjectData* obj, TypedValue* val);
 859   static bool Equals(const ObjectData* obj1, const ObjectData* obj2);
 860   static void Unserialize(ObjectData* obj, VariableUnserializer* uns,
 861                           int64_t sz, char type);
 862
 863   struct Bucket {
 864     /**
 865      * Buckets are 16 bytes. We use m_aux for our own nefarious purposes.
 866      * It is critical that when we return &data to clients, that they not
 867      * read or write the m_aux field.
 868      */
 869     TypedValueAux data;
 870     inline bool hasStr() const { return IS_STRING_TYPE(data.m_type); }
 871     inline bool hasInt() const { return data.m_type == KindOfInt64; }
 872     inline void setStr(StringData* k, strhash_t h) {
 873       k->incRefCount();
 874       data.m_data.pstr = k;
 875       data.m_type = KindOfString;
 876       data.hash() = int32_t(h) | 0x80000000;
 877     }
 878     inline void setInt(int64_t k) {
 879       data.m_data.num = k;
 880       data.m_type = KindOfInt64;
 881       data.hash() = int32_t(k) | 0x80000000;
 882     }
 883     inline int32_t hash() const {
 884       return data.hash();
 885     }
 886     bool validValue() const {
 887       return (intptr_t(data.m_type) > 0);
 888     }
 889     bool empty() const {
 890       return data.m_type == KindOfUninit;
 891     }
 892     bool tombstone() const {
 893       return data.m_type == KindOfTombstone;
 894     }
 895     void dump();
 896   };
 897
 898  private:
 899   /**
 900    * Set uses a power of two for the table size and quadratic probing to
 901    * resolve hash collisions, similar to the Map class. See the comments
 902    * in the Map class for more details on how the hashtable works and how
 903    * we decide when to grow or shrink the table.
 904    */
 905
 906   Bucket* m_data;
 907   uint m_size;
 908   uint m_load;
 909   uint m_nLastSlot;
 910   int32_t m_version;
 911
 912   size_t numSlots() const {
 913     return m_nLastSlot + 1;
 914   }
 915
 916   // The maximum load factor is 75%.
 917   size_t computeMaxLoad() const {
 918     size_t n = numSlots();
 919     return (n - (n >> 2));
 920   }
 921
 922   // When the map is not empty, the minimum allowed ratio
 923   // of # elements / # slots is 18.75%.
 924   size_t computeMinElements() const {
 925     size_t n = numSlots();
 926     return ((n >> 3) + ((n+8) >> 4));
 927   }
 928
 929   Bucket* fetchBucket(Bucket* data, intptr_t slot) const {
 930     return &data[slot];
 931   }
 932
 933   Bucket* fetchBucket(intptr_t slot) const {
 934     return fetchBucket(m_data, slot);
 935   }
 936
 937   Bucket* find(int64_t h) const;
 938   Bucket* find(const char* k, int len, strhash_t prehash) const;
 939   Bucket* findForInsert(int64_t h) const;
 940   Bucket* findForInsert(const char* k, int len, strhash_t prehash) const;
 941   Bucket* findForNewInsert(size_t h0) const;
 942
 943   void update(int64_t h);
 944   void update(StringData* key);
 945   void erase(Bucket* prev);
 946
 947   void adjustCapacityImpl(int64_t sz);
 948   void adjustCapacity() {
 949     adjustCapacityImpl(m_size);
 950   }
 951
 952   void deleteBuckets();
 953
 954   ssize_t iter_begin() const;
 955   ssize_t iter_next(ssize_t prev) const;
 956   ssize_t iter_prev(ssize_t prev) const;
 957   const TypedValue* iter_value(ssize_t pos) const;
 958   Variant iter_key(ssize_t pos) const { return uninit_null(); }
 959
 960   static void throwBadValueType() ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
 961
 962   friend ObjectData* collectionDeepCopySet(c_Set* st);
 963   friend class c_SetIterator;
 964   friend class c_Vector;
 965   friend class c_Map;
 966   friend class c_StableMap;
 967   friend class ArrayIter;
 968 };
 969
 970 ///////////////////////////////////////////////////////////////////////////////
 971 // class SetIterator
 972
 973 FORWARD_DECLARE_CLASS_BUILTIN(SetIterator);
 974 class c_SetIterator : public ExtObjectData {
 975  public:
 976   DECLARE_CLASS(SetIterator, SetIterator, ObjectData)
 977
 978  public:
 979   explicit c_SetIterator(Class* cls = c_SetIterator::s_cls);
 980   ~c_SetIterator();
 981   void t___construct();
 982   Variant t_current();
 983   Variant t_key();
 984   bool t_valid();
 985   void t_next();
 986   void t_rewind();
 987
 988  private:
 989   SmartPtr<c_Set> m_obj;
 990   ssize_t m_pos;
 991   int32_t m_version;
 992
 993   friend class c_Set;
 994 };
 995
 996 ///////////////////////////////////////////////////////////////////////////////
 997 // class Pair
 998
 999 FORWARD_DECLARE_CLASS_BUILTIN(Pair);
1000 class c_Pair : public ExtObjectDataFlags<ObjectData::PairAttrInit|
1001                                           ObjectData::UseGet|
1002                                           ObjectData::UseSet|
1003                                           ObjectData::UseIsset|
1004                                           ObjectData::UseUnset> {
1005  public:
1006   DECLARE_CLASS(Pair, Pair, ObjectData)
1007
1008  public:
1009   explicit c_Pair(Class* cls = c_Pair::s_cls);
1010   ~c_Pair();
1011   void t___construct();
1012   bool t_isempty();
1013   int64_t t_count();
1014   Object t_items();
1015   Object t_keys();
1016   Object t_view();
1017   Object t_kvzip();
1018   Variant t_at(CVarRef key);
1019   Variant t_get(CVarRef key);
1020   bool t_containskey(CVarRef key);
1021   Array t_toarray();
1022   Object t_getiterator();
1023   Object t_map(CVarRef callback);
1024   Object t_filter(CVarRef callback);
1025   Object t_zip(CVarRef iterable);
1026   String t___tostring();
1027   Variant t___get(Variant name);
1028   Variant t___set(Variant name, Variant value);
1029   bool t___isset(Variant name);
1030   Variant t___unset(Variant name);
1031
1032   static void throwOOB(int64_t key) ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
1033
1034   TypedValue* at(int64_t key) {
1035     if (UNLIKELY(uint64_t(key) >= uint64_t(2))) {
1036       throwOOB(key);
1037       return NULL;
1038     }
1039     return &getElms()[key];
1040   }
1041   TypedValue* get(int64_t key) {
1042     if (uint64_t(key) >= uint64_t(2)) {
1043       return NULL;
1044     }
1045     return &getElms()[key];
1046   }
1047   void add(TypedValue* val) {
1048     assert(val->m_type != KindOfRef);
1049     if (m_size == 2) {
1050       Object e(SystemLib::AllocRuntimeExceptionObject(
1051         "Cannot add a new element to a Pair"));
1052       throw e;
1053     }
1054     tvRefcountedIncRef(val);
1055     TypedValue* tv = &getElms()[m_size];
1056     tv->m_data.num = val->m_data.num;
1057     tv->m_type = val->m_type;
1058     ++m_size;
1059   }
1060   void addInt(int64_t val) {
1061     if (m_size == 2) {
1062       Object e(SystemLib::AllocRuntimeExceptionObject(
1063         "Cannot add a new element to a Pair"));
1064       throw e;
1065     }
1066     TypedValue* tv = &getElms()[m_size];
1067     tv->m_data.num = val;
1068     tv->m_type = KindOfInt64;
1069     ++m_size;
1070   }
1071   bool contains(int64_t key) {
1072     return (uint64_t(key) < uint64_t(2));
1073   }
1074
1075   Array toArrayImpl() const;
1076
1077   Array o_toArray() const;
1078   c_Pair* clone();
1079
1080   static TypedValue* OffsetGet(ObjectData* obj, TypedValue* key);
1081   static void OffsetSet(ObjectData* obj, TypedValue* key, TypedValue* val);
1082   static bool OffsetIsset(ObjectData* obj, TypedValue* key);
1083   static bool OffsetEmpty(ObjectData* obj, TypedValue* key);
1084   static bool OffsetContains(ObjectData* obj, TypedValue* key);
1085   static void OffsetUnset(ObjectData* obj, TypedValue* key);
1086   static void OffsetAppend(ObjectData* obj, TypedValue* val);
1087   static bool Equals(const ObjectData* obj1, const ObjectData* obj2);
1088   static void Unserialize(ObjectData* obj, VariableUnserializer* uns,
1089                           int64_t sz, char type);
1090   int64_t size() const {
1091     return 2;
1092   }
1093
1094  private:
1095   static void throwBadKeyType() ATTRIBUTE_COLD ATTRIBUTE_NORETURN;
1096
1097   uint m_size;
1098
1099   // TODO Can we add something here to make sure elm0 is 16-byte aligned?
1100   TypedValue elm0;
1101   TypedValue elm1;
1102
1103   TypedValue* getElms() const {
1104     return (TypedValue*)(&elm0);
1105   }
1106
1107   friend ObjectData* collectionDeepCopyPair(c_Pair* pair);
1108   friend class c_PairIterator;
1109   friend class c_Vector;
1110   friend class c_Map;
1111   friend class c_StableMap;
1112   friend class ArrayIter;
1113 };
1114
1115 ///////////////////////////////////////////////////////////////////////////////
1116 // class PairIterator
1117
1118 FORWARD_DECLARE_CLASS_BUILTIN(PairIterator);
1119 class c_PairIterator : public ExtObjectData {
1120  public:
1121   DECLARE_CLASS(PairIterator, PairIterator, ObjectData)
1122
1123  public:
1124   explicit c_PairIterator(Class* cls = c_PairIterator::s_cls);
1125   ~c_PairIterator();
1126   void t___construct();
1127   Variant t_current();
1128   Variant t_key();
1129   bool t_valid();
1130   void t_next();
1131   void t_rewind();
1132
1133  private:
1134   SmartPtr<c_Pair> m_obj;
1135   ssize_t m_pos;
1136
1137   friend class c_Pair;
1138 };
1139
1140 TypedValue* collectionGet(ObjectData* obj, TypedValue* key);
1141 void collectionSet(ObjectData* obj, TypedValue* key, TypedValue* val);
1142 bool collectionIsset(ObjectData* obj, TypedValue* key);
1143 bool collectionEmpty(ObjectData* obj, TypedValue* key);
1144 void collectionUnset(ObjectData* obj, TypedValue* key);
1145 void collectionAppend(ObjectData* obj, TypedValue* val);
1146 Variant& collectionOffsetGet(ObjectData* obj, int64_t offset);
1147 Variant& collectionOffsetGet(ObjectData* obj, CStrRef offset);
1148 Variant& collectionOffsetGet(ObjectData* obj, CVarRef offset);
1149 void collectionOffsetSet(ObjectData* obj, int64_t offset, CVarRef val);
1150 void collectionOffsetSet(ObjectData* obj, CStrRef offset, CVarRef val);
1151 void collectionOffsetSet(ObjectData* obj, CVarRef offset, CVarRef val);
1152 bool collectionOffsetContains(ObjectData* obj, CVarRef offset);
1153 bool collectionOffsetIsset(ObjectData* obj, CVarRef offset);
1154 bool collectionOffsetEmpty(ObjectData* obj, CVarRef offset);
1155 int64_t collectionSize(ObjectData* obj);
1156 void collectionReserve(ObjectData* obj, int64_t sz);
1157 void collectionUnserialize(ObjectData* obj, VariableUnserializer* uns,
1158                            int64_t sz, char type);
1159 bool collectionEquals(const ObjectData* obj1, const ObjectData* obj2);
1160 void collectionDeepCopyTV(TypedValue* tv);
1161 ArrayData* collectionDeepCopyArray(ArrayData* arr);
1162 ObjectData* collectionDeepCopyVector(c_Vector* vec);
1163 ObjectData* collectionDeepCopyMap(c_Map* mp);
1164 ObjectData* collectionDeepCopyStableMap(c_StableMap* smp);
1165 ObjectData* collectionDeepCopySet(c_Set* st);
1166 ObjectData* collectionDeepCopyPair(c_Pair* pair);
1167
1168 ///////////////////////////////////////////////////////////////////////////////
1169
1170 inline TypedValue* cvarToCell(const Variant* v) {
1171   return const_cast<TypedValue*>(tvToCell(v->asTypedValue()));
1172 }
1173
1174 inline Variant& collectionOffsetGet(ObjectData* obj, bool offset) {
1175   return collectionOffsetGet(obj, Variant(offset));
1176 }
1177
1178 inline Variant& collectionOffsetGet(ObjectData* obj, double offset) {
1179   return collectionOffsetGet(obj, Variant(offset));
1180 }
1181
1182 inline Variant& collectionOffsetGet(ObjectData* obj, litstr offset) {
1183   return collectionOffsetGet(obj, Variant(offset));
1184 }
1185
1186 inline void collectionOffsetSet(ObjectData* obj, bool offset, CVarRef val) {
1187   collectionOffsetSet(obj, Variant(offset), val);
1188 }
1189
1190 inline void collectionOffsetSet(ObjectData* obj, double offset, CVarRef val) {
1191   collectionOffsetSet(obj, Variant(offset), val);
1192 }
1193
1194 inline void collectionOffsetSet(ObjectData* obj, litstr offset, CVarRef val) {
1195   collectionOffsetSet(obj, Variant(offset), val);
1196 }
1197
1198 inline void collectionOffsetUnset(ObjectData* obj, CVarRef offset) {
1199   TypedValue* key = cvarToCell(&offset);
1200   collectionUnset(obj, key);
1201 }
1202
1203 inline void collectionOffsetAppend(ObjectData* obj, CVarRef val) {
1204   TypedValue* tv = cvarToCell(&val);
1205   collectionAppend(obj, tv);
1206 }
1207
1208 inline bool isOptimizableCollectionClass(const Class* klass) {
1209   return klass == c_Vector::s_cls || klass == c_Map::s_cls ||
1210          klass == c_StableMap::s_cls || klass == c_Pair::s_cls;
1211 }
1212
1213
1214 void collectionSerialize(ObjectData* obj, VariableSerializer* serializer);
1215
1216 ///////////////////////////////////////////////////////////////////////////////
1217
1218 }
1219
1220 #endif // incl_HPHP_EXT_COLLECTION_H_