Classes | Public Types | Public Member Functions | Static Public Member Functions | Friends | List of all members
CircularBuffer< T > Class Template Reference

A simple list of objects of type <T> that is intended to be used as a circular buffer (eg, a FIFO) when the alloc/free overhead associated with a linked-list approach is to be avoided. More...

Classes

class  const_iterator
 A simple forward const iterator for a circular buffer. More...
 

Public Types

typedef T value_type
 The value type the list contains. More...
 
typedef Tpointer
 The pointer type for non-const access to value_type items. More...
 
typedef const Tconst_pointer
 The pointer type for const access to value_type items. More...
 
typedef Treference
 The type used for storing into value_type objects. More...
 
typedef const Tconst_reference
 The type used for reading from constant value_type objects. More...
 
typedef label size_type
 The type to represent the size of a buffer. More...
 
typedef label difference_type
 The difference between iterator objects. More...
 

Public Member Functions

constexpr CircularBuffer () noexcept
 Default construct, empty buffer without allocation. More...
 
 CircularBuffer (const label len)
 Construct an empty buffer with given reserve size. More...
 
 CircularBuffer (const CircularBuffer< T > &list)
 Copy construct. More...
 
 CircularBuffer (CircularBuffer< T > &&list)
 Move construct. More...
 
 CircularBuffer (Istream &is)
 Construct from Istream - uses readList. More...
 
label capacity () const noexcept
 Size of the underlying storage. More...
 
bool empty () const noexcept
 Empty or exhausted buffer. More...
 
label size () const noexcept
 The current number of buffer items. More...
 
label space () const noexcept
 The nominal space available to fill. Subtract 1 for the number to append before re-balancing is needed. More...
 
labelRange range_one () const noexcept
 The addressing range covered by array_one() More...
 
labelRange range_two () const noexcept
 The addressing range covered by array_two() More...
 
SubList< Tarray_one ()
 The contents of the first internal array. More...
 
SubList< Tarray_two ()
 The contents of the first internal array. More...
 
const SubList< Tarray_one () const
 The contents of the second internal array. More...
 
const SubList< Tarray_two () const
 The contents of the second internal array. More...
 
Tfront ()
 Access the first element (front). Requires !empty(). More...
 
Tback ()
 Access the last element (back). Requires !empty(). More...
 
const Tfront () const
 Const access to the first element (front). Requires !empty(). More...
 
const Tback () const
 Const access to the last element (back). Requires !empty(). More...
 
void reserve (const label len)
 Reserve allocation space for at least this size, allocating new space if required and retaining old content. More...
 
void reserve_nocopy (const label len)
 Reserve allocation space for at least this size, allocating new space if required without retaining old content. More...
 
void clear () noexcept
 Clear the addressed buffer, does not change allocation. More...
 
void clearStorage ()
 Clear the buffer and delete storage. More...
 
void swap (CircularBuffer< T > &other)
 Swap content, independent of sizing parameter. More...
 
label find (const T &val, label pos=0) const
 Find index of the first occurrence of the value. More...
 
bool contains (const T &val, label pos=0) const
 Is the value contained in the list? More...
 
void push_front (const T &val)
 Copy prepend an element to the front of the buffer. More...
 
void push_front (T &&val)
 Move prepend an element to the front of the buffer. More...
 
void push_back (const T &val)
 Copy append an element to the end of the buffer. More...
 
void push_back (T &&val)
 Move Append an element to the end of the buffer. More...
 
void pop_front (label n=1)
 Shrink by moving the front of the buffer 1 or more times. More...
 
void pop_back (label n=1)
 Shrink by moving the end of the buffer 1 or more times. More...
 
void push_back (const UList< T > &list)
 Copy append multiple elements the end of the buffer. More...
 
template<class Addr >
void push_back (const IndirectListBase< T, Addr > &list)
 Copy append IndirectList elements the end of the buffer. More...
 
label push_uniq (const T &val)
 Append an element if not already in the buffer. More...
 
List< Tlist () const
 Return a copy of the buffer flattened into a single List. Use sparingly! More...
 
void reverse ()
 Reverse the buffer order, swapping elements. More...
 
