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

#include <intrusive.hpp>

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

Public Types
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
	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

Static Public Attributes
static constexpr ppd::generic_traits::memory_access_modes	memory_access_mode

Protected Types
using	node_details_t = private_::node_details< LkT >

using	atomic_ptr_t = typename node_details_t::base_t::atomic_ptr_t

Protected Member Functions
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
static void	insert (typename node_details_t::base_t::atomic_ptr_t i, value_type v) noexcept(true) FORCE_INLINE

Protected Attributes
node_details_t	prefront_

size_ctr_t	size_ctr

Detailed Description

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

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

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::stack, std::stack

Definition at line 309 of file intrusive.hpp.

Member Typedef Documentation

◆ atomic_ptr_t

template<class V , class LkT >

using jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::atomic_ptr_t = typename node_details_t::base_t::atomic_ptr_t

protected

Definition at line 312 of file intrusive.hpp.

◆ const_iterator

template<class V , class LkT >

typedef private_::slist_iterator_internal<V const, LkT> jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::const_iterator

Definition at line 320 of file intrusive.hpp.

◆ const_pointer

template<class V , class LkT >

typedef const_iterator::const_pointer jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::const_pointer

Definition at line 324 of file intrusive.hpp.

◆ const_reference

template<class V , class LkT >

typedef const_iterator::const_reference jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::const_reference

Definition at line 325 of file intrusive.hpp.

◆ ctr_type

template<class V , class LkT >

typedef value_type::ctr_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::ctr_type

Definition at line 328 of file intrusive.hpp.

◆ deleter_t

template<class V , class LkT >

typedef value_type::deleter_t jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::deleter_t

Definition at line 327 of file intrusive.hpp.

◆ difference_type

template<class V , class LkT >

typedef iterator::difference_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::difference_type

Definition at line 321 of file intrusive.hpp.

◆ exception_type

template<class V , class LkT >

typedef value_type::exception_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::exception_type

Definition at line 329 of file intrusive.hpp.

◆ iterator

template<class V , class LkT >

typedef private_::slist_iterator_internal<V, LkT> jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::iterator

Definition at line 319 of file intrusive.hpp.

◆ lock_traits

template<class V , class LkT >

using jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::lock_traits = typename node_details_t::lock_traits

Definition at line 315 of file intrusive.hpp.

◆ node_details_t

template<class V , class LkT >

using jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::node_details_t = private_::node_details<LkT>

protected

Definition at line 311 of file intrusive.hpp.

◆ pointer

template<class V , class LkT >

typedef iterator::pointer jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::pointer

Definition at line 322 of file intrusive.hpp.

◆ reference

template<class V , class LkT >

typedef iterator::reference jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::reference

Definition at line 323 of file intrusive.hpp.

◆ size_ctr_t

template<class V , class LkT >

typedef lock_traits::template atomic_counter_type<unsigned long> jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::size_ctr_t

Definition at line 318 of file intrusive.hpp.

◆ size_type

template<class V , class LkT >

typedef std::size_t jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::size_type

Definition at line 316 of file intrusive.hpp.

◆ value_type

template<class V , class LkT >

typedef shared_ptr<V, LkT> jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::value_type

Definition at line 317 of file intrusive.hpp.

Constructor & Destructor Documentation

◆ stack() [1/3]

template<class V , class LkT >

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

inlinenoexcept

Definition at line 46 of file intrusive_impl.hpp.

References jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::prefront_, and jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::size_ctr.

◆ stack() [2/3]

template<class V , class LkT >

jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::stack ( stack< V, LkT > const & )

delete

◆ stack() [3/3]

template<class V , class LkT >

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

inlinenoexcept

Definition at line 55 of file intrusive_impl.hpp.

References jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::prefront_, and jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::size_ctr.

◆ ~stack()

template<class V , class LkT >

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

inlinevirtualnoexcept

Algorithmic complexity: O(n)

Definition at line 176 of file intrusive_impl.hpp.

Member Function Documentation

◆ begin() [1/2]

template<class V , class LkT >

