git.seregonwar.com

common/slot_vector.h

1	// SPDX-FileCopyrightText: Copyright 2020 yuzu Emulator Project
2	// SPDX-License-Identifier: GPL-2.0-or-later
3
4	#pragma once
5
6	#include <numeric>
7	#include <utility>
8	#include <vector>
9	#include "common/assert.h"
10	#include "common/shadpkg_types.h"
11
12	namespace Common {
13
14	struct SlotId {
15	static constexpr u32 INVALID_INDEX = std::numeric_limits<u32>::max();
16
17	constexpr auto operator<=>(const SlotId&) const noexcept = default;
18
19	constexpr explicit operator bool() const noexcept {
20	return index != INVALID_INDEX;
21	}
22
23	u32 index = INVALID_INDEX;
24	};
25
26	template <class T>
27	class SlotVector {
28	constexpr static std::size_t InitialCapacity = 2048;
29
30	public:
31	SlotVector() {
32	Reserve(InitialCapacity);
33	}
34
35	~SlotVector() noexcept {
36	std::size_t index = 0;
37	for (u64 bits : stored_bitset) {
38	for (std::size_t bit = 0; bits; ++bit, bits >>= 1) {
39	if ((bits & 1) != 0) {
40	values[index + bit].object.~T();
41	}
42	}
43	index += 64;
44	}
45	delete[] values;
46	}
47
48	[[nodiscard]] T& operator[](SlotId id) noexcept {
49	ValidateIndex(id);
50	return values[id.index].object;
51	}
52
53	[[nodiscard]] const T& operator[](SlotId id) const noexcept {
54	ValidateIndex(id);
55	return values[id.index].object;
56	}
57
58	bool is_allocated(SlotId id) const {
59	return ReadStorageBit(id.index);
60	}
61
62	template <typename... Args>
63	[[nodiscard]] SlotId insert(Args&&... args) noexcept {
64	const u32 index = FreeValueIndex();
65	new (&values[index].object) T(std::forward<Args>(args)...);
66	SetStorageBit(index);
67
68	return SlotId{index};
69	}
70
71	void erase(SlotId id) noexcept {
72	values[id.index].object.~T();
73	free_list.push_back(id.index);
74	ResetStorageBit(id.index);
75	}
76
77	std::size_t size() const noexcept {
78	return values_capacity - free_list.size();
79	}
80
81	private:
82	struct NonTrivialDummy {
83	NonTrivialDummy() noexcept {}
84	};
85
86	union Entry {
87	Entry() noexcept : dummy{} {}
88	~Entry() noexcept {}
89
90	NonTrivialDummy dummy;
91	T object;
92	};
93
94	void SetStorageBit(u32 index) noexcept {
95	stored_bitset[index / 64] \|= u64(1) << (index % 64);
96	}
97
98	void ResetStorageBit(u32 index) noexcept {
99	stored_bitset[index / 64] &= ~(u64(1) << (index % 64));
100	}
101
102	bool ReadStorageBit(u32 index) const noexcept {
103	return ((stored_bitset[index / 64] >> (index % 64)) & 1) != 0;
104	}
105
106	void ValidateIndex([[maybe_unused]] SlotId id) const noexcept {
107	DEBUG_ASSERT(id);
108	DEBUG_ASSERT(id.index / 64 < stored_bitset.size());
109	DEBUG_ASSERT(((stored_bitset[id.index / 64] >> (id.index % 64)) & 1) != 0);
110	}
111
112	[[nodiscard]] u32 FreeValueIndex() noexcept {
113	if (free_list.empty()) {
114	Reserve(values_capacity ? (values_capacity << 1) : 1);
115	}
116
117	const u32 free_index = free_list.back();
118	free_list.pop_back();
119	return free_index;
120	}
121
122	void Reserve(std::size_t new_capacity) noexcept {
123	Entry* const new_values = new Entry[new_capacity];
124	std::size_t index = 0;
125	for (u64 bits : stored_bitset) {
126	for (std::size_t bit = 0; bits; ++bit, bits >>= 1) {
127	const std::size_t i = index + bit;
128	if ((bits & 1) == 0) {
129	continue;
130	}
131	T& old_value = values[i].object;
132	new (&new_values[i].object) T(std::move(old_value));
133	old_value.~T();
134	}
135	index += 64;
136	}
137
138	stored_bitset.resize((new_capacity + 63) / 64);
139
140	const std::size_t old_free_size = free_list.size();
141	free_list.resize(old_free_size + (new_capacity - values_capacity));
142	const std::size_t new_free_size = free_list.size();
143	std::iota(free_list.rbegin(), free_list.rbegin() + new_free_size - old_free_size,
144	static_cast<u32>(values_capacity));
145
146	delete[] values;
147	values = new_values;
148	values_capacity = new_capacity;
149	}
150
151	Entry* values = nullptr;
152	std::size_t values_capacity = 0;
153
154	std::vector<u64> stored_bitset;
155	std::vector<u32> free_list;
156	};
157
158	} // namespace Common
159
160	template <>
161	struct std::hash<Common::SlotId> {
162	std::size_t operator()(const Common::SlotId& id) const noexcept {
163	return std::hash<u32>{}(id.index);
164	}
165	};
166

Seregon/ShadPKG