ash::sparse_group< Val, GroupSz, TblAlloc > Class Template Reference

A subset of a sparse_table. More...

#include <ash/impl/sparse_group.h>

List of all members.

Public Types
typedef Val	value_type
	The type of the object the container holds.
typedef TblAlloc	allocator_type
typedef uint16	size_type
	The unsigned type used to represent the size of the container.
typedef int16	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 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 pointer	nonempty_iterator
	The type used to iterate through assigned elements.
typedef const_pointer	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.
Public Member Functions
const_reference	default_value () const
	Get the "default" value to return for an empty bucket.
size_type	pos_to_offset (size_type pos) const
	Wrapper for the static version.
sparse_group &	operator= (sparse_group const &sg)
	Assignment operator.
void	swap (sparse_group &sg)
	Swap contents with another sparse_group.
void	clear ()
	Erase all elements.
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.
Constructors/Destructors
	sparse_group ()
	Default constructor.
	sparse_group (sparse_group const &sg)
	Copy constructor.
	~sparse_group ()
	Default destructor.
Size Methods
size_type	capacity () const
	Identical to max_size().
size_type	size () const
	Get the size of the container.
size_type	max_size () const
	Get the maximum size of the container.
bool	empty () const
	Check if the container is empty.
size_t	dynamic_memory () const
	Get the amount of memory dynamically-allocated by the container.
size_t	memory () const
	Get the total amount of memory used by the container.
Lookup Methods
bool	test (size_type i) const
	Check if a bucket is empty.