List< Toperator() () const
 Return the buffer flattened as a single List. Use sparingly! More...
 
Toperator[] (const label i)
 Non-const access to an element in the list. More...
 
const Toperator[] (const label i) const
 Const access to an element in the list. More...
 
void operator= (const CircularBuffer< T > &list)
 Copy construct. More...
 
void operator= (CircularBuffer< T > &&list)
 Move construct. More...
 
void operator= (const T &val)
 Assign all addressed elements to the given value. More...
 
void operator= (const Foam::zero)
 Assignment of all entries to zero. More...
 
void operator= (const UList< T > &rhs)
 Deep copy values from a list of the addressed elements. More...
 
template<class AnyAddr >
void operator= (const IndirectListBase< T, AnyAddr > &rhs)
 Deep copy values from a list of the addressed elements. More...
 
Ostreaminfo (Ostream &os) const
 Print information. More...
 
IstreamreadList (Istream &is)
 Read buffer contents from Istream. More...
 
OstreamwriteList (Ostream &os, const label shortLen=0) const
 Write buffer contents with line-breaks in ASCII when length exceeds shortLen. More...
 
const_iterator cbegin () const
 Return a const_iterator at begin of buffer. More...
 
const_iterator cend () const
 Return a const_iterator at end of buffer. More...
 
const_iterator begin () const
 Return a const_iterator at begin of buffer. More...
 
const_iterator end () const
 Return a const_iterator at end of buffer. More...
 
bool found (const T &val, label pos=0) const
 Same as contains() More...
 
Tfirst ()
 Access the first element (front). Requires !empty(). More...
 
const Tfirst () const
 Access the first element (front). Requires !empty(). More...
 
Tlast ()
 Access the last element (back). Requires !empty(). More...
 
const Tlast () const
 Access the last element (back). Requires !empty(). More...
 
void append (const T &val)
 Copy append an element to the end of the buffer. More...
 
void append (T &&val)
 Move append an element to the end of the buffer. More...
 
void append (const UList< T > &list)
 Copy append multiple elements the end of the buffer. More...
 
label appendUniq (const T &val)
 Append an element if not already in the buffer. More...
 

Static Public Member Functions

static constexpr label min_size () noexcept
 Lower capacity limit. More...
 

Friends

Istreamoperator>> (Istream &is, CircularBuffer< T > &list)
 Use the readList() method to read contents from Istream. More...
 
Ostreamoperator (Ostream &os, const CircularBuffer< T > &list)
 Write to Ostream. More...
 

Detailed Description

template<class T>
class Foam::CircularBuffer< T >

A simple list of objects of type <T> that is intended to be used as a circular buffer (eg, a FIFO) when the alloc/free overhead associated with a linked-list approach is to be avoided.

The internal storage is addressed by independent begin/end markers.

This results in a variety ofr different possible buffer states:

  1. empty (begin == end)
  2. simple/linear (begin < end) has no wrapping:
       |.|.|.|a|b|c|d|.|.|.|
       beg ___^
       end ___________^
  3. split (begin > end):
       |f|g|h|i|.|.|.|a|b|c|d|e|
       end _____^
       beg ___________^

The methods range_one(), range_two() return the internal indexing and the methods array_one(), array_two() provide direct access to the internal contents.

When filling the buffer, the internal storage will be resized (doubling strategy) as required. When this occurs, the new list will be linearized with begin = 0.

Simultaneously when filling, the storage buffer will be over-allocated to avoid ambiguity when (begin == end), which represents an empty buffer and not a full buffer. Eg,

    |c|d|.|a|b|
    end _^
    beg ___^

after appending one more, it would be incorrect to simply fill the available space:

    |c|d|e|a|b|
    end ___^        WRONG : would represent empty!
    beg ___^

the storage is instead increased (doubled) and rebalanced before the append occurs (old capacity 5, new capacity 10):

    |a|b|c|d|e|.|.|.|.|.|
    _^_ beg
    end _______^
Source files

Definition at line 102 of file CircularBuffer.H.

Member Typedef Documentation

◆ value_type

typedef T value_type

