ArrayData *VectorArray::prepend(CVarRef v, bool copy) {
  if (UNLIKELY(m_size == m_capacity)) {
    ZendArray *a = escalateToNonEmptyZendArray();
    ArrayData *aa UNUSED = a->prepend(v, false);
    assert(!aa);
    return a;
  }
  if (UNLIKELY(copy)) {
    ArrayData *a = UNLIKELY(m_size >= FixedSize && Util::isPowerOfTwo(m_size)) ?
      // in this case, we would escalate in the capacity check anyway
      static_cast<ArrayData*>(escalateToNonEmptyZendArray()) :
      static_cast<ArrayData*>(NEW(VectorArray)(this));
    ArrayData *aa UNUSED = a->prepend(v, false);
    assert(!aa);
    return a;
  }
  checkSize();
  for (uint i = m_size; i > 0; i--) {
    // copying TV's by value, intentionally not refcounting.
    m_elems[i] = m_elems[i-1];
  }
  tvAsUninitializedVariant(&m_elems[0]).constructValHelper(v);
  m_size++;
  // To match PHP-like semantics, the prepend operation resets the array's
  // internal iterator
  m_pos = (ssize_t)0;
  return nullptr;
}

ArrayData *VectorArray::lval(litstr k, Variant *&ret, bool copy,
                             bool checkExist /* = false */) {
  ZendArray *a = escalateToZendArray();
  StringData sd(k, AttachLiteral);
  a->addLvalImpl(&sd, sd.hash(), &ret);
  return a;
}

ZendArray *VectorArray::escalateToNonEmptyZendArray() const {
  assert(m_size);
  ZendArray *ret;
  ZendArray::Bucket *p[256], **pp;
  if (LIKELY(m_size < 256)) {
    pp = p;
  } else {
    pp =
      (ZendArray::Bucket **)malloc(sizeof(ZendArray::Bucket *) * (m_size + 1));
  }
  DECLARE_ALLOCATOR(a, ZendArray::Bucket, Bucket);
  for (int64 i = 0; i < m_size; i++) {
    CVarRef v = tvAsCVarRef(&m_elems[i]);
    pp[i] = NEWALLOC(a) ZendArray::Bucket(i, withRefBind(v));
  }
  pp[m_size] = nullptr;
  ret = NEW(ZendArray)(m_size, m_size, pp);
  if (UNLIKELY(pp != p)) free(pp);
  if (m_pos != ArrayData::invalid_index) {
    ret->setPosition(ret->getIndex(m_pos));
  } else {
    ret->setPosition(0);
  }
  return ret;
}

ArrayData *VectorArray::lval(int64 k, Variant *&ret, bool copy,
                             bool checkExist /* = false */) {
  ret = inRange(k, m_size) ? &tvAsVariant(&m_elems[k]) : nullptr;
  if (ret == nullptr && k != m_size) {
    ZendArray *a = escalateToZendArray();
    a->addLvalImpl(k, &ret, false);
    return a;
  }
  if (LIKELY(!copy)) {
    if (ret) return nullptr;
    assert(m_size == k);
    checkSize();
    Variant& v = tvAsUninitializedVariant(&m_elems[k]);
    v.setUninitNull();
    ret = &v;
    checkInsertIterator((ssize_t)k);
    m_size++;
    return nullptr;
  }
  if (checkExist && ret && (ret->isReferenced() || ret->isObject())) {
    return nullptr;
  }
  VectorArray *a = NEW(VectorArray)(this);
  if (ret) {
    Variant& v = tvAsVariant(&a->m_elems[k]);
    ret = &v;
    assert(ret);
    return a;
  }
  assert(m_size == k);
  a->VectorArray::lvalNew(ret, false);
  return a;
}

ArrayData *ZendArray::append(const ArrayData *elems, ArrayOp op, bool copy) {
  if (UNLIKELY(copy)) {
    ZendArray *a = copyImpl();
    a->append(elems, op, false);
    return a;
  }

  if (op == Plus) {
    for (ArrayIter it(elems); !it.end(); it.next()) {
      Variant key = it.first();
      CVarRef value = it.secondRef();
      if (key.isNumeric()) {
        addValWithRef(key.toInt64(), value);
      } else {
        addValWithRef(key.getStringData(), value);
      }
    }
  } else {
    ASSERT(op == Merge);
    for (ArrayIter it(elems); !it.end(); it.next()) {
      Variant key = it.first();
      CVarRef value = it.secondRef();
      if (key.isNumeric()) {
        nextInsertWithRef(value);
      } else {
        Variant *p;
        StringData *sd = key.getStringData();
        addLvalImpl(sd, sd->hash(), &p, true);
        p->setWithRef(value);
      }
    }
  }
  return NULL;
}

ArrayData *VectorArray::addLval(CVarRef k, Variant *&ret, bool copy) {
  ASSERT(!exists(k));
  Variant::TypedValueAccessor tva = k.getTypedAccessor();
  if (isIntKey(tva)) return VectorArray::addLval(getIntKey(tva), ret, copy);
  ASSERT(k.isString());
  ZendArray *a = escalateToZendArray();
  a->addLval(StrNR(getStringKey(tva)), ret, false);
  return a;
}

ArrayData *ZendArray::addLval(int64 k, Variant *&ret, bool copy) {
  ASSERT(!exists(k));
  if (UNLIKELY(copy)) {
    ZendArray *result = copyImpl();
    result->addLvalImpl(k, &ret, false);
    return result;
  }
  addLvalImpl(k, &ret, false);
  return NULL;
}

