A container that implements a sparse array. More...

#include <ash/sparse_table.h>

Public Types
typedef Val	value_type
	The type of the object the container holds.
typedef TblAlloc	allocator_type

typedef value_alloc_type::size_type	size_type
	The unsigned type used to represent the size of the container.
typedef value_alloc_type::difference_type	difference_type
	The signed integral type used to represent the distance between iterators.
typedef value_alloc_type::reference	reference
	The type that serves as a reference to value_type.
typedef value_alloc_type::const_reference	const_reference
	The type that serves as a pointer to value_type.
typedef value_alloc_type::pointer	pointer
	The type that serves as a pointer to value_type.
typedef value_alloc_type::const_pointer	const_pointer
	The type that serves as a const pointer to value_type.
typedef sparse_group< Val, GroupSz, value_alloc_type >	sparsegroup_type
	The type of sparse_group underneath.
typedef std::vector < sparsegroup_type, vector_alloc >	vector_type
	The type of vector used to hold sparse_groups.
typedef table_iterator< _Type >	iterator
	The type used to iterate through the container.
typedef const_table_iterator < _Type >	const_iterator
	The const type used to iterate through the container.
typedef std::reverse_iterator < iterator >	reverse_iterator
	The type used to iterate through the container in reverse order.
typedef std::reverse_iterator < const_iterator >	const_reverse_iterator
	The const type used to iterate through the container in reverse order.
typedef table_element_adaptor < _Type >	element_adaptor
	The type used to return a non-const reference to an element which may not exist.
typedef two_d_iterator < vector_type >	nonempty_iterator
	The type used to iterate through assigned elements.
typedef const_two_d_iterator < vector_type >	const_nonempty_iterator
	The const type used to iterate through assigned elements.
typedef std::reverse_iterator < nonempty_iterator >	reverse_nonempty_iterator
	The type used to iterate through assigned elements in reverse order.
typedef std::reverse_iterator < const_nonempty_iterator >	const_reverse_nonempty_iterator
	The const type used to iterate through assigned elements in reverse order.
typedef destructive_two_d_iterator < vector_type >	destructive_iterator
	A special iterator that frees memory as it iterates (used to resize).
Public Member Functions
void	swap (sparse_table &st)
	Swap contents with another sparse_table.
void	clear ()
	Erase all elements.
const_nonempty_iterator	get_iter (size_type i) const
	Get a non-empty iterator to an element.
nonempty_iterator	get_iter (size_type i)
	Get a non-empty iterator to an element.
Iterator Methods
iterator	begin ()
	Get an iterator pointing to the beginning.
const_iterator	begin () const
	Get an iterator pointing to the beginning.
iterator	end ()
	Get an iterator pointing to the end.
const_iterator	end () const
	Get an iterator pointing to the end.
reverse_iterator	rbegin ()
	Get a reverse-iterator pointing to the end.
const_reverse_iterator	rbegin () const
	Get a reverse-iterator pointing to the end.
reverse_iterator	rend ()
	Get a reverse-iterator pointing to the beginning.
const_reverse_iterator	rend () const
	Get a reverse-iterator pointing to the beginning.
nonempty_iterator	nonempty_begin ()
	Get a non-empty iterator pointing to the beginning.
const_nonempty_iterator	nonempty_begin () const
	Get a non-empty iterator pointing to the beginning.
nonempty_iterator	nonempty_end ()
	Get a non-empty iterator pointing to the end.
const_nonempty_iterator	nonempty_end () const
	Get a non-empty iterator pointing to the end.
reverse_nonempty_iterator	nonempty_rbegin ()
	Get a non-empty reverse-iterator pointing to the end.
const_reverse_nonempty_iterator	nonempty_rbegin () const
	Get a non-empty reverse-iterator pointing to the end.
reverse_nonempty_iterator	nonempty_rend ()
	Get a non-empty reverse-iterator pointing to the beginning.
const_reverse_nonempty_iterator	nonempty_rend () const
	Get a non-empty reverse-iterator pointing to the beginning.
destructive_iterator	destructive_begin ()
	Get a destructive iterator pointing to the beginning.
destructive_iterator	destructive_end ()
	Get a destructive iterator pointing to the end.
Constructors/Destructors
We use the default copy constructor. We use the default destructor.
	sparse_table (size_type n=0)
	Default constructor.
Size Methods
size_type	capacity () const
	Get the number of currenlty-allocated buckets.
