pool.hxx 15.7 KB
Newer Older
Florian Oetke's avatar
Florian Oetke committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#pragma once

#ifndef MIRRAGE_UTIL_POOL_INCLUDED
#include "pool.hpp"
#endif

namespace mirrage::util {

#define MIRRAGE_POOL_HEADER \
	template <class T, std::size_t ElementsPerChunk, class ValueTraits, class IndexType>
#define MIRRAGE_POOL pool<T, ElementsPerChunk, ValueTraits, IndexType>


	MIRRAGE_POOL_HEADER
	auto MIRRAGE_POOL::operator=(pool&& rhs) noexcept -> pool&
	{
		if(&rhs != this)
			clear();

		_chunks        = std::move(rhs._chunks);
		_used_elements = std::move(rhs._used_elements);
		_freelist      = std::move(rhs._freelist);

		return *this;
	}

	MIRRAGE_POOL_HEADER
	auto MIRRAGE_POOL::begin() noexcept -> iterator { return iterator{*this, 0}; }

	MIRRAGE_POOL_HEADER
	auto MIRRAGE_POOL::end() noexcept -> iterator { return iterator{*this, size()}; }

	MIRRAGE_POOL_HEADER
	void MIRRAGE_POOL::clear() noexcept
	{
		for(auto& inst : *this) {
			inst.~T();
		}

		_chunks.clear();
		_used_elements = 0;
		_freelist.clear();
	}

	MIRRAGE_POOL_HEADER
Florian Oetke's avatar
Florian Oetke committed
46
	template <class Key>
Florian Oetke's avatar
Florian Oetke committed
47
48
	auto MIRRAGE_POOL::find(const Key& key) -> util::maybe<index_t>
	{
Florian Oetke's avatar
Florian Oetke committed
49
50
51
52
53
54
55
56
57
58
59
60
		if constexpr(sorted) {
			auto iter = std::lower_bound(begin(), end(), key, [](auto& lhs, auto& rhs) {
				return lhs.*(ValueTraits::sort_key) < rhs;
			});

			if(iter == end())
				return util::nothing;
			else
				return iter.index();
		} else {
			MIRRAGE_FAIL("called find on unsorted pool.");
		}
Florian Oetke's avatar
Florian Oetke committed
61
62
63
64
	}

	MIRRAGE_POOL_HEADER
	template <typename F>
Florian Oetke's avatar
Florian Oetke committed
65
	void MIRRAGE_POOL::erase(IndexType i, F&& relocation)
Florian Oetke's avatar
Florian Oetke committed
66
67
68
69
70
71
72
73
	{
		MIRRAGE_INVARIANT(i < _used_elements, "erase is out of range: " << i << ">=" << _used_elements);

		if(i == _used_elements - 1) {
			_pop_back();

		} else {
			if constexpr(max_free_slots > 0) {
Florian Oetke's avatar
Florian Oetke committed
74
75
76
77
78
				// empty slot allowed => leave a hole
				auto& e = get(i);
				e.~T();
				std::memset(reinterpret_cast<char*>(&e), 0, sizeof(T));
				_freelist.insert(i);
Florian Oetke's avatar
Florian Oetke committed
79

Florian Oetke's avatar
Florian Oetke committed
80
			} else if constexpr(ValueTraits::sorted) {
Florian Oetke's avatar
Florian Oetke committed
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
				// shift all later elements and delete the last (now empty)
				_move_elements(i + 1, i, relocation, _used_elements - i - 1);
				_pop_back();

			} else {
				// swap with last and pop_back
				if(i < _used_elements - 1) {
					auto& pivot = get(_used_elements - 1);
					relocation(_used_elements - 1, pivot, i);
					get(i) = std::move(pivot);
				}
				_pop_back();
			}
		}
	}

