thread_queue_list.h
1 // Copyright 2014 Citra Emulator Project / PPSSPP Project 2 // Licensed under GPLv2 or any later version 3 // Refer to the license.txt file included. 4 5 #pragma once 6 7 #include <algorithm> 8 #include <array> 9 #include <deque> 10 #include <boost/serialization/deque.hpp> 11 #include <boost/serialization/split_member.hpp> 12 #include "common/common_types.h" 13 14 namespace Common { 15 16 template <class T, unsigned int N> 17 struct ThreadQueueList { 18 // TODO(yuriks): If performance proves to be a problem, the std::deques can be replaced with 19 // (dynamically resizable) circular buffers to remove their overhead when 20 // inserting and popping. 21 22 using Priority = unsigned int; 23 24 // Number of priority levels. (Valid levels are [0..NUM_QUEUES).) 25 static constexpr Priority NUM_QUEUES = N; 26 27 ThreadQueueList() { 28 first = nullptr; 29 } 30 31 // Only for debugging, returns priority level. 32 [[nodiscard]] Priority contains(const T& uid) const { 33 for (Priority i = 0; i < NUM_QUEUES; ++i) { 34 const Queue& cur = queues[i]; 35 if (std::find(cur.data.cbegin(), cur.data.cend(), uid) != cur.data.cend()) { 36 return i; 37 } 38 } 39 40 return -1; 41 } 42 43 [[nodiscard]] T get_first() const { 44 const Queue* cur = first; 45 while (cur != nullptr) { 46 if (!cur->data.empty()) { 47 return cur->data.front(); 48 } 49 cur = cur->next_nonempty; 50 } 51 52 return T(); 53 } 54 55 T pop_first() { 56 Queue* cur = first; 57 while (cur != nullptr) { 58 if (!cur->data.empty()) { 59 auto tmp = std::move(cur->data.front()); 60 cur->data.pop_front(); 61 return tmp; 62 } 63 cur = cur->next_nonempty; 64 } 65 66 return T(); 67 } 68 69 T pop_first_better(Priority priority) { 70 Queue* cur = first; 71 Queue* stop = &queues[priority]; 72 while (cur < stop) { 73 if (!cur->data.empty()) { 74 auto tmp = std::move(cur->data.front()); 75 cur->data.pop_front(); 76 return tmp; 77 } 78 cur = cur->next_nonempty; 79 } 80 81 return T(); 82 } 83 84 void push_front(Priority priority, const T& thread_id) { 85 Queue* cur = &queues[priority]; 86 cur->data.push_front(thread_id); 87 } 88 89 void push_back(Priority priority, const T& thread_id) { 90 Queue* cur = &queues[priority]; 91 cur->data.push_back(thread_id); 92 } 93 94 void move(const T& thread_id, Priority old_priority, Priority new_priority) { 95 remove(old_priority, thread_id); 96 prepare(new_priority); 97 push_back(new_priority, thread_id); 98 } 99 100 void remove(Priority priority, const T& thread_id) { 101 Queue* const cur = &queues[priority]; 102 const auto iter = std::remove(cur->data.begin(), cur->data.end(), thread_id); 103 cur->data.erase(iter, cur->data.end()); 104 } 105 106 void rotate(Priority priority) { 107 Queue* cur = &queues[priority]; 108 109 if (cur->data.size() > 1) { 110 cur->data.push_back(std::move(cur->data.front())); 111 cur->data.pop_front(); 112 } 113 } 114 115 void clear() { 116 queues.fill(Queue()); 117 first = nullptr; 118 } 119 120 [[nodiscard]] bool empty(Priority priority) const { 121 const Queue* cur = &queues[priority]; 122 return cur->data.empty(); 123 } 124 125 void prepare(Priority priority) { 126 Queue* cur = &queues[priority]; 127 if (cur->next_nonempty == UnlinkedTag()) 128 link(priority); 129 } 130 131 private: 132 struct Queue { 133 // Points to the next active priority, skipping over ones that have never been used. 134 Queue* next_nonempty = UnlinkedTag(); 135 // Double-ended queue of threads in this priority level 136 std::deque<T> data; 137 }; 138 139 /// Special tag used to mark priority levels that have never been used. 140 static Queue* UnlinkedTag() { 141 return reinterpret_cast<Queue*>(1); 142 } 143 144 void link(Priority priority) { 145 Queue* cur = &queues[priority]; 146 147 for (int i = priority - 1; i >= 0; --i) { 148 if (queues[i].next_nonempty != UnlinkedTag()) { 149 cur->next_nonempty = queues[i].next_nonempty; 150 queues[i].next_nonempty = cur; 151 return; 152 } 153 } 154 155 cur->next_nonempty = first; 156 first = cur; 157 } 158 159 // The first queue that's ever been used. 160 Queue* first; 161 // The priority level queues of thread ids. 162 std::array<Queue, NUM_QUEUES> queues; 163 164 s64 ToIndex(const Queue* q) const { 165 if (q == nullptr) { 166 return -2; 167 } else if (q == UnlinkedTag()) { 168 return -1; 169 } else { 170 return q - queues.data(); 171 } 172 } 173 174 Queue* ToPointer(s64 idx) { 175 if (idx == -1) { 176 return UnlinkedTag(); 177 } else if (idx < 0) { 178 return nullptr; 179 } else { 180 return &queues[idx]; 181 } 182 } 183 184 friend class boost::serialization::access; 185 template <class Archive> 186 void save(Archive& ar, const unsigned int file_version) const { 187 const s64 idx = ToIndex(first); 188 ar << idx; 189 for (std::size_t i = 0; i < NUM_QUEUES; i++) { 190 const s64 idx1 = ToIndex(queues[i].next_nonempty); 191 ar << idx1; 192 ar << queues[i].data; 193 } 194 } 195 196 template <class Archive> 197 void load(Archive& ar, const unsigned int file_version) { 198 s64 idx; 199 ar >> idx; 200 first = ToPointer(idx); 201 for (std::size_t i = 0; i < NUM_QUEUES; i++) { 202 ar >> idx; 203 queues[i].next_nonempty = ToPointer(idx); 204 ar >> queues[i].data; 205 } 206 } 207 208 BOOST_SERIALIZATION_SPLIT_MEMBER() 209 }; 210 211 } // namespace Common