LLVM
8.0.1
|
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 allocates or 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 instantation 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 79 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::const_iterator = ilist_iterator<OptionsT, false, true> |
Definition at line 97 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::const_pointer = typename OptionsT::const_pointer |
Definition at line 94 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::const_reference = typename OptionsT::const_reference |
Definition at line 95 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::const_reverse_iterator = ilist_iterator<OptionsT, true, true> |
Definition at line 99 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::difference_type = ptrdiff_t |
Definition at line 101 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::iterator = ilist_iterator<OptionsT, false, false> |
Definition at line 96 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::pointer = typename OptionsT::pointer |
Definition at line 92 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::reference = typename OptionsT::reference |
Definition at line 93 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::reverse_iterator = ilist_iterator<OptionsT, true, false> |
Definition at line 98 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::size_type = size_t |
Definition at line 100 of file simple_ilist.h.
using llvm::simple_ilist< T, Options >::value_type = typename OptionsT::value_type |
Definition at line 91 of file simple_ilist.h.
|
default |
|
default |
|
delete |
|
inline |
Definition at line 111 of file simple_ilist.h.
|
inline |
Definition at line 141 of file simple_ilist.h.
Referenced by llvm::AllocatorList< Token >::back().
|
inline |
Definition at line 142 of file simple_ilist.h.
|
inline |
Definition at line 118 of file simple_ilist.h.
Referenced by llvm::AllocatorList< Token >::begin(), llvm::simple_ilist< MachineInstr, Options... >::clearAndDispose(), llvm::simple_ilist< MachineInstr, Options... >::front(), llvm::MemorySSAUpdater::insertDef(), llvm::simple_ilist< MachineInstr, Options... >::merge(), llvm::simple_ilist< MachineInstr, Options... >::pop_front(), llvm::AllocatorList< Token >::pop_front(), llvm::simple_ilist< MachineInstr, Options... >::size(), llvm::simple_ilist< MachineInstr, Options... >::sort(), and llvm::simple_ilist< MachineInstr, Options... >::splice().
|
inline |
Definition at line 119 of file simple_ilist.h.
|
inline |
Clear the list; never deletes.
Definition at line 231 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 234 of file simple_ilist.h.
Referenced by llvm::AllocatorList< Token >::clear(), and llvm::simple_ilist< MachineInstr, Options... >::cloneFrom().
|
inline |
Clone another list.
Definition at line 174 of file simple_ilist.h.
Referenced by llvm::AllocatorList< Token >::AllocatorList(), and llvm::AllocatorList< Token >::operator=().
|
inline |
Check if the list is empty in constant time.
Definition at line 132 of file simple_ilist.h.
Referenced by llvm::AllocatorList< Token >::empty(), llvm::simple_ilist< MachineInstr, Options... >::merge(), and llvm::simple_ilist< MachineInstr, Options... >::sort().
|
inline |
Definition at line 120 of file simple_ilist.h.
Referenced by llvm::MemorySSAUpdater::applyInsertUpdates(), llvm::simple_ilist< MachineInstr, Options... >::clearAndDispose(), llvm::AllocatorList< Token >::end(), llvm::simple_ilist< MachineInstr, Options... >::erase(), llvm::MemorySSA::getWritableBlockDefs(), llvm::simple_ilist< MachineInstr, Options... >::merge(), llvm::simple_ilist< MachineInstr, Options... >::operator=(), llvm::simple_ilist< MachineInstr, Options... >::pop_back(), llvm::AllocatorList< Token >::pop_back(), llvm::simple_ilist< MachineInstr, Options... >::simple_ilist(), llvm::simple_ilist< MachineInstr, Options... >::size(), llvm::simple_ilist< MachineInstr, Options... >::sort(), and llvm::simple_ilist< MachineInstr, Options... >::splice().
|
inline |
Definition at line 121 of file simple_ilist.h.
|
inline |
Remove a node by iterator; never deletes.
Definition at line 197 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; never deletes.
Definition at line 206 of file simple_ilist.h.
|
inline |
Remove a node by iterator and dispose of it.
Definition at line 213 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::clearAndDispose(), llvm::AllocatorList< Token >::erase(), llvm::simple_ilist< MachineInstr, Options... >::eraseAndDispose(), llvm::AllocatorList< Token >::pop_back(), and llvm::AllocatorList< Token >::pop_front().
|
inline |
Remove a range of nodes and dispose of them.
Definition at line 222 of file simple_ilist.h.
|
inline |
Definition at line 139 of file simple_ilist.h.
Referenced by llvm::AllocatorList< Token >::front().
|
inline |
Definition at line 140 of file simple_ilist.h.
|
inline |
Insert a node by reference; never copies.
Definition at line 160 of file simple_ilist.h.
Referenced by llvm::AllocatorList< Token >::emplace(), llvm::simple_ilist< MachineInstr, Options... >::insert(), and llvm::AllocatorList< Token >::insert().
|
inline |
Insert a range of nodes; never copies.
Definition at line 167 of file simple_ilist.h.
|
inline |
Merge in another list.
this
and RHS
are sorted. Definition at line 258 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 271 of file simple_ilist.h.
|
delete |
|
inline |
Definition at line 112 of file simple_ilist.h.
|
inline |
Remove the node at the back; never deletes.
Definition at line 154 of file simple_ilist.h.
|
inline |
Remove the node at the front; never deletes.
Definition at line 151 of file simple_ilist.h.
|
inline |
Insert a node at the back; never copies.
Definition at line 148 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::cloneFrom(), and llvm::MemorySSA::OptimizeUses::optimizeUses().
|
inline |
Insert a node at the front; never copies.
Definition at line 145 of file simple_ilist.h.
|
inline |
Definition at line 122 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::back(), and llvm::AllocatorList< Token >::rbegin().
|
inline |
Definition at line 123 of file simple_ilist.h.
|
inline |
Remove a node by reference; never deletes.
Definition at line 184 of file simple_ilist.h.
|
inline |
Remove a node by reference and dispose of it.
Definition at line 188 of file simple_ilist.h.
|
inline |
Definition at line 126 of file simple_ilist.h.
Referenced by llvm::AllocatorList< Token >::rend().
|
inline |
Definition at line 127 of file simple_ilist.h.
|
inline |
Calculate the size of the list in linear time.
Definition at line 135 of file simple_ilist.h.
Referenced by llvm::AllocatorList< Token >::size().
|
inline |
Sort the list.
Definition at line 264 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 293 of file simple_ilist.h.
|
inline |
Splice in another list.
Definition at line 239 of file simple_ilist.h.
Referenced by llvm::simple_ilist< MachineInstr, Options... >::merge(), 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 244 of file simple_ilist.h.
|
inline |
Splice in a range of nodes from another list.
Definition at line 249 of file simple_ilist.h.
|
inline |
Swap with another list in place using std::swap.
Definition at line 157 of file simple_ilist.h.
Referenced by llvm::AllocatorList< Token >::swap().