Container used to link objects into a sequence. More...

#include </mnt/devel/pabigot-cxx/include/pabigot/container.hpp>

Data Structures
class	chain_iterator_type
	Iterator type designed to support range-for. More...

class	end_iterator_type
	Sentinal type used as end-of-chain iterator value. More...

Public Types
using	chain_type = forward_chain< T, REF_NEXT >
	The type of this chain.

using	value_type = T
	The type of object linked by this chain.

using	pointer_type = value_type *
	The type for a pointer to value_type.

using	predicate_type = std::function< bool(const value_type &)>
	The type for a function that tests a value_type for a condition.

Public Member Functions
bool	is_unlinked (pointer_type ptr) const noexcept
	Test whether a pointer is unlinked.

bool	is_unlinked (value_type &value) const noexcept
	Test whether a value is unlinked.

	forward_chain (const forward_chain &)=delete

forward_chain &	operator= (const forward_chain &)=delete

	forward_chain (forward_chain &&from) noexcept

forward_chain &	operator= (forward_chain &&from) noexcept

chain_iterator_type	begin () const noexcept
	Get an iterator that starts at the beginning of the chain.

end_iterator_type	end () const noexcept
	Get a value `end` for which `iter != end` will return false only when `iter` is a chain_iterator_type that is past the end of its chain.

bool	empty () const noexcept
	Indicate whether the sequence is empty.

pointer_type	front () const noexcept
	Return a pointer to the first value in the sequence.

pointer_type	next (value_type &elt) const noexcept
	Return a pointer to the next value in the sequence. More...

pointer_type	back () const noexcept
	Return a pointer to the last value in the sequence.

void	link_front (value_type &value) noexcept
	Add the value to the front of the sequence. More...

pointer_type	unlink_front () noexcept
	Remove and return a pointer to the first value of the sequence.

void	link_after (value_type &pos, value_type &value) noexcept
	Add the value immediately after an value already in the sequence. More...

void	link_before (value_type &value, predicate_type pred) noexcept
	Add the value immediately before the first value in the sequence for which `pred` is `true`. More...

chain_type	split_through (predicate_type pred) noexcept
	Strip off a chain of all leading elements that satisfy a predicate. More...

void	link_back (value_type &value) noexcept
	Add the value to the end of the sequence. More...

pointer_type	unlink (value_type &value) noexcept
	Remove an value from the sequence at any position. More...

void	clear () noexcept
	Remove all values from the sequence.

Static Public Member Functions
static pointer_type	unlinked_ptr () noexcept
	Test whether a pointer is unlinked.

Static Public Attributes
static constexpr uintptr_t	UNLINKED_PTR = -1
	Integral value of an invalid pointer used to denote unlinked objects.

Detailed Description

template<typename T, typename REF_NEXT>
class pabigot::container::forward_chain< T, REF_NEXT >

Container used to link objects into a sequence.

The container is intended for use in embedded systems where objects may need to be present in one or more sequences and dynamic memory allocation for std::forward_list and similar containers is not desired. Links are instead stored as fields within the linked structures, accessed through a function object provided to the container on construction.

Supports:

constant time LIFO operations via link_front() and unlink_front();
constant time FIFO operations via link_back() and unlink_front();
constant time link_after() an object already in the sequence;
linear time link_before() the first object satisfying a predicate, supporting order sequences;
linear time split_after() to remove the predicate-satisfying prefix of a list;
linear time unlink();
forward iteration including range-for;
detection of values that are not in a list via is_unlinked() as long as the link field is initialized to unlinked_ptr().

Container instances may be moved, but cannot be copied.

Note: References stored in the sequence are not const-qualified: iterating over a const forward_chain instance allows non-const operations to be performed on the objects themselves.; Iterator invalidation with this sequence is not the same as with std::forward_list. It is specifically safe to unlink the current value from the sequence within a range-for statement body: iteration will continue with the next value in the original sequence. Removing other values, or adding values, may produce anomalous behavior if an existing iterator is used after the sequence is modified. Iterators are also invalidated if the sequence is moved.

