A "good enough for PPD" implementation of a singly-linked, hybrid, intrusive, pointer-based list. More...

#include <intrusive.hpp>

Inheritance diagram for jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >:

Collaboration diagram for jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >:

Public Types
typedef stack< V, LkT >	base_t

typedef base_t::value_type	value_type

typedef base_t::lock_traits	lock_traits

typedef base_t::size_ctr_t	size_ctr_t

typedef base_t::size_type	size_type

typedef base_t::iterator	iterator

typedef base_t::const_iterator	const_iterator

typedef base_t::difference_type	difference_type

typedef base_t::pointer	pointer

typedef base_t::reference	reference

typedef base_t::const_pointer	const_pointer

typedef base_t::const_reference	const_reference

typedef base_t::deleter_t	deleter_t

typedef base_t::ctr_type	ctr_type

typedef base_t::exception_type	exception_type

Public Types inherited from jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >
using	lock_traits = typename node_details_t::lock_traits

typedef std::size_t	size_type

typedef shared_ptr< V, LkT >	value_type

typedef lock_traits::template atomic_counter_type< unsigned long >	size_ctr_t

typedef private_::slist_iterator_internal< V, LkT >	iterator

typedef private_::slist_iterator_internal< V const, LkT >	const_iterator

typedef iterator::difference_type	difference_type

typedef iterator::pointer	pointer

typedef iterator::reference	reference

typedef const_iterator::const_pointer	const_pointer

typedef const_iterator::const_reference	const_reference

typedef value_type::deleter_t	deleter_t

typedef value_type::ctr_type	ctr_type

typedef value_type::exception_type	exception_type

Public Member Functions
__stdcall	slist () noexcept(true) FORCE_INLINE

	slist (slist &&) noexcept(true) FORCE_INLINE

__stdcall	~slist () noexcept(true) FORCE_INLINE

iterator __fastcall	find (const_reference v) noexcept(true) FORCE_INLINE
	Find if the element is within the container. More...

const_iterator __fastcall	find (const_reference v) const noexcept(true) FORCE_INLINE
	Find if the element is within the container. More...

size_type __fastcall	erase (const_reference v) noexcept(true) FORCE_INLINE
	Remove the element from the container. More...

value_type __fastcall	front () noexcept(true) FORCE_INLINE

value_type __fastcall	front () const noexcept(true) FORCE_INLINE

value_type __fastcall	back () noexcept(true) FORCE_INLINE

value_type __fastcall	back () const noexcept(true) FORCE_INLINE

void __fastcall	push_front (value_type const &v) noexcept(true) FORCE_INLINE

void __fastcall	push_front (value_type &&v) noexcept(true) FORCE_INLINE

void __fastcall	pop_front () noexcept(true) FORCE_INLINE

void __fastcall	push_back (value_type const &v) noexcept(true) FORCE_INLINE

void __fastcall	push_back (value_type &&v) noexcept(true) FORCE_INLINE

bool	penultimate_reachable_from_prefront () const noexcept(true) FORCE_INLINE

void __fastcall	erase (iterator v) noexcept(true) FORCE_INLINE
	Remove the element from the container. More...

size_type __fastcall	erase (const_reference v) noexcept(true) FORCE_INLINE
	Non-atomically remove the element from the container. More...

Public Member Functions inherited from jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >
	BOOST_MPL_ASSERT ((std::is_base_of< typename node_details_t::base_t, typename value_type::value_type >))

__stdcall	stack () noexcept(true) FORCE_INLINE

	stack (stack const &)=delete

	stack (stack &&) noexcept(true) FORCE_INLINE

virtual __stdcall	~stack () noexcept(true) FORCE_INLINE

iterator __fastcall	begin () noexcept(true) FORCE_INLINE

const_iterator __fastcall	begin () const noexcept(true) FORCE_INLINE

iterator __fastcall	end () noexcept(true) FORCE_INLINE

const_iterator __fastcall	end () const noexcept(true) FORCE_INLINE

bool __fastcall	empty () const noexcept(true) FORCE_INLINE
	Return true if the container is empty, false otherwise. More...

size_type __fastcall	size () const noexcept(true) FORCE_INLINE
	Atomically return the number of elements in the container. More...

size_type __fastcall	size_n () const noexcept(true) FORCE_INLINE
	Non-atomically return the number of elements in the container. More...

void __fastcall	erase (iterator v) noexcept(true) FORCE_INLINE
	Remove the element from the container. More...

size_type __fastcall	erase (const_reference v) noexcept(true) FORCE_INLINE
	Non-atomically remove the element from the container. More...

void __fastcall	clear () noexcept(true) FORCE_INLINE
	Remove all of the elements from the container. More...

value_type __fastcall	top () noexcept(true) FORCE_INLINE

value_type __fastcall	top () const noexcept(true) FORCE_INLINE

