// 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/zone/zone.h" #include "src/base/macros.h" #include "src/base/platform/platform.h" #include "src/utils/memcopy.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, ZoneAllocationPolicy(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<T>& other, Zone* zone) { int result_length = length_ + other.length(); if (capacity_ < result_length) Resize(result_length, ZoneAllocationPolicy(zone)); if (std::is_fundamental<T>()) { memcpy(data_ + length_, other.begin(), sizeof(*data_) * other.length()); } else { for (int i = 0; i < other.length(); i++) data_[length_ + i] = other.at(i); } 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, ZoneAllocationPolicy alloc) { ResizeAddInternal(element, alloc); } template <typename T> void ZoneList<T>::ResizeAddInternal(const T& element, ZoneAllocationPolicy alloc) { 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, alloc); data_[length_++] = temp; } template <typename T> void ZoneList<T>::Resize(int new_capacity, ZoneAllocationPolicy alloc) { DCHECK_LE(length_, new_capacity); T* new_data = NewData(new_capacity, alloc); if (length_ > 0) { MemCopy(new_data, data_, length_ * sizeof(T)); } ZoneList<T>::DeleteData(data_); 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() { DeleteData(data_); // We don't call Initialize(0) since that requires passing a Zone, // which we don't really need. data_ = nullptr; capacity_ = 0; length_ = 0; } 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_