summaryrefslogtreecommitdiffstats
path: root/src/common
diff options
context:
space:
mode:
Diffstat (limited to '')
-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
detached_tasks.h
bit_cast.h
bit_field.h
+ bit_set.h
bit_util.h
cityhash.cpp
cityhash.h
@@ -140,7 +141,6 @@ add_library(common STATIC
microprofile.h
microprofileui.h
misc.cpp
- multi_level_queue.h
page_table.cpp
page_table.h
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 @@
+/*
+ * Copyright (c) 2018-2020 Atmosphère-NX
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#pragma once
+
+#include <array>
+#include <bit>
+
+#include "common/alignment.h"
+#include "common/bit_util.h"
+#include "common/common_types.h"
+
+namespace Common {
+
+namespace impl {
+
+template <typename Storage, size_t N>
+class BitSet {
+
+public:
+ constexpr BitSet() = default;
+
+ constexpr void SetBit(size_t i) {
+ this->words[i / FlagsPerWord] |= GetBitMask(i % FlagsPerWord);
+ }
+
+ constexpr void ClearBit(size_t i) {
+ this->words[i / FlagsPerWord] &= ~GetBitMask(i % FlagsPerWord);
+ }
+
+ constexpr size_t CountLeadingZero() const {
+ for (size_t i = 0; i < NumWords; i++) {
+ if (this->words[i]) {
+ return FlagsPerWord * i + CountLeadingZeroImpl(this->words[i]);
+ }
+ }
+ return FlagsPerWord * NumWords;
+ }
+
+ constexpr size_t GetNextSet(size_t n) const {
+ for (size_t i = (n + 1) / FlagsPerWord; i < NumWords; i++) {
+ Storage word = this->words[i];
+ if (!IsAligned(n + 1, FlagsPerWord)) {
+ word &= GetBitMask(n % FlagsPerWord) - 1;
+ }
+ if (word) {
+ return FlagsPerWord * i + CountLeadingZeroImpl(word);
+ }
+ }
+ return FlagsPerWord * NumWords;
+ }
+
+private:
+ static_assert(std::is_unsigned_v<Storage>);
+ static_assert(sizeof(Storage) <= sizeof(u64));
+
+ static constexpr size_t FlagsPerWord = BitSize<Storage>();
+ static constexpr size_t NumWords = AlignUp(N, FlagsPerWord) / FlagsPerWord;
+
+ static constexpr auto CountLeadingZeroImpl(Storage word) {
+ return std::countl_zero(static_cast<unsigned long long>(word)) -
+ (BitSize<unsigned long long>() - FlagsPerWord);
+ }
+
+ static constexpr Storage GetBitMask(size_t bit) {
+ return Storage(1) << (FlagsPerWord - 1 - bit);
+ }
+
+ std::array<Storage, NumWords> words{};
+};
+
+} // namespace impl
+
+template <size_t N>
+using BitSet8 = impl::BitSet<u8, N>;
+
+template <size_t N>
+using BitSet16 = impl::BitSet<u16, N>;
+
+template <size_t N>
+using BitSet32 = impl::BitSet<u32, N>;
+
+template <size_t N>
+using BitSet64 = impl::BitSet<u64, N>;
+
+} // 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 @@
-// Copyright 2019 TuxSH
-// Licensed under GPLv2 or any later version
-// Refer to the license.txt file included.
-
-#pragma once
-
-#include <array>
-#include <iterator>
-#include <list>
-#include <utility>
-
-#include "common/bit_util.h"
-#include "common/common_types.h"
-
-namespace Common {
-
-/**
- * A MultiLevelQueue is a type of priority queue which has the following characteristics:
- * - iteratable through each of its elements.
- * - back can be obtained.
- * - O(1) add, lookup (both front and back)
- * - discrete priorities and a max of 64 priorities (limited domain)
- * This type of priority queue is normaly used for managing threads within an scheduler
- */
-template <typename T, std::size_t Depth>
-class MultiLevelQueue {
-public:
- using value_type = T;
- using reference = value_type&;
- using const_reference = const value_type&;
- using pointer = value_type*;
- using const_pointer = const value_type*;
-
- using difference_type = typename std::pointer_traits<pointer>::difference_type;
- using size_type = std::size_t;
-
- template <bool is_constant>
- class iterator_impl {
- public:
- using iterator_category = std::bidirectional_iterator_tag;
- using value_type = T;
- using pointer = std::conditional_t<is_constant, T*, const T*>;
- using reference = std::conditional_t<is_constant, const T&, T&>;
- using difference_type = typename std::pointer_traits<pointer>::difference_type;
-
- friend bool operator==(const iterator_impl& lhs, const iterator_impl& rhs) {
- if (lhs.IsEnd() && rhs.IsEnd())
- return true;
- return std::tie(lhs.current_priority, lhs.it) == std::tie(rhs.current_priority, rhs.it);
- }
-
- friend bool operator!=(const iterator_impl& lhs, const iterator_impl& rhs) {
- return !operator==(lhs, rhs);
- }
-
- reference operator*() const {
- return *it;
- }
-
- pointer operator->() const {
- return it.operator->();
- }
-
- iterator_impl& operator++() {
- if (IsEnd()) {
- return *this;
- }
-
- ++it;
-
- if (it == GetEndItForPrio()) {
- u64 prios = mlq.used_priorities;
- prios &= ~((1ULL << (current_priority + 1)) - 1);
- if (prios == 0) {
- current_priority = static_cast<u32>(mlq.depth());
- } else {
- current_priority = CountTrailingZeroes64(prios);
- it = GetBeginItForPrio();
- }
- }
- return *this;
- }
-
- iterator_impl& operator--() {
- if (IsEnd()) {
- if (mlq.used_priorities != 0) {
- current_priority = 63 - CountLeadingZeroes64(mlq.used_priorities);
- it = GetEndItForPrio();
- --it;
- }
- } else if (it == GetBeginItForPrio()) {
- u64 prios = mlq.used_priorities;
- prios &= (1ULL << current_priority) - 1;
- if (prios != 0) {
- current_priority = CountTrailingZeroes64(prios);
- it = GetEndItForPrio();
- --it;
- }
- } else {
- --it;
- }
- return *this;
- }
-
- iterator_impl operator++(int) {
- const iterator_impl v{*this};
- ++(*this);
- return v;
- }
-
- iterator_impl operator--(int) {
- const iterator_impl v{*this};
- --(*this);
- return v;
- }
-
- // allow implicit const->non-const
- iterator_impl(const iterator_impl<false>& other)
- : mlq(other.mlq), it(other.it), current_priority(other.current_priority) {}
-
- iterator_impl(const iterator_impl<true>& other)
- : mlq(other.mlq), it(other.it), current_priority(other.current_priority) {}
-
- iterator_impl& operator=(const iterator_impl<false>& other) {
- mlq = other.mlq;
- it = other.it;
- current_priority = other.current_priority;
- return *this;
- }
-
- friend class iterator_impl<true>;
- iterator_impl() = default;
-
- private:
- friend class MultiLevelQueue;
- using container_ref =
- std::conditional_t<is_constant, const MultiLevelQueue&, MultiLevelQueue&>;
- using list_iterator = std::conditional_t<is_constant, typename std::list<T>::const_iterator,
- typename std::list<T>::iterator>;
-
- explicit iterator_impl(container_ref mlq, list_iterator it, u32 current_priority)
- : mlq(mlq), it(it), current_priority(current_priority) {}
- explicit iterator_impl(container_ref mlq, u32 current_priority)
- : mlq(mlq), it(), current_priority(current_priority) {}
-
- bool IsEnd() const {
- return current_priority == mlq.depth();
- }
-
- list_iterator GetBeginItForPrio() const {
- return mlq.levels[current_priority].begin();
- }
-
- list_iterator GetEndItForPrio() const {
- return mlq.levels[current_priority].end();
- }
-
- container_ref mlq;
- list_iterator it;
- u32 current_priority;
- };
-
- using iterator = iterator_impl<false>;
- using const_iterator = iterator_impl<true>;
-
- void add(const T& element, u32 priority, bool send_back = true) {
- if (send_back)
- levels[priority].push_back(element);
- else
- levels[priority].push_front(element);
- used_priorities |= 1ULL << priority;
- }
-
- void remove(const T& element, u32 priority) {
- auto it = ListIterateTo(levels[priority], element);
- if (it == levels[priority].end())
- return;
- levels[priority].erase(it);
- if (levels[priority].empty()) {
- used_priorities &= ~(1ULL << priority);
- }
- }
-
- void adjust(const T& element, u32 old_priority, u32 new_priority, bool adjust_front = false) {
- remove(element, old_priority);
- add(element, new_priority, !adjust_front);
- }
- void adjust(const_iterator it, u32 old_priority, u32 new_priority, bool adjust_front = false) {
- adjust(*it, old_priority, new_priority, adjust_front);
- }
-
- void transfer_to_front(const T& element, u32 priority, MultiLevelQueue& other) {
- ListSplice(other.levels[priority], other.levels[priority].begin(), levels[priority],
- ListIterateTo(levels[priority], element));
-
- other.used_priorities |= 1ULL << priority;
-
- if (levels[priority].empty()) {
- used_priorities &= ~(1ULL << priority);
- }
- }
-
- void transfer_to_front(const_iterator it, u32 priority, MultiLevelQueue& other) {
- transfer_to_front(*it, priority, other);
- }
-
- void transfer_to_back(const T& element, u32 priority, MultiLevelQueue& other) {
- ListSplice(other.levels[priority], other.levels[priority].end(), levels[priority],
- ListIterateTo(levels[priority], element));
-
- other.used_priorities |= 1ULL << priority;
-
- if (levels[priority].empty()) {
- used_priorities &= ~(1ULL << priority);
- }
- }
-
- void transfer_to_back(const_iterator it, u32 priority, MultiLevelQueue& other) {
- transfer_to_back(*it, priority, other);
- }
-
- void yield(u32 priority, std::size_t n = 1) {
- ListShiftForward(levels[priority], n);
- }
-
- [[nodiscard]] std::size_t depth() const {
- return Depth;
- }
-
- [[nodiscard]] std::size_t size(u32 priority) const {
- return levels[priority].size();
- }
-
- [[nodiscard]] std::size_t size() const {
- u64 priorities = used_priorities;
- std::size_t size = 0;
- while (priorities != 0) {
- const u64 current_priority = CountTrailingZeroes64(priorities);
- size += levels[current_priority].size();
- priorities &= ~(1ULL << current_priority);
- }
- return size;
- }
-
- [[nodiscard]] bool empty() const {
- return used_priorities == 0;
- }
-
- [[nodiscard]] bool empty(u32 priority) const {
- return (used_priorities & (1ULL << priority)) == 0;
- }
-
- [[nodiscard]] u32 highest_priority_set(u32 max_priority = 0) const {
- const u64 priorities =
- max_priority == 0 ? used_priorities : (used_priorities & ~((1ULL << max_priority) - 1));
- return priorities == 0 ? Depth : static_cast<u32>(CountTrailingZeroes64(priorities));
- }
-
- [[nodiscard]] u32 lowest_priority_set(u32 min_priority = Depth - 1) const {
- const u64 priorities = min_priority >= Depth - 1
- ? used_priorities
- : (used_priorities & ((1ULL << (min_priority + 1)) - 1));
- return priorities == 0 ? Depth : 63 - CountLeadingZeroes64(priorities);
- }
-
- [[nodiscard]] const_iterator cbegin(u32 max_prio = 0) const {
- const u32 priority = highest_priority_set(max_prio);
- return priority == Depth ? cend()
- : const_iterator{*this, levels[priority].cbegin(), priority};
- }
- [[nodiscard]] const_iterator begin(u32 max_prio = 0) const {
- return cbegin(max_prio);
- }
- [[nodiscard]] iterator begin(u32 max_prio = 0) {
- const u32 priority = highest_priority_set(max_prio);
- return priority == Depth ? end() : iterator{*this, levels[priority].begin(), priority};
- }
-
- [[nodiscard]] const_iterator cend(u32 min_prio = Depth - 1) const {
- return min_prio == Depth - 1 ? const_iterator{*this, Depth} : cbegin(min_prio + 1);
- }
- [[nodiscard]] const_iterator end(u32 min_prio = Depth - 1) const {
- return cend(min_prio);
- }
- [[nodiscard]] iterator end(u32 min_prio = Depth - 1) {
- return min_prio == Depth - 1 ? iterator{*this, Depth} : begin(min_prio + 1);
- }
-
- [[nodiscard]] T& front(u32 max_priority = 0) {
- const u32 priority = highest_priority_set(max_priority);
- return levels[priority == Depth ? 0 : priority].front();
- }
- [[nodiscard]] const T& front(u32 max_priority = 0) const {
- const u32 priority = highest_priority_set(max_priority);
- return levels[priority == Depth ? 0 : priority].front();
- }
-
- [[nodiscard]] T& back(u32 min_priority = Depth - 1) {
- const u32 priority = lowest_priority_set(min_priority); // intended
- return levels[priority == Depth ? 63 : priority].back();
- }
- [[nodiscard]] const T& back(u32 min_priority = Depth - 1) const {
- const u32 priority = lowest_priority_set(min_priority); // intended
- return levels[priority == Depth ? 63 : priority].back();
- }
-
- void clear() {
- used_priorities = 0;
- for (std::size_t i = 0; i < Depth; i++) {
- levels[i].clear();
- }
- }
-
-private:
- using const_list_iterator = typename std::list<T>::const_iterator;
-
- static void ListShiftForward(std::list<T>& list, const std::size_t shift = 1) {
- if (shift >= list.size()) {
- return;
- }
-
- const auto begin_range = list.begin();
- const auto end_range = std::next(begin_range, shift);
- list.splice(list.end(), list, begin_range, end_range);
- }
-
- static void ListSplice(std::list<T>& in_list, const_list_iterator position,
- std::list<T>& out_list, const_list_iterator element) {
- in_list.splice(position, out_list, element);
- }
-
- [[nodiscard]] static const_list_iterator ListIterateTo(const std::list<T>& list,
- const T& element) {
- auto it = list.cbegin();
- while (it != list.cend() && *it != element) {
- ++it;
- }
- return it;
- }
-
- std::array<std::list<T>, Depth> levels;
- u64 used_priorities = 0;
-};
-
-} // namespace Common
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-02 20:10:23 +0100