CircularBuffer.H
Go to the documentation of this file.
1/*---------------------------------------------------------------------------*\
2 ========= |
3 \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4 \\ / O peration |
5 \\ / A nd | www.openfoam.com
6 \\/ M anipulation |
7-------------------------------------------------------------------------------
8 Copyright (C) 2022 OpenCFD Ltd.
9-------------------------------------------------------------------------------
10License
11 This file is part of OpenFOAM.
12
13 OpenFOAM is free software: you can redistribute it and/or modify it
14 under the terms of the GNU General Public License as published by
15 the Free Software Foundation, either version 3 of the License, or
16 (at your option) any later version.
17
18 OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
19 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
20 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 for more details.
22
23 You should have received a copy of the GNU General Public License
24 along with OpenFOAM. If not, see <http://www.gnu.org/licenses/>.
25
26Class
27 Foam::CircularBuffer
28
29Description
30 A simple list of objects of type <T> that is intended to be used
31 as a circular buffer (eg, a FIFO) when the alloc/free overhead
32 associated with a linked-list approach is to be avoided.
33
34 The internal storage is addressed by independent begin/end markers.
35 - The %begin marker points to the \em front.
36 - The %end marker is a one-past the \em back.
37 .
38 This results in a variety ofr different possible buffer states:
39 -# \em empty (\em begin == \em end)
40
41 -# \em simple/linear (\em begin < \em end) has no wrapping:
42 \verbatim
43 |.|.|.|a|b|c|d|.|.|.|
44 beg ___^
45 end ___________^
46 \endverbatim
47
48 -# \em split (\em begin > \em end):
49 \verbatim
50 |f|g|h|i|.|.|.|a|b|c|d|e|
51 end _____^
52 beg ___________^
53 \endverbatim
54 .
55
56 The methods range_one(), range_two() return the internal indexing and
57 the methods array_one(), array_two() provide direct access to the
58 internal contents.
59
60 When filling the buffer, the internal storage will be resized
61 (doubling strategy) as required. When this occurs, the new list
62 will be linearized with \em begin = 0.
63
64 Simultaneously when filling, the storage buffer will be over-allocated
65 to avoid ambiguity when (\em begin == \em end), which represents an
66 \em %empty buffer and not a \em %full buffer. Eg,
67 \verbatim
68 |c|d|.|a|b|
69 end _^
70 beg ___^
71 \endverbatim
72 after appending one more, it would be incorrect to simply fill
73 the available space:
74 \verbatim
75 |c|d|e|a|b|
76 end ___^ WRONG : would represent empty!
77 beg ___^
78 \endverbatim
79 the storage is instead increased (doubled) and rebalanced before
80 the append occurs (old capacity 5, new capacity 10):
81 \verbatim
82 |a|b|c|d|e|.|.|.|.|.|
83 _^_ beg
84 end _______^
85 \endverbatim
86
87SourceFiles
88 CircularBuffer.C
89 CircularBufferI.H
90 CircularBufferIO.C
91
92\*---------------------------------------------------------------------------*/
93
94#ifndef Foam_CircularBuffer_H
95#define Foam_CircularBuffer_H
96
97#include "labelRange.H"
98#include "List.H"
99#include "SubList.H"
100
101// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
102
103namespace Foam
104{
105
106// Forward Declarations
107template<class T> class CircularBuffer;
108
109template<class T>
110Istream& operator>>(Istream& is, CircularBuffer<T>& rhs);
111
112template<class T>
113Ostream& operator<<(Ostream& os, const CircularBuffer<T>& rhs);
114
115
116/*---------------------------------------------------------------------------*\
117 Class CircularBuffer Declaration
118\*---------------------------------------------------------------------------*/
119
120template<class T>
121class CircularBuffer
122{
123 // Private Data
124
125 //- The allocated buffer storage
126 List<T> storage_;
127
128 //- The first addressable element
129 label begin_;
130
131 //- One past last addressable element
132 label end_;
133
134
135 // Private Member Functions
136
137 //- Map the logical location to the buffer location
138 inline label toGlobal(const label i) const;
139
140 //- Length of array one
141 inline label size_one() const noexcept;
142
143 //- Length of array two
144 inline label size_two() const noexcept;
145
146 //- Reserve allocation space for at least this size.
147 // Never shrinks the allocated size, use setCapacity() for that.
148 // The 'nocopy' option will not attempt to recover old content
149 void doReserve(const bool nocopy, const label len);
150
151 //- Copy all list contents
152 template<class OtherListType>
153 inline void copyList(const OtherListType& rhs);
154
155
156public:
157
158 // STL type definitions
159
160 //- The value type the list contains
161 typedef T value_type;
162
163 //- The pointer type for non-const access to value_type items
164 typedef T* pointer;
165
166 //- The pointer type for const access to value_type items
167 typedef const T* const_pointer;
168
169 //- The type used for storing into value_type objects
170 typedef T& reference;
171
172 //- The type used for reading from constant value_type objects
173 typedef const T& const_reference;
174
175 //- The type to represent the size of a buffer
176 typedef label size_type;
177
178 //- The difference between iterator objects
179 typedef label difference_type;
180
181 //- Forward iterator with const access
182 class const_iterator;
183
184
185 // Constructors
186
187 //- Default construct, empty buffer without allocation
188 inline constexpr CircularBuffer() noexcept;
189
190 //- Construct an empty buffer with given reserve size
191 inline explicit CircularBuffer(const label len);
192
193 //- Copy construct
194 inline CircularBuffer(const CircularBuffer<T>& list);
195
196 //- Move construct
197 inline CircularBuffer(CircularBuffer<T>&& list);
198
199 //- Construct from Istream - uses readList
200 explicit CircularBuffer(Istream& is);
201
202
203 // Member Functions
204
205 // Characteristics
206
207 //- Lower capacity limit
208 static constexpr label min_size() noexcept { return 16; }
209
210 //- Size of the underlying storage.
211 inline label capacity() const noexcept;
212
213 //- Empty or exhausted buffer
214 inline bool empty() const noexcept;
215
216 //- The current number of buffer items
217 inline label size() const noexcept;
218
219
220 // Internal Access
221
222 //- The nominal space available to fill.
223 //- Subtract 1 for the number to append before re-balancing is needed.
224 inline label space() const noexcept;
225
226 //- The addressing range covered by array_one()
227 inline labelRange range_one() const noexcept;
228
229 //- The addressing range covered by array_two()
230 inline labelRange range_two() const noexcept;
231
232 //- The contents of the first internal array
234
235 //- The contents of the first internal array
237
238 //- The contents of the second internal array
239 const SubList<T> array_one() const;
240
241 //- The contents of the second internal array
242 const SubList<T> array_two() const;
243
244
245
246 // Access
247
248 //- Access the first element (front). Requires !empty().
249 T& first();
250
251 //- Access the last element (back). Requires !empty().
252 T& last();
253
254 //- Const access to the first element (front). Requires !empty().
255 const T& first() const;
256
257 //- Const access to the last element (back). Requires !empty().
258 const T& last() const;
259
260
261 // Sizing
262
263 //- Reserve allocation space for at least this size, allocating new
264 //- space if required and \em retaining old content.
265 // Never shrinks.
266 inline void reserve(const label len);
267
268 //- Reserve allocation space for at least this size, allocating new
269 //- space if required \em without retaining old content.
270 // Never shrinks.
271 inline void reserve_nocopy(const label len);
272
273 //- Clear the addressed buffer, does not change allocation
274 inline void clear() noexcept;
275
276 //- Clear the buffer and delete storage.
277 inline void clearStorage();
278
279 //- Swap content, independent of sizing parameter
280 inline void swap(CircularBuffer<T>& other);
281
282
283 // Search
284
285 //- Find index of the first occurrence of the value.
286 // Any occurrences before the start pos are ignored.
287 // Linear search.
288 // \return position in list or -1 if not found.
289 label find(const T& val, label pos = 0) const;
290
291 //- True if the value if found in the list.
292 // Any occurrences before the start pos are ignored.
293 // Linear search.
294 // \return true if found.
295 inline bool found(const T& val, label pos = 0) const;
296
297
298 // Stack-like Operations
299
300 //- Copy prepend an element to the front of the buffer
301 inline void push_front(const T& val);
302
303 //- Move prepend an element to the front of the buffer
304 inline void push_front(T&& val);
305
306 //- Copy append an element to the end of the buffer
307 inline void push_back(const T& val);
308
309 //- Move Append an element to the end of the buffer
310 inline void push_back(T&& val);
311
312 //- Shrink by moving the front of the buffer 1 or more times
313 inline void pop_front(label n = 1);
314
315 //- Shrink by moving the end of the buffer 1 or more times
316 inline void pop_back(label n = 1);
317
318 //- Copy append an element to the end of the buffer
319 void append(const T& val) { this->push_back(val); }
320
321 //- Move append an element to the end of the buffer
322 void append(T&& val) { this->push_back(std::move(val)); }
323
324 //- Copy append multiple elements the end of the buffer
325 inline void append(const UList<T>& list);
326
327 //- Copy append IndirectList elements the end of the buffer
328 template<class Addr>
329 inline void append(const IndirectListBase<T, Addr>& list);
330
331 //- Append an element if not already in the buffer.
332 // \return the change in the buffer length
333 inline label appendUniq(const T& val);
334
335
336 // Other Operations
337
338 //- Reverse the buffer order, swapping elements
339 void reverse();
340
341
342 // Member Operators
343
344 //- Non-const access to an element in the list.
345 // The index is allowed to wrap in both directions
346 inline T& operator[](const label i);
347
348 //- Const access to an element in the list
349 // The index is allowed to wrap in both directions
350 inline const T& operator[](const label i) const;
351
352 //- Copy construct
353 inline void operator=(const CircularBuffer<T>& list);
354
355 //- Move construct
356 inline void operator=(CircularBuffer<T>&& list);
357
358 //- Assign all addressed elements to the given value
359 inline void operator=(const T& val);
360
361 //- Assignment of all entries to zero
362 inline void operator=(const Foam::zero);
363
364 //- Deep copy values from a list of the addressed elements
365 inline void operator=(const UList<T>& rhs);
366
367 //- Deep copy values from a list of the addressed elements
368 template<class AnyAddr>
369 inline void operator=(const IndirectListBase<T, AnyAddr>& rhs);
370
371
372 // IOstream Operators
373
374 //- Print information
375 Ostream& info(Ostream& os) const;
376
377 //- Read buffer contents from Istream.
379
380 //- Write buffer contents with line-breaks in ASCII
381 //- when length exceeds shortLen.
382 // Using '0' suppresses line-breaks entirely.
383 Ostream& writeList(Ostream& os, const label shortLen=0) const;
384
385 //- Use the readList() method to read contents from Istream.
386 friend Istream& operator>> <T>
387 (
388 Istream& is,
390 );
391
392 //- Write to Ostream
393 friend Ostream& operator<< <T>
394 (
395 Ostream& os,
396 const CircularBuffer<T>& list
397 );
398
399
400 // Iterators
401
402 //- A simple forward const iterator for a circular buffer
403 class const_iterator
404 {
405 const CircularBuffer<T>* container_;
406 label iter_;
407
408 public:
410 using difference_type = label;
411 using value_type = const T;
412 using pointer = const T*;
413 using reference = const T&;
414 using iterator_category = std::forward_iterator_tag;
417 const_iterator& operator=(const const_iterator&) = default;
420 (
421 const CircularBuffer<T>* buffer,
422 label i
423 )
424 :
425 container_(buffer),
426 iter_(i)
427 {}
429 reference operator*() const
430 {
431 return (*container_)[iter_];
432 }
435 {
436 ++iter_;
437 return *this;
438 }
441 {
442 auto old(*this);
443 ++iter_;
444 return old;
445 }
447 bool operator==(const const_iterator& rhs) const
448 {
449 return iter_ == rhs.iter_;
450 }
452 bool operator!=(const const_iterator& rhs) const
453 {
454 return iter_ != rhs.iter_;
455 }
456 };
457
458
459 // Iterator (const)
460
461 //- Return a const_iterator at begin of buffer
462 inline const_iterator cbegin() const
463 {
464 return const_iterator(this, 0);
465 }
466
467 //- Return a const_iterator at end of buffer
468 inline const_iterator cend() const
469 {
470 return const_iterator(this, this->size());
471 }
472
473 //- Return a const_iterator at begin of buffer
474 inline const_iterator begin() const { return cbegin(); }
475
476 //- Return a const_iterator at end of buffer
477 inline const_iterator end() const { return cend(); }
478};
479
480
481// * * * * * * * * * * * * * * * IOstream Operators * * * * * * * * * * * * //
482
483//- Read buffer contents from Istream
484template<class T>
486{
487 return rhs.readList(is);
488}
489
490
491//- Write buffer contents to Ostream,
492//- as per CircularBuffer::writeList() with default length.
493template<class T>
495{
496 return rhs.writeList(os);
497}
498
499
500// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
501
502} // End namespace Foam
503
504// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
505
506#include "CircularBufferI.H"
507
508// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
509
510#ifdef NoRepository
511 #include "CircularBuffer.C"
512 #include "CircularBufferIO.C"
513#endif
514
515// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
516
517#endif
518
519// ************************************************************************* //
bool found
label n
A simple forward const iterator for a circular buffer.
std::forward_iterator_tag iterator_category
const_iterator(const CircularBuffer< T > *buffer, label i)
const_iterator(const const_iterator &)=default
bool operator!=(const const_iterator &rhs) const
bool operator==(const const_iterator &rhs) const
const_iterator & operator=(const const_iterator &)=default
A simple list of objects of type <T> that is intended to be used as a circular buffer (eg,...
label size_type
The type to represent the size of a buffer.
void pop_front(label n=1)
Shrink by moving the front of the buffer 1 or more times.
void clear() noexcept
Clear the addressed buffer, does not change allocation.
labelRange range_one() const noexcept
The addressing range covered by array_one()
label difference_type
The difference between iterator objects.
T & first()
Access the first element (front). Requires !empty().
void pop_back(label n=1)
Shrink by moving the end of the buffer 1 or more times.
T value_type
The value type the list contains.
constexpr CircularBuffer() noexcept
Default construct, empty buffer without allocation.
const_iterator begin() const
Return a const_iterator at begin of buffer.
void reverse()
Reverse the buffer order, swapping elements.
const_iterator cbegin() const
Return a const_iterator at begin of buffer.
bool empty() const noexcept
Empty or exhausted buffer.
void reserve_nocopy(const label len)
const T * const_pointer
The pointer type for const access to value_type items.
void append(const T &val)
Copy append an element to the end of the buffer.
T * pointer
The pointer type for non-const access to value_type items.
void clearStorage()
Clear the buffer and delete storage.
label appendUniq(const T &val)
Append an element if not already in the buffer.
void append(T &&val)
Move append an element to the end of the buffer.
Ostream & info(Ostream &os) const
Print information.
label capacity() const noexcept
Size of the underlying storage.
label find(const T &val, label pos=0) const
Find index of the first occurrence of the value.
const_iterator cend() const
Return a const_iterator at end of buffer.
label size() const noexcept
The current number of buffer items.
T & reference
The type used for storing into value_type objects.
void push_back(const T &val)
Copy append an element to the end of the buffer.
static constexpr label min_size() noexcept
Lower capacity limit.
SubList< T > array_two()
The contents of the first internal array.
void reserve(const label len)
Ostream & writeList(Ostream &os, const label shortLen=0) const
labelRange range_two() const noexcept
The addressing range covered by array_two()
void swap(CircularBuffer< T > &other)
Swap content, independent of sizing parameter.
label space() const noexcept
void push_front(const T &val)
Copy prepend an element to the front of the buffer.
const_iterator end() const
Return a const_iterator at end of buffer.
Istream & readList(Istream &is)
Read buffer contents from Istream.
void operator=(const CircularBuffer< T > &list)
Copy construct.
SubList< T > array_one()
The contents of the first internal array.
T & operator[](const label i)
Non-const access to an element in the list.
T & last()
Access the last element (back). Requires !empty().
const T & const_reference
The type used for reading from constant value_type objects.
Base for lists with indirect addressing, templated on the list contents type and the addressing type....
An Istream is an abstract base class for all input systems (streams, files, token lists etc)....
Definition: Istream.H:64
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
Definition: List.H:77
An Ostream is an abstract base class for all output systems (streams, files, token lists,...
Definition: Ostream.H:62
A List obtained as a section of another List.
Definition: SubList.H:70
A 1D vector of objects of type <T>, where the size of the vector is known and can be used for subscri...
Definition: UList.H:94
A range or interval of labels defined by a start and a size.
Definition: labelRange.H:58
A class representing the concept of 0 (zero) that can be used to avoid manipulating objects known to ...
Definition: zero.H:63
const volScalarField & T
OBJstream os(runTime.globalPath()/outputName)
Namespace for OpenFOAM.
dimensionedScalar pos(const dimensionedScalar &ds)
Ostream & operator<<(Ostream &, const boundaryPatch &p)
Write boundaryPatch as dictionary entries (without surrounding braces)
Definition: boundaryPatch.C:83
Istream & operator>>(Istream &, directionInfo &)
const direction noexcept
Definition: Scalar.H:223