void __fastcall	push (value_type const &v) noexcept(true) FORCE_INLINE

void __fastcall	push (value_type &&v) noexcept(true) FORCE_INLINE

void __fastcall	push_front (value_type const &v) noexcept(true) FORCE_INLINE

void __fastcall	push_front (value_type &&v) noexcept(true) FORCE_INLINE

void __fastcall	pop () noexcept(true) FORCE_INLINE

void __fastcall	pop_front () noexcept(true) FORCE_INLINE

value_type __fastcall	pop_top_nochk () noexcept(true) FORCE_INLINE

Additional Inherited Members
Static Public Attributes inherited from jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >
static constexpr ppd::generic_traits::memory_access_modes	memory_access_mode

Protected Types inherited from jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >
using	node_details_t = private_::node_details< LkT >

using	atomic_ptr_t = typename node_details_t::base_t::atomic_ptr_t

Protected Member Functions inherited from jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >
node_details_t::base_t::atomic_ptr_t	unlink_node (typename node_details_t::base_t::atomic_ptr_t &node) noexcept(true) FORCE_INLINE

void	insert (value_type v) noexcept(true) FORCE_INLINE

Static Protected Member Functions inherited from jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >
static void	insert (typename node_details_t::base_t::atomic_ptr_t i, value_type v) noexcept(true) FORCE_INLINE

Protected Attributes inherited from jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >
node_details_t	prefront_

size_ctr_t	size_ctr

Detailed Description

template<class V, class LkT>
class jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >

A "good enough for PPD" implementation of a singly-linked, hybrid, intrusive, pointer-based list.

When inserting a node, no memory allocations are required, which is good in a multi-threading environment as it reduces calls to any memory allocator. If you don't like the cut-down interface of this container, blame YAGNI & TDD.

See also: boost::instrusive::slist, boost::slist, std::list

Definition at line 489 of file intrusive.hpp.

Member Typedef Documentation

◆ base_t

template<class V , class LkT >

typedef stack<V, LkT> jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::base_t

Definition at line 491 of file intrusive.hpp.

◆ const_iterator

template<class V , class LkT >

typedef base_t::const_iterator jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::const_iterator

Definition at line 497 of file intrusive.hpp.

◆ const_pointer

template<class V , class LkT >

typedef base_t::const_pointer jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::const_pointer

Definition at line 501 of file intrusive.hpp.

◆ const_reference

template<class V , class LkT >

typedef base_t::const_reference jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::const_reference

Definition at line 502 of file intrusive.hpp.

◆ ctr_type

template<class V , class LkT >

typedef base_t::ctr_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::ctr_type

Definition at line 505 of file intrusive.hpp.

◆ deleter_t

template<class V , class LkT >

typedef base_t::deleter_t jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::deleter_t

Definition at line 504 of file intrusive.hpp.

◆ difference_type

template<class V , class LkT >

typedef base_t::difference_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::difference_type

Definition at line 498 of file intrusive.hpp.

◆ exception_type

template<class V , class LkT >

typedef base_t::exception_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::exception_type

Definition at line 506 of file intrusive.hpp.

◆ iterator

template<class V , class LkT >

typedef base_t::iterator jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::iterator

Definition at line 496 of file intrusive.hpp.

◆ lock_traits

template<class V , class LkT >

typedef base_t::lock_traits jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::lock_traits

Definition at line 493 of file intrusive.hpp.

◆ pointer

template<class V , class LkT >

typedef base_t::pointer jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::pointer

Definition at line 499 of file intrusive.hpp.

◆ reference

template<class V , class LkT >

typedef base_t::reference jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::reference

Definition at line 500 of file intrusive.hpp.

◆ size_ctr_t

template<class V , class LkT >

typedef base_t::size_ctr_t jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::size_ctr_t

Definition at line 494 of file intrusive.hpp.

◆ size_type

template<class V , class LkT >

typedef base_t::size_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::size_type

Definition at line 495 of file intrusive.hpp.

◆ value_type

template<class V , class LkT >

typedef base_t::value_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::value_type

Definition at line 492 of file intrusive.hpp.

Constructor & Destructor Documentation

◆ slist() [1/2]

template<class V , class LkT >

jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::slist

inlinenoexcept

Definition at line 259 of file intrusive_impl.hpp.

◆ slist() [2/2]

template<class V , class LkT >

jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::slist ( slist< V, LkT > && s )

inlinenoexcept

Definition at line 265 of file intrusive_impl.hpp.

◆ ~slist()

template<class V , class LkT >

jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::~slist

inlinenoexcept

Algorithmic complexity: O(n)

Definition at line 329 of file intrusive_impl.hpp.

Member Function Documentation

◆ back() [1/2]

template<class V , class LkT >

slist< V, LkT >::value_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::back

inlinenoexcept

Algorithmic complexity: O(1)