size_type	size () const
	Get the number of elements.
size_type	max_size () const
	Get the maximum number of elements.
bool	empty () const
	Check if the container is empty.
size_type	dynamic_memory () const
	Get the amount of memory dynamically-allocated by the container.
size_type	memory () const
	Get the total amount of memory used by the container.
void	resize (size_type new_size)
	Resize the container.
Lookup Methods
bool	test (size_type i) const
	Check if a bucket is empty.
bool	test (const_iterator const &pos) const
	Check if a bucket is empty.
const_reference	get (size_type i) const
	Get an element.
const_reference	unsafe_get (size_type i) const
	Get an element that MUST exist.
reference	mutating_get (size_type i)
	Get/Set an element.
const_reference	operator[] (size_type i) const
	Element access.
element_adaptor	operator[] (size_type i)
	Element access.
Insertion Methods
reference	set (size_type i, const_reference val)
	Set the value of an element.
reference	copy (size_type i, const_reference val)
	Copy a value to an element.
Deletion Methods
void	erase (size_type i)
	Delete an element.
void	erase (iterator pos)
	Delete an element.
void	erase (iterator f, iterator l)
	Delete a range of elements.
I/O Methods
bool	write_metadata (FILE *fp) const
	Write the container contents to file in a byte-order-independent format.
bool	read_metadata (FILE *fp)
	Read the container contents from a file written by write_metadata().
bool	write_nopointer_data (FILE *fp) const
	Write the container contents to file in an architecture-dependent format.
bool	read_nopointer_data (FILE *fp)
	Read the container contents from a file written by write_nopointer_data().
Comparison Operators
We only define == and >, others are defined in std::rel_ops.
bool	operator== (const sparse_table &x) const
	Equality operator.
bool	operator< (const sparse_table &x) const
	Less than operator.
Related Functions
(Note that these are not member functions.)
template<class T , uint16 GSz, class TA >
void	swap (sparse_table< T, GSz, TA > &x, sparse_table< T, GSz, TA > &y)

Detailed Description

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>
class ash::sparse_table< Val, GroupSz, TblAlloc >

A container that implements a sparse array.

Concepts:: stl::random_access_container

Concepts:: stl::sequence

Template Parameters:

Val	The type of object stored in the container. Also defined as sparse_table::value_type.
GroupSz	The size of the underlying sparse_groups.
TblAlloc	The table allocator.

A sparse array is an array that uses very little memory to store unassigned indices (in this case, between 1-2 bits per unassigned index). For instance, if you allocate an array of size 5 and assign a[2] = <big struct>, then a[2] will take up a lot of memory but a[0], a[1], a[3], and a[4] will not. Array elements that have a value are called "assigned". Array elements that have no value yet, or have had their value cleared using erase() or clear(), are called "unassigned".

Unassigned values seem to have the default value of T (see below). Nevertheless, there is a difference between an unassigned index and one explicitly assigned the value of T(). The latter is considered assigned.

Access to an array element is constant time, as is insertion and deletion. Insertion and deletion may be fairly slow, however: because of this container's memory economy, each insert and delete causes a memory reallocation.

Todo:: Loki: The STL container that's most closely related seems to be std::vector. Refactor to use std::vector semantics where possible/reasonable. Iterators need special attention; the nonempty_iterator may fit the STL idea of an iterator better.

Member Typedef Documentation

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef TblAlloc ash::sparse_table< Val, GroupSz, TblAlloc >::allocator_type

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef const_table_iterator<_Type> ash::sparse_table< Val, GroupSz, TblAlloc >::const_iterator

The const type used to iterate through the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef const_two_d_iterator<vector_type> ash::sparse_table< Val, GroupSz, TblAlloc >::const_nonempty_iterator

The const type used to iterate through assigned elements.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef value_alloc_type::const_pointer ash::sparse_table< Val, GroupSz, TblAlloc >::const_pointer

The type that serves as a const pointer to value_type.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef value_alloc_type::const_reference ash::sparse_table< Val, GroupSz, TblAlloc >::const_reference

The type that serves as a pointer to value_type.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef std::reverse_iterator<const_iterator> ash::sparse_table< Val, GroupSz, TblAlloc >::const_reverse_iterator

The const type used to iterate through the container in reverse order.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef std::reverse_iterator<const_nonempty_iterator> ash::sparse_table< Val, GroupSz, TblAlloc >::const_reverse_nonempty_iterator

