mCRL2
Loading...
Searching...
No Matches
mcrl2::utilities::detail::free_list< Element > Class Template Reference

This essentially implements the std::forward_list, with the difference that it does not own the nodes in the list. It just keeps track of the list next pointers. Furthermore this assumes that the objects in the list will not be accessed, so it stores the next pointer within the Element. More...

#include <free_list.h>

Classes

union  slot
 The nodes of the free list without. More...
 
class  slot_iterator
 Iterator over all keys in a bucket list. More...
 

Public Types

using Freelist = free_list< Element >
 
using iterator = slot_iterator< false >
 
using const_iterator = slot_iterator< true >
 

Public Member Functions

 free_list ()
 
iterator begin ()
 
iterator end ()
 
iterator before_begin ()
 
const_iterator begin () const
 
const_iterator end () const
 
const_iterator before_begin () const
 
iterator erase_after (iterator it)
 Removes the element after the given iterator from the list. The returned iterator.
 
void clear ()
 Empties the bucket list.
 
bool contains (Element *pointer)
 
std::size_t count ()
 
void destructive_mark ()
 Mark all elements in this list with a special value, destroys the list.
 
bool empty () const noexcept
 
iterator insert_after (iterator it, slot &element)
 Inserts an element at the position after the iterator.
 
Element & pop_front ()
 Removes the head of the list and returns a reference to this head slot.
 
void push_front (slot &slot)
 Puts the given node before the head of the list.
 
void erase_after (iterator position, iterator last)
 Erases elements in the range (position, last], constant complexity since no destructors will be called.
 

Static Public Attributes

static constexpr std::uintptr_t FreeListSentinel = std::numeric_limits<std::uintptr_t>::max()
 A sentinel value for the next of a slot to indicate that it belonged to the freelist.
 

Private Member Functions

slothead () noexcept
 Provides access to the head as if it was an actual slot.
 
const slothead () const noexcept
 

Private Attributes

slot m_head
 The first node in the bucket list.
 

Detailed Description

template<typename Element>
class mcrl2::utilities::detail::free_list< Element >

This essentially implements the std::forward_list, with the difference that it does not own the nodes in the list. It just keeps track of the list next pointers. Furthermore this assumes that the objects in the list will not be accessed, so it stores the next pointer within the Element.

Definition at line 31 of file free_list.h.

Member Typedef Documentation

◆ const_iterator

template<typename Element >
using mcrl2::utilities::detail::free_list< Element >::const_iterator = slot_iterator<true>

Definition at line 143 of file free_list.h.

◆ Freelist

template<typename Element >
using mcrl2::utilities::detail::free_list< Element >::Freelist = free_list<Element>

Definition at line 141 of file free_list.h.

◆ iterator

template<typename Element >
using mcrl2::utilities::detail::free_list< Element >::iterator = slot_iterator<false>

Definition at line 142 of file free_list.h.

Constructor & Destructor Documentation

◆ free_list()

template<typename Element >
mcrl2::utilities::detail::free_list< Element >::free_list ( )
inline

Definition at line 145 of file free_list.h.

Member Function Documentation

◆ before_begin() [1/2]

template<typename Element >
iterator mcrl2::utilities::detail::free_list< Element >::before_begin ( )
inline
Returns
An iterator pointing to the before the head of the list.

Definition at line 152 of file free_list.h.

◆ before_begin() [2/2]

template<typename Element >
const_iterator mcrl2::utilities::detail::free_list< Element >::before_begin ( ) const
inline
Returns
A const iterator pointing to the before the head of the list.

Definition at line 159 of file free_list.h.

◆ begin() [1/2]

template<typename Element >
iterator mcrl2::utilities::detail::free_list< Element >::begin ( )
inline
Returns
An iterator over the keys of this bucket and successor buckets.

Definition at line 148 of file free_list.h.

◆ begin() [2/2]