stack< V, LkT >::const_iterator jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::begin

inlinenoexcept

Algorithmic complexity: O(1)

Definition at line 85 of file intrusive_impl.hpp.

References jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::prefront_.

◆ begin() [2/2]

template<class V , class LkT >

stack< V, LkT >::iterator jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::begin

inlinenoexcept

Algorithmic complexity: O(1)

Definition at line 79 of file intrusive_impl.hpp.

References jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::prefront_.

◆ BOOST_MPL_ASSERT()

template<class V , class LkT >

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 >) )

◆ clear()

template<class V , class LkT >

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

inlinenoexcept

Remove all of the elements from the container.

Calls the dtor for each element within the container. Algorithmic complexity: O(n)

Definition at line 167 of file intrusive_impl.hpp.

◆ empty()

template<class V , class LkT >

bool jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::empty

inlinenoexcept

Return true if the container is empty, false otherwise.

Algorithmic complexity: O(1)

Returns: True if the container is empty, false otherwise.

Definition at line 23 of file intrusive_impl.hpp.

References jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::size_ctr.

◆ end() [1/2]

template<class V , class LkT >

stack< V, LkT >::const_iterator jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::end

inlinenoexcept

Algorithmic complexity: O(1)

Definition at line 97 of file intrusive_impl.hpp.

◆ end() [2/2]

template<class V , class LkT >

stack< V, LkT >::iterator jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::end

inlinenoexcept

Algorithmic complexity: O(1)

Definition at line 91 of file intrusive_impl.hpp.

◆ erase() [1/2]

template<class V , class LkT >

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

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 146 of file intrusive_impl.hpp.

◆ erase() [2/2]

template<class V , class LkT >

void jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::erase ( iterator v )

inlinenoexcept

Remove the element from the container.

Algorithmic complexity: O(1)

Parameters

v	Iterator to the element to be removed.

Definition at line 129 of file intrusive_impl.hpp.

References jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::size_ctr, and jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::unlink_node().

◆ insert() [1/2]

template<class V , class LkT >

void jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::insert	(	typename node_details_t::base_t::atomic_ptr_t	i,
		value_type	v
	)

inlinestaticprotectednoexcept

Algorithmic complexity: O(1)

Parameters

i	The iterator immediately after which the element should be added.
v	The element to be added.

See also: push()

Definition at line 182 of file intrusive_impl.hpp.

◆ insert() [2/2]

template<class V , class LkT >

void jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::insert ( value_type v )

inlineprotectednoexcept

Definition at line 202 of file intrusive_impl.hpp.

References jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::prefront_, and jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::size_ctr.

◆ pop()

template<class V , class LkT >

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

inlinenoexcept

Algorithmic complexity: O(1)

Definition at line 111 of file intrusive_impl.hpp.

References jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::prefront_, and jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::unlink_node().

◆ pop_front()

template<class V , class LkT >

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

inlinenoexcept

Algorithmic complexity: O(1)

Definition at line 161 of file intrusive_impl.hpp.

◆ pop_top_nochk()

template<class V , class LkT >

stack< V, LkT >::value_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::pop_top_nochk

inlinenoexcept

Algorithmic complexity: O(1) This method assumes that only one thread is popping at a time, and that the container is not empty.

Definition at line 246 of file intrusive_impl.hpp.

References jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::prefront_, and jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::unlink_node().

◆ push() [1/2]

template<class V , class LkT >

void jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::push ( value_type && v )

inlinenoexcept

Algorithmic complexity: O(1)

Parameters

v	The element to be added.

Definition at line 228 of file intrusive_impl.hpp.

◆ push() [2/2]

template<class V , class LkT >

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

inlinenoexcept

Algorithmic complexity: O(1)

Parameters

v	The element to be added.

Definition at line 222 of file intrusive_impl.hpp.

◆ push_front() [1/2]

template<class V , class LkT >

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

inlinenoexcept

Algorithmic complexity: O(1)

Parameters

v	The element to be added.

Definition at line 240 of file intrusive_impl.hpp.

◆ push_front() [2/2]

