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
|
/*
* 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_SRC_COMPILER_DEX_GROWABLE_LIST_H_
#define ART_SRC_COMPILER_DEX_GROWABLE_LIST_H_
#include <stdint.h>
#include <stddef.h>
#include "compiler_enums.h"
#include "arena_allocator.h"
namespace art {
struct CompilationUnit;
// Type of growable list for memory tuning.
enum OatListKind {
kGrowableArrayMisc = 0,
kGrowableArrayBlockList,
kGrowableArraySSAtoDalvikMap,
kGrowableArrayDfsOrder,
kGrowableArrayDfsPostOrder,
kGrowableArrayDomPostOrderTraversal,
kGrowableArrayThrowLaunchPads,
kGrowableArraySuspendLaunchPads,
kGrowableArraySwitchTables,
kGrowableArrayFillArrayData,
kGrowableArraySuccessorBlocks,
kGrowableArrayPredecessors,
kGNumListKinds
};
template<typename T>
class GrowableArray {
public:
class Iterator {
public:
Iterator(GrowableArray* g_list)
: idx_(0),
g_list_(g_list) {};
// NOTE: returns 0/NULL when no next.
// TODO: redo to make usage consistent with other iterators.
T Next() {
if (idx_ >= g_list_->Size()) {
return 0;
} else {
return g_list_->Get(idx_++);
}
}
void Reset() {
idx_ = 0;
}
static void* operator new(size_t size, ArenaAllocator* arena) {
return arena->NewMem(sizeof(GrowableArray::Iterator), true, ArenaAllocator::kAllocGrowableArray);
};
static void operator delete(void* p) {}; // Nop.
private:
size_t idx_;
GrowableArray* const g_list_;
};
GrowableArray(ArenaAllocator* arena, size_t init_length, OatListKind kind = kGrowableArrayMisc)
: arena_(arena),
num_allocated_(init_length),
num_used_(0),
kind_(kind) {
elem_list_ = static_cast<T*>(arena_->NewMem(sizeof(T) * init_length, true,
ArenaAllocator::kAllocGrowableArray));
};
// 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 = static_cast<T*>(arena_->NewMem(sizeof(T) * target_length, true,
ArenaAllocator::kAllocGrowableArray));
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;
};
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]++;
}
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.
DCHECK(found || (element == elem_list_[num_used_ - 1]));
num_used_--;
};
size_t GetNumAllocated() const { return num_allocated_; }
size_t Size() const { return num_used_; }
T* GetRawStorage() const { return elem_list_; }
static void* operator new(size_t size, ArenaAllocator* arena) {
return arena->NewMem(sizeof(GrowableArray<T>), true, ArenaAllocator::kAllocGrowableArray);
};
static void operator delete(void* p) {}; // Nop.
private:
ArenaAllocator* const arena_;
size_t num_allocated_;
size_t num_used_;
OatListKind kind_;
T* elem_list_;
};
} // namespace art
#endif // ART_SRC_COMPILER_DEX_GROWABLE_LIST_H_
|
