A simple intrusive list implementation. More...

#include "llvm/ADT/simple_ilist.h"

Inheritance diagram for llvm::simple_ilist< T, Options >:

[legend]

Public Types
using	value_type = typename OptionsT::value_type

using	pointer = typename OptionsT::pointer

using	reference = typename OptionsT::reference

using	const_pointer = typename OptionsT::const_pointer

using	const_reference = typename OptionsT::const_reference

using	iterator = ilist_iterator< OptionsT, false, false >

using	const_iterator = ilist_iterator< OptionsT, false, true >

using	reverse_iterator = ilist_iterator< OptionsT, true, false >

using	const_reverse_iterator = ilist_iterator< OptionsT, true, true >

using	size_type = size_t

using	difference_type = ptrdiff_t

Public Member Functions
	simple_ilist ()=default

	~simple_ilist ()=default

	simple_ilist (const simple_ilist &)=delete

simple_ilist &	operator= (const simple_ilist &)=delete

	simple_ilist (simple_ilist &&X)

simple_ilist &	operator= (simple_ilist &&X)

iterator	begin ()

const_iterator	begin () const

iterator	end ()

const_iterator	end () const

reverse_iterator	rbegin ()

const_reverse_iterator	rbegin () const

reverse_iterator	rend ()

const_reverse_iterator	rend () const

bool	empty () const
	Check if the list is empty in constant time.

size_type	size () const
	Calculate the size of the list in linear time.

reference	front ()

const_reference	front () const

reference	back ()

const_reference	back () const

void	push_front (reference Node)
	Insert a node at the front; never copies.

void	push_back (reference Node)
	Insert a node at the back; never copies.

void	pop_front ()
	Remove the node at the front; never deletes.

void	pop_back ()
	Remove the node at the back; never deletes.

void	swap (simple_ilist &X)
	Swap with another list in place using std::swap.

iterator	insert (iterator I, reference Node)
	Insert a node by reference; never copies.

template<class Iterator >
void	insert (iterator I, Iterator First, Iterator Last)
	Insert a range of nodes; never copies.

template<class Cloner , class Disposer >
void	cloneFrom (const simple_ilist &L2, Cloner clone, Disposer dispose)
	Clone another list.

void	remove (reference N)
	Remove a node by reference; never deletes.

template<class Disposer >
void	removeAndDispose (reference N, Disposer dispose)
	Remove a node by reference and dispose of it.

iterator	erase (iterator I)
	Remove a node by iterator; never deletes.

iterator	erase (iterator First, iterator Last)
	Remove a range of nodes; never deletes.

template<class Disposer >
iterator	eraseAndDispose (iterator I, Disposer dispose)
	Remove a node by iterator and dispose of it.

template<class Disposer >
iterator	eraseAndDispose (iterator First, iterator Last, Disposer dispose)
	Remove a range of nodes and dispose of them.

void	clear ()
	Clear the list; never deletes.

template<class Disposer >
void	clearAndDispose (Disposer dispose)
	Clear the list and dispose of the nodes.

void	splice (iterator I, simple_ilist &L2)
	Splice in another list.

void	splice (iterator I, simple_ilist &L2, iterator Node)
	Splice in a node from another list.

void	splice (iterator I, simple_ilist &, iterator First, iterator Last)
	Splice in a range of nodes from another list.


void	merge (simple_ilist &RHS)
	Merge in another list.

template<class Compare >
void	merge (simple_ilist &RHS, Compare comp)


void	sort ()
	Sort the list.

template<class Compare >
void	sort (Compare comp)

Detailed Description

template<typename T, class... Options>
class llvm::simple_ilist< T, Options >

A simple intrusive list implementation.

This is a simple intrusive list for a T that inherits from ilist_node<T>. The list never takes ownership of anything inserted in it.

Unlike iplist<T> and ilist<T>, simple_ilist<T> never deletes values, and has no callback traits.

The API for adding nodes include push_front(), push_back(), and insert(). These all take values by reference (not by pointer), except for the range version of insert().

There are three sets of API for discarding nodes from the list: remove(), which takes a reference to the node to remove, erase(), which takes an iterator or iterator range and returns the next one, and clear(), which empties out the container. All three are constant time operations. None of these deletes any nodes; in particular, if there is a single node in the list, then these have identical semantics:

L.remove(L.front());
L.erase(L.begin());
L.clear();

As a convenience for callers, there are parallel APIs that take a Disposer (such as std::default_delete<T>): removeAndDispose(), eraseAndDispose(), and clearAndDispose(). These have different names because the extra semantic is otherwise non-obvious. They are equivalent to calling std::for_each() on the range to be discarded.

