Requirements on the contained type are to be cloneable, hashable and equality comparable. More...

#include <UniqueTableId.hh>

Collaboration diagram for UniqueTableId< T, ID >:

Classes
struct	id_compare

struct	id_hash

Public Types
typedef table_t::const_iterator	table_it

Public Member Functions
void	mark (const id_t &id)

void	ref (const id_t &id)

void	deref (const id_t &id)

table_it	begin () const

table_it	end () const

	UniqueTableId (size_t s=4096)
	Provide an initial size for both hash and index tables. More...

const T *	resolve (const id_t &id) const

id_t	operator() (const T &_g)
	The application operator, returns the address of the value already in the table if it exists, or inserts and returns the address of the value inserted. More...

size_t	size () const
	Returns the current number of filled entries in the table. More...

size_t	peak_size ()

void	garbage ()

Static Public Member Functions
static UniqueTableId &	instance ()

Private Types
typedef ID	id_t

typedef d3::hash_set< id_t, id_hash, id_compare >::type	table_t
	Typedef helps hide implementation type. More...

typedef std::vector< const T * >	indexes_t
	The Indexes table stores the id to (unique) T* map. More...

typedef google::sparsetable< id_t >	refs_t
	a sparse table holding refcounts for ref'd objects. More...

typedef std::vector< bool >	marks_t
	A bitset to store marks on objects used for mark&sweep. More...

Private Member Functions
void	push (const id_t &id)
	add a node to free list More...

id_t	next_id ()
	return the next free id, either collected from free_list or the newly allocated last position of the index table More...

void	print_free_list (std::ostream &os) const

void	print_table (std::ostream &os) const

void	print_marked (std::ostream &os) const

Private Attributes
table_t	table
	The actual table, operations on the UniqueTable are delegated on this. More...

indexes_t	index
	The actual index table, resolution of object from Id is done with this. More...

id_t	head
	The free list is stored hidden in the free space of the index table. More...

refs_t	refs
	The reference counters for ref'd nodes. It is a sparse table that only stores values for non-zero entries. More...

marks_t	marks
	The marking entries, a bitset. More...

size_t	peak_size_

Detailed Description

template<typename T, typename ID>
class UniqueTableId< T, ID >

Requirements on the contained type are to be cloneable, hashable and equality comparable.

For memory recollection, it should be markable, i.e. able

template interface T { T* clone () const ; bool operator==(const T&) const; size_t hash() const; } These are the comparators/hash of d3:: namespace. member hash and operator== are enough thanks to template instanciations.
This class implements a unique table mechanism, based on a hash.

Member Typedef Documentation

◆ id_t

template<typename T , typename ID >

typedef ID UniqueTableId< T, ID >::id_t

private

◆ indexes_t

template<typename T , typename ID >

typedef std::vector<const T*> UniqueTableId< T, ID >::indexes_t

private

The Indexes table stores the id to (unique) T* map.

It also stores the free list in potential spare spaces.

◆ marks_t

template<typename T , typename ID >

typedef std::vector<bool> UniqueTableId< T, ID >::marks_t

private

A bitset to store marks on objects used for mark&sweep.

◆ refs_t

template<typename T , typename ID >

typedef google::sparsetable<id_t> UniqueTableId< T, ID >::refs_t

private

a sparse table holding refcounts for ref'd objects.

Hopefully, we don't have more refs than there are nodes, id_t should be long enough to hold refcounts.

◆ table_it

template<typename T , typename ID >

typedef table_t::const_iterator UniqueTableId< T, ID >::table_it

◆ table_t

template<typename T , typename ID >

typedef d3::hash_set<id_t, id_hash, id_compare>::type UniqueTableId< T, ID >::table_t

private

Typedef helps hide implementation type.

The table wil hold actual entries for hashed unique test, These are the currently valid ids.

Constructor & Destructor Documentation

◆ UniqueTableId()

template<typename T , typename ID >

UniqueTableId< T, ID >::UniqueTableId ( size_t s = 4096 )

inline

Provide an initial size for both hash and index tables.

Both will grow as needed if this size is exceeded.

References UniqueTableId< T, ID >::index, UniqueTableId< T, ID >::marks, UniqueTableId< T, ID >::refs, and UniqueTableId< T, ID >::table.

Referenced by UniqueTableId< T, ID >::instance().

Member Function Documentation

◆ begin()

template<typename T , typename ID >

table_it UniqueTableId< T, ID >::begin ( ) const

inline

References UniqueTableId< T, ID >::table.

Referenced by UniqueTableId< T, ID >::garbage(), and UniqueTableId< T, ID >::print_table().

◆ deref()

template<typename T , typename ID >

void UniqueTableId< T, ID >::deref ( const id_t & id )

inline

References UniqueTableId< T, ID >::refs.

Referenced by DDD::operator=(), and DDD::~DDD().

◆ end()

template<typename T , typename ID >

table_it UniqueTableId< T, ID >::end ( ) const

inline

References UniqueTableId< T, ID >::table.

Referenced by UniqueTableId< T, ID >::garbage(), and UniqueTableId< T, ID >::print_table().

◆ garbage()

template<typename T , typename ID >

void UniqueTableId< T, ID >::garbage ( )

inline

References UniqueTableId< T, ID >::begin(), UniqueTableId< T, ID >::end(), UniqueTableId< T, ID >::index, UniqueTableId< T, ID >::mark(), UniqueTableId< T, ID >::marks, UniqueTableId< T, ID >::peak_size(), UniqueTableId< T, ID >::push(), UniqueTableId< T, ID >::refs, and UniqueTableId< T, ID >::table.

Referenced by GDDD::garbage().

◆ instance()

template<typename T , typename ID >

static UniqueTableId& UniqueTableId< T, ID >::instance ( )

inlinestatic

References UniqueTableId< T, ID >::UniqueTableId().

Referenced by _GDDD::create_unique_GDDD(), DDD::DDD(), GDDD::garbage(), GDDD::mark(), UniqueTableId< T, ID >::id_hash::operator()(), UniqueTableId< T, ID >::id_compare::operator()(), DDD::operator=(), GDDD::peak(), GDDD::pstats(), _GDDD::resolve(), GDDD::statistics(), and DDD::~DDD().

◆ mark()

template<typename T , typename ID >

void UniqueTableId< T, ID >::mark ( const id_t & id )

inline

References UniqueTableId< T, ID >::marks, and UniqueTableId< T, ID >::resolve().

Referenced by UniqueTableId< T, ID >::garbage(), and GDDD::mark().

◆ next_id()

template<typename T , typename ID >

id_t UniqueTableId< T, ID >::next_id ( )

inlineprivate

return the next free id, either collected from free_list or the newly allocated last position of the index table

References UniqueTableId< T, ID >::head, UniqueTableId< T, ID >::index, and UniqueTableId< T, ID >::marks.

Referenced by UniqueTableId< T, ID >::operator()().

◆ operator()()

template<typename T , typename ID >

id_t UniqueTableId< T, ID >::operator() ( const T & _g )

inline

The application operator, returns the address of the value already in the table if it exists, or inserts and returns the address of the value inserted.

Parameters