The const type used to iterate through assigned elements in reverse order.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef destructive_two_d_iterator<vector_type> ash::sparse_table< Val, GroupSz, TblAlloc >::destructive_iterator

A special iterator that frees memory as it iterates (used to resize).

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef value_alloc_type::difference_type ash::sparse_table< Val, GroupSz, TblAlloc >::difference_type

The signed integral type used to represent the distance between iterators.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef table_element_adaptor<_Type> ash::sparse_table< Val, GroupSz, TblAlloc >::element_adaptor

The type used to return a non-const reference to an element which may not exist.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef table_iterator<_Type> ash::sparse_table< Val, GroupSz, TblAlloc >::iterator

The type used to iterate through the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef two_d_iterator<vector_type> ash::sparse_table< Val, GroupSz, TblAlloc >::nonempty_iterator

The type used to iterate through assigned elements.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef value_alloc_type::pointer ash::sparse_table< Val, GroupSz, TblAlloc >::pointer

The type that serves as a pointer to value_type.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef value_alloc_type::reference ash::sparse_table< Val, GroupSz, TblAlloc >::reference

The type that serves as a reference to value_type.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef std::reverse_iterator<iterator> ash::sparse_table< Val, GroupSz, TblAlloc >::reverse_iterator

The type used to iterate through the container in reverse order.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef std::reverse_iterator<nonempty_iterator> ash::sparse_table< Val, GroupSz, TblAlloc >::reverse_nonempty_iterator

The type used to iterate through assigned elements in reverse order.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef value_alloc_type::size_type ash::sparse_table< Val, GroupSz, TblAlloc >::size_type

The unsigned type used to represent the size of the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef sparse_group<Val, GroupSz, value_alloc_type> ash::sparse_table< Val, GroupSz, TblAlloc >::sparsegroup_type

The type of sparse_group underneath.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef Val ash::sparse_table< Val, GroupSz, TblAlloc >::value_type

The type of the object the container holds.

Must be Assignable .

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

typedef std::vector<sparsegroup_type, vector_alloc> ash::sparse_table< Val, GroupSz, TblAlloc >::vector_type

The type of vector used to hold sparse_groups.

Constructor & Destructor Documentation

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

ash::sparse_table< Val, GroupSz, TblAlloc >::sparse_table ( size_type n = 0 ) [inline]

Default constructor.

Parameters:

n	The number of buckets to start with.

Member Function Documentation

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

iterator ash::sparse_table< Val, GroupSz, TblAlloc >::begin ( ) [inline]

Get an iterator pointing to the beginning.

Returns:: An iterator pointing to the beginning of the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

const_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::begin ( ) const [inline]

Get an iterator pointing to the beginning.

Returns:: A const_iterator pointing to the beginning of the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

size_type ash::sparse_table< Val, GroupSz, TblAlloc >::capacity ( ) const [inline]

Get the number of currenlty-allocated buckets.

Returns:: The number of elements the container has allocated memory for.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

void ash::sparse_table< Val, GroupSz, TblAlloc >::clear ( ) [inline]

Erase all elements.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

reference ash::sparse_table< Val, GroupSz, TblAlloc >::copy	(	size_type	i,
		const_reference	val
	)		`[inline]`

Copy a value to an element.

Similar to set(), but ignores the Move functor. If the move functor is trivial, the two are identical.

Parameters:

i	The index of the element.
val	The new value of the element.

Returns:: A reference to the inserted item (which is a copy of val).

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

destructive_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::destructive_begin ( ) [inline]

Get a destructive iterator pointing to the beginning.

Returns:: a destructive_iterator pointing to the beginning of the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

destructive_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::destructive_end ( ) [inline]

Get a destructive iterator pointing to the end.

Returns:: a destructive_iterator pointing to the end of the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

size_type ash::sparse_table< Val, GroupSz, TblAlloc >::dynamic_memory ( ) const [inline]

Get the amount of memory dynamically-allocated by the container.

Returns:: The amount of dynamically-allocated memory in bytes.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_table< Val, GroupSz, TblAlloc >::empty ( ) const [inline]

Check if the container is empty.

Returns:: True if the container is empty.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

iterator ash::sparse_table< Val, GroupSz, TblAlloc >::end ( ) [inline]