Definition at line 341 of file intrusive_impl.hpp.

◆ back() [2/2]

template<class V , class LkT >

slist< V, LkT >::value_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::back

inlinenoexcept

Algorithmic complexity: O(1)

Definition at line 334 of file intrusive_impl.hpp.

◆ erase() [1/3]

template<class V , class LkT >

stack< V, LkT >::size_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::erase

inlinenoexcept

Non-atomically remove the element from the container.

Algorithmic complexity: O(n).

Parameters

v	The value equivalent to the element to be removed.

Returns: The number of elements erased from the list, at most 1.

Definition at line 402 of file intrusive_impl.hpp.

◆ erase() [2/3]

template<class V , class LkT >

slist< V, LkT >::size_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::erase ( const_reference v )

inlinenoexcept

Remove the element from the container.

Algorithmic complexity: O(n).

Parameters

v	The value equivalent to the element to be removed.

Returns: The number of elements erased from the list, at most 1.

Definition at line 317 of file intrusive_impl.hpp.

◆ erase() [3/3]

template<class V , class LkT >

void jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::erase

inlinenoexcept

Remove the element from the container.

Algorithmic complexity: O(1)

Parameters

v	Iterator to the element to be removed.

Definition at line 394 of file intrusive_impl.hpp.

◆ find() [1/2]

template<class V , class LkT >

slist< V, LkT >::const_iterator jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::find ( const_reference v ) const

inlinenoexcept

Find if the element is within the container.

Algorithmic complexity: O(n).

Parameters

v	The element to be found.

Returns: The iterator to the element within the container, or end() otherwise.

Definition at line 298 of file intrusive_impl.hpp.

◆ find() [2/2]

template<class V , class LkT >

slist< V, LkT >::iterator jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::find ( const_reference v )

inlinenoexcept

Find if the element is within the container.

Algorithmic complexity: O(n).

Parameters

v	The element to be found.

Returns: The iterator to the element within the container, or end() otherwise.

Definition at line 288 of file intrusive_impl.hpp.

◆ front() [1/2]

template<class V , class LkT >

slist< V, LkT >::value_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::front

inlinenoexcept

Algorithmic complexity: O(1)

Returns: The front of the list.

Definition at line 282 of file intrusive_impl.hpp.

◆ front() [2/2]

template<class V , class LkT >

slist< V, LkT >::value_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::front

inlinenoexcept

Algorithmic complexity: O(1)

Definition at line 276 of file intrusive_impl.hpp.

◆ penultimate_reachable_from_prefront()

template<class V , class LkT >

bool jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::penultimate_reachable_from_prefront

inlinenoexcept

Algorithmic complexity: O(n)

Returns: True if the internal iterators are consistent.

Definition at line 409 of file intrusive_impl.hpp.

◆ pop_front()

template<class V , class LkT >

void jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::pop_front

inlinenoexcept

Algorithmic complexity: O(1)

Definition at line 308 of file intrusive_impl.hpp.

◆ push_back() [1/2]

template<class V , class LkT >

void jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::push_back ( value_type && v )

inlinenoexcept

Note that this is NOT atomic! So NOT thread-safe. Algorithmic complexity: O(1)

Parameters

v	The element to be added.

Definition at line 396 of file intrusive_impl.hpp.

◆ push_back() [2/2]

template<class V , class LkT >

void jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::push_back ( value_type const & v )

inlinenoexcept

Note that this is NOT atomic! So NOT thread-safe. Algorithmic complexity: O(1)

Parameters

v	The element to be added.

Definition at line 383 of file intrusive_impl.hpp.

◆ push_front() [1/2]

template<class V , class LkT >

void jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::push_front ( value_type && v )

inlinenoexcept

Algorithmic complexity: O(1)

Parameters

v	The element to be added.

Definition at line 361 of file intrusive_impl.hpp.

◆ push_front() [2/2]

template<class V , class LkT >

void jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::slist< V, LkT >::push_front ( value_type const & v )

inlinenoexcept

Algorithmic complexity: O(1)

Parameters

v	The element to be added.

Definition at line 348 of file intrusive_impl.hpp.

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

core/intrusive.hpp
core/intrusive_impl.hpp

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ base_t

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ ctr_type

◆ deleter_t

◆ difference_type

◆ exception_type

◆ iterator

◆ lock_traits

◆ pointer

◆ reference

◆ size_ctr_t

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ slist() [1/2]

◆ slist() [2/2]

◆ ~slist()

Member Function Documentation

◆ back() [1/2]

◆ back() [2/2]

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ find() [1/2]

◆ find() [2/2]

◆ front() [1/2]

◆ front() [2/2]

◆ penultimate_reachable_from_prefront()

◆ pop_front()

◆ push_back() [1/2]

◆ push_back() [2/2]

◆ push_front() [1/2]

◆ push_front() [2/2]