fifo_queue.h (6411B)
1 // SPDX-FileCopyrightText: 2019-2024 Connor McLaughlin <stenzek@gmail.com> 2 // SPDX-License-Identifier: (GPL-3.0 OR CC-BY-NC-ND-4.0) 3 4 #pragma once 5 #include "assert.h" 6 #include "types.h" 7 #include <algorithm> 8 #include <cstring> 9 #include <type_traits> 10 11 #ifdef _MSC_VER 12 #include <malloc.h> // _aligned_malloc 13 #else 14 #include <stdlib.h> // posix_memalign 15 #endif 16 17 template<typename T, u32 CAPACITY> 18 class FIFOQueue 19 { 20 public: 21 const T* GetDataPointer() const { return m_ptr; } 22 T* GetDataPointer() { return m_ptr; } 23 const T* GetReadPointer() const { return &m_ptr[m_head]; } 24 T* GetReadPointer() { return &m_ptr[m_head]; } 25 constexpr u32 GetCapacity() const { return CAPACITY; } 26 T* GetWritePointer() { return &m_ptr[m_tail]; } 27 u32 GetSize() const { return m_size; } 28 u32 GetSpace() const { return CAPACITY - m_size; } 29 u32 GetContiguousSpace() const 30 { 31 if (m_tail == m_head && m_size > 0) 32 return 0; 33 else if (m_tail >= m_head) 34 return (CAPACITY - m_tail); 35 else 36 return (m_head - m_tail); 37 } 38 u32 GetContiguousSize() const { return std::min<u32>(CAPACITY - m_head, m_size); } 39 bool IsEmpty() const { return m_size == 0; } 40 bool IsFull() const { return m_size == CAPACITY; } 41 42 void Clear() 43 { 44 m_head = 0; 45 m_tail = 0; 46 m_size = 0; 47 } 48 49 template<class... Args> 50 T& Emplace(Args&&... args) 51 { 52 T& ref = PushAndGetReference(); 53 new (&ref) T(std::forward<Args...>(args...)); 54 return ref; 55 } 56 57 template<class Y = T, std::enable_if_t<std::is_standard_layout_v<Y> && std::is_trivial_v<Y>, int> = 0> 58 T& Push(const T& value) 59 { 60 T& ref = PushAndGetReference(); 61 std::memcpy(&ref, &value, sizeof(T)); 62 return ref; 63 } 64 65 template<class Y = T, std::enable_if_t<!std::is_standard_layout_v<Y> || !std::is_trivial_v<Y>, int> = 0> 66 T& Push(const T& value) 67 { 68 T& ref = PushAndGetReference(); 69 new (&ref) T(value); 70 return ref; 71 } 72 73 // faster version of push_back_range for POD types which can be memcpy()ed 74 template<class Y = T, std::enable_if_t<std::is_standard_layout_v<Y> && std::is_trivial_v<Y>, int> = 0> 75 void PushRange(const T* data, u32 size) 76 { 77 DebugAssert((m_size + size) <= CAPACITY); 78 const u32 space_before_end = CAPACITY - m_tail; 79 const u32 size_before_end = (size > space_before_end) ? space_before_end : size; 80 const u32 size_after_end = size - size_before_end; 81 82 std::memcpy(&m_ptr[m_tail], data, sizeof(T) * size_before_end); 83 m_tail = (m_tail + size_before_end) % CAPACITY; 84 85 if (size_after_end > 0) 86 { 87 std::memcpy(&m_ptr[m_tail], data + size_before_end, sizeof(T) * size_after_end); 88 m_tail = (m_tail + size_after_end) % CAPACITY; 89 } 90 91 m_size += size; 92 } 93 94 template<class Y = T, std::enable_if_t<!std::is_standard_layout_v<Y> || !std::is_trivial_v<Y>, int> = 0> 95 void PushRange(const T* data, u32 size) 96 { 97 DebugAssert((m_size + size) <= CAPACITY); 98 while (size > 0) 99 { 100 T& ref = PushAndGetReference(); 101 new (&ref) T(*data); 102 data++; 103 size--; 104 } 105 } 106 107 const T& Peek() const { return m_ptr[m_head]; } 108 const T& Peek(u32 offset) { return m_ptr[(m_head + offset) % CAPACITY]; } 109 110 void Remove(u32 count) 111 { 112 DebugAssert(m_size >= count); 113 for (u32 i = 0; i < count; i++) 114 { 115 m_ptr[m_head].~T(); 116 m_head = (m_head + 1) % CAPACITY; 117 m_size--; 118 } 119 } 120 121 void RemoveOne() 122 { 123 DebugAssert(m_size > 0); 124 m_ptr[m_head].~T(); 125 m_head = (m_head + 1) % CAPACITY; 126 m_size--; 127 } 128 129 // removes and returns moved value 130 T Pop() 131 { 132 DebugAssert(m_size > 0); 133 T val = std::move(m_ptr[m_head]); 134 m_ptr[m_head].~T(); 135 m_head = (m_head + 1) % CAPACITY; 136 m_size--; 137 return val; 138 } 139 140 template<class Y = T, std::enable_if_t<std::is_standard_layout_v<Y> && std::is_trivial_v<Y>, int> = 0> 141 void PopRange(T* out_data, u32 count) 142 { 143 DebugAssert(m_size >= count); 144 do 145 { 146 const u32 contig_count = std::min(count, CAPACITY - m_head); 147 std::memcpy(out_data, &m_ptr[m_head], sizeof(T) * contig_count); 148 out_data += contig_count; 149 m_head = (m_head + contig_count) % CAPACITY; 150 m_size -= contig_count; 151 count -= contig_count; 152 } while (count > 0); 153 } 154 155 template<class Y = T, std::enable_if_t<!std::is_standard_layout_v<Y> || !std::is_trivial_v<Y>, int> = 0> 156 void PopRange(T* out_data, u32 count) 157 { 158 DebugAssert(m_size >= count); 159 for (u32 i = 0; i < count; i++) 160 { 161 out_data[i] = std::move(m_ptr[m_head]); 162 m_ptr[m_head].~T(); 163 m_head = (m_head + 1) % CAPACITY; 164 m_size--; 165 } 166 } 167 168 template<u32 QUEUE_CAPACITY> 169 void PushFromQueue(FIFOQueue<T, QUEUE_CAPACITY>* other_queue) 170 { 171 while (!other_queue->IsEmpty() && !IsFull()) 172 { 173 T& dest = PushAndGetReference(); 174 dest = std::move(other_queue->Pop()); 175 } 176 } 177 178 void AdvanceTail(u32 count) 179 { 180 DebugAssert((m_size + count) <= CAPACITY); 181 DebugAssert((m_tail + count) <= CAPACITY); 182 m_tail = (m_tail + count) % CAPACITY; 183 m_size += count; 184 } 185 186 protected: 187 FIFOQueue() = default; 188 189 T& PushAndGetReference() 190 { 191 DebugAssert(m_size < CAPACITY); 192 T& ref = m_ptr[m_tail]; 193 m_tail = (m_tail + 1) % CAPACITY; 194 m_size++; 195 return ref; 196 } 197 198 T* m_ptr = nullptr; 199 u32 m_head = 0; 200 u32 m_tail = 0; 201 u32 m_size = 0; 202 }; 203 204 template<typename T, u32 CAPACITY> 205 class InlineFIFOQueue : public FIFOQueue<T, CAPACITY> 206 { 207 public: 208 InlineFIFOQueue() : FIFOQueue<T, CAPACITY>() { this->m_ptr = m_inline_data; } 209 210 private: 211 T m_inline_data[CAPACITY] = {}; 212 }; 213 214 template<typename T, u32 CAPACITY, u32 ALIGNMENT = 0> 215 class HeapFIFOQueue : public FIFOQueue<T, CAPACITY> 216 { 217 public: 218 HeapFIFOQueue() : FIFOQueue<T, CAPACITY>() 219 { 220 if constexpr (ALIGNMENT > 0) 221 { 222 #ifdef _MSC_VER 223 this->m_ptr = static_cast<T*>(_aligned_malloc(sizeof(T) * CAPACITY, ALIGNMENT)); 224 #else 225 if (posix_memalign(reinterpret_cast<void**>(&this->m_ptr), ALIGNMENT, sizeof(T) * CAPACITY) != 0) 226 this->m_ptr = nullptr; 227 #endif 228 } 229 else 230 { 231 this->m_ptr = static_cast<T*>(std::malloc(sizeof(T) * CAPACITY)); 232 } 233 234 if (!this->m_ptr) 235 Panic("Heap allocation failed"); 236 237 std::memset(this->m_ptr, 0, sizeof(T) * CAPACITY); 238 } 239 240 ~HeapFIFOQueue() 241 { 242 if constexpr (ALIGNMENT > 0) 243 { 244 #ifdef _MSC_VER 245 _aligned_free(this->m_ptr); 246 #else 247 free(this->m_ptr); 248 #endif 249 } 250 else 251 { 252 free(this->m_ptr); 253 } 254 } 255 };