The currently available Options customize the nodes in the list. The same options must be specified in the ilist_node instantiation for compatibility (although the order is irrelevant).

Use ilist_tag to designate which ilist_node for a given T this list should use. This is useful if a type T is part of multiple, independent lists simultaneously.
Use ilist_sentinel_tracking to always (or never) track whether a node is a sentinel. Specifying true enables the ilist_node::isSentinel() API. Unlike ilist_node::isKnownSentinel(), which is only appropriate for assertions, ilist_node::isSentinel() is appropriate for real logic.

Here are examples of Options usage:

simple_ilist<T> gives the defaults.
simple_ilist<T,ilist_sentinel_tracking<true>> enables the ilist_node::isSentinel() API.
simple_ilist<T,ilist_tag,ilist_sentinel_tracking<false>> specifies a tag of A and that tracking should be off (even when LLVM_ENABLE_ABI_BREAKING_CHECKS are enabled).
simple_ilist<T,ilist_sentinel_tracking<false>,ilist_tag> is equivalent to the last.

See is_valid_option for steps on adding a new option.

Definition at line 78 of file simple_ilist.h.

Member Typedef Documentation

◆ const_iterator

template<typename T , class... Options>

using llvm::simple_ilist< T, Options >::const_iterator = ilist_iterator<OptionsT, false, true>

Definition at line 96 of file simple_ilist.h.

◆ const_pointer

template<typename T , class... Options>

using llvm::simple_ilist< T, Options >::const_pointer = typename OptionsT::const_pointer

Definition at line 93 of file simple_ilist.h.

◆ const_reference

template<typename T , class... Options>

using llvm::simple_ilist< T, Options >::const_reference = typename OptionsT::const_reference

Definition at line 94 of file simple_ilist.h.

◆ const_reverse_iterator

template<typename T , class... Options>

using llvm::simple_ilist< T, Options >::const_reverse_iterator = ilist_iterator<OptionsT, true, true>

Definition at line 98 of file simple_ilist.h.

◆ difference_type

template<typename T , class... Options>

using llvm::simple_ilist< T, Options >::difference_type = ptrdiff_t

Definition at line 100 of file simple_ilist.h.

◆ iterator

template<typename T , class... Options>

using llvm::simple_ilist< T, Options >::iterator = ilist_iterator<OptionsT, false, false>

Definition at line 95 of file simple_ilist.h.

◆ pointer

template<typename T , class... Options>

using llvm::simple_ilist< T, Options >::pointer = typename OptionsT::pointer

Definition at line 91 of file simple_ilist.h.

◆ reference

template<typename T , class... Options>

using llvm::simple_ilist< T, Options >::reference = typename OptionsT::reference

Definition at line 92 of file simple_ilist.h.

◆ reverse_iterator

template<typename T , class... Options>

using llvm::simple_ilist< T, Options >::reverse_iterator = ilist_iterator<OptionsT, true, false>

Definition at line 97 of file simple_ilist.h.

◆ size_type

template<typename T , class... Options>

using llvm::simple_ilist< T, Options >::size_type = size_t

Definition at line 99 of file simple_ilist.h.

◆ value_type

template<typename T , class... Options>

using llvm::simple_ilist< T, Options >::value_type = typename OptionsT::value_type

Definition at line 90 of file simple_ilist.h.

Constructor & Destructor Documentation

◆ simple_ilist() [1/3]

template<typename T , class... Options>

llvm::simple_ilist< T, Options >::simple_ilist ( )

default

◆ ~simple_ilist()

template<typename T , class... Options>

llvm::simple_ilist< T, Options >::~simple_ilist ( )

default

◆ simple_ilist() [2/3]

template<typename T , class... Options>

llvm::simple_ilist< T, Options >::simple_ilist ( const simple_ilist< T, Options > & )

delete

◆ simple_ilist() [3/3]

template<typename T , class... Options>

llvm::simple_ilist< T, Options >::simple_ilist ( simple_ilist< T, Options > && X )

inline

Definition at line 110 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::end(), llvm::simple_ilist< T, Options >::splice(), and X.

Member Function Documentation

◆ back() [1/2]

template<typename T , class... Options>

reference llvm::simple_ilist< T, Options >::back ( )

inline

Definition at line 138 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::rbegin().

◆ back() [2/2]

template<typename T , class... Options>

const_reference llvm::simple_ilist< T, Options >::back ( ) const

inline

Definition at line 139 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::rbegin().

◆ begin() [1/2]

template<typename T , class... Options>

iterator llvm::simple_ilist< T, Options >::begin ( )

inline

Definition at line 117 of file simple_ilist.h.

