LLVM 20.0.0git
Classes | Public Types | Public Member Functions | List of all members
llvm::PagedVector< T, PageSize > Class Template Reference

A vector that allocates memory in pages. More...

#include "llvm/ADT/PagedVector.h"

Classes

class  MaterializedIterator
 Iterator on all the elements of the vector which have actually being constructed. More...
 

Public Types

using value_type = T
 

Public Member Functions

 PagedVector ()
 Default constructor.
 
 PagedVector (BumpPtrAllocator *A)
 
 ~PagedVector ()
 
 PagedVector (const PagedVector &)=delete
 
 PagedVector (PagedVector &&)=delete
 
PagedVectoroperator= (const PagedVector &)=delete
 
PagedVectoroperator= (PagedVector &&)=delete
 
Toperator[] (size_t Index) const
 Look up an element at position Index.
 
size_t capacity () const
 Return the capacity of the vector.
 
size_t size () const
 Return the size of the vector.
 
void resize (size_t NewSize)
 Resize the vector.
 
bool empty () const
 
void clear ()
 Clear the vector, i.e.
 
MaterializedIterator materialized_begin () const
 Iterators over the materialized elements of the vector.
 
MaterializedIterator materialized_end () const
 
llvm::iterator_range< MaterializedIteratormaterialized () const
 

Detailed Description

template<typename T, size_t PageSize = 1024 / sizeof(T)>
class llvm::PagedVector< T, PageSize >

A vector that allocates memory in pages.

Order is kept, but memory is allocated only when one element of the page is accessed. This introduces a level of indirection, but it is useful when you have a sparsely initialised vector where the full size is allocated upfront.

As a side effect the elements are initialised later than in a normal vector. On the first access to one of the elements of a given page, all the elements of the page are initialised. This also means that the elements of the page are initialised beyond the size of the vector.

Similarly on destruction the elements are destroyed only when the page is not needed anymore, delaying invoking the destructor of the elements.

Notice that this has iterators only on materialized elements. This is deliberately done under the assumption you would dereference the elements while iterating, therefore materialising them and losing the gains in terms of memory usage this container provides. If you have such a use case, you probably want to use a normal std::vector or a llvm::SmallVector.

Definition at line 42 of file PagedVector.h.

Member Typedef Documentation

◆ value_type

template<typename T , size_t PageSize = 1024 / sizeof(T)>
using llvm::PagedVector< T, PageSize >::value_type = T

Definition at line 57 of file PagedVector.h.

Constructor & Destructor Documentation

◆ PagedVector() [1/4]

template<typename T , size_t PageSize = 1024 / sizeof(T)>
llvm::PagedVector< T, PageSize >::PagedVector ( )
inline

Default constructor.

We build our own allocator and mark it as such with true in the second pair element.

Definition at line 61 of file PagedVector.h.

◆ PagedVector() [2/4]

template<typename T , size_t PageSize = 1024 / sizeof(T)>
llvm::PagedVector< T, PageSize >::PagedVector ( BumpPtrAllocator A)
inlineexplicit

Definition at line 62 of file PagedVector.h.

References A, and assert().

◆ ~PagedVector()

template<typename T , size_t PageSize = 1024 / sizeof(T)>
llvm::PagedVector< T, PageSize >::~PagedVector ( )
inline

Definition at line 66 of file PagedVector.h.

References Allocator, and clear().

◆ PagedVector() [3/4]

template<typename T , size_t PageSize = 1024 / sizeof(T)>
llvm::PagedVector< T, PageSize >::PagedVector ( const PagedVector< T, PageSize > &  )
delete

◆ PagedVector() [4/4]

template<typename T , size_t PageSize = 1024 / sizeof(T)>
llvm::PagedVector< T, PageSize >::PagedVector ( PagedVector< T, PageSize > &&  )
delete

Member Function Documentation

◆ capacity()

template<typename T , size_t PageSize = 1024 / sizeof(T)>
size_t llvm::PagedVector< T, PageSize >::capacity ( ) const
inline

Return the capacity of the vector.

I.e. the maximum size it can be expanded to with the resize method without allocating more pages.

Definition at line 99 of file PagedVector.h.

References PageSize, and llvm::SmallVectorBase< Size_T >::size().

◆ clear()

template<typename T , size_t PageSize = 1024 / sizeof(T)>
void llvm::PagedVector< T, PageSize >::clear ( )
inline

Clear the vector, i.e.

clear the allocated pages, the whole page lookup index and reset the size.

Definition at line 150 of file PagedVector.h.

References Allocator, PageSize, and Size.

◆ empty()

template<typename T , size_t PageSize = 1024 / sizeof(T)>
bool llvm::PagedVector< T, PageSize >::empty ( ) const
inline

Definition at line 146 of file PagedVector.h.

References Size.

◆ materialized()

template<typename T , size_t PageSize = 1024 / sizeof(T)>
llvm::iterator_range< MaterializedIterator > llvm::PagedVector< T, PageSize >::materialized ( ) const
inline

Definition at line 259 of file PagedVector.h.

◆ materialized_begin()

template<typename T , size_t PageSize = 1024 / sizeof(T)>
MaterializedIterator llvm::PagedVector< T, PageSize >::materialized_begin ( ) const
inline

Iterators over the materialized elements of the vector.

This includes all the elements belonging to allocated pages, even if they have not been accessed yet. It's enough to access one element of a page to materialize all the elements of the page.

Definition at line 245 of file PagedVector.h.

References PageSize, and Size.

◆ materialized_end()

template<typename T , size_t PageSize = 1024 / sizeof(T)>
MaterializedIterator llvm::PagedVector< T, PageSize >::materialized_end ( ) const
inline

Definition at line 254 of file PagedVector.h.

References Size.

◆ operator=() [1/2]

template<typename T , size_t PageSize = 1024 / sizeof(T)>
PagedVector & llvm::PagedVector< T, PageSize >::operator= ( const PagedVector< T, PageSize > &  )
delete

◆ operator=() [2/2]

template<typename T , size_t PageSize = 1024 / sizeof(T)>
PagedVector & llvm::PagedVector< T, PageSize >::operator= ( PagedVector< T, PageSize > &&  )
delete

◆ operator[]()

template<typename T , size_t PageSize = 1024 / sizeof(T)>
T & llvm::PagedVector< T, PageSize >::operator[] ( size_t  Index) const
inline

Look up an element at position Index.

If the associated page is not filled, it will be filled with default constructed elements.

Definition at line 82 of file PagedVector.h.

References Allocator, assert(), PageSize, llvm::SmallVectorBase< Size_T >::size(), and Size.

◆ resize()

template<typename T , size_t PageSize = 1024 / sizeof(T)>
void llvm::PagedVector< T, PageSize >::resize ( size_t  NewSize)
inline

Resize the vector.

Notice that the constructor of the elements will not be invoked until an element of a given page is accessed, at which point all the elements of the page will be constructed.

If the new size is smaller than the current size, the elements of the pages that are not needed anymore will be destroyed, however, elements of the last page will not be destroyed.

For these reason the usage of this vector is discouraged if you rely on the construction / destructor of the elements to be invoked.

Definition at line 116 of file PagedVector.h.

References Allocator, clear(), I, N, PageSize, llvm::SmallVectorImpl< T >::resize(), llvm::SmallVectorBase< Size_T >::size(), and Size.

◆ size()

template<typename T , size_t PageSize = 1024 / sizeof(T)>
size_t llvm::PagedVector< T, PageSize >::size ( ) const
inline

Return the size of the vector.

Definition at line 104 of file PagedVector.h.

References Size.


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