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 25 namespace art { 26 27 struct CompilationUnit; 28 29 // Type of growable list for memory tuning. 30 enum 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 46 template<typename T> 47 class GrowableArray { 48 public: 49 class Iterator { 50 public: Iterator(GrowableArray * g_list)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. Next()57 T Next() { 58 if (idx_ >= g_list_->Size()) { 59 return 0; 60 } else { 61 return g_list_->Get(idx_++); 62 } 63 } 64 Reset()65 void Reset() { 66 idx_ = 0; 67 } 68 new(size_t size,ArenaAllocator * arena)69 static void* operator new(size_t size, ArenaAllocator* arena) { 70 return arena->Alloc(sizeof(GrowableArray::Iterator), ArenaAllocator::kAllocGrowableArray); 71 }; delete(void * p)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) arena_(arena)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. Resize(size_t 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. Reset()106 void Reset() { 107 num_used_ = 0; 108 } 109 110 // Insert an element to the end of a list, resizing if necessary. Insert(T elem)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 Get(size_t index)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. Put(size_t index,T elem)124 void Put(size_t index, T elem) { 125 DCHECK_LT(index, num_used_); 126 elem_list_[index] = elem; 127 } 128 Increment(size_t index)129 void Increment(size_t index) { 130 DCHECK_LT(index, num_used_); 131 elem_list_[index]++; 132 } 133 Delete(T element)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 GetNumAllocated()149 size_t GetNumAllocated() const { return num_allocated_; } 150 Size()151 size_t Size() const { return num_used_; } 152 GetRawStorage()153 T* GetRawStorage() const { return elem_list_; } 154 new(size_t size,ArenaAllocator * arena)155 static void* operator new(size_t size, ArenaAllocator* arena) { 156 return arena->Alloc(sizeof(GrowableArray<T>), ArenaAllocator::kAllocGrowableArray); 157 }; delete(void * p)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