summaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
Diffstat (limited to 'src/common')
-rw-r--r--src/common/CMakeLists.txt2
-rw-r--r--src/common/bit_set.h99
-rw-r--r--src/common/multi_level_queue.h345
3 files changed, 100 insertions, 346 deletions
diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt
index 0acf70a0a..943ff996e 100644
--- a/src/common/CMakeLists.txt
+++ b/src/common/CMakeLists.txt
@@ -104,6 +104,7 @@ add_library(common STATIC
104 detached_tasks.h 104 detached_tasks.h
105 bit_cast.h 105 bit_cast.h
106 bit_field.h 106 bit_field.h
107 bit_set.h
107 bit_util.h 108 bit_util.h
108 cityhash.cpp 109 cityhash.cpp
109 cityhash.h 110 cityhash.h
@@ -140,7 +141,6 @@ add_library(common STATIC
140 microprofile.h 141 microprofile.h
141 microprofileui.h 142 microprofileui.h
142 misc.cpp 143 misc.cpp
143 multi_level_queue.h
144 page_table.cpp 144 page_table.cpp
145 page_table.h 145 page_table.h
146 param_package.cpp 146 param_package.cpp
diff --git a/src/common/bit_set.h b/src/common/bit_set.h
new file mode 100644
index 000000000..9235ad412
--- /dev/null
+++ b/src/common/bit_set.h
@@ -0,0 +1,99 @@
1/*
2 * Copyright (c) 2018-2020 Atmosphère-NX
3 *
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms and conditions of the GNU General Public License,
6 * version 2, as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
11 * more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program. If not, see <http://www.gnu.org/licenses/>.
15 */
16
17#pragma once
18
19#include <array>
20#include <bit>
21
22#include "common/alignment.h"
23#include "common/bit_util.h"
24#include "common/common_types.h"
25
26namespace Common {
27
28namespace impl {
29
30template <typename Storage, size_t N>
31class BitSet {
32
33public:
34 constexpr BitSet() = default;
35
36 constexpr void SetBit(size_t i) {
37 this->words[i / FlagsPerWord] |= GetBitMask(i % FlagsPerWord);
38 }
39
40 constexpr void ClearBit(size_t i) {
41 this->words[i / FlagsPerWord] &= ~GetBitMask(i % FlagsPerWord);
42 }
43
44 constexpr size_t CountLeadingZero() const {
45 for (size_t i = 0; i < NumWords; i++) {
46 if (this->words[i]) {
47 return FlagsPerWord * i + CountLeadingZeroImpl(this->words[i]);
48 }
49 }
50 return FlagsPerWord * NumWords;
51 }
52
53 constexpr size_t GetNextSet(size_t n) const {
54 for (size_t i = (n + 1) / FlagsPerWord; i < NumWords; i++) {
55 Storage word = this->words[i];
56 if (!IsAligned(n + 1, FlagsPerWord)) {
57 word &= GetBitMask(n % FlagsPerWord) - 1;
58 }
59 if (word) {
60 return FlagsPerWord * i + CountLeadingZeroImpl(word);
61 }
62 }
63 return FlagsPerWord * NumWords;
64 }
65
66private:
67 static_assert(std::is_unsigned_v<Storage>);
68 static_assert(sizeof(Storage) <= sizeof(u64));
69
70 static constexpr size_t FlagsPerWord = BitSize<Storage>();
71 static constexpr size_t NumWords = AlignUp(N, FlagsPerWord) / FlagsPerWord;
72
73 static constexpr auto CountLeadingZeroImpl(Storage word) {
74 return std::countl_zero(static_cast<unsigned long long>(word)) -
75 (BitSize<unsigned long long>() - FlagsPerWord);
76 }
77
78 static constexpr Storage GetBitMask(size_t bit) {
79 return Storage(1) << (FlagsPerWord - 1 - bit);
80 }
81
82 std::array<Storage, NumWords> words{};
83};
84
85} // namespace impl
86
87template <size_t N>
88using BitSet8 = impl::BitSet<u8, N>;
89
90template <size_t N>
91using BitSet16 = impl::BitSet<u16, N>;
92
93template <size_t N>
94using BitSet32 = impl::BitSet<u32, N>;
95
96template <size_t N>
97using BitSet64 = impl::BitSet<u64, N>;
98
99} // namespace Common
diff --git a/src/common/multi_level_queue.h b/src/common/multi_level_queue.h
deleted file mode 100644
index 4b305bf40..000000000
--- a/src/common/multi_level_queue.h
+++ /dev/null
@@ -1,345 +0,0 @@
1// Copyright 2019 TuxSH
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#pragma once
6
7#include <array>
8#include <iterator>
9#include <list>
10#include <utility>
11
12#include "common/bit_util.h"
13#include "common/common_types.h"
14
15namespace Common {
16
17/**
18 * A MultiLevelQueue is a type of priority queue which has the following characteristics:
19 * - iteratable through each of its elements.
20 * - back can be obtained.
21 * - O(1) add, lookup (both front and back)
22 * - discrete priorities and a max of 64 priorities (limited domain)
23 * This type of priority queue is normaly used for managing threads within an scheduler
24 */
25template <typename T, std::size_t Depth>
26class MultiLevelQueue {
27public:
28 using value_type = T;
29 using reference = value_type&;
30 using const_reference = const value_type&;
31 using pointer = value_type*;
32 using const_pointer = const value_type*;
33
34 using difference_type = typename std::pointer_traits<pointer>::difference_type;
35 using size_type = std::size_t;
36
37 template <bool is_constant>
38 class iterator_impl {
39 public:
40 using iterator_category = std::bidirectional_iterator_tag;
41 using value_type = T;
42 using pointer = std::conditional_t<is_constant, T*, const T*>;
43 using reference = std::conditional_t<is_constant, const T&, T&>;
44 using difference_type = typename std::pointer_traits<pointer>::difference_type;
45
46 friend bool operator==(const iterator_impl& lhs, const iterator_impl& rhs) {
47 if (lhs.IsEnd() && rhs.IsEnd())
48 return true;
49 return std::tie(lhs.current_priority, lhs.it) == std::tie(rhs.current_priority, rhs.it);
50 }
51
52 friend bool operator!=(const iterator_impl& lhs, const iterator_impl& rhs) {
53 return !operator==(lhs, rhs);
54 }
55
56 reference operator*() const {
57 return *it;
58 }
59
60 pointer operator->() const {
61 return it.operator->();
62 }
63
64 iterator_impl& operator++() {
65 if (IsEnd()) {
66 return *this;
67 }
68
69 ++it;
70
71 if (it == GetEndItForPrio()) {
72 u64 prios = mlq.used_priorities;
73 prios &= ~((1ULL << (current_priority + 1)) - 1);
74 if (prios == 0) {
75 current_priority = static_cast<u32>(mlq.depth());
76 } else {
77 current_priority = CountTrailingZeroes64(prios);
78 it = GetBeginItForPrio();
79 }
80 }
81 return *this;
82 }
83
84 iterator_impl& operator--() {
85 if (IsEnd()) {
86 if (mlq.used_priorities != 0) {
87 current_priority = 63 - CountLeadingZeroes64(mlq.used_priorities);
88 it = GetEndItForPrio();
89 --it;
90 }
91 } else if (it == GetBeginItForPrio()) {
92 u64 prios = mlq.used_priorities;
93 prios &= (1ULL << current_priority) - 1;
94 if (prios != 0) {
95 current_priority = CountTrailingZeroes64(prios);
96 it = GetEndItForPrio();
97 --it;
98 }
99 } else {
100 --it;
101 }
102 return *this;
103 }
104
105 iterator_impl operator++(int) {
106 const iterator_impl v{*this};
107 ++(*this);
108 return v;
109 }
110
111 iterator_impl operator--(int) {
112 const iterator_impl v{*this};
113 --(*this);
114 return v;
115 }
116
117 // allow implicit const->non-const
118 iterator_impl(const iterator_impl<false>& other)
119 : mlq(other.mlq), it(other.it), current_priority(other.current_priority) {}
120
121 iterator_impl(const iterator_impl<true>& other)
122 : mlq(other.mlq), it(other.it), current_priority(other.current_priority) {}
123
124 iterator_impl& operator=(const iterator_impl<false>& other) {
125 mlq = other.mlq;
126 it = other.it;
127 current_priority = other.current_priority;
128 return *this;
129 }
130
131 friend class iterator_impl<true>;
132 iterator_impl() = default;
133
134 private:
135 friend class MultiLevelQueue;
136 using container_ref =
137 std::conditional_t<is_constant, const MultiLevelQueue&, MultiLevelQueue&>;
138 using list_iterator = std::conditional_t<is_constant, typename std::list<T>::const_iterator,
139 typename std::list<T>::iterator>;
140
141 explicit iterator_impl(container_ref mlq, list_iterator it, u32 current_priority)
142 : mlq(mlq), it(it), current_priority(current_priority) {}
143 explicit iterator_impl(container_ref mlq, u32 current_priority)
144 : mlq(mlq), it(), current_priority(current_priority) {}
145
146 bool IsEnd() const {
147 return current_priority == mlq.depth();
148 }
149
150 list_iterator GetBeginItForPrio() const {
151 return mlq.levels[current_priority].begin();
152 }
153
154 list_iterator GetEndItForPrio() const {
155 return mlq.levels[current_priority].end();
156 }
157
158 container_ref mlq;
159 list_iterator it;
160 u32 current_priority;
161 };
162
163 using iterator = iterator_impl<false>;
164 using const_iterator = iterator_impl<true>;
165
166 void add(const T& element, u32 priority, bool send_back = true) {
167 if (send_back)
168 levels[priority].push_back(element);
169 else
170 levels[priority].push_front(element);
171 used_priorities |= 1ULL << priority;
172 }
173
174 void remove(const T& element, u32 priority) {
175 auto it = ListIterateTo(levels[priority], element);
176 if (it == levels[priority].end())
177 return;
178 levels[priority].erase(it);
179 if (levels[priority].empty()) {
180 used_priorities &= ~(1ULL << priority);
181 }
182 }
183
184 void adjust(const T& element, u32 old_priority, u32 new_priority, bool adjust_front = false) {
185 remove(element, old_priority);
186 add(element, new_priority, !adjust_front);
187 }
188 void adjust(const_iterator it, u32 old_priority, u32 new_priority, bool adjust_front = false) {
189 adjust(*it, old_priority, new_priority, adjust_front);
190 }
191
192 void transfer_to_front(const T& element, u32 priority, MultiLevelQueue& other) {
193 ListSplice(other.levels[priority], other.levels[priority].begin(), levels[priority],
194 ListIterateTo(levels[priority], element));
195
196 other.used_priorities |= 1ULL << priority;
197
198 if (levels[priority].empty()) {
199 used_priorities &= ~(1ULL << priority);
200 }
201 }
202
203 void transfer_to_front(const_iterator it, u32 priority, MultiLevelQueue& other) {
204 transfer_to_front(*it, priority, other);
205 }
206
207 void transfer_to_back(const T& element, u32 priority, MultiLevelQueue& other) {
208 ListSplice(other.levels[priority], other.levels[priority].end(), levels[priority],
209 ListIterateTo(levels[priority], element));
210
211 other.used_priorities |= 1ULL << priority;
212
213 if (levels[priority].empty()) {
214 used_priorities &= ~(1ULL << priority);
215 }
216 }
217
218 void transfer_to_back(const_iterator it, u32 priority, MultiLevelQueue& other) {
219 transfer_to_back(*it, priority, other);
220 }
221
222 void yield(u32 priority, std::size_t n = 1) {
223 ListShiftForward(levels[priority], n);
224 }
225
226 [[nodiscard]] std::size_t depth() const {
227 return Depth;
228 }
229
230 [[nodiscard]] std::size_t size(u32 priority) const {
231 return levels[priority].size();
232 }
233
234 [[nodiscard]] std::size_t size() const {
235 u64 priorities = used_priorities;
236 std::size_t size = 0;
237 while (priorities != 0) {
238 const u64 current_priority = CountTrailingZeroes64(priorities);
239 size += levels[current_priority].size();
240 priorities &= ~(1ULL << current_priority);
241 }
242 return size;
243 }
244
245 [[nodiscard]] bool empty() const {
246 return used_priorities == 0;
247 }
248
249 [[nodiscard]] bool empty(u32 priority) const {
250 return (used_priorities & (1ULL << priority)) == 0;
251 }
252
253 [[nodiscard]] u32 highest_priority_set(u32 max_priority = 0) const {
254 const u64 priorities =
255 max_priority == 0 ? used_priorities : (used_priorities & ~((1ULL << max_priority) - 1));
256 return priorities == 0 ? Depth : static_cast<u32>(CountTrailingZeroes64(priorities));
257 }
258
259 [[nodiscard]] u32 lowest_priority_set(u32 min_priority = Depth - 1) const {
260 const u64 priorities = min_priority >= Depth - 1
261 ? used_priorities
262 : (used_priorities & ((1ULL << (min_priority + 1)) - 1));
263 return priorities == 0 ? Depth : 63 - CountLeadingZeroes64(priorities);
264 }
265
266 [[nodiscard]] const_iterator cbegin(u32 max_prio = 0) const {
267 const u32 priority = highest_priority_set(max_prio);
268 return priority == Depth ? cend()
269 : const_iterator{*this, levels[priority].cbegin(), priority};
270 }
271 [[nodiscard]] const_iterator begin(u32 max_prio = 0) const {
272 return cbegin(max_prio);
273 }
274 [[nodiscard]] iterator begin(u32 max_prio = 0) {
275 const u32 priority = highest_priority_set(max_prio);
276 return priority == Depth ? end() : iterator{*this, levels[priority].begin(), priority};
277 }
278
279 [[nodiscard]] const_iterator cend(u32 min_prio = Depth - 1) const {
280 return min_prio == Depth - 1 ? const_iterator{*this, Depth} : cbegin(min_prio + 1);
281 }
282 [[nodiscard]] const_iterator end(u32 min_prio = Depth - 1) const {
283 return cend(min_prio);
284 }
285 [[nodiscard]] iterator end(u32 min_prio = Depth - 1) {
286 return min_prio == Depth - 1 ? iterator{*this, Depth} : begin(min_prio + 1);
287 }
288
289 [[nodiscard]] T& front(u32 max_priority = 0) {
290 const u32 priority = highest_priority_set(max_priority);
291 return levels[priority == Depth ? 0 : priority].front();
292 }
293 [[nodiscard]] const T& front(u32 max_priority = 0) const {
294 const u32 priority = highest_priority_set(max_priority);
295 return levels[priority == Depth ? 0 : priority].front();
296 }
297
298 [[nodiscard]] T& back(u32 min_priority = Depth - 1) {
299 const u32 priority = lowest_priority_set(min_priority); // intended
300 return levels[priority == Depth ? 63 : priority].back();
301 }
302 [[nodiscard]] const T& back(u32 min_priority = Depth - 1) const {
303 const u32 priority = lowest_priority_set(min_priority); // intended
304 return levels[priority == Depth ? 63 : priority].back();
305 }
306
307 void clear() {
308 used_priorities = 0;
309 for (std::size_t i = 0; i < Depth; i++) {
310 levels[i].clear();
311 }
312 }
313
314private:
315 using const_list_iterator = typename std::list<T>::const_iterator;
316
317 static void ListShiftForward(std::list<T>& list, const std::size_t shift = 1) {
318 if (shift >= list.size()) {
319 return;
320 }
321
322 const auto begin_range = list.begin();
323 const auto end_range = std::next(begin_range, shift);
324 list.splice(list.end(), list, begin_range, end_range);
325 }
326
327 static void ListSplice(std::list<T>& in_list, const_list_iterator position,
328 std::list<T>& out_list, const_list_iterator element) {
329 in_list.splice(position, out_list, element);
330 }
331
332 [[nodiscard]] static const_list_iterator ListIterateTo(const std::list<T>& list,
333 const T& element) {
334 auto it = list.cbegin();
335 while (it != list.cend() && *it != element) {
336 ++it;
337 }
338 return it;
339 }
340
341 std::array<std::list<T>, Depth> levels;
342 u64 used_priorities = 0;
343};
344
345} // namespace Common
HIC SVNT DRACONES