di 0.1.0
Loading...
Searching...
No Matches
ring_operations.h
Go to the documentation of this file.
1#pragma once
2
12#include "di/util/create.h"
14
16constexpr auto size(concepts::detail::ConstantRing auto& ring) {
17 return ring.span().size();
18}
19
20constexpr auto size_bytes(concepts::detail::ConstantRing auto& ring) {
21 return ring.span().size_bytes();
22}
23
24constexpr auto empty(concepts::detail::ConstantRing auto& ring) -> bool {
25 return ring::size(ring) == 0;
26}
27
28constexpr auto begin_pointer(concepts::detail::ConstantRing auto& ring) -> auto* {
29 return ring.span().data();
30}
31
32constexpr auto end_pointer(concepts::detail::ConstantRing auto& ring) -> auto* {
33 return ring::begin_pointer(ring) + ring.capacity();
34}
35
36constexpr auto head_pointer(concepts::detail::ConstantRing auto& ring) -> auto* {
37 return ring::begin_pointer(ring) + ring.head();
38}
39
40constexpr auto tail_pointer(concepts::detail::ConstantRing auto& ring) -> auto* {
41 return ring::begin_pointer(ring) + ring.tail();
42}
43
44template<concepts::detail::ConstantRing Ring, typename Value = meta::detail::RingValue<Ring>>
49
50template<concepts::detail::ConstantRing Ring, typename Value = meta::detail::RingValue<Ring>>
55
56constexpr auto lookup(concepts::detail::ConstantRing auto& ring, usize index) -> decltype(auto) {
57 return ring::begin(ring)[index];
58}
59
60constexpr auto at(concepts::detail::ConstantRing auto& ring, usize index) {
61 return lift_bool(index < ring::size(ring)) % [&] {
62 return util::ref(ring::lookup(ring, index));
63 };
64}
65
66constexpr auto front(concepts::detail::ConstantRing auto& ring) {
67 return ring::at(ring, 0);
68}
69
70constexpr auto back(concepts::detail::ConstantRing auto& ring) {
71 // NOTE: This is safe because unsigned underflow is defined behavior. If the ring is empty, then at() will return
72 // nullopt.
73 return ring::at(ring, ring::size(ring) - 1U);
74}
75
76template<concepts::detail::MutableRing Ring, typename Value = meta::detail::RingValue<Ring>>
77requires(!concepts::Const<Ring>)
79 // SAFETY: this is safe because we are provided a mutable reference to the ring.
80 return iterator.unconst_unsafe();
81}
82
83template<concepts::detail::ConstantRing Ring>
84requires(!concepts::Const<Ring>)
85constexpr auto iterator(Ring& ring, usize index) {
86 DI_ASSERT(index <= ring::size(ring));
87 return ring::begin(ring) + index;
88}
89
90template<concepts::detail::ConstantRing Ring>
91constexpr auto iterator(Ring const& ring, usize index) {
92 DI_ASSERT(index <= ring::size(ring));
93 return ring::begin(ring) + index;
94}
95
96template<concepts::detail::MutableRing Ring, typename Value = meta::detail::RingValue<Ring>>
98 if (first == last) {
99 return ring::iterator(ring, first);
100 }
101
102 // Rotate the range [first, last) to the end of the buffer.
103 auto const first_position = first - ring::begin(ring);
104 auto const to_remove = last - first;
105 auto [new_tail, end] = container::rotate(ring::iterator(ring, first), ring::iterator(ring, last), ring::end(ring));
106
107 // Destroy the trailing elements.
108 container::destroy(new_tail, end);
109
110 ring.assume_size(ring::size(ring) - to_remove);
111 ring.assume_tail((ring.tail() + ring.capacity() - to_remove) % ring.capacity());
112 return ring::iterator(ring, first_position);
113}
114
115template<concepts::detail::MutableRing Ring, typename Value = meta::detail::RingValue<Ring>>
116constexpr auto erase(Ring& ring, RingIterator<Value const> citerator) {
117 return ring::erase(ring, citerator, citerator + 1);
118}
119
120constexpr void clear(concepts::detail::MutableRing auto& ring) {
122 ring.assume_size(0);
123 ring.assume_head(0);
124 ring.assume_tail(0);
125}
126
127template<concepts::detail::MutableRing Ring, typename R = meta::detail::RingAllocResult<Ring>>
128constexpr auto reserve(Ring& ring, usize capacity) -> R {
129 if (capacity <= ring.capacity()) {
130 return util::create<R>();
131 }
132
133 auto size = ring::size(ring);
134 auto temp = Ring();
135 return invoke_as_fallible([&] {
136 return temp.reserve_from_nothing(capacity);
137 }) % [&] {
138 auto new_buffer = ring::begin_pointer(temp);
139 // FIXME: Use an optimized algorithm which breaks the ring buffer into 2 contigous parts.
140 container::uninitialized_relocate(ring::begin(ring), ring::end(ring), new_buffer, new_buffer + capacity);
141 temp.assume_size(size);
142 temp.assume_head(0);
143 temp.assume_tail(size);
144 ring.assume_size(0);
145 ring.assume_head(0);
146 ring.assume_tail(0);
147 util::swap(ring, temp);
148 } | try_infallible;
149}
150
151template<concepts::detail::MutableRing Ring, typename... Args>
153constexpr auto emplace_back(Ring& ring, Args&&... args) -> decltype(auto) {
154 auto size = ring::size(ring);
155 return invoke_as_fallible([&] {
156 return ring::reserve(ring, ring.grow_capacity(size + 1));
157 }) % [&] {
159 auto result = util::construct_at(end, util::forward<Args>(args)...);
160 ring.assume_size(size + 1);
161 ring.assume_tail((ring.tail() + 1) % ring.capacity());
162 return util::ref(*result);
163 } | try_infallible;
164}
165
166template<concepts::detail::MutableRing Ring, concepts::InputContainer Con, typename T = meta::detail::RingValue<Ring>,
167 typename R = meta::detail::RingAllocResult<Ring>>
169constexpr auto append_container(Ring& ring, Con&& container) -> R {
170 return container::sequence(util::forward<Con>(container), [&]<typename X>(X&& value) {
171 return as_fallible(ring::emplace_back(ring, util::forward<X>(value)));
172 });
173}
174
175constexpr auto pop_back(concepts::detail::MutableRing auto& ring) {
176 auto size = ring::size(ring);
177 return lift_bool(size > 0) % [&] {
178 auto new_size = size - 1;
179 auto result = util::relocate(ring::lookup(ring, new_size));
180 ring.assume_size(new_size);
181 ring.assume_tail((ring.tail() + ring.capacity() - 1) % ring.capacity());
182 return result;
183 };
184}
185
186template<concepts::detail::MutableRing Ring, typename... Args>
188constexpr auto emplace_front(Ring& ring, Args&&... args) -> decltype(auto) {
189 auto size = ring::size(ring);
190 return invoke_as_fallible([&] {
191 return ring::reserve(ring, ring.grow_capacity(size + 1));
192 }) % [&] {
193 auto new_head = (ring.head() + ring.capacity() - 1) % ring.capacity();
194 ring.assume_head(new_head);
195
196 auto head = ring::head_pointer(ring);
197 auto result = util::construct_at(head, util::forward<Args>(args)...);
198
199 ring.assume_size(size + 1);
200 return util::ref(*result);
201 } | try_infallible;
202}
203
204template<concepts::detail::MutableRing Ring, concepts::InputContainer Con, typename T = meta::detail::RingValue<Ring>,
205 typename R = meta::detail::RingAllocResult<Ring>>
207constexpr auto prepend_container(Ring& ring, Con&& container) -> R {
208 return container::sequence(util::forward<Con>(container), [&]<typename X>(X&& value) {
209 return as_fallible(ring::emplace_front(ring, util::forward<X>(value)));
210 });
211}
212
213constexpr auto pop_front(concepts::detail::MutableRing auto& ring) {
214 auto size = ring::size(ring);
215 return lift_bool(size > 0) % [&] {
216 auto new_size = size - 1;
217 auto result = util::relocate(ring::lookup(ring, 0));
218 ring.assume_size(new_size);
219 ring.assume_head((ring.head() + 1) % ring.capacity());
220 return result;
221 };
222}
223
224template<concepts::detail::MutableRing Ring, typename T = meta::detail::RingValue<Ring>, typename... Args>
226constexpr auto emplace(Ring& ring, RingIterator<T const> it, Args&&... args) {
227 auto position = it - ring::begin(ring);
228 return as_fallible(ring::emplace_back(ring, util::forward<Args>(args)...)) % [&](auto&) {
229 auto new_it = ring::begin(ring) + position;
230 auto last = ring::end(ring);
231 container::rotate(new_it, last - 1, last);
232 return new_it;
233 } | try_infallible;
234}
235
236template<concepts::detail::MutableRing Ring, concepts::InputContainer Con, typename T = meta::detail::RingValue<Ring>,
237 typename R = meta::detail::RingAllocResult<Ring, di::View<RingIterator<T>, RingIterator<T>>>>
239constexpr auto insert_container(Ring& ring, RingIterator<T const> it, Con&& container) -> R {
240 auto position = it - ring::begin(ring);
241 auto old_size = ring::size(ring);
242 auto inserted = usize(0);
243 return invoke_as_fallible([&] {
244 return container::sequence(util::forward<Con>(container), [&]<typename X>(X&& value) {
245 inserted++;
246 return as_fallible(ring::emplace_back(ring, util::forward<X>(value)));
247 });
248 })
249 .transform_error([&] {
250 // On errors, remove any inserted elements.
251 auto& cring = di::as_const(ring);
252 ring::erase(ring, ring::begin(cring) + old_size, ring::end(cring));
253 })
254 .transform([&] {
255 // Rotate elements into place.
256 auto start = ring::begin(ring) + position;
257 auto mid = ring::end(ring) - inserted;
258 di::rotate(start, mid, ring::end(ring));
259 return di::View { start, start + inserted };
260 }) |
262}
263
264constexpr auto make_contigous(concepts::detail::MutableRing auto& ring) {
265 auto head = ring.head();
266 auto tail = ring.tail();
267 auto size = ring::size(ring);
268 if (head < tail) {
269 // Move the range [head, tail) to the beginning of the buffer.
272 ring.assume_head(0);
273 ring.assume_tail(size);
274 return ring.span();
275 }
276
277 // Move the range [head, capacity) to directly after tail.
280 // Rotate the range [0, tail) into place.
282 ring.assume_head(0);
283 ring.assume_tail(size);
284 return ring.span();
285}
286
287template<concepts::detail::MutableRing Ring, typename T = meta::detail::RingValue<Ring>>
289constexpr auto resize(Ring& ring, usize count) {
291 return invoke_as_fallible([&] {
292 return vector::resize(ring, count);
293 }) % [&] {
294 ring.assume_tail(ring::size(ring));
295 } | try_infallible;
296}
297
298template<concepts::detail::MutableRing Ring, typename T = meta::detail::RingValue<Ring>>
300constexpr auto resize(Ring& ring, usize count, T const& value) {
302 return invoke_as_fallible([&] {
303 return vector::resize(ring, count, value);
304 }) % [&] {
305 ring.assume_tail(ring::size(ring));
306 } | try_infallible;
307}
308}
#define DI_ASSERT(...)
Definition assert_bool.h:7
Definition ring_iterator.h:8
Definition ring.h:22
Definition view.h:35
Definition language.h:18
Definition operations.h:11
Definition container_compatible.h:9
Definition operations.h:34
Definition operations.h:24
Definition ring_operations.h:15
constexpr auto pop_front(concepts::detail::MutableRing auto &ring)
Definition ring_operations.h:213
constexpr auto prepend_container(Ring &ring, Con &&container) -> R
Definition ring_operations.h:207
constexpr auto end(Ring &ring)
Definition ring_operations.h:51
constexpr auto emplace_back(Ring &ring, Args &&... args) -> decltype(auto)
Definition ring_operations.h:153
constexpr auto append_container(Ring &ring, Con &&container) -> R
Definition ring_operations.h:169
constexpr auto lookup(concepts::detail::ConstantRing auto &ring, usize index) -> decltype(auto)
Definition ring_operations.h:56
constexpr auto iterator(Ring &, RingIterator< Value const > iterator)
Definition ring_operations.h:78
constexpr auto end_pointer(concepts::detail::ConstantRing auto &ring) -> auto *
Definition ring_operations.h:32
constexpr auto empty(concepts::detail::ConstantRing auto &ring) -> bool
Definition ring_operations.h:24
constexpr auto resize(Ring &ring, usize count)
Definition ring_operations.h:289
constexpr auto make_contigous(concepts::detail::MutableRing auto &ring)
Definition ring_operations.h:264
constexpr auto begin_pointer(concepts::detail::ConstantRing auto &ring) -> auto *
Definition ring_operations.h:28
constexpr auto at(concepts::detail::ConstantRing auto &ring, usize index)
Definition ring_operations.h:60
constexpr auto size_bytes(concepts::detail::ConstantRing auto &ring)
Definition ring_operations.h:20
constexpr auto begin(Ring &ring)
Definition ring_operations.h:45
constexpr void clear(concepts::detail::MutableRing auto &ring)
Definition ring_operations.h:120
constexpr auto erase(Ring &ring, RingIterator< Value const > first, RingIterator< Value const > last)
Definition ring_operations.h:97
constexpr auto reserve(Ring &ring, usize capacity) -> R
Definition ring_operations.h:128
constexpr auto emplace_front(Ring &ring, Args &&... args) -> decltype(auto)
Definition ring_operations.h:188
constexpr auto tail_pointer(concepts::detail::ConstantRing auto &ring) -> auto *
Definition ring_operations.h:40
constexpr auto insert_container(Ring &ring, RingIterator< T const > it, Con &&container) -> R
Definition ring_operations.h:239
constexpr auto pop_back(concepts::detail::MutableRing auto &ring)
Definition ring_operations.h:175
constexpr auto emplace(Ring &ring, RingIterator< T const > it, Args &&... args)
Definition ring_operations.h:226
constexpr auto head_pointer(concepts::detail::ConstantRing auto &ring) -> auto *
Definition ring_operations.h:36
constexpr auto size(concepts::detail::ConstantRing auto &ring)
Definition ring_operations.h:16
constexpr auto resize(Vec &vector, size_t count) -> R
Definition vector_resize.h:19
Definition sequence.h:12
constexpr auto front
Definition access.h:58
constexpr auto empty
Definition empty.h:45
constexpr auto uninitialized_relocate
Definition uninitialized_relocate.h:41
constexpr auto uninitialized_relocate_backwards
Definition uninitialized_relocate_backwards.h:45
constexpr auto at
Definition access.h:147
constexpr auto sequence
Definition sequence.h:34
constexpr auto destroy
Definition destroy.h:35
constexpr auto size
Definition size.h:62
constexpr auto erase
Definition erase.h:76
constexpr auto count
Definition count.h:37
constexpr auto end
Definition end.h:55
constexpr auto transform
Definition transform.h:59
constexpr auto back
Definition access.h:94
constexpr auto rotate
Definition rotate.h:94
constexpr auto begin
Definition begin.h:52
size_t usize
Definition integers.h:33
constexpr auto ref
Definition reference_wrapper.h:98
constexpr auto relocate
Definition relocate.h:21
constexpr struct di::util::SwapFunction swap
constexpr auto create(Args &&... args)
Definition create.h:21
constexpr auto construct_at
Definition construct_at.h:27
constexpr auto invoke_as_fallible
Definition invoke_as_fallible.h:37
constexpr auto as_fallible
Definition as_fallible.h:26
constexpr auto try_infallible
Definition try_infallible.h:31
constexpr auto lift_bool
Definition lift_bool.h:13
constexpr auto rotate
Definition rotate.h:94