1// Copyright 2017 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_ZONE_ZONE_LIST_INL_H_
6#define V8_ZONE_ZONE_LIST_INL_H_
7
8#include "src/zone/zone.h"
9
10#include "src/base/macros.h"
11#include "src/base/platform/platform.h"
12#include "src/memcopy.h"
13
14namespace v8 {
15namespace internal {
16
17template <typename T>
18void ZoneList<T>::Add(const T& element, Zone* zone) {
19 if (length_ < capacity_) {
20 data_[length_++] = element;
21 } else {
22 ZoneList<T>::ResizeAdd(element, ZoneAllocationPolicy(zone));
23 }
24}
25
26template <typename T>
27void ZoneList<T>::AddAll(const ZoneList<T>& other, Zone* zone) {
28 AddAll(other.ToVector(), zone);
29}
30
31template <typename T>
32void ZoneList<T>::AddAll(const Vector<T>& other, Zone* zone) {
33 int result_length = length_ + other.length();
34 if (capacity_ < result_length)
35 Resize(result_length, ZoneAllocationPolicy(zone));
36 if (std::is_fundamental<T>()) {
37 memcpy(data_ + length_, other.start(), sizeof(*data_) * other.length());
38 } else {
39 for (int i = 0; i < other.length(); i++) data_[length_ + i] = other.at(i);
40 }
41 length_ = result_length;
42}
43
44// Use two layers of inlining so that the non-inlined function can
45// use the same implementation as the inlined version.
46template <typename T>
47void ZoneList<T>::ResizeAdd(const T& element, ZoneAllocationPolicy alloc) {
48 ResizeAddInternal(element, alloc);
49}
50
51template <typename T>
52void ZoneList<T>::ResizeAddInternal(const T& element,
53 ZoneAllocationPolicy alloc) {
54 DCHECK(length_ >= capacity_);
55 // Grow the list capacity by 100%, but make sure to let it grow
56 // even when the capacity is zero (possible initial case).
57 int new_capacity = 1 + 2 * capacity_;
58 // Since the element reference could be an element of the list, copy
59 // it out of the old backing storage before resizing.
60 T temp = element;
61 Resize(new_capacity, alloc);
62 data_[length_++] = temp;
63}
64
65template <typename T>
66void ZoneList<T>::Resize(int new_capacity, ZoneAllocationPolicy alloc) {
67 DCHECK_LE(length_, new_capacity);
68 T* new_data = NewData(new_capacity, alloc);
69 if (length_ > 0) {
70 MemCopy(new_data, data_, length_ * sizeof(T));
71 }
72 ZoneList<T>::DeleteData(data_);
73 data_ = new_data;
74 capacity_ = new_capacity;
75}
76
77template <typename T>
78Vector<T> ZoneList<T>::AddBlock(T value, int count, Zone* zone) {
79 int start = length_;
80 for (int i = 0; i < count; i++) Add(value, zone);
81 return Vector<T>(&data_[start], count);
82}
83
84template <typename T>
85void ZoneList<T>::Set(int index, const T& elm) {
86 DCHECK(index >= 0 && index <= length_);
87 data_[index] = elm;
88}
89
90template <typename T>
91void ZoneList<T>::InsertAt(int index, const T& elm, Zone* zone) {
92 DCHECK(index >= 0 && index <= length_);
93 Add(elm, zone);
94 for (int i = length_ - 1; i > index; --i) {
95 data_[i] = data_[i - 1];
96 }
97 data_[index] = elm;
98}
99
100template <typename T>
101T ZoneList<T>::Remove(int i) {
102 T element = at(i);
103 length_--;
104 while (i < length_) {
105 data_[i] = data_[i + 1];
106 i++;
107 }
108 return element;
109}
110
111template <typename T>
112void ZoneList<T>::Clear() {
113 DeleteData(data_);
114 // We don't call Initialize(0) since that requires passing a Zone,
115 // which we don't really need.
116 data_ = nullptr;
117 capacity_ = 0;
118 length_ = 0;
119}
120
121template <typename T>
122void ZoneList<T>::Rewind(int pos) {
123 DCHECK(0 <= pos && pos <= length_);
124 length_ = pos;
125}
126
127template <typename T>
128template <class Visitor>
129void ZoneList<T>::Iterate(Visitor* visitor) {
130 for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
131}
132
133template <typename T>
134template <typename CompareFunction>
135void ZoneList<T>::Sort(CompareFunction cmp) {
136 ToVector().Sort(cmp, 0, length_);
137#ifdef DEBUG
138 for (int i = 1; i < length_; i++) {
139 DCHECK_LE(cmp(&data_[i - 1], &data_[i]), 0);
140 }
141#endif
142}
143
144template <typename T>
145template <typename CompareFunction>
146void ZoneList<T>::StableSort(CompareFunction cmp, size_t s, size_t l) {
147 ToVector().StableSort(cmp, s, l);
148#ifdef DEBUG
149 for (size_t i = s + 1; i < l; i++) {
150 DCHECK_LE(cmp(&data_[i - 1], &data_[i]), 0);
151 }
152#endif
153}
154
155} // namespace internal
156} // namespace v8
157
158#endif // V8_ZONE_ZONE_LIST_INL_H_
159