1862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee/* 2862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * Copyright (C) 2013 The Android Open Source Project 3862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * 4862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * Licensed under the Apache License, Version 2.0 (the "License"); 5862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * you may not use this file except in compliance with the License. 6862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * You may obtain a copy of the License at 7862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * 8862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * http://www.apache.org/licenses/LICENSE-2.0 9862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * 10862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * Unless required by applicable law or agreed to in writing, software 11862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * distributed under the License is distributed on an "AS IS" BASIS, 12862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * See the License for the specific language governing permissions and 14862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * limitations under the License. 15862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee */ 16862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 17fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#ifndef ART_COMPILER_DEX_GROWABLE_ARRAY_H_ 18fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#define ART_COMPILER_DEX_GROWABLE_ARRAY_H_ 19862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 20862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#include <stdint.h> 21862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#include <stddef.h> 22862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#include "compiler_enums.h" 23862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#include "arena_allocator.h" 24862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 25862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeenamespace art { 26862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 27862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeestruct CompilationUnit; 28862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 29862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee// Type of growable list for memory tuning. 30862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeeenum OatListKind { 31862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGrowableArrayMisc = 0, 32862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGrowableArrayBlockList, 33862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGrowableArraySSAtoDalvikMap, 34862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGrowableArrayDfsOrder, 35862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGrowableArrayDfsPostOrder, 36862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGrowableArrayDomPostOrderTraversal, 37862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGrowableArrayThrowLaunchPads, 38862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGrowableArraySuspendLaunchPads, 39862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGrowableArraySwitchTables, 40862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGrowableArrayFillArrayData, 41862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGrowableArraySuccessorBlocks, 42862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGrowableArrayPredecessors, 43862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kGNumListKinds 44862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee}; 45862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 46862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeetemplate<typename T> 47862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeeclass GrowableArray { 48862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee public: 49862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee class Iterator { 50862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee public: 5193ba893c20532990a430741e0a97212900094e8cBrian Carlstrom explicit Iterator(GrowableArray* g_list) 52862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee : idx_(0), 539b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom g_list_(g_list) {} 54862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 55862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // NOTE: returns 0/NULL when no next. 56862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // TODO: redo to make usage consistent with other iterators. 57862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee T Next() { 58862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (idx_ >= g_list_->Size()) { 59862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return 0; 60862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } else { 61862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return g_list_->Get(idx_++); 62862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 63862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 64862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 65862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Reset() { 66862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee idx_ = 0; 67862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 68862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 69862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void* operator new(size_t size, ArenaAllocator* arena) { 70f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier return arena->Alloc(sizeof(GrowableArray::Iterator), ArenaAllocator::kAllocGrowableArray); 71862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 729b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom static void operator delete(void* p) {} // Nop. 73862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 74862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee private: 75862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee size_t idx_; 76862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray* const g_list_; 77862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 78862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 79862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray(ArenaAllocator* arena, size_t init_length, OatListKind kind = kGrowableArrayMisc) 80862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee : arena_(arena), 81a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee num_allocated_(init_length), 82862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee num_used_(0), 83862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kind_(kind) { 84f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier elem_list_ = static_cast<T*>(arena_->Alloc(sizeof(T) * init_length, 85f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ArenaAllocator::kAllocGrowableArray)); 86862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 87862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 88862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 89862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // Expand the list size to at least new length. 90862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Resize(size_t new_length) { 91862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (new_length <= num_allocated_) return; 92a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee // If it's a small list double the size, else grow 1.5x. 93a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee size_t target_length = 94a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee (num_allocated_ < 128) ? num_allocated_ << 1 : num_allocated_ + (num_allocated_ >> 1); 95862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (new_length > target_length) { 96862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee target_length = new_length; 97862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 98f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier T* new_array = static_cast<T*>(arena_->Alloc(sizeof(T) * target_length, 99f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ArenaAllocator::kAllocGrowableArray)); 100862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee memcpy(new_array, elem_list_, sizeof(T) * num_allocated_); 101862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee num_allocated_ = target_length; 102862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee elem_list_ = new_array; 103862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 104862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 105862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // NOTE: does not return storage, just resets use count. 106862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Reset() { 107862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee num_used_ = 0; 108862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 109862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 110862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // Insert an element to the end of a list, resizing if necessary. 111862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Insert(T elem) { 112862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (num_used_ == num_allocated_) { 113862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee Resize(num_used_ + 1); 114862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 115862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee elem_list_[num_used_++] = elem; 116862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 117862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 118862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee T Get(size_t index) const { 119862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee DCHECK_LT(index, num_used_); 120862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return elem_list_[index]; 121862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 122862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 123862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // Overwrite existing element at position index. List must be large enough. 124862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Put(size_t index, T elem) { 125862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee DCHECK_LT(index, num_used_); 126862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee elem_list_[index] = elem; 127862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 128862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 129862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Increment(size_t index) { 130862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee DCHECK_LT(index, num_used_); 131862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee elem_list_[index]++; 132862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 133862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 134862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Delete(T element) { 135862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool found = false; 136862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee for (size_t i = 0; i < num_used_ - 1; i++) { 137862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (!found && elem_list_[i] == element) { 138862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee found = true; 139862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 140862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (found) { 141862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee elem_list_[i] = elem_list_[i+1]; 142862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 143862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 144862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // We should either have found the element, or it was the last (unscanned) element. 145862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee DCHECK(found || (element == elem_list_[num_used_ - 1])); 146862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee num_used_--; 147862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 148862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 149862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee size_t GetNumAllocated() const { return num_allocated_; } 150862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 151862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee size_t Size() const { return num_used_; } 152862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 153862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee T* GetRawStorage() const { return elem_list_; } 154862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 155862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void* operator new(size_t size, ArenaAllocator* arena) { 156f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier return arena->Alloc(sizeof(GrowableArray<T>), ArenaAllocator::kAllocGrowableArray); 157862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 1589b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom static void operator delete(void* p) {} // Nop. 159862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 160862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee private: 161862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaAllocator* const arena_; 162862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee size_t num_allocated_; 163862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee size_t num_used_; 164862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee OatListKind kind_; 165862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee T* elem_list_; 166862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee}; 167862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 168862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee} // namespace art 169862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 170fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#endif // ART_COMPILER_DEX_GROWABLE_ARRAY_H_ 171