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_DEX_GROWABLE_ARRAY_H_
18#define ART_COMPILER_DEX_GROWABLE_ARRAY_H_
19
20#include <stdint.h>
21#include <stddef.h>
22#include "compiler_enums.h"
23#include "arena_allocator.h"
24
25namespace art {
26
27struct CompilationUnit;
28
29// Type of growable list for memory tuning.
30enum OatListKind {
31  kGrowableArrayMisc = 0,
32  kGrowableArrayBlockList,
33  kGrowableArraySSAtoDalvikMap,
34  kGrowableArrayDfsOrder,
35  kGrowableArrayDfsPostOrder,
36  kGrowableArrayDomPostOrderTraversal,
37  kGrowableArrayThrowLaunchPads,
38  kGrowableArraySuspendLaunchPads,
39  kGrowableArraySwitchTables,
40  kGrowableArrayFillArrayData,
41  kGrowableArraySuccessorBlocks,
42  kGrowableArrayPredecessors,
43  kGNumListKinds
44};
45
46template<typename T>
47class GrowableArray {
48  public:
49    class Iterator {
50      public:
51        explicit Iterator(GrowableArray* g_list)
52          : idx_(0),
53            g_list_(g_list) {}
54
55        // NOTE: returns 0/NULL when no next.
56        // TODO: redo to make usage consistent with other iterators.
57        T Next() {
58          if (idx_ >= g_list_->Size()) {
59            return 0;
60          } else {
61            return g_list_->Get(idx_++);
62          }
63        }
64
65        void Reset() {
66          idx_ = 0;
67        }
68
69        static void* operator new(size_t size, ArenaAllocator* arena) {
70          return arena->Alloc(sizeof(GrowableArray::Iterator), ArenaAllocator::kAllocGrowableArray);
71        };
72        static void operator delete(void* p) {}  // Nop.
73
74      private:
75        size_t idx_;
76        GrowableArray* const g_list_;
77    };
78
79    GrowableArray(ArenaAllocator* arena, size_t init_length, OatListKind kind = kGrowableArrayMisc)
80      : arena_(arena),
81        num_allocated_(init_length),
82        num_used_(0),
83        kind_(kind) {
84      elem_list_ = static_cast<T*>(arena_->Alloc(sizeof(T) * init_length,
85                                                 ArenaAllocator::kAllocGrowableArray));
86    };
87
88
89    // Expand the list size to at least new length.
90    void Resize(size_t new_length) {
91      if (new_length <= num_allocated_) return;
92      // If it's a small list double the size, else grow 1.5x.
93      size_t target_length =
94          (num_allocated_ < 128) ? num_allocated_ << 1 : num_allocated_ + (num_allocated_ >> 1);
95      if (new_length > target_length) {
96         target_length = new_length;
97      }
98      T* new_array = static_cast<T*>(arena_->Alloc(sizeof(T) * target_length,
99                                                   ArenaAllocator::kAllocGrowableArray));
100      memcpy(new_array, elem_list_, sizeof(T) * num_allocated_);
101      num_allocated_ = target_length;
102      elem_list_ = new_array;
103    };
104
105    // NOTE: does not return storage, just resets use count.
106    void Reset() {
107      num_used_ = 0;
108    }
109
110    // Insert an element to the end of a list, resizing if necessary.
111    void Insert(T elem) {
112      if (num_used_ == num_allocated_) {
113        Resize(num_used_ + 1);
114      }
115      elem_list_[num_used_++] = elem;
116    };
117
118    T Get(size_t index) const {
119      DCHECK_LT(index, num_used_);
120      return elem_list_[index];
121    };
122
123    // Overwrite existing element at position index.  List must be large enough.
124    void Put(size_t index, T elem) {
125      DCHECK_LT(index, num_used_);
126      elem_list_[index] = elem;
127    }
128
129    void Increment(size_t index) {
130      DCHECK_LT(index, num_used_);
131      elem_list_[index]++;
132    }
133
134    void Delete(T element) {
135      bool found = false;
136      for (size_t i = 0; i < num_used_ - 1; i++) {
137        if (!found && elem_list_[i] == element) {
138          found = true;
139        }
140        if (found) {
141          elem_list_[i] = elem_list_[i+1];
142        }
143      }
144      // We should either have found the element, or it was the last (unscanned) element.
145      DCHECK(found || (element == elem_list_[num_used_ - 1]));
146      num_used_--;
147    };
148
149    size_t GetNumAllocated() const { return num_allocated_; }
150
151    size_t Size() const { return num_used_; }
152
153    T* GetRawStorage() const { return elem_list_; }
154
155    static void* operator new(size_t size, ArenaAllocator* arena) {
156      return arena->Alloc(sizeof(GrowableArray<T>), ArenaAllocator::kAllocGrowableArray);
157    };
158    static void operator delete(void* p) {}  // Nop.
159
160  private:
161    ArenaAllocator* const arena_;
162    size_t num_allocated_;
163    size_t num_used_;
164    OatListKind kind_;
165    T* elem_list_;
166};
167
168}  // namespace art
169
170#endif  // ART_COMPILER_DEX_GROWABLE_ARRAY_H_
171