References llvm::Sentinel.

Referenced by llvm::simple_ilist< T, Options >::clearAndDispose(), llvm::simple_ilist< T, Options >::front(), getNewDefiningAccessForClone(), llvm::MemorySSAUpdater::insertDef(), llvm::simple_ilist< T, Options >::pop_front(), llvm::simple_ilist< T, Options >::push_front(), llvm::simple_ilist< T, Options >::size(), and llvm::simple_ilist< T, Options >::splice().

◆ begin() [2/2]

template<typename T , class... Options>

const_iterator llvm::simple_ilist< T, Options >::begin ( ) const

inline

Definition at line 118 of file simple_ilist.h.

References llvm::Sentinel.

◆ clear()

template<typename T , class... Options>

void llvm::simple_ilist< T, Options >::clear ( )

inline

Clear the list; never deletes.

See also: clearAndDispose() if the nodes should be deleted.

Definition at line 228 of file simple_ilist.h.

References llvm::Sentinel.

Referenced by llvm::simple_ilist< T, Options >::operator=().

◆ clearAndDispose()

template<typename T , class... Options>

template<class Disposer >

void llvm::simple_ilist< T, Options >::clearAndDispose ( Disposer dispose )

inline

Clear the list and dispose of the nodes.

Definition at line 231 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::begin(), llvm::simple_ilist< T, Options >::end(), and llvm::simple_ilist< T, Options >::eraseAndDispose().

Referenced by llvm::simple_ilist< T, Options >::cloneFrom().

◆ cloneFrom()

template<typename T , class... Options>

template<class Cloner , class Disposer >

void llvm::simple_ilist< T, Options >::cloneFrom	(	const simple_ilist< T, Options > &	L2,
		Cloner	clone,
		Disposer	dispose
	)

inline

Clone another list.

Definition at line 171 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::clearAndDispose(), and llvm::simple_ilist< T, Options >::push_back().

◆ empty()

template<typename T , class... Options>

bool llvm::simple_ilist< T, Options >::empty ( ) const

inline

Check if the list is empty in constant time.

Definition at line 131 of file simple_ilist.h.

References llvm::Sentinel.

◆ end() [1/2]

template<typename T , class... Options>

iterator llvm::simple_ilist< T, Options >::end ( )

inline

Definition at line 119 of file simple_ilist.h.

References llvm::Sentinel.

Referenced by llvm::simple_ilist< T, Options >::clearAndDispose(), llvm::simple_ilist< T, Options >::erase(), llvm::MemorySSA::getWritableBlockDefs(), llvm::simple_ilist< T, Options >::operator=(), llvm::simple_ilist< T, Options >::pop_back(), llvm::simple_ilist< T, Options >::push_back(), llvm::simple_ilist< T, Options >::simple_ilist(), llvm::simple_ilist< T, Options >::size(), and llvm::simple_ilist< T, Options >::splice().

◆ end() [2/2]

template<typename T , class... Options>

const_iterator llvm::simple_ilist< T, Options >::end ( ) const

inline

Definition at line 120 of file simple_ilist.h.

References llvm::Sentinel.

◆ erase() [1/2]

template<typename T , class... Options>

iterator llvm::simple_ilist< T, Options >::erase	(	iterator	First,
		iterator	Last
	)

inline

Remove a range of nodes; never deletes.

See also: eraseAndDispose() if the nodes should be deleted.

Definition at line 203 of file simple_ilist.h.

References llvm::First, and llvm::Last.

◆ erase() [2/2]

template<typename T , class... Options>

iterator llvm::simple_ilist< T, Options >::erase ( iterator I )

inline

Remove a node by iterator; never deletes.

See also: remove() for removing by reference.; eraseAndDispose() it the node should be deleted.

Definition at line 194 of file simple_ilist.h.

References assert(), llvm::simple_ilist< T, Options >::end(), I, and llvm::simple_ilist< T, Options >::remove().

Referenced by llvm::simple_ilist< T, Options >::eraseAndDispose(), llvm::simple_ilist< T, Options >::pop_back(), and llvm::simple_ilist< T, Options >::pop_front().

◆ eraseAndDispose() [1/2]

template<typename T , class... Options>

template<class Disposer >

iterator llvm::simple_ilist< T, Options >::eraseAndDispose	(	iterator	First,
		iterator	Last,
		Disposer	dispose
	)

inline

Remove a range of nodes and dispose of them.

Definition at line 219 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::eraseAndDispose(), llvm::First, and llvm::Last.

◆ eraseAndDispose() [2/2]

template<typename T , class... Options>

template<class Disposer >