	MIRRAGE_POOL_HEADER
	template <typename F>
	void MIRRAGE_POOL::shrink_to_fit(F&& relocation)
	{
		if constexpr(max_free_slots > 0) {
			if(_freelist.size() > max_free_slots) {
				if constexpr(ValueTraits::sorted) {
					// find first free index
					auto free_iter      = _freelist.begin();
					auto write_position = *free_iter++;
					auto read_position  = write_position + 1;

					while(read_position < _used_elements) {
						// skip all free slots
						while(free_iter != _freelist.end() && read_position == *free_iter) {
							free_iter++;
							read_position++;
						}

						// count non-free slots
						auto next_free  = (free_iter == _freelist.end()) ? _used_elements : *free_iter;
						auto block_size = next_free - read_position;

						// move block of non-free slots to insert_position
Florian Oetke's avatar
Florian Oetke committed
121
						_move_elements_uninitialized(read_position, write_position, relocation, block_size);
Florian Oetke's avatar
Florian Oetke committed
122
123
124
125
126
127
128
						read_position += block_size;
						write_position += block_size;
					}

					_used_elements = write_position;

				} else {
Florian Oetke's avatar
Florian Oetke committed
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
					auto last_used_idx = std::int64_t(_used_elements) - 1;
					auto next_free     = std::int64_t(_freelist.size()) - 1;

					for(auto to_fill : util::range(std::int64_t(_freelist.size()))) {
						for(; next_free > to_fill; next_free--) {
							if(_freelist[next_free] == last_used_idx)
								last_used_idx--;
							else if(_freelist[next_free] < last_used_idx)
								break;
						}

						if(last_used_idx < 0 || next_free <= to_fill)
							break;

						auto& src  = get(last_used_idx);
						auto  addr = new(_get_raw(_freelist[to_fill])) T(std::move(src));
						src.~T();
						std::memset(reinterpret_cast<char*>(&src), 0, sizeof(T));

						relocation(last_used_idx, *addr, _freelist[to_fill]);
						last_used_idx--;
Florian Oetke's avatar
Florian Oetke committed
150
					}
Florian Oetke's avatar
Florian Oetke committed
151
152

					_used_elements -= _freelist.size();
Florian Oetke's avatar
Florian Oetke committed
153
154
155
156
157
158
159
160
				}

				_freelist.clear();
			}
		}

		// free unused chunks
		auto min_chunks = std::ceil(static_cast<float>(_used_elements) / chunk_len);
Florian Oetke's avatar
Florian Oetke committed
161
162
		_chunks.resize(
		        util::max(static_cast<std::size_t>(min_chunks), util::min(_chunks.size(), std::size_t(1))));
Florian Oetke's avatar
Florian Oetke committed
163
164
	}

Florian Oetke's avatar
Florian Oetke committed
165
166
167
	namespace detail {
	}

Florian Oetke's avatar
Florian Oetke committed
168
169
170
171
172
173
174
175
176
177
	MIRRAGE_POOL_HEADER
	template <typename F, class... Args>
	auto MIRRAGE_POOL::emplace(F&& relocation, Args&&... args) -> std::tuple<T&, IndexType>
	{
		using std::swap;

		auto addr = [&](auto index) {
			auto chunk = index / chunk_len;

			if(chunk < static_cast<IndexType>(_chunks.size())) {
178
				return _chunks[std::size_t(chunk)].get() + (index % chunk_len);
Florian Oetke's avatar
Florian Oetke committed
179
180
181
182
183
184
185
186
187
			} else {
				return _chunks.emplace_back(std::make_unique<storage_t[]>(chunk_len)).get();
			}
		};


		auto i = _used_elements;

		if constexpr(ValueTraits::sorted) {
Florian Oetke's avatar
Florian Oetke committed
188
			auto sort_key = decltype(std::declval<T>().*(ValueTraits::sort_key)){};
Florian Oetke's avatar
Florian Oetke committed
189

Florian Oetke's avatar
Florian Oetke committed
190
191
			using first_arg_type =
			        std::remove_cv_t<std::remove_reference_t<std::tuple_element_t<0, std::tuple<Args...>>>>;
Florian Oetke's avatar
Florian Oetke committed
192

Florian Oetke's avatar
Florian Oetke committed
193
194
195
			if constexpr(sizeof...(args) == 1 && std::is_same_v<T, first_arg_type>) {
				// copy/move construction
				auto&& first_arg = std::get<0>(std::forward_as_tuple(args...));
196
				sort_key         = first_arg.*(ValueTraits::sort_key);
Florian Oetke's avatar
Florian Oetke committed
197
198
199
200
201

			} else {
				// normal constructor call
				sort_key = std::get<ValueTraits::sort_key_constructor_idx>(std::tie(args...));
			}
Florian Oetke's avatar
Florian Oetke committed
202

Florian Oetke's avatar
Florian Oetke committed
203

Florian Oetke's avatar
Florian Oetke committed
204
205
206
207
208
209
210
211
212
213
214
			// find insert position
			auto iter = std::lower_bound(begin(), end(), sort_key, [](auto& lhs, auto& rhs) {
				return lhs.*(ValueTraits::sort_key) < rhs;
			});

			// shift to make room
			if(iter != end()) {
				// calc insert index
				i = iter.physical_index();

				// find first free slot
Florian Oetke's avatar
Florian Oetke committed
215
216
217
218
219
220
221
				auto first_empty = util::maybe<IndexType>{};
				if constexpr(max_free_slots > 0) {
					auto min = std::lower_bound(_freelist.begin(), _freelist.end(), i);
					if(min != _freelist.end()) {
						auto min_v = *min;
						_freelist.erase(min);
						first_empty = min_v;
Florian Oetke's avatar
Florian Oetke committed
222
					}
Florian Oetke's avatar
Florian Oetke committed
223
				}
Florian Oetke's avatar
Florian Oetke committed
224

Florian Oetke's avatar
Florian Oetke committed
225
				if(first_empty.is_nothing()) {
Florian Oetke's avatar
Florian Oetke committed
226
227
228
					// create new slot if required
					addr(_used_elements);
					_used_elements++;
Florian Oetke's avatar
Florian Oetke committed
229
230
					first_empty = _used_elements - 1;
				}
Florian Oetke's avatar
Florian Oetke committed
231

Florian Oetke's avatar
Florian Oetke committed
232
233
				MIRRAGE_INVARIANT(first_empty.get_or_throw() >= i,
				                  "first_empty (" << first_empty.get_or_throw() << ") < i (" << i << ")");
Florian Oetke's avatar
Florian Oetke committed
234

Florian Oetke's avatar
Florian Oetke committed
235
				if(first_empty.get_or_throw() > i) {
Florian Oetke's avatar
Florian Oetke committed
236
					// shift to make room for new element
Florian Oetke's avatar
Florian Oetke committed
237
					_move_elements(i, i + 1, relocation, first_empty.get_or_throw() - i, true);
Florian Oetke's avatar
Florian Oetke committed
238
239
240
					iter->~T();
				}

Florian Oetke's avatar
Florian Oetke committed
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
				// create new element
				auto instance = new(addr(i)) T(std::forward<Args>(args)...);

#ifdef MIRRAGE_SLOW_INVARIANTS
				for(auto& e : *this) {
					MIRRAGE_INVARIANT(e.*(ValueTraits::sort_key), "invalid key");
				}

				MIRRAGE_INVARIANT(std::is_sorted(begin(),
				                                 end(),
				                                 [](auto& lhs, auto& rhs) {
					                                 return lhs.*(ValueTraits::sort_key)
					                                        < rhs.*(ValueTraits::sort_key);
				                                 }),
				                  "pool is not sorted anymore");
#endif

				return {*instance, i};

Florian Oetke's avatar
Florian Oetke committed
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
			} else {
				// insert at the end
				_used_elements++;
			}

		} else if constexpr(max_free_slots > 0) {
			// check free-list first
			if(!_freelist.empty()) {
				i = _freelist.pop_back();
			} else {
				_used_elements++;
			}
		}

		// create new element
		auto instance  = new(addr(i)) T(std::forward<Args>(args)...);
		auto instance2 = instance + 1;

		(void) instance2;

Florian Oetke's avatar
Florian Oetke committed
280
281
282
283
284
285
286
287
288
		MIRRAGE_INVARIANT(!ValueTraits::sorted
		                          || std::is_sorted(begin(),
		                                            end(),
		                                            [](auto& lhs, auto& rhs) {
			                                            return lhs.*(ValueTraits::sort_key)
			                                                   < rhs.*(ValueTraits::sort_key);
		                                            }),
		                  "pool is not sorted anymore");

Florian Oetke's avatar
Florian Oetke committed
289
290
291
292
293
294
295
296
297
		return {*instance, i};
	}