template<class V , class LkT >

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

inlinenoexcept

Algorithmic complexity: O(1)

Parameters

v	The element to be added.

Definition at line 234 of file intrusive_impl.hpp.

◆ size()

template<class V , class LkT >

stack< V, LkT >::size_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::size ( void ) const

inlinenoexcept

Atomically return the number of elements in the container.

Algorithmic complexity: O(1)

Returns: The number of elements in the container.

Definition at line 30 of file intrusive_impl.hpp.

References jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::size_ctr.

◆ size_n()

template<class V , class LkT >

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

inlinenoexcept

Non-atomically return the number of elements in the container.

Algorithmic complexity: O(n) Mainly used for verifying list integrity in testing. Not much use for anything else.

Returns: The number of elements in the container.

Definition at line 36 of file intrusive_impl.hpp.

◆ top() [1/2]

template<class V , class LkT >

stack< V, LkT >::value_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::top

inlinenoexcept

Algorithmic complexity: O(1)

Returns: The top of the stack.

Definition at line 71 of file intrusive_impl.hpp.

References jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::prefront_.

◆ top() [2/2]

template<class V , class LkT >

stack< V, LkT >::value_type jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::top

inlinenoexcept

Algorithmic complexity: O(1)

Returns: The top of the stack.

Definition at line 63 of file intrusive_impl.hpp.

References jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::prefront_.

◆ unlink_node()

template<class V , class LkT >

stack< V, LkT >::node_details_t::base_t::atomic_ptr_t jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::unlink_node ( typename node_details_t::base_t::atomic_ptr_t & node )

inlineprotectednoexcept

Definition at line 103 of file intrusive_impl.hpp.

Referenced by jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::erase(), jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::pop(), and jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::pop_top_nochk().

Member Data Documentation

◆ memory_access_mode

template<class V , class LkT >

constexpr ppd::generic_traits::memory_access_modes jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::memory_access_mode

staticconstexpr

Initial value:

=(
         atomic_ptr_t::memory_access_mode==ppd::generic_traits::memory_access_modes::crew_memory_access
         && size_ctr_t::memory_access_mode==ppd::generic_traits::memory_access_modes::crew_memory_access
         ? ppd::generic_traits::memory_access_modes::crew_memory_access
         : ppd::generic_traits::memory_access_modes::erew_memory_access
      )

To assist in allowing compile-time computation of the algorithmic order of the threading model.

Definition at line 333 of file intrusive.hpp.

◆ prefront_

template<class V , class LkT >

node_details_t jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::prefront_

mutableprotected

Definition at line 460 of file intrusive.hpp.

Referenced by jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::begin(), jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::insert(), jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::pop(), jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::pop_top_nochk(), jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::stack(), and jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::top().

◆ size_ctr

template<class V , class LkT >

size_ctr_t jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::size_ctr

protected

Definition at line 461 of file intrusive.hpp.

Referenced by jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::empty(), jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::erase(), jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::insert(), jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::size(), and jmmcg::LIBJMMCG_VER_NAMESPACE::intrusive::stack< V, LkT >::stack().

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

core/intrusive.hpp
core/intrusive_impl.hpp

Public Types

Public Member Functions

Static Public Attributes

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ atomic_ptr_t

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ ctr_type

◆ deleter_t

◆ difference_type

◆ exception_type

◆ iterator

◆ lock_traits

◆ node_details_t

◆ pointer

◆ reference

◆ size_ctr_t

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ stack() [1/3]

◆ stack() [2/3]

◆ stack() [3/3]

◆ ~stack()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ BOOST_MPL_ASSERT()

◆ clear()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ insert() [1/2]

◆ insert() [2/2]

◆ pop()

◆ pop_front()

◆ pop_top_nochk()

◆ push() [1/2]

◆ push() [2/2]

◆ push_front() [1/2]

◆ push_front() [2/2]

◆ size()

◆ size_n()

◆ top() [1/2]

◆ top() [2/2]

◆ unlink_node()

Member Data Documentation

◆ memory_access_mode

◆ prefront_

◆ size_ctr