iterator llvm::simple_ilist< T, Options >::eraseAndDispose	(	iterator	I,
		Disposer	dispose
	)

inline

Remove a node by iterator and dispose of it.

Definition at line 210 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::erase(), and I.

Referenced by llvm::simple_ilist< T, Options >::clearAndDispose(), and llvm::simple_ilist< T, Options >::eraseAndDispose().

◆ front() [1/2]

template<typename T , class... Options>

reference llvm::simple_ilist< T, Options >::front ( )

inline

Definition at line 136 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::begin().

◆ front() [2/2]

template<typename T , class... Options>

const_reference llvm::simple_ilist< T, Options >::front ( ) const

inline

Definition at line 137 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::begin().

◆ insert() [1/2]

template<typename T , class... Options>

template<class Iterator >

void llvm::simple_ilist< T, Options >::insert	(	iterator	I,
		Iterator	First,
		Iterator	Last
	)

inline

Insert a range of nodes; never copies.

Definition at line 164 of file simple_ilist.h.

References llvm::First, I, llvm::simple_ilist< T, Options >::insert(), and llvm::Last.

◆ insert() [2/2]

template<typename T , class... Options>

iterator llvm::simple_ilist< T, Options >::insert	(	iterator	I,
		reference	Node
	)

inline

Insert a node by reference; never copies.

Definition at line 157 of file simple_ilist.h.

References I.

Referenced by llvm::simple_ilist< T, Options >::insert(), llvm::simple_ilist< T, Options >::push_back(), and llvm::simple_ilist< T, Options >::push_front().

◆ merge() [1/2]

template<typename T , class... Options>

void llvm::simple_ilist< T, Options >::merge ( simple_ilist< T, Options > & RHS )

inline

Merge in another list.

Precondition: this and RHS are sorted.

Definition at line 255 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::merge(), and RHS.

Referenced by llvm::simple_ilist< T, Options >::merge().

◆ merge() [2/2]

template<class T , class... Options>

template<class Compare >

void llvm::simple_ilist< T, Options >::merge	(	simple_ilist< T, Options > &	RHS,
		Compare	comp
	)

Definition at line 268 of file simple_ilist.h.

References RHS.

◆ operator=() [1/2]

template<typename T , class... Options>

simple_ilist & llvm::simple_ilist< T, Options >::operator= ( const simple_ilist< T, Options > & )

delete

◆ operator=() [2/2]

template<typename T , class... Options>

simple_ilist & llvm::simple_ilist< T, Options >::operator= ( simple_ilist< T, Options > && X )

inline

Definition at line 111 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::clear(), llvm::simple_ilist< T, Options >::end(), llvm::simple_ilist< T, Options >::splice(), and X.

◆ pop_back()

template<typename T , class... Options>

void llvm::simple_ilist< T, Options >::pop_back ( )

inline

Remove the node at the back; never deletes.

Definition at line 151 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::end(), and llvm::simple_ilist< T, Options >::erase().

◆ pop_front()

template<typename T , class... Options>

void llvm::simple_ilist< T, Options >::pop_front ( )

inline

Remove the node at the front; never deletes.

Definition at line 148 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::begin(), and llvm::simple_ilist< T, Options >::erase().

◆ push_back()

template<typename T , class... Options>

void llvm::simple_ilist< T, Options >::push_back ( reference Node )

inline

Insert a node at the back; never copies.

Definition at line 145 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::end(), and llvm::simple_ilist< T, Options >::insert().

Referenced by llvm::simple_ilist< T, Options >::cloneFrom(), and llvm::IRSimilarity::IRInstructionMapper::convertToUnsignedVec().

◆ push_front()

template<typename T , class... Options>

void llvm::simple_ilist< T, Options >::push_front ( reference Node )

inline

Insert a node at the front; never copies.

Definition at line 142 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::begin(), and llvm::simple_ilist< T, Options >::insert().

◆ rbegin() [1/2]

template<typename T , class... Options>

reverse_iterator llvm::simple_ilist< T, Options >::rbegin ( )

inline

Definition at line 121 of file simple_ilist.h.

References llvm::Sentinel.

Referenced by llvm::simple_ilist< T, Options >::back().

◆ rbegin() [2/2]

template<typename T , class... Options>

const_reverse_iterator llvm::simple_ilist< T, Options >::rbegin ( ) const

inline

Definition at line 122 of file simple_ilist.h.

References llvm::Sentinel.

◆ remove()

template<typename T , class... Options>

void llvm::simple_ilist< T, Options >::remove ( reference N )

inline

Remove a node by reference; never deletes.

See also: erase() for removing by iterator.; removeAndDispose() if the node should be deleted.

