growable_array.h revision a5abf7091711eed1e9f1d0e1538fe9963ebdf31c
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 17862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#ifndef ART_SRC_COMPILER_DEX_GROWABLE_LIST_H_ 18862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#define ART_SRC_COMPILER_DEX_GROWABLE_LIST_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 50862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee class Iterator { 51862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee public: 52862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee Iterator(GrowableArray* g_list) 53862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee : idx_(0), 54862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee g_list_(g_list) {}; 55862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 56862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // NOTE: returns 0/NULL when no next. 57862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // TODO: redo to make usage consistent with other iterators. 58862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee T Next() { 59862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (idx_ >= g_list_->Size()) { 60862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return 0; 61862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } else { 62862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return g_list_->Get(idx_++); 63862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 64862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 65862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 66862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Reset() { 67862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee idx_ = 0; 68862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 69862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 70862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void* operator new(size_t size, ArenaAllocator* arena) { 71862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return arena->NewMem(sizeof(GrowableArray::Iterator), true, ArenaAllocator::kAllocGrowableArray); 72862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 73862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void operator delete(void* p) {}; // Nop. 74862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 75862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee private: 76862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee size_t idx_; 77862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray* const g_list_; 78862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 79862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 80862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray(ArenaAllocator* arena, size_t init_length, OatListKind kind = kGrowableArrayMisc) 81862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee : arena_(arena), 82a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee num_allocated_(init_length), 83862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee num_used_(0), 84862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kind_(kind) { 85862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee elem_list_ = static_cast<T*>(arena_->NewMem(sizeof(T) * init_length, true, 86a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee ArenaAllocator::kAllocGrowableArray)); 87862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 88862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 89862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 90862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // Expand the list size to at least new length. 91862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Resize(size_t new_length) { 92862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (new_length <= num_allocated_) return; 93a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee // If it's a small list double the size, else grow 1.5x. 94a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee size_t target_length = 95a5abf7091711eed1e9f1d0e1538fe9963ebdf31cbuzbee (num_allocated_ < 128) ? num_allocated_ << 1 : num_allocated_ + (num_allocated_ >> 1); 96862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (new_length > target_length) { 97862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee target_length = new_length; 98862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 99862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee T* new_array = static_cast<T*>(arena_->NewMem(sizeof(T) * target_length, true, 100862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaAllocator::kAllocGrowableArray)); 101862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee memcpy(new_array, elem_list_, sizeof(T) * num_allocated_); 102862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee num_allocated_ = target_length; 103862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee elem_list_ = new_array; 104862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 105862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 106862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // NOTE: does not return storage, just resets use count. 107862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Reset() { 108862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee num_used_ = 0; 109862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 110862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 111862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // Insert an element to the end of a list, resizing if necessary. 112862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Insert(T elem) { 113862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (num_used_ == num_allocated_) { 114862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee Resize(num_used_ + 1); 115862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 116862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee elem_list_[num_used_++] = elem; 117862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 118862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 119862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee T Get(size_t index) const { 120862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee DCHECK_LT(index, num_used_); 121862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return elem_list_[index]; 122862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 123862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 124862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // Overwrite existing element at position index. List must be large enough. 125862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Put(size_t index, T elem) { 126862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee DCHECK_LT(index, num_used_); 127862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee elem_list_[index] = elem; 128862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 129862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 130862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Increment(size_t index) { 131862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee DCHECK_LT(index, num_used_); 132862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee elem_list_[index]++; 133862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 134862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 135862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Delete(T element) { 136862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool found = false; 137862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee for (size_t i = 0; i < num_used_ - 1; i++) { 138862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (!found && elem_list_[i] == element) { 139862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee found = true; 140862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 141862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee if (found) { 142862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee elem_list_[i] = elem_list_[i+1]; 143862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 144862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 145862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // We should either have found the element, or it was the last (unscanned) element. 146862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee DCHECK(found || (element == elem_list_[num_used_ - 1])); 147862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee num_used_--; 148862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 149862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 150862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee size_t GetNumAllocated() const { return num_allocated_; } 151862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 152862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee size_t Size() const { return num_used_; } 153862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 154862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee T* GetRawStorage() const { return elem_list_; } 155862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 156862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void* operator new(size_t size, ArenaAllocator* arena) { 157862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return arena->NewMem(sizeof(GrowableArray<T>), true, ArenaAllocator::kAllocGrowableArray); 158862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 159862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void operator delete(void* p) {}; // Nop. 160862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 161862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee private: 162862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaAllocator* const arena_; 163862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee size_t num_allocated_; 164862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee size_t num_used_; 165862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee OatListKind kind_; 166862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee T* elem_list_; 167862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee}; 168862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 169862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee} // namespace art 170862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 171862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#endif // ART_SRC_COMPILER_DEX_GROWABLE_LIST_H_ 172