Home | History | Annotate | Download | only in dex 
      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:
     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