	MIRRAGE_POOL_HEADER
	const unsigned char* MIRRAGE_POOL::_get_raw(IndexType i) const
	{
		MIRRAGE_INVARIANT(i < _used_elements,
		                  "Pool-Index out of bounds " + to_string(i) + ">=" + to_string(_used_elements));

298
299
		return reinterpret_cast<const unsigned char*>(_chunks[std::size_t(i / chunk_len)].get()
		                                              + (i % chunk_len));
Florian Oetke's avatar
Florian Oetke committed
300
301
302
303
304
305
	}

	MIRRAGE_POOL_HEADER
	T* MIRRAGE_POOL::_chunk(IndexType chunk_idx) noexcept
	{
		if(chunk_idx * chunk_len < _used_elements)
306
			return reinterpret_cast<T*>(_chunks.at(std::size_t(chunk_idx)).get());
Florian Oetke's avatar
Florian Oetke committed
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
		else
			return nullptr;
	}

	MIRRAGE_POOL_HEADER
	T* MIRRAGE_POOL::_chunk_end(T* begin, IndexType chunk_idx) noexcept
	{
		if(chunk_idx < _used_elements / chunk_len) {
			return begin + chunk_len;
		} else {
			return begin + (_used_elements % chunk_len);
		}
	}

	MIRRAGE_POOL_HEADER
	template <typename F>
Florian Oetke's avatar
Florian Oetke committed
323
324
	void MIRRAGE_POOL::_move_elements(
	        const index_t src, const index_t dst, F&& on_relocate, const index_t count, const bool last_empty)
Florian Oetke's avatar
Florian Oetke committed
325
	{
Florian Oetke's avatar
Florian Oetke committed
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
		MIRRAGE_INVARIANT(src != dst, "_move_elements with src==dst");

		(void) last_empty;

		if constexpr(!std::is_trivially_copyable_v<T>) {
			if(dst > src && last_empty) {
				new(_get_raw(dst + count - 1)) T(std::move(get(src + count - 1)));
				if(count > 1)
					_move_elements(src, dst, on_relocate, count - 1, false);

				on_relocate(src + count - 1, get(dst + count - 1), dst + count - 1);
				return;
			}
		}

Florian Oetke's avatar
Florian Oetke committed
341
342
343
344
345
346
		auto c_src = src;
		auto c_dst = dst;
		while(c_src - src < count) {
			auto step = util::min(count, chunk_len - c_src % chunk_len, chunk_len - c_dst % chunk_len);
			if constexpr(std::is_trivially_copyable_v<T>) {
				// yay, we can memmove
Florian Oetke's avatar
Florian Oetke committed
347
				std::memmove(_get_raw(c_dst), _get_raw(c_src), std::size_t(step) * sizeof(T));
Florian Oetke's avatar
Florian Oetke committed
348
			} else {
Florian Oetke's avatar
Florian Oetke committed
349
350
				// nay, we hava to move the objects
				if(dst > src) {
351
					std::move_backward(&get(c_src), &get(c_src) + step, &get(c_dst) + step);
Florian Oetke's avatar
Florian Oetke committed
352
353
354
355
356
357
358
359
360
361
362
363
364
				} else {
					std::move(&get(c_src), &get(c_src) + step, &get(c_dst));
				}
			}
			c_src += step;
			c_dst += step;
		}

		for(auto i : util::range(count)) {
			on_relocate(src + i, get(dst + i), dst + i);
		}
	}

Florian Oetke's avatar
Florian Oetke committed
365
366
367
368
369
370
371
	MIRRAGE_POOL_HEADER
	template <typename F>
	void MIRRAGE_POOL::_move_elements_uninitialized(const index_t src,
	                                                const index_t dst,
	                                                F&&           on_relocate,
	                                                const index_t count)
	{
372
		MIRRAGE_INVARIANT(src > dst || src + count < dst,
Florian Oetke's avatar
Florian Oetke committed
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
		                  "_move_elements_uninitialized with overlapping ranges");

		auto c_src = src;
		auto c_dst = dst;
		while(c_src - src < count) {
			auto step = util::min(count, chunk_len - c_src % chunk_len, chunk_len - c_dst % chunk_len);
			if constexpr(std::is_trivially_copyable_v<T>) {
				// yay, we can memmove
				std::memmove(_get_raw(c_dst), _get_raw(c_src), std::size_t(step) * sizeof(T));
			} else {
				// nay, we hava to move the objects
				std::uninitialized_move(
				        &get(c_src), &get(c_src) + step, reinterpret_cast<T*>(_get_raw(c_dst)));
			}
			c_src += step;
			c_dst += step;
		}

		for(auto i : util::range(count)) {
			on_relocate(src + i, get(dst + i), dst + i);
		}
	}

Florian Oetke's avatar
Florian Oetke committed
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
	MIRRAGE_POOL_HEADER
	void MIRRAGE_POOL::_pop_back()
	{
		MIRRAGE_INVARIANT(_used_elements > 0, "pop_back on empty pool");
#ifdef _NDEBUG
		std::memset(get(_usedElements - 1), 0xdead, element_size);
#endif
		get(_used_elements - 1).~T();
		_used_elements--;
	}

#undef MIRRAGE_POOL_HEADER
#undef MIRRAGE_POOL


