blob: 979989aa2fd9f6d835f057efc4ae1f8ecdc51996 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
/*
* Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
*
* SPDX-License-Identifier: BSD-2-Clause
*/
#pragma once
#include <AK/Assertions.h>
#include <AK/Forward.h>
#include <AK/StdLibExtras.h>
namespace AK {
template<typename T, size_t Capacity>
class CircularQueue {
friend CircularDuplexStream<Capacity>;
public:
CircularQueue() = default;
~CircularQueue()
{
clear();
}
void clear()
{
for (size_t i = 0; i < m_size; ++i)
elements()[(m_head + i) % Capacity].~T();
m_head = 0;
m_size = 0;
}
bool is_empty() const { return m_size == 0; }
size_t size() const { return m_size; }
size_t capacity() const { return Capacity; }
template<typename U = T>
void enqueue(U&& value)
{
auto& slot = elements()[(m_head + m_size) % Capacity];
if (m_size == Capacity)
slot.~T();
new (&slot) T(forward<U>(value));
if (m_size == Capacity)
m_head = (m_head + 1) % Capacity;
else
++m_size;
}
T dequeue()
{
VERIFY(!is_empty());
auto& slot = elements()[m_head];
T value = move(slot);
slot.~T();
m_head = (m_head + 1) % Capacity;
--m_size;
return value;
}
const T& at(size_t index) const { return elements()[(m_head + index) % Capacity]; }
T& at(size_t index) { return elements()[(m_head + index) % Capacity]; }
const T& first() const { return at(0); }
const T& last() const { return at(size() - 1); }
class ConstIterator {
public:
bool operator!=(ConstIterator const& other) { return m_index != other.m_index; }
ConstIterator& operator++()
{
++m_index;
return *this;
}
const T& operator*() const { return m_queue.at(m_index); }
private:
friend class CircularQueue;
ConstIterator(CircularQueue const& queue, const size_t index)
: m_queue(queue)
, m_index(index)
{
}
CircularQueue const& m_queue;
size_t m_index { 0 };
};
class Iterator {
public:
bool operator!=(Iterator const& other) { return m_index != other.m_index; }
Iterator& operator++()
{
++m_index;
return *this;
}
T& operator*() const { return m_queue.at(m_index); }
private:
friend class CircularQueue;
Iterator(CircularQueue& queue, size_t const index)
: m_queue(queue)
, m_index(index)
{
}
CircularQueue& m_queue;
size_t m_index { 0 };
};
ConstIterator begin() const { return ConstIterator(*this, 0); }
ConstIterator end() const { return ConstIterator(*this, size()); }
Iterator begin() { return Iterator(*this, 0); }
Iterator end() { return Iterator(*this, size()); }
size_t head_index() const { return m_head; }
protected:
T* elements() { return reinterpret_cast<T*>(m_storage); }
const T* elements() const { return reinterpret_cast<const T*>(m_storage); }
friend class ConstIterator;
alignas(T) u8 m_storage[sizeof(T) * Capacity];
size_t m_size { 0 };
size_t m_head { 0 };
};
}
using AK::CircularQueue;
|