bool	test (iterator 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== (sparse_group const &sg) const
	Equality operator.
bool	operator< (sparse_group const &sg) const
	Less than operator.
Static Public Member Functions
static size_type	pos_to_offset (uint8 const *bm, size_type pos)
	Find out how many set bits there are in a given position in the bitmap.
Related Functions
(Note that these are not member functions.)
template<class T , uint16 GSz, class TA >
void	swap (sparse_group< T, GSz, TA > &x, sparse_group< T, GSz, TA > &y)

---

Detailed Description

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

A subset of a sparse_table.

Concepts:

stl::sequence

Concepts:

stl::random_access_container

Template Parameters:

Val	The type of object stored in the container. Also defined as sparse_group::value_type.
GroupSz	The number of objects per group.
TblAlloc	The table allocator type. Also defined as sparse_group::allocator_type.

The idea is that a table with (logically) t buckets is divided into t/M groups of M buckets each. (M is a constant set in GroupSz for efficiency.) Each group is stored sparsely. Thus, inserting into the table causes some array to grow, which is slow but still constant time. Lookup involves doing a logical-position-to-sparse-position lookup, which is also slow but constant time. The larger M is, the slower these operations are but the less overhead (slightly).

To store the sparse array, we store a bitmap B, where B[i] = 1 iff bucket i is non-empty. Then to look up bucket i we really look up array[# of 1s before i in B]. This is constant time for fixed M.

Terminology: the position of an item in the overall table (from 1 .. t) is called its "location." The logical position in a group (from 1 .. M ) is called its "position." The actual location in the array (from 1 .. # of non-empty buckets in the group) is called its "offset."

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, class TblAlloc = libc_table_value_allocator<Val>>

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

Concept: tr1::container

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

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

The const type used to iterate through the container.

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

typedef const_pointer ash::sparse_group< Val, GroupSz, TblAlloc >::const_nonempty_iterator

The const type used to iterate through assigned elements.

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

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

The type that serves as a const pointer to value_type.

Concept: stl::container

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

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

The type that serves as a pointer to value_type.

Concept: stl::container

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

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

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

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

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

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

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

typedef int16 ash::sparse_group< Val, GroupSz, TblAlloc >::difference_type

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

Concept: stl::container

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

typedef table_element_adaptor<_Type> ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

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

The type used to iterate through the container.

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

typedef pointer ash::sparse_group< Val, GroupSz, TblAlloc >::nonempty_iterator

The type used to iterate through assigned elements.

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

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

The type that serves as a pointer to value_type.

Concept: stl::container

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

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

The type that serves as a reference to value_type.

Concept: stl::container

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

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

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

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

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

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

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

typedef uint16 ash::sparse_group< Val, GroupSz, TblAlloc >::size_type

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

Concept: stl::container

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

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

The type of the object the container holds.

Must be Assignable .

Concept: stl::container

---

Constructor & Destructor Documentation

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

ash::sparse_group< Val, GroupSz, TblAlloc >::sparse_group

(

)

[inline]

Default constructor.

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

ash::sparse_group< Val, GroupSz, TblAlloc >::sparse_group

(

sparse_group< Val, GroupSz, TblAlloc > const &

sg

)

[inline]

Copy constructor.

Parameters:

sg	The sparse_group to copy.

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

ash::sparse_group< Val, GroupSz, TblAlloc >::~sparse_group

(

)

[inline]

Default destructor.

---

Member Function Documentation

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

iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

const_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

size_type ash::sparse_group< Val, GroupSz, TblAlloc >::capacity

(

)

const [inline]

Identical to max_size().

Needed for the iterators.

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

void ash::sparse_group< Val, GroupSz, TblAlloc >::clear

(

)

[inline]

Erase all elements.

Concept: stl::sequence

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

reference ash::sparse_group< 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).

Todo:

austern: Make this exception safe: handle exceptions from value_type's copy constructor.

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

const_reference ash::sparse_group< Val, GroupSz, TblAlloc >::default_value

(

)

const [inline]

Get the "default" value to return for an empty bucket.

Returns:

The "default" value for empty buckets.

Note:

We just use the default constructor on value_type.

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

size_t ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_group< Val, GroupSz, TblAlloc >::empty

(

)

const [inline]

Check if the container is empty.

Returns:

True if the container is empty.

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

iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

const_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

void ash::sparse_group< Val, GroupSz, TblAlloc >::erase

(

size_type

i

)

[inline]

Delete an element.

Parameters:

i	The element's index.

Note:

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

Todo:

austern: Make this exception safe: handle exceptions from value_type's copy constructor.

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

void ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

void ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

const_reference ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

size_type ash::sparse_group< Val, GroupSz, TblAlloc >::max_size

(

)

const [inline]

Get the maximum size of the container.

Returns:

The maximum number of elements the container can hold.

Concept: stl::container

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

size_t ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

reference ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

nonempty_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

const_nonempty_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

nonempty_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

const_nonempty_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

reverse_nonempty_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

const_reverse_nonempty_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

reverse_nonempty_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

const_reverse_nonempty_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_group< Val, GroupSz, TblAlloc >::operator<

(

sparse_group< Val, GroupSz, TblAlloc > const &

sg

)

const [inline]

Less than operator.

Note:

Just a lexographical comparison.

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

sparse_group& ash::sparse_group< Val, GroupSz, TblAlloc >::operator=

(

sparse_group< Val, GroupSz, TblAlloc > const &

sg

)

[inline]

Assignment operator.

Todo:

austern: Make this exception safe. Handle exceptions in value_type's copy constructor.

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

bool ash::sparse_group< Val, GroupSz, TblAlloc >::operator==

(

sparse_group< Val, GroupSz, TblAlloc > const &

sg

)

const [inline]

Equality operator.

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

const_reference ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

element_adaptor ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

static size_type ash::sparse_group< Val, GroupSz, TblAlloc >::pos_to_offset	(	uint8 const *	bm,
		size_type	pos
	)		[inline, static]

Find out how many set bits there are in a given position in the bitmap.

Parameters:

bm	The bitmap.
pos	The position to look up.

Returns:

The number of set bits in bm at pos.

It uses a big table; we make it static so templates don't allocate lots of these. There are lots of ways to do this calculation (called 'popcount'). The 8-bit table lookup is one of the fastest, though this implementation suffers from not doing any loop unrolling. <http://www.dalkescientific.com/writings/diary/ archive/2008/07/03/hakmem_and_other_popcounts.html> http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

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

size_type ash::sparse_group< Val, GroupSz, TblAlloc >::pos_to_offset

(

size_type

pos

)

const [inline]

Wrapper for the static version.

Parameters:

pos	The position to look up.

Returns:

The number of set bits in the container's bitmap at pos.

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

reverse_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

const_reverse_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_group< 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:

Reading destroys the old group contents!

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

bool ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

reverse_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

const_reverse_iterator ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

reference ash::sparse_group< 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).

Todo:

austern: Make this exception safe: handle exceptions from value_type's copy constructor.

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

size_type ash::sparse_group< Val, GroupSz, TblAlloc >::size

(

)

const [inline]

Get the size of the container.

Returns:

The number of elements in the container.

Concept: stl::container

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

void ash::sparse_group< Val, GroupSz, TblAlloc >::swap

(

sparse_group< Val, GroupSz, TblAlloc > &

sg

)

[inline]

Swap contents with another sparse_group.

Parameters:

sg	The sparse_group with which to swap contents.

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

bool ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_group< Val, GroupSz, TblAlloc >::test

(

iterator

pos

)

const [inline]

Check if a bucket is empty.

Parameters:

pos	An iterator to the bucket.

Returns:

True if the bucket is non-empty.

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

const_reference ash::sparse_group< 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, class TblAlloc = libc_table_value_allocator<Val>>

bool ash::sparse_group< 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.

Note:

We don't store the actual array contents (which we don't know how to store), just the bitmap and size. Meant to be used with table I/O.

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

bool ash::sparse_group< 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.

If your keys and values are simple enough, we can write them to disk for you. "simple enough" means POD and no pointers. However, we don't try to normalize endianness.

---

Friends And Related Function Documentation

template<class T , uint16 GSz, class TA >

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

---

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

• ash/impl/sparse_group.h