LLVM
15.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 |
LLVM_NODISCARD bool | empty () const |
Check if the list is empty in constant time. More... | |
LLVM_NODISCARD size_type | size () const |
Calculate the size of the list in linear time. More... | |
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. More... | |
void | push_back (reference Node) |
Insert a node at the back; never copies. More... | |
void | pop_front () |
Remove the node at the front; never deletes. More... | |
void | pop_back () |
Remove the node at the back; never deletes. More... | |
void | swap (simple_ilist &X) |
Swap with another list in place using std::swap. More... | |
iterator | insert (iterator I, reference Node) |
Insert a node by reference; never copies. More... | |
template<class Iterator > | |
void | insert (iterator I, Iterator First, Iterator Last) |
Insert a range of nodes; never copies. More... | |
template<class Cloner , class Disposer > | |
void | cloneFrom (const simple_ilist &L2, Cloner clone, Disposer dispose) |
Clone another list. More... | |
void | remove (reference N) |
Remove a node by reference; never deletes. More... | |
template<class Disposer > | |
void | removeAndDispose (reference N, Disposer dispose) |
Remove a node by reference and dispose of it. More... | |
iterator | erase (iterator I) |
Remove a node by iterator; never deletes. More... | |
iterator | erase (iterator First, iterator Last) |
Remove a range of nodes; never deletes. More... | |
template<class Disposer > | |
iterator | eraseAndDispose (iterator I, Disposer dispose) |
Remove a node by iterator and dispose of it. More... | |
template<class Disposer > | |
iterator | eraseAndDispose (iterator First, iterator Last, Disposer dispose) |
Remove a range of nodes and dispose of them. More... | |
void | clear () |
Clear the list; never deletes. More... | |
template<class Disposer > | |
void | clearAndDispose (Disposer dispose) |
Clear the list and dispose of the nodes. More... | |
void | splice (iterator I, simple_ilist &L2) |
Splice in another list. More... | |
void | splice (iterator I, simple_ilist &L2, iterator Node) |
Splice in a node from another list. More... | |
void | splice (iterator I, simple_ilist &, iterator First, iterator Last) |
Splice in a range of nodes from another list. More... | |
void | merge (simple_ilist &RHS) |
Merge in another list. More... | |
template<class Compare > | |
void | merge (simple_ilist &RHS, Compare comp) |
void | sort () |
Sort the list. More... | |
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.
|
inline |
Definition at line 140 of file simple_ilist.h.
|
inline |
Definition at line 141 of file simple_ilist.h.
|
inline |
Definition at line 117 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::clearAndDispose(), llvm::simple_ilist< MachineInstr, Options... >::front(), getNewDefiningAccessForClone(), llvm::MemorySSAUpdater::insertDef(), llvm::simple_ilist< MachineInstr, Options... >::pop_front(), llvm::simple_ilist< MachineInstr, Options... >::push_front(), and llvm::simple_ilist< MachineInstr, Options... >::size().
|
inline |
Definition at line 118 of file simple_ilist.h.
|
inline |
Clear the list; never deletes.
Definition at line 230 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::operator=().
|
inline |
Clear the list and dispose of the nodes.
Definition at line 233 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::cloneFrom().
|
inline |
Clone another list.
Definition at line 173 of file simple_ilist.h.
|
inline |
Check if the list is empty in constant time.
Definition at line 131 of file simple_ilist.h.
|
inline |
Definition at line 119 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::clearAndDispose(), llvm::simple_ilist< MachineInstr, Options... >::erase(), llvm::MemorySSA::getWritableBlockDefs(), llvm::simple_ilist< MachineInstr, Options... >::operator=(), llvm::simple_ilist< MachineInstr, Options... >::pop_back(), llvm::simple_ilist< MachineInstr, Options... >::push_back(), llvm::simple_ilist< MachineInstr, Options... >::simple_ilist(), and llvm::simple_ilist< MachineInstr, Options... >::size().
|
inline |
Definition at line 120 of file simple_ilist.h.
|
inline |
Remove a range of nodes; never deletes.
Definition at line 205 of file simple_ilist.h.
|
inline |
Remove a node by iterator; never deletes.
Definition at line 196 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::eraseAndDispose(), llvm::simple_ilist< MachineInstr, Options... >::pop_back(), and llvm::simple_ilist< MachineInstr, Options... >::pop_front().
|
inline |
Remove a range of nodes and dispose of them.
Definition at line 221 of file simple_ilist.h.
|
inline |
Remove a node by iterator and dispose of it.
Definition at line 212 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::clearAndDispose(), and llvm::simple_ilist< MachineInstr, Options... >::eraseAndDispose().
|
inline |
Definition at line 138 of file simple_ilist.h.
|
inline |
Definition at line 139 of file simple_ilist.h.
|
inline |
Insert a range of nodes; never copies.
Definition at line 166 of file simple_ilist.h.
|
inline |
Insert a node by reference; never copies.
Definition at line 159 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::insert(), llvm::simple_ilist< MachineInstr, Options... >::push_back(), and llvm::simple_ilist< MachineInstr, Options... >::push_front().
|
inline |
Merge in another list.
this
and RHS
are sorted. Definition at line 257 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::merge().
void llvm::simple_ilist< T, Options >::merge | ( | simple_ilist< T, Options > & | RHS, |
Compare | comp | ||
) |
Definition at line 270 of file simple_ilist.h.
|
delete |
|
inline |
Definition at line 111 of file simple_ilist.h.
|
inline |
Remove the node at the back; never deletes.
Definition at line 153 of file simple_ilist.h.
|
inline |
Remove the node at the front; never deletes.
Definition at line 150 of file simple_ilist.h.
|
inline |
Insert a node at the back; never copies.
Definition at line 147 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::cloneFrom(), and llvm::IRSimilarity::IRInstructionMapper::convertToUnsignedVec().
|
inline |
Insert a node at the front; never copies.
Definition at line 144 of file simple_ilist.h.
|
inline |
Definition at line 121 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::back().
|
inline |
Definition at line 122 of file simple_ilist.h.
|
inline |
Remove a node by reference; never deletes.
Definition at line 183 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::erase(), and llvm::simple_ilist< MachineInstr, Options... >::removeAndDispose().
|
inline |
Remove a node by reference and dispose of it.
Definition at line 187 of file simple_ilist.h.
|
inline |
Definition at line 125 of file simple_ilist.h.
|
inline |
Definition at line 126 of file simple_ilist.h.
|
inline |
Calculate the size of the list in linear time.
Definition at line 134 of file simple_ilist.h.
|
inline |
Sort the list.
Definition at line 263 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::sort().
void llvm::simple_ilist< T, Options >::sort | ( | Compare | comp | ) |
Definition at line 292 of file simple_ilist.h.
|
inline |
Splice in a range of nodes from another list.
Definition at line 248 of file simple_ilist.h.
|
inline |
Splice in another list.
Definition at line 238 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::operator=(), llvm::simple_ilist< MachineInstr, Options... >::simple_ilist(), and llvm::simple_ilist< MachineInstr, Options... >::splice().
|
inline |
Splice in a node from another list.
Definition at line 243 of file simple_ilist.h.
|
inline |
Swap with another list in place using std::swap.
Definition at line 156 of file simple_ilist.h.