	// ITERATOR IMPL

	template <class Pool>
	pool_iterator<Pool>::pool_iterator()
	  : _pool(nullptr)
	  , _chunk_index(0)
	  , _element_iter(nullptr)
	  , _element_iter_begin(nullptr)
	  , _element_iter_end(nullptr)
	{
	}

	template <class Pool>
	pool_iterator<Pool>::pool_iterator(Pool& pool, typename Pool::index_t index)
	  : _pool(&pool)
	  , _logical_index(0)
	  , _physical_index(0)
	  , _chunk_index(0)
	  , _element_iter(pool._chunk(0))
	  , _element_iter_begin(_element_iter)
	  , _element_iter_end(pool._chunk_end(_element_iter_begin, 0))
	  , _next_free(pool._freelist.begin())
	{

		if(index >= pool.size() || !_element_iter) {
			_logical_index  = pool.size();
			_physical_index = pool._used_elements;
			_element_iter   = nullptr;

		} else {
			if(_next_free != pool._freelist.end() && *_next_free == 0) {
				++_next_free;
				++*this; // jump to first valid element
			}

			_logical_index = 0;

			// skip the first 'index' elements
			*this += index;
		}
	}

	template <class Pool>
	auto pool_iterator<Pool>::get() noexcept -> value_type*
	{
		MIRRAGE_INVARIANT(_element_iter, "access to invalid pool_iterator");
Florian Oetke's avatar
Florian Oetke committed
457
458
459
460
461
462
463
		return std::launder(_element_iter);
	}