The value type the list contains.

Definition at line 175 of file CircularBuffer.H.

◆ pointer

typedef T* pointer

The pointer type for non-const access to value_type items.

Definition at line 180 of file CircularBuffer.H.

◆ const_pointer

typedef const T* const_pointer

The pointer type for const access to value_type items.

Definition at line 185 of file CircularBuffer.H.

◆ reference

typedef T& reference

The type used for storing into value_type objects.

Definition at line 190 of file CircularBuffer.H.

◆ const_reference

typedef const T& const_reference

The type used for reading from constant value_type objects.

Definition at line 195 of file CircularBuffer.H.

◆ size_type

typedef label size_type

The type to represent the size of a buffer.

Definition at line 200 of file CircularBuffer.H.

◆ difference_type

typedef label difference_type

The difference between iterator objects.

Definition at line 205 of file CircularBuffer.H.

Constructor & Destructor Documentation

◆ CircularBuffer() [1/5]

constexpr CircularBuffer ( )
inlinenoexcept

Default construct, empty buffer without allocation.

Definition at line 107 of file CircularBufferI.H.

◆ CircularBuffer() [2/5]

CircularBuffer ( const label  len)
inlineexplicit

Construct an empty buffer with given reserve size.

Definition at line 116 of file CircularBufferI.H.

◆ CircularBuffer() [3/5]

CircularBuffer ( const CircularBuffer< T > &  list)
inline

Copy construct.

Definition at line 126 of file CircularBufferI.H.

◆ CircularBuffer() [4/5]

CircularBuffer ( CircularBuffer< T > &&  list)
inline

Move construct.

Definition at line 138 of file CircularBufferI.H.

◆ CircularBuffer() [5/5]

CircularBuffer ( Istream is)
explicit

Construct from Istream - uses readList.

Definition at line 28 of file CircularBufferIO.C.

Member Function Documentation

◆ min_size()

static constexpr label min_size ( )
inlinestaticnoexcept

Lower capacity limit.

Definition at line 248 of file CircularBuffer.H.

◆ capacity()

Foam::label capacity ( ) const
inlinenoexcept

Size of the underlying storage.

Definition at line 154 of file CircularBufferI.H.

◆ empty()

bool empty ( ) const
inlinenoexcept

Empty or exhausted buffer.

Definition at line 161 of file CircularBufferI.H.

Referenced by Foam::meshTools::bandCompression().

Here is the caller graph for this function:

◆ size()

Foam::label size ( ) const
inlinenoexcept

The current number of buffer items.

Definition at line 168 of file CircularBufferI.H.

References Foam::diff().

Referenced by CircularBuffer< T >::cend(), and Foam::polyMeshZipUpCells().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ space()

Foam::label space ( ) const
inlinenoexcept

The nominal space available to fill. Subtract 1 for the number to append before re-balancing is needed.

Definition at line 182 of file CircularBufferI.H.

◆ range_one()

Foam::labelRange range_one ( ) const
inlinenoexcept

The addressing range covered by array_one()

Definition at line 189 of file CircularBufferI.H.

◆ range_two()

Foam::labelRange range_two ( ) const
inlinenoexcept

The addressing range covered by array_two()

Definition at line 201 of file CircularBufferI.H.

◆ array_one() [1/2]

Foam::SubList< T > array_one ( )

The contents of the first internal array.

Definition at line 70 of file CircularBuffer.C.

Referenced by CircularBuffer< T >::operator=().

Here is the caller graph for this function:

◆ array_two() [1/2]

Foam::SubList< T > array_two ( )

The contents of the first internal array.

Definition at line 78 of file CircularBuffer.C.

Referenced by CircularBuffer< T >::operator=().

Here is the caller graph for this function:

◆ array_one() [2/2]

const Foam::SubList< T > array_one ( ) const

The contents of the second internal array.

Definition at line 86 of file CircularBuffer.C.

◆ array_two() [2/2]

const Foam::SubList< T > array_two ( ) const

The contents of the second internal array.

Definition at line 94 of file CircularBuffer.C.

◆ front() [1/2]

T & front ( )
inline

