LLVM 17.0.0git
|
A simple intrusive list implementation. More...
#include "llvm/ADT/simple_ilist.h"
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) |
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).
T
this list should use. This is useful if a type T
is part of multiple, independent lists simultaneously. 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.
using llvm::simple_ilist< T, Options >::const_iterator = ilist_iterator<OptionsT, false, true> |
Definition at line 96 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::const_pointer = typename OptionsT::const_pointer |
Definition at line 93 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::const_reference = typename OptionsT::const_reference |
Definition at line 94 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::const_reverse_iterator = ilist_iterator<OptionsT, true, true> |
Definition at line 98 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::difference_type = ptrdiff_t |
Definition at line 100 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::iterator = ilist_iterator<OptionsT, false, false> |
Definition at line 95 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::pointer = typename OptionsT::pointer |
Definition at line 91 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::reference = typename OptionsT::reference |
Definition at line 92 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::reverse_iterator = ilist_iterator<OptionsT, true, false> |
Definition at line 97 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::size_type = size_t |
Definition at line 99 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::value_type = typename OptionsT::value_type |
Definition at line 90 of file simple_ilist.h.
|
default |
|
default |
|
delete |
|
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.
|
inline |
Definition at line 138 of file simple_ilist.h.
References llvm::simple_ilist< T, Options >::rbegin().
|
inline |
Definition at line 139 of file simple_ilist.h.
References llvm::simple_ilist< T, Options >::rbegin().
|
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().
|
inline |
Definition at line 118 of file simple_ilist.h.
References llvm::Sentinel.
|
inline |
Clear the list; never deletes.
Definition at line 228 of file simple_ilist.h.
References llvm::Sentinel.
Referenced by llvm::simple_ilist< T, Options >::operator=().
|
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().
|
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().
|
inline |
Check if the list is empty in constant time.
Definition at line 131 of file simple_ilist.h.
References llvm::Sentinel.
|
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().
|
inline |
Definition at line 120 of file simple_ilist.h.
References llvm::Sentinel.
|
inline |
Remove a range of nodes; never deletes.
Definition at line 203 of file simple_ilist.h.
References llvm::Last.
|
inline |
Remove a node by iterator; never deletes.
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().
|
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(), and llvm::Last.
|
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().
|
inline |
Definition at line 136 of file simple_ilist.h.
References llvm::simple_ilist< T, Options >::begin().
|
inline |
Definition at line 137 of file simple_ilist.h.
References llvm::simple_ilist< T, Options >::begin().
|
inline |
Insert a range of nodes; never copies.
Definition at line 164 of file simple_ilist.h.
References I, llvm::simple_ilist< T, Options >::insert(), and llvm::Last.
|
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().
|
inline |
Merge in another list.
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().
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.
|
delete |
|
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.
|
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().
|
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().
|
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().
|
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().
|
inline |
Definition at line 121 of file simple_ilist.h.
References llvm::Sentinel.
Referenced by llvm::simple_ilist< T, Options >::back().
|
inline |
Definition at line 122 of file simple_ilist.h.
References llvm::Sentinel.
|
inline |
Remove a node by reference; never deletes.
Definition at line 181 of file simple_ilist.h.
Referenced by llvm::simple_ilist< T, Options >::erase(), and llvm::simple_ilist< T, Options >::removeAndDispose().
|
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().
|
inline |
Definition at line 125 of file simple_ilist.h.
References llvm::Sentinel.
|
inline |
Definition at line 126 of file simple_ilist.h.
References llvm::Sentinel.
|
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().
|
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().
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().
|
inline |
Splice in a range of nodes from another list.
Definition at line 246 of file simple_ilist.h.
References I, and llvm::Last.
|
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().
|
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().
|
inline |
Swap with another list in place using std::swap.
Definition at line 154 of file simple_ilist.h.
References std::swap(), and X.