jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2022, Lucas Chollet <lucas.chollet@free.fr>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <AK/CircularBuffer.h>
8#include <AK/MemMem.h>
9
10namespace AK {
11
12CircularBuffer::CircularBuffer(ByteBuffer buffer)
13 : m_buffer(move(buffer))
14{
15}
16
17ErrorOr<CircularBuffer> CircularBuffer::create_empty(size_t size)
18{
19 auto temporary_buffer = TRY(ByteBuffer::create_uninitialized(size));
20
21 CircularBuffer circular_buffer { move(temporary_buffer) };
22
23 return circular_buffer;
24}
25
26ErrorOr<CircularBuffer> CircularBuffer::create_initialized(ByteBuffer buffer)
27{
28 CircularBuffer circular_buffer { move(buffer) };
29
30 circular_buffer.m_used_space = circular_buffer.m_buffer.size();
31
32 return circular_buffer;
33}
34
35size_t CircularBuffer::empty_space() const
36{
37 return capacity() - m_used_space;
38}
39
40size_t CircularBuffer::used_space() const
41{
42 return m_used_space;
43}
44
45size_t CircularBuffer::capacity() const
46{
47 return m_buffer.size();
48}
49
50bool CircularBuffer::is_wrapping_around() const
51{
52 return capacity() <= m_reading_head + m_used_space;
53}
54
55Optional<size_t> CircularBuffer::offset_of(StringView needle, Optional<size_t> from, Optional<size_t> until) const
56{
57 auto const read_from = from.value_or(0);
58 auto const read_until = until.value_or(m_used_space);
59 VERIFY(read_from <= read_until);
60
61 Array<ReadonlyBytes, 2> spans {};
62 spans[0] = next_read_span();
63 auto const original_span_0_size = spans[0].size();
64
65 if (read_from > 0)
66 spans[0] = spans[0].slice(min(spans[0].size(), read_from));
67
68 if (spans[0].size() + read_from > read_until)
69 spans[0] = spans[0].trim(read_until - read_from);
70 else if (is_wrapping_around())
71 spans[1] = m_buffer.span().slice(max(original_span_0_size, read_from) - original_span_0_size, min(read_until, m_used_space) - original_span_0_size);
72
73 auto maybe_found = AK::memmem(spans.begin(), spans.end(), needle.bytes());
74 if (maybe_found.has_value())
75 *maybe_found += read_from;
76
77 return maybe_found;
78}
79
80void CircularBuffer::clear()
81{
82 m_reading_head = 0;
83 m_used_space = 0;
84 m_seekback_limit = 0;
85}
86
87Bytes CircularBuffer::next_write_span()
88{
89 if (is_wrapping_around())
90 return m_buffer.span().slice(m_reading_head + m_used_space - capacity(), capacity() - m_used_space);
91 return m_buffer.span().slice(m_reading_head + m_used_space, capacity() - (m_reading_head + m_used_space));
92}
93
94ReadonlyBytes CircularBuffer::next_read_span() const
95{
96 return m_buffer.span().slice(m_reading_head, min(capacity() - m_reading_head, m_used_space));
97}
98
99ReadonlyBytes CircularBuffer::next_read_span_with_seekback(size_t distance) const
100{
101 VERIFY(m_seekback_limit <= capacity());
102 VERIFY(distance <= m_seekback_limit);
103
104 // Note: We are adding the capacity once here to ensure that we can wrap around the negative space by using modulo.
105 auto read_offset = (capacity() + m_reading_head + m_used_space - distance) % capacity();
106
107 return m_buffer.span().slice(read_offset, min(capacity() - read_offset, m_seekback_limit));
108}
109
110size_t CircularBuffer::write(ReadonlyBytes bytes)
111{
112 auto remaining = bytes.size();
113
114 while (remaining > 0) {
115 auto const next_span = next_write_span();
116 if (next_span.size() == 0)
117 break;
118
119 auto const written_bytes = bytes.slice(bytes.size() - remaining).copy_trimmed_to(next_span);
120
121 m_used_space += written_bytes;
122
123 m_seekback_limit += written_bytes;
124 if (m_seekback_limit > capacity())
125 m_seekback_limit = capacity();
126
127 remaining -= written_bytes;
128 }
129
130 return bytes.size() - remaining;
131}
132
133Bytes CircularBuffer::read(Bytes bytes)
134{
135 auto remaining = bytes.size();
136
137 while (remaining > 0) {
138 auto const next_span = next_read_span();
139 if (next_span.size() == 0)
140 break;
141
142 auto written_bytes = next_span.copy_trimmed_to(bytes.slice(bytes.size() - remaining));
143
144 m_used_space -= written_bytes;
145 m_reading_head += written_bytes;
146
147 if (m_reading_head >= capacity())
148 m_reading_head -= capacity();
149
150 remaining -= written_bytes;
151 }
152
153 return bytes.trim(bytes.size() - remaining);
154}
155
156ErrorOr<Bytes> CircularBuffer::read_with_seekback(Bytes bytes, size_t distance)
157{
158 if (distance > m_seekback_limit)
159 return Error::from_string_literal("Tried a seekback read beyond the seekback limit");
160
161 auto remaining = bytes.size();
162
163 while (remaining > 0) {
164 auto const next_span = next_read_span_with_seekback(distance);
165 if (next_span.size() == 0)
166 break;
167
168 auto written_bytes = next_span.copy_trimmed_to(bytes.slice(bytes.size() - remaining));
169
170 distance -= written_bytes;
171 remaining -= written_bytes;
172 }
173
174 return bytes.trim(bytes.size() - remaining);
175}
176
177ErrorOr<void> CircularBuffer::discard(size_t discarding_size)
178{
179 if (m_used_space < discarding_size)
180 return Error::from_string_literal("Can not discard more data than what the buffer contains");
181 m_used_space -= discarding_size;
182 m_reading_head = (m_reading_head + discarding_size) % capacity();
183
184 return {};
185}
186
187}