	template <class Pool>
	auto pool_iterator<Pool>::get() const noexcept -> const value_type*
	{
		MIRRAGE_INVARIANT(_element_iter, "access to invalid pool_iterator");
Florian Oetke's avatar
Florian Oetke committed
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
		return std::launder(_element_iter);
	}

	template <class Pool>
	auto pool_iterator<Pool>::operator++() -> pool_iterator&
	{
		MIRRAGE_INVARIANT(_element_iter != nullptr, "iterator overflow");

		auto failed = false;
		do {
			++_element_iter;
			++_physical_index;
			if(_element_iter == _element_iter_end) {
				++_chunk_index;
				_element_iter_begin = _element_iter = _pool->_chunk(_chunk_index);
				_element_iter_end                   = _pool->_chunk_end(_element_iter_begin, _chunk_index);
			}

			if(failed && _next_free != _pool->_freelist.end()) {
				_next_free++;
			}
			failed = true;
		} while(_next_free != _pool->_freelist.end() && *_next_free == _physical_index);

		++_logical_index;

		return *this;
	}

	template <class Pool>
	auto pool_iterator<Pool>::operator++(int) -> pool_iterator
	{
		pool_iterator t = *this;
		++*this;
		return t;
	}

	template <class Pool>
	auto pool_iterator<Pool>::operator--() -> pool_iterator&
	{
		auto failed = false;
		do {
			if(_element_iter == _element_iter_begin) {
				MIRRAGE_INVARIANT(_chunk_index > 0, "iterator underflow");
				--_chunk_index;
				_element_iter_begin = _pool->_chunk(_chunk_index);
				_element_iter_end   = _pool->_chunk_end(_element_iter_begin, _chunk_index);

				if(_element_iter_end != _element_iter_begin) {
					_element_iter = _element_iter_end - 1;
				} else {
					_element_iter = _element_iter_begin;
				}
			} else {
				--_element_iter;
			}

			--_physical_index;

			if(failed && _next_free != _pool->_freelist.end()) {
				_next_free++;
			}
			failed = true;
		} while(_next_free != _pool->_freelist.end() && *_next_free == _physical_index);

		--_logical_index;

		return *this;
	}