Get an iterator pointing to the end.

Returns:: An iterator pointing to the end of the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

const_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::end ( ) const [inline]

Get an iterator pointing to the end.

Returns:: A const_iterator pointing to the end of the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

void ash::sparse_table< Val, GroupSz, TblAlloc >::erase ( size_type i ) [inline]

Delete an element.

Parameters:

i	The element's index.

Note:: This is "undefining", rather than "clearing".

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

void ash::sparse_table< Val, GroupSz, TblAlloc >::erase ( iterator pos ) [inline]

Delete an element.

Parameters:

pos	An iterator pointing to the element.

Note:: This is "undefining", rather than "clearing".

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

void ash::sparse_table< Val, GroupSz, TblAlloc >::erase	(	iterator	f,
		iterator	l
	)		`[inline]`

Delete a range of elements.

Parameters:

f	An iterator pointing to the beginning of the range.
l	An iterator pointing to the end of the range.

Note:: This is "undefining", rather than "clearing".

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

const_reference ash::sparse_table< Val, GroupSz, TblAlloc >::get ( size_type i ) const [inline]

Get an element.

Parameters:

i	The index of the element.

Returns:: A const_reference to the element, or the default if none exists.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

const_nonempty_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::get_iter ( size_type i ) const [inline]

Get a non-empty iterator to an element.

Parameters:

i	The element's index.

Returns:: A const_nonempty_iterator to the element.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

nonempty_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::get_iter ( size_type i ) [inline]

Get a non-empty iterator to an element.

Parameters:

i	The element's index.

Returns:: A nonempty_iterator to the element.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

size_type ash::sparse_table< Val, GroupSz, TblAlloc >::max_size ( ) const [inline]

Get the maximum number of elements.

Returns:: The maximum number of elements the container can hold.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

size_type ash::sparse_table< Val, GroupSz, TblAlloc >::memory ( ) const [inline]

Get the total amount of memory used by the container.

Returns:: The amount of memory in bytes.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

reference ash::sparse_table< Val, GroupSz, TblAlloc >::mutating_get ( size_type i ) [inline]

Get/Set an element.

Parameters:

i	The index of the element.

Returns:: A reference to the element.

Note:: A new element is inserted if none exists at the given index.

Todo:: csilvers: make protected + friend.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

nonempty_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::nonempty_begin ( ) [inline]

Get a non-empty iterator pointing to the beginning.

Returns:: A nonempty_iterator pointing to the beginning of the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

const_nonempty_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::nonempty_begin ( ) const [inline]

Get a non-empty iterator pointing to the beginning.

Returns:: A const_nonempty_iterator pointing to the beginning of the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

nonempty_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::nonempty_end ( ) [inline]

Get a non-empty iterator pointing to the end.

Returns:: A nonempty_iterator pointing to the end of the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

const_nonempty_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::nonempty_end ( ) const [inline]

Get a non-empty iterator pointing to the end.

Returns:: A const_nonempty_iterator pointing to the end of the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

reverse_nonempty_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::nonempty_rbegin ( ) [inline]

Get a non-empty reverse-iterator pointing to the end.

Returns:: A reverse_nonempty_iterator pointing to the beginning of the reversed container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

const_reverse_nonempty_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::nonempty_rbegin ( ) const [inline]

Get a non-empty reverse-iterator pointing to the end.

Returns:: A const_reverse_nonempty_iterator pointing to the beginning of the reversed container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

reverse_nonempty_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::nonempty_rend ( ) [inline]

Get a non-empty reverse-iterator pointing to the beginning.

Returns:: A reverse_nonempty_iterator pointing to the end of the reversed container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

const_reverse_nonempty_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::nonempty_rend ( ) const [inline]

Get a non-empty reverse-iterator pointing to the beginning.

Returns:: A const_reverse_nonempty_iterator pointing to the end of the reversed container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_table< Val, GroupSz, TblAlloc >::operator< ( const sparse_table< Val, GroupSz, TblAlloc > & x ) const [inline]

Less than operator.

Note:: Just a lexographical comparison.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_table< Val, GroupSz, TblAlloc >::operator== ( const sparse_table< Val, GroupSz, TblAlloc > & x ) const [inline]

Equality operator.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

const_reference ash::sparse_table< Val, GroupSz, TblAlloc >::operator[] ( size_type i ) const [inline]

Element access.

Get an element.

Parameters:

