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