HOT_FUNC_HPHP
ArrayData *ZendArray::append(CVarRef v, bool copy) {
  if (UNLIKELY(copy)) {
    ZendArray *a = copyImpl();
    a->nextInsert(v);
    return a;
  }
  nextInsert(v);
  return NULL;
}

inline ALWAYS_INLINE ZendArray *ZendArray::copyImplHelper(bool sma) const {
  ZendArray *target = LIKELY(sma) ? NEW(ZendArray)(m_size)
                                  : new ZendArray(m_size);
  Bucket *last = NULL;
  for (Bucket *p = m_pListHead; p; p = p->pListNext) {
    Bucket *np = LIKELY(sma) ? NEW(Bucket)(Variant::noInit)
                             : new Bucket(Variant::noInit);
    np->data.constructWithRefHelper(p->data, this);
    uint nIndex;
    if (p->hasStrKey()) {
      np->setStrKey(p->skey, p->hash());
      nIndex = p->hash() & target->m_nTableMask;
    } else {
      np->setIntKey(p->ikey);
      nIndex = p->ikey & target->m_nTableMask;
    }

    np->pNext = target->m_arBuckets[nIndex];
    target->m_arBuckets[nIndex] = np;

    if (last) {
      last->pListNext = np;
      np->pListLast = last;
    } else {
      target->m_pListHead = np;
      np->pListLast = NULL;
    }
    last = np;
  }
  if (last) last->pListNext = NULL;
  target->m_pListTail = last;

  target->m_size = m_size;
  target->m_nNextFreeElement = m_nNextFreeElement;

  Bucket *p = reinterpret_cast<Bucket *>(m_pos);
  if (p == NULL) {
    target->m_pos = (ssize_t)0;
  } else if (p == m_pListHead) {
    target->m_pos = (ssize_t)target->m_pListHead;
  } else {
    if (p->hasStrKey()) {
      target->m_pos = (ssize_t)target->find(p->skey->data(),
                                            p->skey->size(),
                                            (int64)p->hash());
    } else {
      target->m_pos = (ssize_t)target->find((int64)p->ikey);
    }
  }
  return target;
}

HOT_FUNC_HPHP
ArrayData *VectorArray::set(int64 k, CVarRef v, bool copy) {
  if (inRange(k, m_size)) {
    if (copy) {
      VectorArray *a = NEW(VectorArray)(this);
      tvAsVariant(&a->m_elems[k]).assignVal(v);
      return a;
    }
    tvAsVariant(&m_elems[k]).assignVal(v);
    return nullptr;
  }
  if (k == m_size) return VectorArray::append(v, copy);
  ZendArray *a = escalateToZendArray();
  a->add(k, v, false);
  return a;
}

ZendArray *ZendArray::copyImpl() const {
  ZendArray *target = NEW(ZendArray)(m_nNumOfElements);
  Bucket *last = NULL;
  for (Bucket *p = m_pListHead; p; p = p->pListNext) {
    Bucket *np = NEW(Bucket)(Variant::noInit);
    np->data.constructWithRefHelper(p->data, this);
    np->h = p->h;
    if (p->key) {
      np->key = p->key;
      np->key->incRefCount();
    }

    uint nIndex = (p->h & target->m_nTableMask);
    np->pNext = target->m_arBuckets[nIndex];
    target->m_arBuckets[nIndex] = np;

    if (last) {
      last->pListNext = np;
      np->pListLast = last;
    } else {
      target->m_pListHead = np;
      np->pListLast = NULL;
    }
    last = np;
  }
  if (last) last->pListNext = NULL;
  target->m_pListTail = last;

  target->m_nNumOfElements = m_nNumOfElements;
  target->m_nNextFreeElement = m_nNextFreeElement;

  Bucket *p = reinterpret_cast<Bucket *>(m_pos);
  if (p == NULL) {
    target->m_pos = (ssize_t)0;
  } else if (p == m_pListHead) {
    target->m_pos = (ssize_t)target->m_pListHead;
  } else {
    if (p->key) {
      target->m_pos = (ssize_t)target->find(p->key->data(),
                                            p->key->size(),
                                            (int64)p->h);
    } else {
      target->m_pos = (ssize_t)target->find((int64)p->h);
    }
  }
  return target;
}

HOT_FUNC_HPHP
ArrayData *ZendArray::add(CStrRef k, CVarRef v, bool copy) {
  ASSERT(!exists(k));
  if (UNLIKELY(copy)) {
    ZendArray *result = copyImpl();
    result->add(k, v, false);
    return result;
  }
  int64 h = k->hash();
  Bucket *p = NEW(Bucket)(v);
  p->setStrKey(k.get(), h);
  uint nIndex = (h & m_nTableMask);
  CONNECT_TO_BUCKET_LIST(p, m_arBuckets[nIndex]);
  SET_ARRAY_BUCKET_HEAD(m_arBuckets, nIndex, p);
  CONNECT_TO_GLOBAL_DLLIST(p);
  if (++m_size > tableSize()) {
    resize();
  }
  return NULL;
}

ArrayData *ZendArray::lval(int64 k, Variant *&ret, bool copy,
                           bool checkExist /* = false */) {
  if (!copy) {
    addLvalImpl(k, &ret);
    return NULL;
  }
  if (!checkExist) {
    ZendArray *a = copyImpl();
    a->addLvalImpl(k, &ret);
    return a;
  }
  Bucket *p = find(k);
  if (p &&
      (p->data.isReferenced() || p->data.isObject())) {
    ret = &p->data;
    return NULL;
  }
  ZendArray *a = copyImpl();
  a->addLvalImpl(k, &ret, p);
  return a;
}