simple_list.h File Reference

Simple list implementation (with pool allocator) More...

Go to the source code of this file.

Classes
class	mcrl2::lts::detail::my_pool< T, NR_ELEMENTS >
class	mcrl2::lts::detail::my_pool< T, NR_ELEMENTS >::pool_block_t
class	mcrl2::lts::detail::simple_list< T >
	a simple implementation of lists More...
class	mcrl2::lts::detail::simple_list< T >::entry
	list entry More...
class	mcrl2::lts::detail::simple_list< T >::const_iterator
	constant iterator class for simple_list More...
class	mcrl2::lts::detail::simple_list< T >::iterator
	iterator class for simple_list More...
class	mcrl2::lts::detail::simple_list< T >::iterator_or_null
	class that stores either an iterator or a null value More...

Namespaces
namespace	mcrl2
	A class that takes a linear process specification and checks all tau-summands of that LPS for confluence.
namespace	mcrl2::lts
	The main LTS namespace.
namespace	mcrl2::lts::detail
	A base class for the lts_dot labelled transition system.

Macros
#define	USE_SIMPLE_LIST
#define	USE_POOL_ALLOCATOR
#define	ONLY_IF_POOL_ALLOCATOR(...)   __VA_ARGS__

Typedefs
template<class El >
using	mcrl2::lts::detail::iterator_or_null_t = typename simple_list< El >::iterator_or_null

Detailed Description

Simple list implementation (with pool allocator)

This file supports partition refinement algorithms by implementing a simple list data structure, possibly with a pool allocator.

The main difference to std::list<T> is that the simple list only stores a pointer to the first list element; there is no sentinel. The list elements themselves form a doubly-linked list that is almost circular; only the pointer from the last element to the next one is nullptr. This allows to find the last element in the list (namely as predecessor of the first). A disadvantage is that the list does not allow to find the last element through std::prev(end()); to alleviate this, we offer a separate function before_end().

Also, a simple list requires the stored elements to be trivially destructible, so they can be stored in a pool allocator data structure.

The pool allocator uses larger blocks to allocate data items, mostly list elements, but also other items can be stored, as long as they are trivially destructible. To access the pool, one uses simple_list<element type>::get_pool(). However, only elements of the same size as simple_list<element type> entries can be deleted. This is a static pool that is available throughout the running time of the program. (If you are really concerned about shaving off every small bit of time, you might destroy the pool through a memory leak upon termination of the program – to that end, modify the destructor of my_pool to do nothing.)

Author

David N. Jansen, Institute of Software, Chinese Academy of Sciences, Beijing, PR China

Definition in file simple_list.h.

Macro Definition Documentation

ONLY_IF_POOL_ALLOCATOR

#define ONLY_IF_POOL_ALLOCATOR

(

...

)

__VA_ARGS__

Definition at line 90 of file simple_list.h.

USE_POOL_ALLOCATOR

#define USE_POOL_ALLOCATOR

Definition at line 66 of file simple_list.h.

USE_SIMPLE_LIST

#define USE_SIMPLE_LIST

Definition at line 60 of file simple_list.h.