Access the first element (front). Requires !empty().

Definition at line 259 of file CircularBufferI.H.

References Foam::abort(), Foam::FatalError, and FatalErrorInFunction.

Referenced by Foam::meshTools::bandCompression(), CircularBuffer< T >::first(), and Foam::polyMeshZipUpCells().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ back() [1/2]

T & back ( )
inline

Access the last element (back). Requires !empty().

Definition at line 283 of file CircularBufferI.H.

References Foam::abort(), Foam::FatalError, and FatalErrorInFunction.

Referenced by CircularBuffer< T >::last(), and Foam::polyMeshZipUpCells().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ front() [2/2]

const T & front ( ) const
inline

Const access to the first element (front). Requires !empty().

Definition at line 271 of file CircularBufferI.H.

References Foam::abort(), Foam::FatalError, and FatalErrorInFunction.

Here is the call graph for this function:

◆ back() [2/2]

const T & back ( ) const
inline

Const access to the last element (back). Requires !empty().

Definition at line 295 of file CircularBufferI.H.

References Foam::abort(), Foam::FatalError, and FatalErrorInFunction.

Here is the call graph for this function:

◆ reserve()

void reserve ( const label  len)
inline

Reserve allocation space for at least this size, allocating new space if required and retaining old content.

Never shrinks.

Definition at line 238 of file CircularBufferI.H.

◆ reserve_nocopy()

void reserve_nocopy ( const label  len)
inline

Reserve allocation space for at least this size, allocating new space if required without retaining old content.

Never shrinks.

Definition at line 245 of file CircularBufferI.H.

◆ clear()

void clear ( )
inlinenoexcept

Clear the addressed buffer, does not change allocation.

Definition at line 208 of file CircularBufferI.H.

Referenced by Foam::polyMeshZipUpCells().

Here is the caller graph for this function:

◆ clearStorage()

void clearStorage ( )
inline

Clear the buffer and delete storage.

Definition at line 215 of file CircularBufferI.H.

◆ swap()

void swap ( CircularBuffer< T > &  other)
inline

Swap content, independent of sizing parameter.

Definition at line 223 of file CircularBufferI.H.

◆ find()

Foam::label find ( const T val,
label  pos = 0 
) const

Find index of the first occurrence of the value.

Any occurrences before the start pos are ignored. Linear search.

Returns
position in list or -1 if not found.

Definition at line 102 of file CircularBuffer.C.

References Foam::pos().

Here is the call graph for this function:

◆ contains()

bool contains ( const T val,
label  pos = 0 
) const
inline

Is the value contained in the list?

Linear search from start pos until the end of the list. Any occurrences before the start pos are ignored.

Returns
true if found.

Definition at line 252 of file CircularBufferI.H.

References Foam::ListOps::find(), and Foam::pos().

Referenced by CircularBuffer< T >::found().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ push_front() [1/2]

void push_front ( const T val)
inline

Copy prepend an element to the front of the buffer.

Definition at line 307 of file CircularBufferI.H.

References reserve().

Referenced by Foam::polyMeshZipUpCells().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ push_front() [2/2]

void push_front ( T &&  val)
inline

Move prepend an element to the front of the buffer.

Definition at line 319 of file CircularBufferI.H.

References reserve().

Here is the call graph for this function:

◆ push_back() [1/4]

void push_back ( const T val)
inline

Copy append an element to the end of the buffer.

Definition at line 331 of file CircularBufferI.H.

References reserve().

Referenced by CircularBuffer< T >::append(), Foam::meshTools::bandCompression(), and Foam::polyMeshZipUpCells().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ push_back() [2/4]

void push_back ( T &&  val)
inline

Move Append an element to the end of the buffer.

Definition at line 343 of file CircularBufferI.H.

References reserve().

Here is the call graph for this function:

◆ pop_front()

void pop_front ( label  n = 1)
inline

Shrink by moving the front of the buffer 1 or more times.

Definition at line 355 of file CircularBufferI.H.

References n.

Referenced by Foam::meshTools::bandCompression(), and Foam::polyMeshZipUpCells().

Here is the caller graph for this function:

◆ pop_back()