	template <class Pool>
	auto pool_iterator<Pool>::operator--(int) -> pool_iterator
	{
		pool_iterator t = *this;
		--*this;
		return t;
	}

	template <class Pool>
	auto pool_iterator<Pool>::operator+=(difference_type n) -> pool_iterator&
	{
		// compute physical_index, skipping empty slots
546
		auto target_physical_idx = index_type(physical_index() + n);
Florian Oetke's avatar
Florian Oetke committed
547
548
549
550
551
552
553

		while(_next_free != _pool->_freelist.end() && *_next_free <= target_physical_idx) {
			target_physical_idx++;
			_next_free++;
		}

		// compute chunk and pointers based on new physical index
554
		_logical_index      = index_type(_logical_index + n);
Florian Oetke's avatar
Florian Oetke committed
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
		_physical_index     = target_physical_idx;
		_chunk_index        = target_physical_idx / Pool::chunk_len;
		_element_iter_begin = _pool->_chunk(_chunk_index);
		_element_iter_end   = _pool->_chunk_end(_element_iter_begin, _chunk_index);
		_element_iter       = _element_iter_begin + (target_physical_idx % Pool::chunk_len);

		if(target_physical_idx >= _pool->_used_elements) {
			*this = _pool->end();
		}

		return *this;
	}

	template <class Pool>
	auto pool_iterator<Pool>::operator-=(difference_type n) -> pool_iterator&
	{
		*this += -n;
		return *this;
	}

	template <class Pool>
	auto pool_iterator<Pool>::operator[](difference_type i) -> reference
	{
		auto iter = *this;
		iter += i;
		return *iter;
	}

} // namespace mirrage::util