/*
   +----------------------------------------------------------------------+
   | HipHop for PHP                                                       |
   +----------------------------------------------------------------------+
   | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   +----------------------------------------------------------------------+
   | This source file is subject to version 3.01 of the PHP license,      |
   | that is bundled with this package in the file LICENSE, and is        |
   | available through the world-wide-web at the following url:           |
   | http://www.php.net/license/3_01.txt                                  |
   | If you did not receive a copy of the PHP license and are unable to   |
   | obtain it through the world-wide-web, please send a note to          |
   | license@php.net so we can mail you a copy immediately.               |
   +----------------------------------------------------------------------+
*/

#ifndef incl_HPHP_SET_ARRAY_H_
#define incl_HPHP_SET_ARRAY_H_

#include "hphp/runtime/base/array-data.h"
#include "hphp/runtime/base/array-common.h"
#include "hphp/runtime/base/data-walker.h"
#include "hphp/runtime/base/hash-table.h"
#include "hphp/runtime/base/tv-val.h"
#include "hphp/runtime/base/string-data.h"
#include "hphp/runtime/base/tv-mutate.h"
#include "hphp/runtime/base/typed-value.h"

#include <folly/portability/Constexpr.h>

namespace HPHP {

//////////////////////////////////////////////////////////////////////

namespace jit {
struct ArrayOffsetProfile;
}
struct APCArray;
struct APCHandle;

struct SetArrayElm {
  using hash_t = strhash_t;
  /*
   * We store elements of the set here, but also some information
   * local to this array: tv.m_aux.u_hash contains either a negative
   * number (for an int key) or a string hashcode (31-bit and thus
   * non-negative).  The field tv.m_type == kInvalidDataType is used
   * to mark a deleted element (tombstone); tv.m_type == KindOfUninit
   * is used for debugging to mark empty elements.
   */
  TypedValueAux tv;

  static auto constexpr kTombstone = kInvalidDataType;
  static auto constexpr kEmpty = KindOfUninit;

  void setStrKey(StringData* k, strhash_t h) {
    assertx(isEmpty());
    k->incRefCount();
    tv.m_type = KindOfString;
    tv.m_data.pstr = k;
    tv.hash() = h;
    assertx(!isInvalid());
  }

  void setIntKey(int64_t k, inthash_t h) {
    assertx(isEmpty());
    tv.m_type = KindOfInt64;
    tv.m_data.num = k;
    tv.hash() = h | STRHASH_MSB;
    assertx(!isInvalid());
    assertx(hasIntKey());
  }

  void setTombstone() {
    tv.m_type = kTombstone;
    static_assert(!isRefcountedType(kTombstone), "");
  }

  bool isEmpty() const {
    return tv.m_type == kEmpty;
  }

  // Members below here are required for HashTable implemenation.
  ALWAYS_INLINE const TypedValue* datatv() const {
    return &tv;
  }

  ALWAYS_INLINE bool hasStrKey() const {
    /*
     * Currently string hash is 31-bit, thus it saves us some
     * instructions to encode int keys as a negative hash, so
     * that we don't have to care about the MSB when working
     * with strhash_t.
     */
    assertx(!isInvalid());
    return tv.hash() >= 0;
  }

  ALWAYS_INLINE StringData* strKey() const {
    assertx(hasStrKey());
    return tv.m_data.pstr;
  }

  ALWAYS_INLINE bool hasIntKey() const {
    assertx(!isInvalid());
    return tv.hash() < 0;
  }

  ALWAYS_INLINE int64_t intKey() const {
    return tv.m_data.num;
  }

  ALWAYS_INLINE
  Cell getKey() const {
    assertx(!isInvalid());
    Cell out;
    cellDup(tv, out);
    return out;
  }


  ALWAYS_INLINE hash_t hash() const {
    return tv.hash();
  }

  ALWAYS_INLINE bool isTombstone() const {
    return tv.m_type == kTombstone;
  }

  ALWAYS_INLINE bool isInvalid() const {
    return tv.m_type == kEmpty || isTombstone();
  }