void pop_back ( label  n = 1)
inline

Shrink by moving the end of the buffer 1 or more times.

Definition at line 372 of file CircularBufferI.H.

References n.

◆ push_back() [3/4]

void push_back ( const UList< T > &  list)
inline

Copy append multiple elements the end of the buffer.

Definition at line 404 of file CircularBufferI.H.

References UList< T >::fcIndex(), reserve(), and UList< T >::size().

Here is the call graph for this function:

◆ push_back() [4/4]

void push_back ( const IndirectListBase< T, Addr > &  list)
inline

Copy append IndirectList elements the end of the buffer.

Definition at line 426 of file CircularBufferI.H.

References IndirectListBase< T, Addr >::fcIndex(), reserve(), and IndirectListBase< T, Addr >::size().

Here is the call graph for this function:

◆ push_uniq()

Foam::label push_uniq ( const T val)
inline

Append an element if not already in the buffer.

Returns
the change in the buffer length

Definition at line 389 of file CircularBufferI.H.

Referenced by CircularBuffer< T >::appendUniq().

Here is the caller graph for this function:

◆ list()

Foam::List< T > list ( ) const

Return a copy of the buffer flattened into a single List. Use sparingly!

Definition at line 154 of file CircularBuffer.C.

References UList< T >::slice().

Referenced by CircularBuffer< T >::operator()(), and Foam::polyMeshZipUpCells().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ reverse()

void reverse ( )

Reverse the buffer order, swapping elements.

Definition at line 141 of file CircularBuffer.C.

References n, and Foam::Swap().

Here is the call graph for this function:

◆ operator()()

List<T> operator() ( ) const
inline

Return the buffer flattened as a single List. Use sparingly!

Definition at line 454 of file CircularBuffer.H.

References CircularBuffer< T >::list().

Here is the call graph for this function:

◆ operator[]() [1/2]

T & operator[] ( const label  i)
inline

Non-const access to an element in the list.

The index is allowed to wrap in both directions

Definition at line 450 of file CircularBufferI.H.

◆ operator[]() [2/2]

const T & operator[] ( const label  i) const
inline

Const access to an element in the list.

The index is allowed to wrap in both directions

Definition at line 458 of file CircularBufferI.H.

◆ operator=() [1/6]

void operator= ( const CircularBuffer< T > &  list)
inline

Copy construct.

Definition at line 466 of file CircularBufferI.H.

References CircularBuffer< T >::array_one(), CircularBuffer< T >::array_two(), clear(), reserve(), and Foam::T().

Here is the call graph for this function:

◆ operator=() [2/6]

void operator= ( CircularBuffer< T > &&  list)
inline

Move construct.

Definition at line 503 of file CircularBufferI.H.

◆ operator=() [3/6]

void operator= ( const T val)
inline

Assign all addressed elements to the given value.

Definition at line 516 of file CircularBufferI.H.

◆ operator=() [4/6]

void operator= ( const Foam::zero  )
inline

Assignment of all entries to zero.

Definition at line 524 of file CircularBufferI.H.

References Foam::Zero.

◆ operator=() [5/6]

void operator= ( const UList< T > &  rhs)
inline

Deep copy values from a list of the addressed elements.

Definition at line 532 of file CircularBufferI.H.

◆ operator=() [6/6]

void operator= ( const IndirectListBase< T, AnyAddr > &  rhs)
inline

Deep copy values from a list of the addressed elements.

Definition at line 541 of file CircularBufferI.H.

◆ info()

Foam::Ostream & info ( Ostream os) const

Print information.

<< " one=" << this->range_one() << this->array_one() << " two=" << this->range_two() << this->array_two()

Definition at line 37 of file CircularBufferIO.C.

References Foam::nl, and os().

Here is the call graph for this function:

◆ readList()

Foam::Istream & readList ( Istream is)

◆ writeList()

Foam::Ostream & writeList ( Ostream os,
const label  shortLen = 0 
) const

Write buffer contents with line-breaks in ASCII when length exceeds shortLen.

Using '0' suppresses line-breaks entirely.

Definition at line 145 of file CircularBufferIO.C.