Warning: The application is responsible for ensuring that instances are only added to the chain when they are not already in a chain . Violation of this may result in corrupted data structures that include cycles or cross-linked chains.

Template Parameters

T	the type of the instance.
REF_NEXT	a function object type where `operator()` converts a `T&` to a `T*&` which is the lvalue for the pointer to the next `T` in the chain.

Example:

struct object {
  // Function object type used to reference field next
  struct ref_next {
    using pointer_type = object *;
    pointer_type& operator() (object& m) noexcept
    {
      return m.next;
    }
  };
  using chain_type = forward_chain<object>;

  // Declare link used when in a chain, initalized as unlinked
  chain_type::pointer_type next{chain_type::unlinked_ptr()};

  // Declare the chain that links objects
  static chain_type chain;
};

Member Function Documentation

◆ link_after()

template<typename T , typename REF_NEXT >

void pabigot::container::forward_chain< T, REF_NEXT >::link_after	(	value_type &	pos,
		value_type &	value
	)

inlinenoexcept

Add the value immediately after an value already in the sequence.

Parameters

pos	the value already in the sequence.
value	the value to add after `pos`.

◆ link_back()

template<typename T , typename REF_NEXT >

void pabigot::container::forward_chain< T, REF_NEXT >::link_back ( value_type & value )

inlinenoexcept

Add the value to the end of the sequence.

Warning: value must not already be in the sequence.

◆ link_before()

template<typename T , typename REF_NEXT >

void pabigot::container::forward_chain< T, REF_NEXT >::link_before	(	value_type &	value,
		predicate_type	pred
	)

inlinenoexcept

Add the value immediately before the first value in the sequence for which pred is true.

If no value in the sequence satisfies the predicate the new value is linked at the end.

Parameters

value	the value to insert into the chain.
pred	the predicate that identifies the linked member before which `value` will be inserted.

◆ link_front()

template<typename T , typename REF_NEXT >

void pabigot::container::forward_chain< T, REF_NEXT >::link_front ( value_type & value )

inlinenoexcept

Add the value to the front of the sequence.

Warning: value must not already be in the sequence.

◆ next()

template<typename T , typename REF_NEXT >

pointer_type pabigot::container::forward_chain< T, REF_NEXT >::next ( value_type & elt ) const

inlinenoexcept

Return a pointer to the next value in the sequence.

Parameters

ptr	an object known to be in the chain.

Returns: a pointer to the next object in the chain, or nullptr if elt is last.

◆ split_through()

template<typename T , typename REF_NEXT >

chain_type pabigot::container::forward_chain< T, REF_NEXT >::split_through ( predicate_type pred )

inlinenoexcept

Strip off a chain of all leading elements that satisfy a predicate.

This may be used on a chain linking objects by some ordinal function via insert_before(), to extract the prefix list of items that are ready to process.

Parameters

pred	the predicate that identifies elements that are to be removed from the list.

Returns: a new chain containing only the elements that satisfy pred. The chain in which this method is invoked holds any remaining elements.

◆ unlink()

template<typename T , typename REF_NEXT >

pointer_type pabigot::container::forward_chain< T, REF_NEXT >::unlink ( value_type & value )

inlinenoexcept

Remove an value from the sequence at any position.

Parameters

value the value to be removed

Returns: the address of value if value was in the sequence, otherwise a null pointer.

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

/mnt/devel/pabigot-cxx/include/pabigot/container.hpp

Data Structures

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

template<typename T, typename REF_NEXT> class pabigot::container::forward_chain< T, REF_NEXT >

Member Function Documentation

◆ link_after()

◆ link_back()

◆ link_before()

◆ link_front()

◆ next()

◆ split_through()

◆ unlink()

template<typename T, typename REF_NEXT>
class pabigot::container::forward_chain< T, REF_NEXT >