Home | History | Annotate | Download | only in base 
      1 /*
      2  * Copyright (C) 2014 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_LIBARTBASE_BASE_ARENA_CONTAINERS_H_
     18 #define ART_LIBARTBASE_BASE_ARENA_CONTAINERS_H_
     19 
     20 #include <deque>
     21 #include <queue>
     22 #include <set>
     23 #include <stack>
     24 #include <unordered_map>
     25 #include <utility>
     26 
     27 #include "arena_allocator.h"
     28 #include "dchecked_vector.h"
     29 #include "hash_map.h"
     30 #include "hash_set.h"
     31 #include "safe_map.h"
     32 
     33 namespace art {
     34 
     35 // Adapter for use of ArenaAllocator in STL containers.
     36 // Use ArenaAllocator::Adapter() to create an adapter to pass to container constructors.
     37 // For example,
     38 //   struct Foo {
     39 //     explicit Foo(ArenaAllocator* allocator)
     40 //         : foo_vector(allocator->Adapter(kArenaAllocMisc)),
     41 //           foo_map(std::less<int>(), allocator->Adapter()) {
     42 //     }
     43 //     ArenaVector<int> foo_vector;
     44 //     ArenaSafeMap<int, int> foo_map;
     45 //   };
     46 template <typename T>
     47 class ArenaAllocatorAdapter;
     48 
     49 template <typename T>
     50 using ArenaDeque = std::deque<T, ArenaAllocatorAdapter<T>>;
     51 
     52 template <typename T>
     53 using ArenaQueue = std::queue<T, ArenaDeque<T>>;
     54 
     55 template <typename T>
     56 using ArenaVector = dchecked_vector<T, ArenaAllocatorAdapter<T>>;
     57 
     58 template <typename T, typename Comparator = std::less<T>>
     59 using ArenaPriorityQueue = std::priority_queue<T, ArenaVector<T>, Comparator>;
     60 
     61 template <typename T>
     62 using ArenaStdStack = std::stack<T, ArenaDeque<T>>;
     63 
     64 template <typename T, typename Comparator = std::less<T>>
     65 using ArenaSet = std::set<T, Comparator, ArenaAllocatorAdapter<T>>;
     66 
     67 template <typename K, typename V, typename Comparator = std::less<K>>
     68 using ArenaSafeMap =
     69     SafeMap<K, V, Comparator, ArenaAllocatorAdapter<std::pair<const K, V>>>;
     70 
     71 template <typename T,
     72           typename EmptyFn = DefaultEmptyFn<T>,
     73           typename HashFn = DefaultHashFn<T>,
     74           typename Pred = DefaultPred<T>>
     75 using ArenaHashSet = HashSet<T, EmptyFn, HashFn, Pred, ArenaAllocatorAdapter<T>>;
     76 
     77 template <typename Key,
     78           typename Value,
     79           typename EmptyFn = DefaultEmptyFn<std::pair<Key, Value>>,
     80           typename HashFn = DefaultHashFn<Key>,
     81           typename Pred = DefaultPred<Key>>
     82 using ArenaHashMap = HashMap<Key,
     83                              Value,
     84                              EmptyFn,
     85                              HashFn,
     86                              Pred,
     87                              ArenaAllocatorAdapter<std::pair<Key, Value>>>;
     88 
     89 template <typename Key,
     90           typename Value,
     91           typename Hash = std::hash<Key>,
     92           typename Pred = std::equal_to<Value>>
     93 using ArenaUnorderedMap = std::unordered_map<Key,
     94                                              Value,
     95                                              Hash,
     96                                              Pred,
     97                                              ArenaAllocatorAdapter<std::pair<const Key, Value>>>;
     98 
     99 // Implementation details below.
    100 
    101 template <bool kCount>
    102 class ArenaAllocatorAdapterKindImpl;
    103 
    104 template <>
    105 class ArenaAllocatorAdapterKindImpl<false> {
    106  public:
    107   // Not tracking allocations, ignore the supplied kind and arbitrarily provide kArenaAllocSTL.
    108   explicit ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind ATTRIBUTE_UNUSED) {}
    109   ArenaAllocatorAdapterKindImpl(const ArenaAllocatorAdapterKindImpl&) = default;
    110   ArenaAllocatorAdapterKindImpl& operator=(const ArenaAllocatorAdapterKindImpl&) = default;
    111   ArenaAllocKind Kind() { return kArenaAllocSTL; }
    112 };
    113 
    114 template <bool kCount>
    115 class ArenaAllocatorAdapterKindImpl {
    116  public:
    117   explicit ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind) : kind_(kind) { }
    118   ArenaAllocatorAdapterKindImpl(const ArenaAllocatorAdapterKindImpl&) = default;
    119   ArenaAllocatorAdapterKindImpl& operator=(const ArenaAllocatorAdapterKindImpl&) = default;
    120   ArenaAllocKind Kind() { return kind_; }
    121 
    122  private:
    123   ArenaAllocKind kind_;
    124 };
    125 
    126 typedef ArenaAllocatorAdapterKindImpl<kArenaAllocatorCountAllocations> ArenaAllocatorAdapterKind;
    127 
    128 template <>
    129 class ArenaAllocatorAdapter<void> : private ArenaAllocatorAdapterKind {
    130  public:
    131   typedef void value_type;
    132   typedef void* pointer;
    133   typedef const void* const_pointer;
    134 
    135   template <typename U>
    136   struct rebind {
    137     typedef ArenaAllocatorAdapter<U> other;
    138   };
    139 
    140   explicit ArenaAllocatorAdapter(ArenaAllocator* allocator,
    141                                  ArenaAllocKind kind = kArenaAllocSTL)
    142       : ArenaAllocatorAdapterKind(kind),
    143         allocator_(allocator) {
    144   }
    145   template <typename U>
    146   ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other)
    147       : ArenaAllocatorAdapterKind(other),
    148         allocator_(other.allocator_) {
    149   }
    150   ArenaAllocatorAdapter(const ArenaAllocatorAdapter&) = default;
    151   ArenaAllocatorAdapter& operator=(const ArenaAllocatorAdapter&) = default;
    152   ~ArenaAllocatorAdapter() = default;
    153 
    154  private:
    155   ArenaAllocator* allocator_;
    156 
    157   template <typename U>
    158   friend class ArenaAllocatorAdapter;
    159 };
    160 
    161 template <typename T>
    162 class ArenaAllocatorAdapter : private ArenaAllocatorAdapterKind {
    163  public:
    164   typedef T value_type;
    165   typedef T* pointer;
    166   typedef T& reference;
    167   typedef const T* const_pointer;
    168   typedef const T& const_reference;
    169   typedef size_t size_type;
    170   typedef ptrdiff_t difference_type;
    171 
    172   template <typename U>
    173   struct rebind {
    174     typedef ArenaAllocatorAdapter<U> other;
    175   };
    176 
    177   ArenaAllocatorAdapter(ArenaAllocator* allocator, ArenaAllocKind kind)
    178       : ArenaAllocatorAdapterKind(kind),
    179         allocator_(allocator) {
    180   }
    181   template <typename U>
    182   ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other)
    183       : ArenaAllocatorAdapterKind(other),
    184         allocator_(other.allocator_) {
    185   }
    186   ArenaAllocatorAdapter(const ArenaAllocatorAdapter&) = default;
    187   ArenaAllocatorAdapter& operator=(const ArenaAllocatorAdapter&) = default;
    188   ~ArenaAllocatorAdapter() = default;
    189 
    190   size_type max_size() const {
    191     return static_cast<size_type>(-1) / sizeof(T);
    192   }
    193 
    194   pointer address(reference x) const { return &x; }
    195   const_pointer address(const_reference x) const { return &x; }
    196 
    197   pointer allocate(size_type n,
    198                    ArenaAllocatorAdapter<void>::pointer hint ATTRIBUTE_UNUSED = nullptr) {
    199     DCHECK_LE(n, max_size());
    200     return allocator_->AllocArray<T>(n, ArenaAllocatorAdapterKind::Kind());
    201   }
    202   void deallocate(pointer p, size_type n) {
    203     allocator_->MakeInaccessible(p, sizeof(T) * n);
    204   }
    205 
    206   template <typename U, typename... Args>
    207   void construct(U* p, Args&&... args) {
    208     ::new (static_cast<void*>(p)) U(std::forward<Args>(args)...);
    209   }
    210   template <typename U>
    211   void destroy(U* p) {
    212     p->~U();
    213   }
    214 
    215  private:
    216   ArenaAllocator* allocator_;
    217 
    218   template <typename U>
    219   friend class ArenaAllocatorAdapter;
    220 
    221   template <typename U>
    222   friend bool operator==(const ArenaAllocatorAdapter<U>& lhs,
    223                          const ArenaAllocatorAdapter<U>& rhs);
    224 };
    225 
    226 template <typename T>
    227 inline bool operator==(const ArenaAllocatorAdapter<T>& lhs,
    228                        const ArenaAllocatorAdapter<T>& rhs) {
    229   return lhs.allocator_ == rhs.allocator_;
    230 }
    231 
    232 template <typename T>
    233 inline bool operator!=(const ArenaAllocatorAdapter<T>& lhs,
    234                        const ArenaAllocatorAdapter<T>& rhs) {
    235   return !(lhs == rhs);
    236 }
    237 
    238 inline ArenaAllocatorAdapter<void> ArenaAllocator::Adapter(ArenaAllocKind kind) {
    239   return ArenaAllocatorAdapter<void>(this, kind);
    240 }
    241 
    242 }  // namespace art
    243 
    244 #endif  // ART_LIBARTBASE_BASE_ARENA_CONTAINERS_H_
    245