i	The index of the element.

Returns:: A const_reference to the element, or the default if none exists.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

element_adaptor ash::sparse_table< Val, GroupSz, TblAlloc >::operator[] ( size_type i ) [inline]

Element access.

Parameters:

i	The index of the element.

Returns:: An element_adaptor to the element.

Note:: If the element does not exist, it will not be inserted until the element_adaptor is assigned.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

reverse_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::rbegin ( ) [inline]

Get a reverse-iterator pointing to the end.

Returns:: A reverse_iterator pointing to the beginning of the reversed container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

const_reverse_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::rbegin ( ) const [inline]

Get a reverse-iterator pointing to the end.

Returns:: A const_reverse_iterator pointing to the beginning of the reversed container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_table< Val, GroupSz, TblAlloc >::read_metadata ( FILE * fp ) [inline]

Read the container contents from a file written by write_metadata().

Parameters:

fp	The file to read.

Returns:: True if successful.

Note:: Destroys old contents.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_table< Val, GroupSz, TblAlloc >::read_nopointer_data ( FILE * fp ) [inline]

Read the container contents from a file written by write_nopointer_data().

Parameters:

fp	The file to read.

Returns:: True if successful.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

reverse_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::rend ( ) [inline]

Get a reverse-iterator pointing to the beginning.

Returns:: A reverse_iterator pointing to the end of the reversed container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

const_reverse_iterator ash::sparse_table< Val, GroupSz, TblAlloc >::rend ( ) const [inline]

Get a reverse-iterator pointing to the beginning.

Returns:: A const_reverse_iterator pointing to the end of the reversed container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

void ash::sparse_table< Val, GroupSz, TblAlloc >::resize ( size_type new_size ) [inline]

Resize the container.

Parameters:

new_size The expected number of elements.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

reference ash::sparse_table< Val, GroupSz, TblAlloc >::set	(	size_type	i,
		const_reference	val
	)		`[inline]`

Set the value of an element.

Parameters:

i	The index of the element.
val	The new value of the element.

Returns:: A reference to the inserted item (which is a copy of val).

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

size_type ash::sparse_table< Val, GroupSz, TblAlloc >::size ( ) const [inline]

Get the number of elements.

Returns:: The number of elements in the container.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

void ash::sparse_table< Val, GroupSz, TblAlloc >::swap ( sparse_table< Val, GroupSz, TblAlloc > & st ) [inline]

Swap contents with another sparse_table.

Parameters:

st	The sparse_table with which to swap contents.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_table< Val, GroupSz, TblAlloc >::test ( size_type i ) const [inline]

Check if a bucket is empty.

Parameters:

i	The index of the bucket.

Returns:: True if the bucket is non-empty.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_table< Val, GroupSz, TblAlloc >::test ( const_iterator const & pos ) const [inline]

Check if a bucket is empty.

Parameters:

pos	An iterator pointing to the bucket.

Returns:: True if the bucket is non-empty.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

const_reference ash::sparse_table< Val, GroupSz, TblAlloc >::unsafe_get ( size_type i ) const [inline]

Get an element that MUST exist.

Parameters:

i	The index of the element.

Returns:: A const_reference to the element.

Note:: The existance of the element is verified by assert().

Todo:: csilvers: make protected + friend. This is used by sparse_hashtable to get an element from the table when we know it exists.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_table< Val, GroupSz, TblAlloc >::write_metadata ( FILE * fp ) const [inline]

Write the container contents to file in a byte-order-independent format.

Parameters:

fp	The file to write.

Returns:: True if successful.

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_table< Val, GroupSz, TblAlloc >::write_nopointer_data ( FILE * fp ) const [inline]

Write the container contents to file in an architecture-dependent format.

Parameters:

fp	The file to write.

Returns:: True if successful.

Friends And Related Function Documentation

template<class T , uint16 GSz, class TA >

void swap	(	sparse_table< T, GSz, TA > &	x,
		sparse_table< T, GSz, TA > &	y
	)		`[related]`

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

ash/sparse_table.h

Public Types

Public Member Functions

Related Functions

Detailed Description

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>> class ash::sparse_table< Val, GroupSz, TblAlloc >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

template<class Val, uint16 GroupSz = DEFAULT_SPARSEGROUP_SIZE, class TblAlloc = libc_table_value_allocator<Val>>
class ash::sparse_table< Val, GroupSz, TblAlloc >