LLVM  6.0.0svn
Public Types | Public Member Functions | List of all members
llvm::simple_ilist< T, Options > Class Template Reference

A simple intrusive list implementation. More...

#include "llvm/ADT/simple_ilist.h"

Inheritance diagram for llvm::simple_ilist< T, Options >:
Inheritance graph
[legend]
Collaboration diagram for llvm::simple_ilist< T, Options >:
Collaboration graph
[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_ilistoperator= (const simple_ilist &)=delete
 
 simple_ilist (simple_ilist &&X)
 
simple_ilistoperator= (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)
 

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

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

Here are examples of Options usage:

See is_valid_option for steps on adding a new option.

Definition at line 79 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 97 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 94 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 95 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 99 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 101 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 96 of file simple_ilist.h.

◆ pointer

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

Definition at line 92 of file simple_ilist.h.

◆ reference

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

Definition at line 93 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 98 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 100 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 91 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 111 of file simple_ilist.h.

Member Function Documentation

◆ back() [1/2]

template<typename T, class... Options>
reference llvm::simple_ilist< T, Options >::back ( )
inline

Definition at line 141 of file simple_ilist.h.

Referenced by llvm::AllocatorList< Token >::back().

◆ back() [2/2]

template<typename T, class... Options>
const_reference llvm::simple_ilist< T, Options >::back ( ) const
inline

Definition at line 142 of file simple_ilist.h.

◆ begin() [1/2]

template<typename T, class... Options>
iterator llvm::simple_ilist< T, Options >::begin ( )
inline

◆ begin() [2/2]

template<typename T, class... Options>
const_iterator llvm::simple_ilist< T, Options >::begin ( ) const
inline

Definition at line 119 of file simple_ilist.h.

◆ 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 231 of file simple_ilist.h.

Referenced by llvm::simple_ilist< MachineInstr, 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 234 of file simple_ilist.h.

Referenced by llvm::AllocatorList< Token >::clear(), and llvm::simple_ilist< MachineInstr, 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 174 of file simple_ilist.h.

Referenced by llvm::AllocatorList< Token >::AllocatorList(), and llvm::AllocatorList< Token >::operator=().

◆ empty()

template<typename T, class... Options>
LLVM_NODISCARD bool llvm::simple_ilist< T, Options >::empty ( ) const
inline

◆ end() [1/2]

template<typename T, class... Options>
iterator llvm::simple_ilist< T, Options >::end ( )
inline

◆ end() [2/2]

template<typename T, class... Options>
const_iterator llvm::simple_ilist< T, Options >::end ( ) const
inline

Definition at line 121 of file simple_ilist.h.

◆ erase() [1/2]

template<typename T, class... Options>
iterator llvm::simple_ilist< T, Options >::erase ( iterator  I)
inline

◆ erase() [2/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 206 of file simple_ilist.h.

◆ eraseAndDispose() [1/2]

template<typename T, class... Options>
template<class Disposer >
iterator llvm::simple_ilist< T, Options >::eraseAndDispose ( iterator  I,
Disposer  dispose 
)
inline

◆ eraseAndDispose() [2/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 222 of file simple_ilist.h.

◆ front() [1/2]

template<typename T, class... Options>
reference llvm::simple_ilist< T, Options >::front ( )
inline

Definition at line 139 of file simple_ilist.h.

Referenced by llvm::AllocatorList< Token >::front().

◆ front() [2/2]

template<typename T, class... Options>
const_reference llvm::simple_ilist< T, Options >::front ( ) const
inline

Definition at line 140 of file simple_ilist.h.

◆ insert() [1/2]

template<typename T, class... Options>
iterator llvm::simple_ilist< T, Options >::insert ( iterator  I,
reference  Node 
)
inline

◆ insert() [2/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 167 of file simple_ilist.h.

◆ 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 258 of file simple_ilist.h.

Referenced by llvm::simple_ilist< MachineInstr, Options... >::merge(), and llvm::simple_ilist< MachineInstr, Options... >::sort().

◆ 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 271 of file simple_ilist.h.

◆ 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 112 of file simple_ilist.h.

◆ 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 154 of file simple_ilist.h.

◆ 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 151 of file simple_ilist.h.

◆ 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 148 of file simple_ilist.h.

Referenced by llvm::simple_ilist< MachineInstr, Options... >::cloneFrom(), and llvm::MemorySSA::OptimizeUses::optimizeUses().

◆ 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 145 of file simple_ilist.h.

◆ rbegin() [1/2]

template<typename T, class... Options>
reverse_iterator llvm::simple_ilist< T, Options >::rbegin ( )
inline

◆ rbegin() [2/2]

template<typename T, class... Options>
const_reverse_iterator llvm::simple_ilist< T, Options >::rbegin ( ) const
inline

Definition at line 123 of file simple_ilist.h.

◆ 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 184 of file simple_ilist.h.

◆ 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 188 of file simple_ilist.h.

◆ rend() [1/2]

template<typename T, class... Options>
reverse_iterator llvm::simple_ilist< T, Options >::rend ( )
inline

Definition at line 126 of file simple_ilist.h.

Referenced by llvm::AllocatorList< Token >::rend().

◆ rend() [2/2]

template<typename T, class... Options>
const_reverse_iterator llvm::simple_ilist< T, Options >::rend ( ) const
inline

Definition at line 127 of file simple_ilist.h.

◆ size()

template<typename T, class... Options>
LLVM_NODISCARD size_type llvm::simple_ilist< T, Options >::size ( ) const
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().

◆ sort() [1/2]

template<typename T, class... Options>
void llvm::simple_ilist< T, Options >::sort ( )
inline

Sort the list.

Definition at line 264 of file simple_ilist.h.

Referenced by llvm::simple_ilist< MachineInstr, 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 293 of file simple_ilist.h.

◆ splice() [1/3]

template<typename T, class... Options>
void llvm::simple_ilist< T, Options >::splice ( iterator  I,
simple_ilist< T, Options > &  L2 
)
inline

◆ splice() [2/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 244 of file simple_ilist.h.

◆ splice() [3/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 249 of file simple_ilist.h.

◆ 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 157 of file simple_ilist.h.

Referenced by llvm::AllocatorList< Token >::swap().


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