References Foam::abort(), Foam::FatalError, FatalErrorInFunction, FUNCTION_NAME, Foam::nl, os(), and T.

Here is the call graph for this function:

◆ cbegin()

const_iterator cbegin ( ) const
inline

Return a const_iterator at begin of buffer.

Definition at line 607 of file CircularBuffer.H.

Referenced by CircularBuffer< T >::begin().

Here is the caller graph for this function:

◆ cend()

const_iterator cend ( ) const
inline

Return a const_iterator at end of buffer.

Definition at line 615 of file CircularBuffer.H.

References CircularBuffer< T >::size().

Referenced by CircularBuffer< T >::end().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ begin()

const_iterator begin ( ) const
inline

Return a const_iterator at begin of buffer.

Definition at line 623 of file CircularBuffer.H.

References CircularBuffer< T >::cbegin().

Here is the call graph for this function:

◆ end()

const_iterator end ( ) const
inline

Return a const_iterator at end of buffer.

Definition at line 628 of file CircularBuffer.H.

References CircularBuffer< T >::cend().

Here is the call graph for this function:

◆ found()

bool found ( const T val,
label  pos = 0 
) const
inline

Same as contains()

Definition at line 636 of file CircularBuffer.H.

References CircularBuffer< T >::contains(), and Foam::pos().

Here is the call graph for this function:

◆ first() [1/2]

T& first ( )
inline

Access the first element (front). Requires !empty().

FOAM_DEPRECATED_FOR(2022-10, "front()")

Definition at line 646 of file CircularBuffer.H.

References CircularBuffer< T >::front().

Here is the call graph for this function:

◆ first() [2/2]

const T& first ( ) const
inline

Access the first element (front). Requires !empty().

FOAM_DEPRECATED_FOR(2022-10, "front()")

Definition at line 653 of file CircularBuffer.H.

References CircularBuffer< T >::front().

Here is the call graph for this function:

◆ last() [1/2]

T& last ( )
inline

Access the last element (back). Requires !empty().

FOAM_DEPRECATED_FOR(2022-10, "back()")

Definition at line 660 of file CircularBuffer.H.

References CircularBuffer< T >::back().

Here is the call graph for this function:

◆ last() [2/2]

const T& last ( ) const
inline

Access the last element (back). Requires !empty().

FOAM_DEPRECATED_FOR(2022-10, "back()")

Definition at line 667 of file CircularBuffer.H.

References CircularBuffer< T >::back().

Here is the call graph for this function:

◆ append() [1/3]

void append ( const T val)
inline

Copy append an element to the end of the buffer.

FOAM_DEPRECATED_FOR(2022-10, "push_back()")

Definition at line 674 of file CircularBuffer.H.

References CircularBuffer< T >::push_back().

Here is the call graph for this function:

◆ append() [2/3]

void append ( T &&  val)
inline

Move append an element to the end of the buffer.

FOAM_DEPRECATED_FOR(2022-10, "push_back()")

Definition at line 681 of file CircularBuffer.H.

References CircularBuffer< T >::push_back().

Here is the call graph for this function:

◆ append() [3/3]

void append ( const UList< T > &  list)
inline

Copy append multiple elements the end of the buffer.

FOAM_DEPRECATED_FOR(2022-10, "push_back()")

Definition at line 688 of file CircularBuffer.H.

References CircularBuffer< T >::push_back().

Here is the call graph for this function:

◆ appendUniq()

label appendUniq ( const T val)
inline

Append an element if not already in the buffer.

FOAM_DEPRECATED_FOR(2022-10, "push_uniq()")

Definition at line 695 of file CircularBuffer.H.

References CircularBuffer< T >::push_uniq().

Here is the call graph for this function:

Friends And Related Function Documentation

◆ operator>>

Istream& operator>> ( Istream is,
CircularBuffer< T > &  list 
)
friend

Use the readList() method to read contents from Istream.

Definition at line 705 of file CircularBuffer.H.

◆ operator

Ostream& operator ( Ostream os,
const CircularBuffer< T > &  list 
)
friend

Write to Ostream.


The documentation for this class was generated from the following files: