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