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_COMPILER_UTILS_ARENA_CONTAINERS_H_
18 #define ART_COMPILER_UTILS_ARENA_CONTAINERS_H_
19 
20 #include <deque>
21 #include <queue>
22 #include <set>
23 #include <vector>
24 
25 #include "utils/arena_allocator.h"
26 #include "safe_map.h"
27 
28 namespace art {
29 
30 // Adapter for use of ArenaAllocator in STL containers.
31 // Use ArenaAllocator::Adapter() to create an adapter to pass to container constructors.
32 // For example,
33 //   struct Foo {
34 //     explicit Foo(ArenaAllocator* allocator)
35 //         : foo_vector(allocator->Adapter(kArenaAllocMisc)),
36 //           foo_map(std::less<int>(), allocator->Adapter()) {
37 //     }
38 //     ArenaVector<int> foo_vector;
39 //     ArenaSafeMap<int, int> foo_map;
40 //   };
41 template <typename T>
42 class ArenaAllocatorAdapter;
43 
44 template <typename T>
45 using ArenaDeque = std::deque<T, ArenaAllocatorAdapter<T>>;
46 
47 template <typename T>
48 using ArenaQueue = std::queue<T, ArenaDeque<T>>;
49 
50 template <typename T>
51 using ArenaVector = std::vector<T, ArenaAllocatorAdapter<T>>;
52 
53 template <typename T, typename Comparator = std::less<T>>
54 using ArenaSet = std::set<T, Comparator, ArenaAllocatorAdapter<T>>;
55 
56 template <typename K, typename V, typename Comparator = std::less<K>>
57 using ArenaSafeMap =
58     SafeMap<K, V, Comparator, ArenaAllocatorAdapter<std::pair<const K, V>>>;
59 
60 // Implementation details below.
61 
62 template <bool kCount>
63 class ArenaAllocatorAdapterKindImpl;
64 
65 template <>
66 class ArenaAllocatorAdapterKindImpl<false> {
67  public:
68   // Not tracking allocations, ignore the supplied kind and arbitrarily provide kArenaAllocSTL.
ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind)69   explicit ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind) { }
70   ArenaAllocatorAdapterKindImpl& operator=(const ArenaAllocatorAdapterKindImpl& other) = default;
Kind()71   ArenaAllocKind Kind() { return kArenaAllocSTL; }
72 };
73 
74 template <bool kCount>
75 class ArenaAllocatorAdapterKindImpl {
76  public:
ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind)77   explicit ArenaAllocatorAdapterKindImpl(ArenaAllocKind kind) : kind_(kind) { }
78   ArenaAllocatorAdapterKindImpl& operator=(const ArenaAllocatorAdapterKindImpl& other) = default;
Kind()79   ArenaAllocKind Kind() { return kind_; }
80 
81  private:
82   ArenaAllocKind kind_;
83 };
84 
85 typedef ArenaAllocatorAdapterKindImpl<kArenaAllocatorCountAllocations> ArenaAllocatorAdapterKind;
86 
87 template <>
88 class ArenaAllocatorAdapter<void>
89     : private DebugStackReference, private ArenaAllocatorAdapterKind {
90  public:
91   typedef void value_type;
92   typedef void* pointer;
93   typedef const void* const_pointer;
94 
95   template <typename U>
96   struct rebind {
97     typedef ArenaAllocatorAdapter<U> other;
98   };
99 
100   explicit ArenaAllocatorAdapter(ArenaAllocator* arena_allocator,
101                                  ArenaAllocKind kind = kArenaAllocSTL)
DebugStackReference(arena_allocator)102       : DebugStackReference(arena_allocator),
103         ArenaAllocatorAdapterKind(kind),
104         arena_allocator_(arena_allocator) {
105   }
106   template <typename U>
ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U> & other)107   ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other)
108       : DebugStackReference(other),
109         ArenaAllocatorAdapterKind(other),
110         arena_allocator_(other.arena_allocator_) {
111   }
112   ArenaAllocatorAdapter(const ArenaAllocatorAdapter& other) = default;
113   ArenaAllocatorAdapter& operator=(const ArenaAllocatorAdapter& other) = default;
114   ~ArenaAllocatorAdapter() = default;
115 
116  private:
117   ArenaAllocator* arena_allocator_;
118 
119   template <typename U>
120   friend class ArenaAllocatorAdapter;
121 };
122 
123 template <typename T>
124 class ArenaAllocatorAdapter : private DebugStackReference, private ArenaAllocatorAdapterKind {
125  public:
126   typedef T value_type;
127   typedef T* pointer;
128   typedef T& reference;
129   typedef const T* const_pointer;
130   typedef const T& const_reference;
131   typedef size_t size_type;
132   typedef ptrdiff_t difference_type;
133 
134   template <typename U>
135   struct rebind {
136     typedef ArenaAllocatorAdapter<U> other;
137   };
138 
ArenaAllocatorAdapter(ArenaAllocator * arena_allocator,ArenaAllocKind kind)139   explicit ArenaAllocatorAdapter(ArenaAllocator* arena_allocator, ArenaAllocKind kind)
140       : DebugStackReference(arena_allocator),
141         ArenaAllocatorAdapterKind(kind),
142         arena_allocator_(arena_allocator) {
143   }
144   template <typename U>
ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U> & other)145   ArenaAllocatorAdapter(const ArenaAllocatorAdapter<U>& other)
146       : DebugStackReference(other),
147         ArenaAllocatorAdapterKind(other),
148         arena_allocator_(other.arena_allocator_) {
149   }
150   ArenaAllocatorAdapter(const ArenaAllocatorAdapter& other) = default;
151   ArenaAllocatorAdapter& operator=(const ArenaAllocatorAdapter& other) = default;
152   ~ArenaAllocatorAdapter() = default;
153 
max_size()154   size_type max_size() const {
155     return static_cast<size_type>(-1) / sizeof(T);
156   }
157 
address(reference x)158   pointer address(reference x) const { return &x; }
address(const_reference x)159   const_pointer address(const_reference x) const { return &x; }
160 
161   pointer allocate(size_type n, ArenaAllocatorAdapter<void>::pointer hint = nullptr) {
162     DCHECK_LE(n, max_size());
163     return reinterpret_cast<T*>(arena_allocator_->Alloc(n * sizeof(T),
164                                                         ArenaAllocatorAdapterKind::Kind()));
165   }
deallocate(pointer p,size_type n)166   void deallocate(pointer p, size_type n) {
167   }
168 
construct(pointer p,const_reference val)169   void construct(pointer p, const_reference val) {
170     new (static_cast<void*>(p)) value_type(val);
171   }
destroy(pointer p)172   void destroy(pointer p) {
173     p->~value_type();
174   }
175 
176  private:
177   ArenaAllocator* arena_allocator_;
178 
179   template <typename U>
180   friend class ArenaAllocatorAdapter;
181 
182   template <typename U>
183   friend bool operator==(const ArenaAllocatorAdapter<U>& lhs,
184                          const ArenaAllocatorAdapter<U>& rhs);
185 };
186 
187 template <typename T>
188 inline bool operator==(const ArenaAllocatorAdapter<T>& lhs,
189                        const ArenaAllocatorAdapter<T>& rhs) {
190   return lhs.arena_allocator_ == rhs.arena_allocator_;
191 }
192 
193 template <typename T>
194 inline bool operator!=(const ArenaAllocatorAdapter<T>& lhs,
195                        const ArenaAllocatorAdapter<T>& rhs) {
196   return !(lhs == rhs);
197 }
198 
Adapter(ArenaAllocKind kind)199 inline ArenaAllocatorAdapter<void> ArenaAllocator::Adapter(ArenaAllocKind kind) {
200   return ArenaAllocatorAdapter<void>(this, kind);
201 }
202 
203 }  // namespace art
204 
205 #endif  // ART_COMPILER_UTILS_ARENA_CONTAINERS_H_
206