1 // Copyright 2019 The Marl Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef marl_containers_h
16 #define marl_containers_h
17
18 #include "debug.h"
19 #include "memory.h"
20
21 #include <algorithm> // std::max
22 #include <cstddef> // size_t
23 #include <utility> // std::move
24
25 #include <deque>
26 #include <map>
27 #include <set>
28 #include <unordered_map>
29 #include <unordered_set>
30
31 namespace marl {
32 namespace containers {
33
34 ////////////////////////////////////////////////////////////////////////////////
35 // STL wrappers
36 // STL containers that use a marl::StlAllocator backed by a marl::Allocator.
37 // Note: These may be re-implemented to optimize for marl's usage cases.
38 // See: https://github.com/google/marl/issues/129
39 ////////////////////////////////////////////////////////////////////////////////
40 template <typename T>
41 using deque = std::deque<T, StlAllocator<T>>;
42
43 template <typename K, typename V, typename C = std::less<K>>
44 using map = std::map<K, V, C, StlAllocator<std::pair<const K, V>>>;
45
46 template <typename K, typename C = std::less<K>>
47 using set = std::set<K, C, StlAllocator<K>>;
48
49 template <typename K,
50 typename V,
51 typename H = std::hash<K>,
52 typename E = std::equal_to<K>>
53 using unordered_map =
54 std::unordered_map<K, V, H, E, StlAllocator<std::pair<const K, V>>>;
55
56 template <typename K, typename H = std::hash<K>, typename E = std::equal_to<K>>
57 using unordered_set = std::unordered_set<K, H, E, StlAllocator<K>>;
58
59 // take() takes and returns the front value from the deque.
60 template <typename T>
take(deque<T> & queue)61 MARL_NO_EXPORT inline T take(deque<T>& queue) {
62 auto out = std::move(queue.front());
63 queue.pop_front();
64 return out;
65 }
66
67 // take() takes and returns the first value from the unordered_set.
68 template <typename T, typename H, typename E>
take(unordered_set<T,H,E> & set)69 MARL_NO_EXPORT inline T take(unordered_set<T, H, E>& set) {
70 auto it = set.begin();
71 auto out = std::move(*it);
72 set.erase(it);
73 return out;
74 }
75
76 ////////////////////////////////////////////////////////////////////////////////
77 // vector<T, BASE_CAPACITY>
78 ////////////////////////////////////////////////////////////////////////////////
79
80 // vector is a container of contiguously stored elements.
81 // Unlike std::vector, marl::containers::vector keeps the first
82 // BASE_CAPACITY elements internally, which will avoid dynamic heap
83 // allocations. Once the vector exceeds BASE_CAPACITY elements, vector will
84 // allocate storage from the heap.
85 template <typename T, int BASE_CAPACITY>
86 class vector {
87 public:
88 MARL_NO_EXPORT inline vector(Allocator* allocator = Allocator::Default);
89
90 template <int BASE_CAPACITY_2>
91 MARL_NO_EXPORT inline vector(const vector<T, BASE_CAPACITY_2>& other,
92 Allocator* allocator = Allocator::Default);
93
94 template <int BASE_CAPACITY_2>
95 MARL_NO_EXPORT inline vector(vector<T, BASE_CAPACITY_2>&& other,
96 Allocator* allocator = Allocator::Default);
97
98 MARL_NO_EXPORT inline ~vector();
99
100 MARL_NO_EXPORT inline vector& operator=(const vector&);
101
102 template <int BASE_CAPACITY_2>
103 MARL_NO_EXPORT inline vector<T, BASE_CAPACITY>& operator=(
104 const vector<T, BASE_CAPACITY_2>&);
105
106 template <int BASE_CAPACITY_2>
107 MARL_NO_EXPORT inline vector<T, BASE_CAPACITY>& operator=(
108 vector<T, BASE_CAPACITY_2>&&);
109
110 MARL_NO_EXPORT inline void push_back(const T& el);
111 MARL_NO_EXPORT inline void emplace_back(T&& el);
112 MARL_NO_EXPORT inline void pop_back();
113 MARL_NO_EXPORT inline T& front();
114 MARL_NO_EXPORT inline T& back();
115 MARL_NO_EXPORT inline const T& front() const;
116 MARL_NO_EXPORT inline const T& back() const;
117 MARL_NO_EXPORT inline T* begin();
118 MARL_NO_EXPORT inline T* end();
119 MARL_NO_EXPORT inline const T* begin() const;
120 MARL_NO_EXPORT inline const T* end() const;
121 MARL_NO_EXPORT inline T& operator[](size_t i);
122 MARL_NO_EXPORT inline const T& operator[](size_t i) const;
123 MARL_NO_EXPORT inline size_t size() const;
124 MARL_NO_EXPORT inline size_t cap() const;
125 MARL_NO_EXPORT inline void resize(size_t n);
126 MARL_NO_EXPORT inline void reserve(size_t n);
127 MARL_NO_EXPORT inline T* data();
128 MARL_NO_EXPORT inline const T* data() const;
129
130 Allocator* const allocator;
131
132 private:
133 using TStorage = typename marl::aligned_storage<sizeof(T), alignof(T)>::type;
134
135 vector(const vector&) = delete;
136
137 MARL_NO_EXPORT inline void free();
138
139 size_t count = 0;
140 size_t capacity = BASE_CAPACITY;
141 TStorage buffer[BASE_CAPACITY];
142 TStorage* elements = buffer;
143 Allocation allocation;
144 };
145
146 template <typename T, int BASE_CAPACITY>
vector(Allocator * allocator)147 vector<T, BASE_CAPACITY>::vector(
148 Allocator* allocator /* = Allocator::Default */)
149 : allocator(allocator) {}
150
151 template <typename T, int BASE_CAPACITY>
152 template <int BASE_CAPACITY_2>
vector(const vector<T,BASE_CAPACITY_2> & other,Allocator * allocator)153 vector<T, BASE_CAPACITY>::vector(
154 const vector<T, BASE_CAPACITY_2>& other,
155 Allocator* allocator /* = Allocator::Default */)
156 : allocator(allocator) {
157 *this = other;
158 }
159
160 template <typename T, int BASE_CAPACITY>
161 template <int BASE_CAPACITY_2>
vector(vector<T,BASE_CAPACITY_2> && other,Allocator * allocator)162 vector<T, BASE_CAPACITY>::vector(
163 vector<T, BASE_CAPACITY_2>&& other,
164 Allocator* allocator /* = Allocator::Default */)
165 : allocator(allocator) {
166 *this = std::move(other);
167 }
168
169 template <typename T, int BASE_CAPACITY>
~vector()170 vector<T, BASE_CAPACITY>::~vector() {
171 free();
172 }
173
174 template <typename T, int BASE_CAPACITY>
175 vector<T, BASE_CAPACITY>& vector<T, BASE_CAPACITY>::operator=(
176 const vector& other) {
177 free();
178 reserve(other.size());
179 count = other.size();
180 for (size_t i = 0; i < count; i++) {
181 new (&reinterpret_cast<T*>(elements)[i]) T(other[i]);
182 }
183 return *this;
184 }
185
186 template <typename T, int BASE_CAPACITY>
187 template <int BASE_CAPACITY_2>
188 vector<T, BASE_CAPACITY>& vector<T, BASE_CAPACITY>::operator=(
189 const vector<T, BASE_CAPACITY_2>& other) {
190 free();
191 reserve(other.size());
192 count = other.size();
193 for (size_t i = 0; i < count; i++) {
194 new (&reinterpret_cast<T*>(elements)[i]) T(other[i]);
195 }
196 return *this;
197 }
198
199 template <typename T, int BASE_CAPACITY>
200 template <int BASE_CAPACITY_2>
201 vector<T, BASE_CAPACITY>& vector<T, BASE_CAPACITY>::operator=(
202 vector<T, BASE_CAPACITY_2>&& other) {
203 free();
204 reserve(other.size());
205 count = other.size();
206 for (size_t i = 0; i < count; i++) {
207 new (&reinterpret_cast<T*>(elements)[i]) T(std::move(other[i]));
208 }
209 other.resize(0);
210 return *this;
211 }
212
213 template <typename T, int BASE_CAPACITY>
push_back(const T & el)214 void vector<T, BASE_CAPACITY>::push_back(const T& el) {
215 reserve(count + 1);
216 new (&reinterpret_cast<T*>(elements)[count]) T(el);
217 count++;
218 }
219
220 template <typename T, int BASE_CAPACITY>
emplace_back(T && el)221 void vector<T, BASE_CAPACITY>::emplace_back(T&& el) {
222 reserve(count + 1);
223 new (&reinterpret_cast<T*>(elements)[count]) T(std::move(el));
224 count++;
225 }
226
227 template <typename T, int BASE_CAPACITY>
pop_back()228 void vector<T, BASE_CAPACITY>::pop_back() {
229 MARL_ASSERT(count > 0, "pop_back() called on empty vector");
230 count--;
231 reinterpret_cast<T*>(elements)[count].~T();
232 }
233
234 template <typename T, int BASE_CAPACITY>
front()235 T& vector<T, BASE_CAPACITY>::front() {
236 MARL_ASSERT(count > 0, "front() called on empty vector");
237 return reinterpret_cast<T*>(elements)[0];
238 }
239
240 template <typename T, int BASE_CAPACITY>
back()241 T& vector<T, BASE_CAPACITY>::back() {
242 MARL_ASSERT(count > 0, "back() called on empty vector");
243 return reinterpret_cast<T*>(elements)[count - 1];
244 }
245
246 template <typename T, int BASE_CAPACITY>
front()247 const T& vector<T, BASE_CAPACITY>::front() const {
248 MARL_ASSERT(count > 0, "front() called on empty vector");
249 return reinterpret_cast<T*>(elements)[0];
250 }
251
252 template <typename T, int BASE_CAPACITY>
back()253 const T& vector<T, BASE_CAPACITY>::back() const {
254 MARL_ASSERT(count > 0, "back() called on empty vector");
255 return reinterpret_cast<T*>(elements)[count - 1];
256 }
257
258 template <typename T, int BASE_CAPACITY>
begin()259 T* vector<T, BASE_CAPACITY>::begin() {
260 return reinterpret_cast<T*>(elements);
261 }
262
263 template <typename T, int BASE_CAPACITY>
end()264 T* vector<T, BASE_CAPACITY>::end() {
265 return reinterpret_cast<T*>(elements) + count;
266 }
267
268 template <typename T, int BASE_CAPACITY>
begin()269 const T* vector<T, BASE_CAPACITY>::begin() const {
270 return reinterpret_cast<T*>(elements);
271 }
272
273 template <typename T, int BASE_CAPACITY>
end()274 const T* vector<T, BASE_CAPACITY>::end() const {
275 return reinterpret_cast<T*>(elements) + count;
276 }
277
278 template <typename T, int BASE_CAPACITY>
279 T& vector<T, BASE_CAPACITY>::operator[](size_t i) {
280 MARL_ASSERT(i < count, "index %d exceeds vector size %d", int(i), int(count));
281 return reinterpret_cast<T*>(elements)[i];
282 }
283
284 template <typename T, int BASE_CAPACITY>
285 const T& vector<T, BASE_CAPACITY>::operator[](size_t i) const {
286 MARL_ASSERT(i < count, "index %d exceeds vector size %d", int(i), int(count));
287 return reinterpret_cast<T*>(elements)[i];
288 }
289
290 template <typename T, int BASE_CAPACITY>
size()291 size_t vector<T, BASE_CAPACITY>::size() const {
292 return count;
293 }
294
295 template <typename T, int BASE_CAPACITY>
resize(size_t n)296 void vector<T, BASE_CAPACITY>::resize(size_t n) {
297 reserve(n);
298 while (count < n) {
299 new (&reinterpret_cast<T*>(elements)[count++]) T();
300 }
301 while (n < count) {
302 reinterpret_cast<T*>(elements)[--count].~T();
303 }
304 }
305
306 template <typename T, int BASE_CAPACITY>
reserve(size_t n)307 void vector<T, BASE_CAPACITY>::reserve(size_t n) {
308 if (n > capacity) {
309 capacity = std::max<size_t>(n * 2, 8);
310
311 Allocation::Request request;
312 request.size = sizeof(T) * capacity;
313 request.alignment = alignof(T);
314 request.usage = Allocation::Usage::Vector;
315
316 auto alloc = allocator->allocate(request);
317 auto grown = reinterpret_cast<TStorage*>(alloc.ptr);
318 for (size_t i = 0; i < count; i++) {
319 new (&reinterpret_cast<T*>(grown)[i])
320 T(std::move(reinterpret_cast<T*>(elements)[i]));
321 }
322 free();
323 elements = grown;
324 allocation = alloc;
325 }
326 }
327
328 template <typename T, int BASE_CAPACITY>
data()329 T* vector<T, BASE_CAPACITY>::data() {
330 return elements;
331 }
332
333 template <typename T, int BASE_CAPACITY>
data()334 const T* vector<T, BASE_CAPACITY>::data() const {
335 return elements;
336 }
337
338 template <typename T, int BASE_CAPACITY>
free()339 void vector<T, BASE_CAPACITY>::free() {
340 for (size_t i = 0; i < count; i++) {
341 reinterpret_cast<T*>(elements)[i].~T();
342 }
343
344 if (allocation.ptr != nullptr) {
345 allocator->free(allocation);
346 allocation = {};
347 elements = nullptr;
348 }
349 }
350
351 ////////////////////////////////////////////////////////////////////////////////
352 // list<T, BASE_CAPACITY>
353 ////////////////////////////////////////////////////////////////////////////////
354
355 // list is a minimal std::list like container that supports constant time
356 // insertion and removal of elements.
357 // list keeps hold of allocations (it only releases allocations on destruction),
358 // to avoid repeated heap allocations and frees when frequently inserting and
359 // removing elements.
360 template <typename T>
361 class list {
362 struct Entry {
363 T data;
364 Entry* next;
365 Entry* prev;
366 };
367
368 public:
369 class iterator {
370 public:
371 MARL_NO_EXPORT inline iterator(Entry*);
372 MARL_NO_EXPORT inline T* operator->();
373 MARL_NO_EXPORT inline T& operator*();
374 MARL_NO_EXPORT inline iterator& operator++();
375 MARL_NO_EXPORT inline bool operator==(const iterator&) const;
376 MARL_NO_EXPORT inline bool operator!=(const iterator&) const;
377
378 private:
379 friend list;
380 Entry* entry;
381 };
382
383 MARL_NO_EXPORT inline list(Allocator* allocator = Allocator::Default);
384 MARL_NO_EXPORT inline ~list();
385
386 MARL_NO_EXPORT inline iterator begin();
387 MARL_NO_EXPORT inline iterator end();
388 MARL_NO_EXPORT inline size_t size() const;
389
390 template <typename... Args>
391 MARL_NO_EXPORT inline iterator emplace_front(Args&&... args);
392 MARL_NO_EXPORT inline void erase(iterator);
393
394 private:
395 // copy / move is currently unsupported.
396 list(const list&) = delete;
397 list(list&&) = delete;
398 list& operator=(const list&) = delete;
399 list& operator=(list&&) = delete;
400
401 struct AllocationChain {
402 Allocation allocation;
403 AllocationChain* next;
404 };
405
406 MARL_NO_EXPORT inline void grow(size_t count);
407
408 MARL_NO_EXPORT static inline void unlink(Entry* entry, Entry*& list);
409 MARL_NO_EXPORT static inline void link(Entry* entry, Entry*& list);
410
411 Allocator* const allocator;
412 size_t size_ = 0;
413 size_t capacity = 0;
414 AllocationChain* allocations = nullptr;
415 Entry* free = nullptr;
416 Entry* head = nullptr;
417 };
418
419 template <typename T>
iterator(Entry * entry)420 list<T>::iterator::iterator(Entry* entry) : entry(entry) {}
421
422 template <typename T>
423 T* list<T>::iterator::operator->() {
424 return &entry->data;
425 }
426
427 template <typename T>
428 T& list<T>::iterator::operator*() {
429 return entry->data;
430 }
431
432 template <typename T>
433 typename list<T>::iterator& list<T>::iterator::operator++() {
434 entry = entry->next;
435 return *this;
436 }
437
438 template <typename T>
439 bool list<T>::iterator::operator==(const iterator& rhs) const {
440 return entry == rhs.entry;
441 }
442
443 template <typename T>
444 bool list<T>::iterator::operator!=(const iterator& rhs) const {
445 return entry != rhs.entry;
446 }
447
448 template <typename T>
list(Allocator * allocator)449 list<T>::list(Allocator* allocator /* = Allocator::Default */)
450 : allocator(allocator) {}
451
452 template <typename T>
~list()453 list<T>::~list() {
454 for (auto el = head; el != nullptr; el = el->next) {
455 el->data.~T();
456 }
457
458 auto curr = allocations;
459 while (curr != nullptr) {
460 auto next = curr->next;
461 allocator->free(curr->allocation);
462 curr = next;
463 }
464 }
465
466 template <typename T>
begin()467 typename list<T>::iterator list<T>::begin() {
468 return {head};
469 }
470
471 template <typename T>
end()472 typename list<T>::iterator list<T>::end() {
473 return {nullptr};
474 }
475
476 template <typename T>
size()477 size_t list<T>::size() const {
478 return size_;
479 }
480
481 template <typename T>
482 template <typename... Args>
emplace_front(Args &&...args)483 typename list<T>::iterator list<T>::emplace_front(Args&&... args) {
484 if (free == nullptr) {
485 grow(std::max<size_t>(capacity, 8));
486 }
487
488 auto entry = free;
489
490 unlink(entry, free);
491 link(entry, head);
492
493 new (&entry->data) T(std::forward<T>(args)...);
494 size_++;
495
496 return entry;
497 }
498
499 template <typename T>
erase(iterator it)500 void list<T>::erase(iterator it) {
501 auto entry = it.entry;
502 unlink(entry, head);
503 link(entry, free);
504
505 entry->data.~T();
506 size_--;
507 }
508
509 template <typename T>
grow(size_t count)510 void list<T>::grow(size_t count) {
511 auto const entriesSize = sizeof(Entry) * count;
512 auto const allocChainOffset = alignUp(entriesSize, alignof(AllocationChain));
513 auto const allocSize = allocChainOffset + sizeof(AllocationChain);
514
515 Allocation::Request request;
516 request.size = allocSize;
517 request.alignment = std::max(alignof(Entry), alignof(AllocationChain));
518 request.usage = Allocation::Usage::List;
519 auto alloc = allocator->allocate(request);
520
521 auto entries = reinterpret_cast<Entry*>(alloc.ptr);
522 for (size_t i = 0; i < count; i++) {
523 auto entry = &entries[i];
524 entry->prev = nullptr;
525 entry->next = free;
526 if (free) {
527 free->prev = entry;
528 }
529 free = entry;
530 }
531
532 auto allocChain = reinterpret_cast<AllocationChain*>(
533 reinterpret_cast<uint8_t*>(alloc.ptr) + allocChainOffset);
534
535 allocChain->allocation = alloc;
536 allocChain->next = allocations;
537 allocations = allocChain;
538
539 capacity += count;
540 }
541
542 template <typename T>
unlink(Entry * entry,Entry * & list)543 void list<T>::unlink(Entry* entry, Entry*& list) {
544 if (list == entry) {
545 list = list->next;
546 }
547 if (entry->prev) {
548 entry->prev->next = entry->next;
549 }
550 if (entry->next) {
551 entry->next->prev = entry->prev;
552 }
553 entry->prev = nullptr;
554 entry->next = nullptr;
555 }
556
557 template <typename T>
link(Entry * entry,Entry * & list)558 void list<T>::link(Entry* entry, Entry*& list) {
559 MARL_ASSERT(entry->next == nullptr, "link() called on entry already linked");
560 MARL_ASSERT(entry->prev == nullptr, "link() called on entry already linked");
561 if (list) {
562 entry->next = list;
563 list->prev = entry;
564 }
565 list = entry;
566 }
567
568 } // namespace containers
569 } // namespace marl
570
571 #endif // marl_containers_h
572