  static constexpr ptrdiff_t keyOff() {
    return offsetof(SetArrayElm, tv) + offsetof(TypedValue, m_data.pstr);
  }
  static constexpr ptrdiff_t dataOff() {
    return offsetof(SetArrayElm, tv) + offsetof(TypedValue, m_data);
  }
  static constexpr ptrdiff_t typeOff() {
    return offsetof(SetArrayElm, tv) + offsetof(TypedValue, m_type);
  }
  static constexpr ptrdiff_t hashOff() {
    return offsetof(SetArrayElm, tv) + offsetof(TypedValue, m_aux);
  }
};

//////////////////////////////////////////////////////////////////////

struct SetArray final : ArrayData,
                        array::HashTable<SetArray, SetArrayElm>,
                        type_scan::MarkCollectable<SetArray> {

//////////////////////////////////////////////////////////////////////
// Set Layout

public:
  void scan(type_scan::Scanner& scanner) const {
    auto const elms = data();
    scanner.scan(*elms, m_used * sizeof(*elms));
  }

//////////////////////////////////////////////////////////////////////
// Initialization, Copies, and Conversions

public:
  /*
   * Allocate a new, empty, request-local set array, with enough space
   * reserved for `size' members.
   *
   * The returned array is already incref'd.
   */
  static ArrayData* MakeReserveSet(uint32_t size);
  static constexpr auto MakeReserve = &MakeReserveSet;

  static ArrayData* MakeSet(uint32_t size, const TypedValue* values);

  /*
   * Allocate an uncounted SetArray and copy the values from the
   * input 'array' into the uncounted one.
   *
   * If withApcTypedValue is true, space for an APCTypedValue will be
   * allocated in front of the returned pointer.
   */
  static ArrayData* MakeUncounted(ArrayData* array,
                                  bool withApcTypedValue = false,
                                  DataWalker::PointerMap* m = nullptr);
  static ArrayData* MakeUncounted(ArrayData* array, int) = delete;
  static ArrayData* MakeUncounted(ArrayData* array, size_t) = delete;

  static void Release(ArrayData*);
  static void ReleaseUncounted(ArrayData*);
  /*
   * Recursively register {allocation, rootAPCHandle} with APCGCManager
   */
  static void RegisterUncountedAllocations(ArrayData* ad,
                                           APCHandle* rootAPCHandle);

  /*
   * Safe downcast helpers.
   */
  static SetArray* asSet(ArrayData* ad);
  static const SetArray* asSet(const ArrayData* ad);

  static ArrayData* MakeSetFromAPC(const APCArray*);

  /*
   * For array initialization using KeysetInit.
   */
  static ArrayData* AddToSet(ArrayData*, int64_t);
  static ArrayData* AddToSetInPlace(ArrayData*, int64_t);
  static ArrayData* AddToSet(ArrayData*, StringData*);
  static ArrayData* AddToSetInPlace(ArrayData*, StringData*);

private:
  static bool ClearElms(Elm* elms, uint32_t count);

  enum class AllocMode : bool { Request, Static };

  static SetArray* CopySet(const SetArray& other, AllocMode);
  static SetArray* CopyReserve(const SetArray* src, size_t expectedSize);
  SetArray* copySet() const { return CopySet(*this, AllocMode::Request); }

  template <typename Init, IntishCast IC>
  static ArrayData* ToArrayImpl(ArrayData*, bool);

private:
  SetArray() = delete;
  SetArray(const SetArray&) = delete;
  SetArray& operator=(const SetArray&) = delete;
  ~SetArray() = delete;

//////////////////////////////////////////////////////////////////////
// Iteration

private:
  Cell getElm(ssize_t ei) const;

public:
  const TypedValue* tvOfPos(uint32_t) const;

  template <class F, bool inc = true>
  static void Iterate(const SetArray* a, F fn) {
    if (inc) a->incRefCount();
    SCOPE_EXIT { if (inc) decRefArr(const_cast<SetArray*>(a)); };
    auto const* elm = a->data();
    for (auto i = a->m_used; i--; elm++) {
      if (LIKELY(!elm->isTombstone())) {
        if (ArrayData::call_helper(fn, elm->tv)) break;
      }
    }
  }

//////////////////////////////////////////////////////////////////////
// Sorting

public:
  static ArrayData* EscalateForSort(ArrayData* ad, SortFunction);

  static void Sort(ArrayData*, int, bool);
  static void Ksort(ArrayData*, int, bool);
  static constexpr auto Asort = &Ksort;

  static bool Usort(ArrayData*, const Variant&);
  static bool Uksort(ArrayData*, const Variant&);
  static constexpr auto Uasort = &Uksort;

private:
  template <typename AccessorT>
  SortFlavor preSort(const AccessorT& acc, bool checkTypes);
  void postSort(bool);

//////////////////////////////////////////////////////////////////////
// Set Internals

private:
  bool checkInvariants() const;

  /*
   * These functions require !isFull().  The index of the position
   * where the element was inserted is returned.
   */
  void insert(int64_t k, inthash_t h);
  void insert(int64_t k);
  void insert(StringData* k, strhash_t h);
  void insert(StringData* k);

  ssize_t findElm(const Elm& e) const;

  void erase(int32_t);

  /*
   * Append idx at the end of the linked list containing the set
   * insertion order.
   */
  void linkLast(uint32_t idx);

  /*
   * Helper routine for inserting elements into a new array
   * when grow()ing the array, that also checks for potentially
   * unbalanced entries because of hash collision.
   */
  SetArray* insertCheckUnbalanced(SetArray* ad, Elm* table,
                                  uint32_t mask,
                                  Elm* iter, Elm* stop);


  /*
   * Returns a copy of the set with twice the scale of the original. It
   * rebuilds the hash table, but it does not compact the elements. If copy is
   * true, it will copy elements instead of taking ownership of them.
   */
  SetArray* grow(bool copy);

  /*
   * prepareForInsert ensures that the set has room to insert an element and
   * has a refcount of 1, copying if requested and growing if needed.
   */
  SetArray* prepareForInsert(bool copy);

  /*
   * compact() removes all tombstones from the hash table by going
   * through the inner linked list.
   */
  void compact();

  /*
   * Zombie arrays!
   */
  bool isZombie() const { return m_used + 1 == 0; }
  void setZombie() { m_used = -uint32_t{1}; }

  /*
   * Comparison helper.
   */
  static bool EqualHelper(const ArrayData*, const ArrayData*, bool);

//////////////////////////////////////////////////////////////////////
// Elements

public:

//////////////////////////////////////////////////////////////////////
// JIT Supporting Routines

  static constexpr ptrdiff_t tvOff(uint32_t pos) {
    return dataOff() + pos * sizeof(Elm) + offsetof(Elm, tv);
  }

//////////////////////////////////////////////////////////////////////
// Reference Counting

public:
  using ArrayData::decRefCount;
  using ArrayData::hasMultipleRefs;
  using ArrayData::hasExactlyOneRef;
  using ArrayData::decWillRelease;
  using ArrayData::incRefCount;

//////////////////////////////////////////////////////////////////////
// Misc ArrayData Methods

  /*
   * These using directives ensure the full set of overloaded functions
   * are visible in this class, to avoid triggering implicit conversions
   * from a const Variant& key to int64.
   */
private:
  using ArrayData::exists;
  using ArrayData::at;
  using ArrayData::rval;
  using ArrayData::lval;
  using ArrayData::lvalNew;
  using ArrayData::set;
  using ArrayData::remove;
  using ArrayData::release;

//////////////////////////////////////////////////////////////////////
// Friends

private:
  friend struct array::HashTable<SetArray, SetArrayElm>;
  friend struct MemoryProfile;
  friend struct jit::ArrayOffsetProfile;
  friend struct EmptyArray;
  friend struct PackedArray;
  friend struct StructArray;
  friend struct MixedArray;
  friend struct HashCollection;
  friend struct BaseMap;
  friend struct c_Map;
  friend struct c_ImmMap;
  friend struct BaseSet;
  friend struct c_Set;
  friend struct c_ImmSet;
  friend struct c_AwaitAllWaitHandle;

  friend size_t getMemSize(const ArrayData*, bool);
  template <typename AccessorT, class ArrayT>
  friend SortFlavor genericPreSort(ArrayT&, const AccessorT&, bool);

//////////////////////////////////////////////////////////////////////
// ArrayData API

public:
  static tv_rval NvTryGetInt(const ArrayData*, int64_t);
  static tv_rval NvTryGetStr(const ArrayData*, const StringData*);
  static tv_rval RvalIntStrict(const ArrayData* ad, int64_t k) {
    return NvTryGetInt(ad, k);
  }
  static tv_rval RvalStrStrict(const ArrayData* ad, const StringData* k) {
    return NvTryGetStr(ad, k);
  }
  static tv_rval RvalAtPos(const ArrayData* ad, ssize_t pos) {
    return GetValueRef(ad, pos);
  }
  static size_t Vsize(const ArrayData*);
  static tv_rval GetValueRef(const ArrayData*, ssize_t);
  static bool IsVectorData(const ArrayData*);
  static bool ExistsInt(const ArrayData*, int64_t);
  static bool ExistsStr(const ArrayData*, const StringData*);
  static arr_lval LvalInt(ArrayData*, int64_t, bool);
  static arr_lval LvalIntRef(ArrayData*, int64_t, bool);
  static arr_lval LvalStr(ArrayData*, StringData*, bool);
  static arr_lval LvalStrRef(ArrayData*, StringData*, bool);
  static arr_lval LvalNew(ArrayData*, bool);
  static arr_lval LvalNewRef(ArrayData*, bool);
  static ArrayData* SetInt(ArrayData*, int64_t, Cell);
  static constexpr auto SetIntInPlace = &SetInt;
  static ArrayData* SetStr(ArrayData*, StringData*, Cell);
  static constexpr auto SetStrInPlace = &SetStr;
  static ArrayData* SetWithRefInt(ArrayData*, int64_t, TypedValue);
  static constexpr auto SetWithRefIntInPlace = &SetWithRefInt;
  static ArrayData* SetWithRefStr(ArrayData*, StringData*, TypedValue);
  static constexpr auto SetWithRefStrInPlace = &SetWithRefStr;
  static ArrayData* RemoveInt(ArrayData*, int64_t);
  static ArrayData* RemoveIntInPlace(ArrayData*, int64_t);
  static ArrayData* RemoveStr(ArrayData*, const StringData*);
  static ArrayData* RemoveStrInPlace(ArrayData*, const StringData*);
  static ArrayData* Copy(const ArrayData*);
  static ArrayData* CopyStatic(const ArrayData*);
  static ArrayData* Append(ArrayData*, Cell);
  static ArrayData* AppendInPlace(ArrayData*, Cell);
  static ArrayData* AppendWithRef(ArrayData*, TypedValue);
  static ArrayData* AppendWithRefInPlace(ArrayData*, TypedValue);
  static ArrayData* PlusEq(ArrayData*, const ArrayData*);
  static ArrayData* Merge(ArrayData*, const ArrayData*);
  static ArrayData* Pop(ArrayData*, Variant&);
  static ArrayData* Dequeue(ArrayData*, Variant&);
  static ArrayData* Prepend(ArrayData*, Cell);
  static void Renumber(ArrayData*);
  static void OnSetEvalScalar(ArrayData*);
  static ArrayData* Escalate(const ArrayData*);
  static constexpr auto ToDict = &ArrayCommon::ToDict;
  static constexpr auto ToVec = &ArrayCommon::ToVec;
  static ArrayData* ToPHPArray(ArrayData*, bool);
  static ArrayData* ToPHPArrayIntishCast(ArrayData*, bool);
  static ArrayData* ToKeyset(ArrayData*, bool);
  static constexpr auto ToVArray = &ArrayCommon::ToVArray;
  static ArrayData* ToDArray(ArrayData*, bool);
  static ArrayData* ToShape(ArrayData*, bool);
  static bool Equal(const ArrayData*, const ArrayData*);
  static bool NotEqual(const ArrayData*, const ArrayData*);
  static bool Same(const ArrayData*, const ArrayData*);
  static bool NotSame(const ArrayData*, const ArrayData*);

//////////////////////////////////////////////////////////////////////

private:
  template<class K>
  static ArrayData* RemoveImpl(ArrayData*, K key, bool, SetArrayElm::hash_t);
  static ArrayData* AppendImpl(ArrayData*, Cell, bool);

private:
  struct Initializer;
  static Initializer s_initializer;

  uint64_t m_padding;
};

HASH_TABLE_CHECK_OFFSETS(SetArray, SetArrayElm)
//////////////////////////////////////////////////////////////////////

}

#endif // incl_HPHP_SET_ARRAY_H_
