1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
/*
* Copyright (C) 2013 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef ART_COMPILER_UTILS_GROWABLE_ARRAY_H_
#define ART_COMPILER_UTILS_GROWABLE_ARRAY_H_
#include <stdint.h>
#include <stddef.h>
#include "base/arena_object.h"
namespace art {
// Deprecated
// TODO: Replace all uses with ArenaVector<T>.
template<typename T>
class GrowableArray : public ArenaObject<kArenaAllocGrowableArray> {
public:
GrowableArray(ArenaAllocator* arena, size_t init_length)
: arena_(arena),
num_allocated_(init_length),
num_used_(0) {
elem_list_ = arena_->AllocArray<T>(init_length, kArenaAllocGrowableArray);
}
GrowableArray(ArenaAllocator* arena, size_t init_length, T initial_data)
: arena_(arena),
num_allocated_(init_length),
num_used_(init_length) {
elem_list_ = arena_->AllocArray<T>(init_length, kArenaAllocGrowableArray);
for (size_t i = 0; i < init_length; ++i) {
elem_list_[i] = initial_data;
}
}
bool Contains(T value) const {
for (size_t i = 0; i < num_used_; ++i) {
if (elem_list_[i] == value) {
return true;
}
}
return false;
}
// Expand the list size to at least new length.
void Resize(size_t new_length) {
if (new_length <= num_allocated_) return;
// If it's a small list double the size, else grow 1.5x.
size_t target_length =
(num_allocated_ < 128) ? num_allocated_ << 1 : num_allocated_ + (num_allocated_ >> 1);
if (new_length > target_length) {
target_length = new_length;
}
T* new_array = arena_->AllocArray<T>(target_length, kArenaAllocGrowableArray);
memcpy(new_array, elem_list_, sizeof(T) * num_allocated_);
num_allocated_ = target_length;
elem_list_ = new_array;
}
// NOTE: does not return storage, just resets use count.
void Reset() {
num_used_ = 0;
}
// Insert an element to the end of a list, resizing if necessary.
void Insert(T elem) {
if (num_used_ == num_allocated_) {
Resize(num_used_ + 1);
}
elem_list_[num_used_++] = elem;
}
void InsertAt(size_t index, T elem) {
DCHECK(index <= Size());
Insert(elem);
for (size_t i = Size() - 1; i > index; --i) {
elem_list_[i] = elem_list_[i - 1];
}
elem_list_[index] = elem;
}
void Add(T elem) {
Insert(elem);
}
T Get(size_t index) const {
DCHECK_LT(index, num_used_);
return elem_list_[index];
}
// Overwrite existing element at position index. List must be large enough.
void Put(size_t index, T elem) {
DCHECK_LT(index, num_used_);
elem_list_[index] = elem;
}
void Increment(size_t index) {
DCHECK_LT(index, num_used_);
elem_list_[index]++;
}
/*
* Remove an existing element from list. If there are more than one copy
* of the element, only the first one encountered will be deleted.
*/
// TODO: consider renaming this.
void Delete(T element) {
bool found = false;
for (size_t i = 0; i < num_used_ - 1; i++) {
if (!found && elem_list_[i] == element) {
found = true;
}
if (found) {
elem_list_[i] = elem_list_[i+1];
}
}
// We should either have found the element, or it was the last (unscanned) element.
// if element is not in array, don't touch anything
if(!found && (element != elem_list_[num_used_ - 1]))
return;
num_used_--;
}
void DeleteAt(size_t index) {
for (size_t i = index; i < num_used_ - 1; i++) {
elem_list_[i] = elem_list_[i + 1];
}
num_used_--;
}
size_t GetNumAllocated() const { return num_allocated_; }
size_t Size() const { return num_used_; }
bool IsEmpty() const { return num_used_ == 0; }
T Pop() {
DCHECK_GE(num_used_, (size_t)0);
return elem_list_[--num_used_];
}
T Peek() const {
DCHECK_GE(num_used_, (size_t)0);
return elem_list_[num_used_ - 1];
}
void SetSize(size_t new_size) {
Resize(new_size);
num_used_ = new_size;
}
T* GetRawStorage() const { return elem_list_; }
private:
ArenaAllocator* const arena_;
size_t num_allocated_;
size_t num_used_;
T* elem_list_;
};
} // namespace art
#endif // ART_COMPILER_UTILS_GROWABLE_ARRAY_H_
|
