// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_ZONE_ZONE_LIST_INL_H_
#define V8_ZONE_ZONE_LIST_INL_H_

#include "src/base/macros.h"
#include "src/base/platform/platform.h"
#include "src/utils/memcopy.h"
#include "src/zone/zone-list.h"

namespace v8 {
namespace internal {

template <typename T>
void ZoneList<T>::Add(const T& element, Zone* zone) {
  if (length_ < capacity_) {
    data_[length_++] = element;
  } else {
    ZoneList<T>::ResizeAdd(element, zone);
  }
}

template <typename T>
void ZoneList<T>::AddAll(const ZoneList<T>& other, Zone* zone) {
  AddAll(other.ToVector(), zone);
}

template <typename T>
void ZoneList<T>::AddAll(const Vector<const T>& other, Zone* zone) {
  int length = other.length();
  if (length == 0) return;

  int result_length = length_ + length;
  if (capacity_ < result_length) Resize(result_length, zone);
  if (std::is_trivially_copyable<T>::value) {
    memcpy(&data_[length_], other.begin(), sizeof(T) * length);
  } else {
    std::copy(other.begin(), other.end(), &data_[length_]);
  }
  length_ = result_length;
}

// Use two layers of inlining so that the non-inlined function can
// use the same implementation as the inlined version.
template <typename T>
void ZoneList<T>::ResizeAdd(const T& element, Zone* zone) {
  ResizeAddInternal(element, zone);
}

template <typename T>
void ZoneList<T>::ResizeAddInternal(const T& element, Zone* zone) {
  DCHECK(length_ >= capacity_);
  // Grow the list capacity by 100%, but make sure to let it grow
  // even when the capacity is zero (possible initial case).
  int new_capacity = 1 + 2 * capacity_;
  // Since the element reference could be an element of the list, copy
  // it out of the old backing storage before resizing.
  T temp = element;
  Resize(new_capacity, zone);
  data_[length_++] = temp;
}

template <typename T>
void ZoneList<T>::Resize(int new_capacity, Zone* zone) {
  DCHECK_LE(length_, new_capacity);
  T* new_data = zone->NewArray<T>(new_capacity);
  if (length_ > 0) {
    if (std::is_trivially_copyable<T>::value) {
      MemCopy(new_data, data_, length_ * sizeof(T));
    } else {
      std::copy(&data_[0], &data_[length_], &new_data[0]);
    }
  }
  if (data_) zone->DeleteArray<T>(data_, capacity_);
  data_ = new_data;
  capacity_ = new_capacity;
}

template <typename T>
Vector<T> ZoneList<T>::AddBlock(T value, int count, Zone* zone) {
  int start = length_;
  for (int i = 0; i < count; i++) Add(value, zone);
  return Vector<T>(&data_[start], count);
}

template <typename T>
void ZoneList<T>::Set(int index, const T& elm) {
  DCHECK(index >= 0 && index <= length_);
  data_[index] = elm;
}

template <typename T>
void ZoneList<T>::InsertAt(int index, const T& elm, Zone* zone) {
  DCHECK(index >= 0 && index <= length_);
  Add(elm, zone);
  for (int i = length_ - 1; i > index; --i) {
    data_[i] = data_[i - 1];
  }
  data_[index] = elm;
}

template <typename T>
T ZoneList<T>::Remove(int i) {
  T element = at(i);
  length_--;
  while (i < length_) {
    data_[i] = data_[i + 1];
    i++;
  }
  return element;
}

template <typename T>
void ZoneList<T>::Clear(Zone* zone) {
  if (data_) zone->DeleteArray<T>(data_, capacity_);
  DropAndClear();
}

template <typename T>
void ZoneList<T>::Rewind(int pos) {
  DCHECK(0 <= pos && pos <= length_);
  length_ = pos;
}

template <typename T>
template <class Visitor>
void ZoneList<T>::Iterate(Visitor* visitor) {
  for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
}

template <typename T>
template <typename CompareFunction>
void ZoneList<T>::Sort(CompareFunction cmp) {
  std::sort(begin(), end(),
            [cmp](const T& a, const T& b) { return cmp(&a, &b) < 0; });
#ifdef DEBUG
  for (int i = 1; i < length_; i++) {
    DCHECK_LE(cmp(&data_[i - 1], &data_[i]), 0);
  }
#endif
}

template <typename T>
template <typename CompareFunction>
void ZoneList<T>::StableSort(CompareFunction cmp, size_t s, size_t l) {
  std::stable_sort(begin() + s, begin() + s + l,
                   [cmp](const T& a, const T& b) { return cmp(&a, &b) < 0; });
#ifdef DEBUG
  for (size_t i = s + 1; i < l; i++) {
    DCHECK_LE(cmp(&data_[i - 1], &data_[i]), 0);
  }
#endif
}

}  // namespace internal
}  // namespace v8

#endif  // V8_ZONE_ZONE_LIST_INL_H_