template<typename Element >
const_iterator mcrl2::utilities::detail::free_list< Element >::begin ( ) const
inline
Returns
A const iterator over the keys of this bucket and successor buckets.

Definition at line 155 of file free_list.h.

◆ clear()

template<typename Element >
void mcrl2::utilities::detail::free_list< Element >::clear ( )
inline

Empties the bucket list.

Definition at line 177 of file free_list.h.

◆ contains()

template<typename Element >
bool mcrl2::utilities::detail::free_list< Element >::contains ( Element *  pointer)
inline
Returns
True if the given pointer is already in the freelist.

Definition at line 180 of file free_list.h.

◆ count()

template<typename Element >
std::size_t mcrl2::utilities::detail::free_list< Element >::count ( )
inline
Returns
The length of the freelist.

Definition at line 195 of file free_list.h.

◆ destructive_mark()

template<typename Element >
void mcrl2::utilities::detail::free_list< Element >::destructive_mark ( )
inline

Mark all elements in this list with a special value, destroys the list.

Definition at line 206 of file free_list.h.

◆ empty()

template<typename Element >
bool mcrl2::utilities::detail::free_list< Element >::empty ( ) const
inlinenoexcept
Returns
True if and only if this list is empty.

Definition at line 219 of file free_list.h.

◆ end() [1/2]

template<typename Element >
iterator mcrl2::utilities::detail::free_list< Element >::end ( )
inline

Definition at line 149 of file free_list.h.

◆ end() [2/2]

template<typename Element >
const_iterator mcrl2::utilities::detail::free_list< Element >::end ( ) const
inline

Definition at line 156 of file free_list.h.

◆ erase_after() [1/2]

template<typename Element >
iterator mcrl2::utilities::detail::free_list< Element >::erase_after ( iterator  it)
inline

Removes the element after the given iterator from the list. The returned iterator.

Definition at line 162 of file free_list.h.

◆ erase_after() [2/2]

template<typename Element >
void mcrl2::utilities::detail::free_list< Element >::erase_after ( iterator  position,
iterator  last 
)
inline

Erases elements in the range (position, last], constant complexity since no destructors will be called.

Definition at line 250 of file free_list.h.

◆ head() [1/2]

template<typename Element >
const slot & mcrl2::utilities::detail::free_list< Element >::head ( ) const
inlineprivatenoexcept

Definition at line 258 of file free_list.h.

◆ head() [2/2]

template<typename Element >
slot & mcrl2::utilities::detail::free_list< Element >::head ( )
inlineprivatenoexcept

Provides access to the head as if it was an actual slot.

Definition at line 257 of file free_list.h.

◆ insert_after()

template<typename Element >
iterator mcrl2::utilities::detail::free_list< Element >::insert_after ( iterator  it,
slot element 
)
inline

Inserts an element at the position after the iterator.

Definition at line 225 of file free_list.h.

◆ pop_front()

template<typename Element >
Element & mcrl2::utilities::detail::free_list< Element >::pop_front ( )
inline

Removes the head of the list and returns a reference to this head slot.

Definition at line 234 of file free_list.h.

◆ push_front()

template<typename Element >
void mcrl2::utilities::detail::free_list< Element >::push_front ( slot slot)
inline

Puts the given node before the head of the list.

Definition at line 242 of file free_list.h.

Member Data Documentation

◆ FreeListSentinel

template<typename Element >
constexpr std::uintptr_t mcrl2::utilities::detail::free_list< Element >::FreeListSentinel = std::numeric_limits<std::uintptr_t>::max()
staticconstexpr

A sentinel value for the next of a slot to indicate that it belonged to the freelist.

Definition at line 36 of file free_list.h.

◆ m_head

template<typename Element >
slot mcrl2::utilities::detail::free_list< Element >::m_head
private

The first node in the bucket list.

This wastes sizeof(Element) space, because slot can store both an Element or a next pointer.

Definition at line 262 of file free_list.h.


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