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
25namespace art {
26
27// Deprecated
28// TODO: Replace all uses with ArenaVector<T>.
29template<typename T>
30class GrowableArray : public ArenaObject<kArenaAllocGrowableArray> {
31  public:
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
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
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.
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.
74    void Reset() {
75      num_used_ = 0;
76    }
77
78    // Insert an element to the end of a list, resizing if necessary.
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
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
95    void Add(T elem) {
96      Insert(elem);
97    }
98
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.
105    void Put(size_t index, T elem) {
106      DCHECK_LT(index, num_used_);
107      elem_list_[index] = elem;
108    }
109
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.
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
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
142    size_t GetNumAllocated() const { return num_allocated_; }
143
144    size_t Size() const { return num_used_; }
145
146    bool IsEmpty() const { return num_used_ == 0; }
147
148    T Pop() {
149      DCHECK_GE(num_used_, (size_t)0);
150      return elem_list_[--num_used_];
151    }
152
153    T Peek() const {
154      DCHECK_GE(num_used_, (size_t)0);
155      return elem_list_[num_used_ - 1];
156    }
157
158    void SetSize(size_t new_size) {
159      Resize(new_size);
160      num_used_ = new_size;
161    }
162
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