Definition at line 181 of file simple_ilist.h.

References llvm::ilist_detail::SpecificNodeAccess< ilist_detail::compute_node_options< T, Options... >::type >::getNodePtr().

Referenced by llvm::simple_ilist< T, Options >::erase(), and llvm::simple_ilist< T, Options >::removeAndDispose().

◆ removeAndDispose()

template<typename T , class... Options>

template<class Disposer >

void llvm::simple_ilist< T, Options >::removeAndDispose	(	reference	N,
		Disposer	dispose
	)

inline

Remove a node by reference and dispose of it.

Definition at line 185 of file simple_ilist.h.

References N, and llvm::simple_ilist< T, Options >::remove().

◆ rend() [1/2]

template<typename T , class... Options>

reverse_iterator llvm::simple_ilist< T, Options >::rend ( )

inline

Definition at line 125 of file simple_ilist.h.

References llvm::Sentinel.

◆ rend() [2/2]

template<typename T , class... Options>

const_reverse_iterator llvm::simple_ilist< T, Options >::rend ( ) const

inline

Definition at line 126 of file simple_ilist.h.

References llvm::Sentinel.

◆ size()

template<typename T , class... Options>

size_type llvm::simple_ilist< T, Options >::size ( ) const

inline

Calculate the size of the list in linear time.

Definition at line 134 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::begin(), and llvm::simple_ilist< T, Options >::end().

◆ sort() [1/2]

template<typename T , class... Options>

void llvm::simple_ilist< T, Options >::sort ( )

inline

Sort the list.

Definition at line 261 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::sort().

Referenced by llvm::simple_ilist< T, Options >::sort().

◆ sort() [2/2]

template<class T , class... Options>

template<class Compare >

void llvm::simple_ilist< T, Options >::sort ( Compare comp )

Definition at line 290 of file simple_ilist.h.

References llvm::Center, End, merge(), RHS, and llvm::sort().

◆ splice() [1/3]

template<typename T , class... Options>

void llvm::simple_ilist< T, Options >::splice	(	iterator	I,
		simple_ilist< T, Options > &	,
		iterator	First,
		iterator	Last
	)

inline

Splice in a range of nodes from another list.

Definition at line 246 of file simple_ilist.h.

References llvm::First, I, and llvm::Last.

◆ splice() [2/3]

template<typename T , class... Options>

void llvm::simple_ilist< T, Options >::splice	(	iterator	I,
		simple_ilist< T, Options > &	L2
	)

inline

Splice in another list.

Definition at line 236 of file simple_ilist.h.

References llvm::simple_ilist< T, Options >::begin(), llvm::simple_ilist< T, Options >::end(), I, and llvm::simple_ilist< T, Options >::splice().

Referenced by llvm::simple_ilist< T, Options >::operator=(), llvm::simple_ilist< T, Options >::simple_ilist(), and llvm::simple_ilist< T, Options >::splice().

◆ splice() [3/3]

template<typename T , class... Options>

void llvm::simple_ilist< T, Options >::splice	(	iterator	I,
		simple_ilist< T, Options > &	L2,
		iterator	Node
	)

inline

Splice in a node from another list.

Definition at line 241 of file simple_ilist.h.

References I, and llvm::simple_ilist< T, Options >::splice().

◆ swap()

template<typename T , class... Options>

void llvm::simple_ilist< T, Options >::swap ( simple_ilist< T, Options > & X )

inline

Swap with another list in place using std::swap.

Definition at line 154 of file simple_ilist.h.

References std::swap(), and X.

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

include/llvm/ADT/simple_ilist.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ const_reverse_iterator

◆ difference_type

◆ iterator

◆ pointer

◆ reference

◆ reverse_iterator

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ simple_ilist() [1/3]

◆ ~simple_ilist()

◆ simple_ilist() [2/3]

◆ simple_ilist() [3/3]

Member Function Documentation

◆ back() [1/2]

◆ back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ clear()

◆ clearAndDispose()

◆ cloneFrom()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ eraseAndDispose() [1/2]

◆ eraseAndDispose() [2/2]

◆ front() [1/2]

◆ front() [2/2]

◆ insert() [1/2]

◆ insert() [2/2]

◆ merge() [1/2]

◆ merge() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ pop_back()

◆ pop_front()

◆ push_back()

◆ push_front()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ remove()

◆ removeAndDispose()

◆ rend() [1/2]

◆ rend() [2/2]

◆ size()

◆ sort() [1/2]

◆ sort() [2/2]

◆ splice() [1/3]

◆ splice() [2/3]

◆ splice() [3/3]

◆ swap()