N-Tier lookup map for sparse-representation of large memory spaces. This is essentially a M-Tree where the child lookup at each node is a simple offset computed by a rshift and mask. More...

#include <TieredMap.hpp>

Classes
class	const_iterator
	Const for walking contents of this map if const-qualified. More...

class	iterator
	Iterator for walking contents of this map. More...

Public Types
Types
typedef std::pair< const KeyT, ValT >	pair_t
	This map contains mappings between a unique set of keys to values. This type represents that mapping for the purposes of iteration and some queries.

typedef std::vector< void * >	node_t
	Node in the map tree. Each node contains up to node_size children, any of which may be.

Public Member Functions
Construction
	TieredMap (uint64_t node_size=512)
	Constructor.

	~TieredMap ()
	Destructor.

Attributes
uint64_t	size () const
	Number of elements allocated in this map.

uint64_t	getNumTiers () const
	Number of tiers used by this map to represent the entire space containing the largest key added. Because this map is sparse, has no consistent relationship with memory use.

uint64_t	getNumNodes () const
	Returns the number of nodes allocated within this map.

uint64_t	getEstimatedMemory () const
	Returns the estimated memory use by this map in bytes.

Iteration
const_iterator	begin () const

const_iterator	end () const

iterator	begin ()

iterator	end ()

Search & Modify
void	clear ()
	Clears the map. Frees all mappings and data structures.

const pair_t *	find (const KeyT &k) const
	Finds a mapping for key k if one exists in this map.

pair_t *	find (const KeyT &k)
	Overload for find.

ValT &	operator[] (const KeyT &k)
	Finds a value by its key.

const ValT &	operator[] (const KeyT &k) const
	const-qualified index operator

pair_t *	tryGet (const KeyT &k)
	Attempts to get a pair_t associated with the key k without modifying the data structure.

const pair_t *	tryGet (const KeyT &k) const
	const-qualified version of tryGet.

Detailed Description

template<typename KeyT = uint64_t, typename ValT = void*>
class sparta::TieredMap< KeyT, ValT >

N-Tier lookup map for sparse-representation of large memory spaces. This is essentially a M-Tree where the child lookup at each node is a simple offset computed by a rshift and mask.

Template Parameters

KeyT	Type of key. Should be an unsigned integer or behave like one
ValT	Value to associate with key. Must be copy-assignable. Should generally be a pointer as it is stored by value internally.

Note: This does not behave exactly like a std::map or unordered_map in that the find method returns a pair* instead of an iterator.

Represents some number space (e.g. an address space) using a number of tiers dependending on the data being represented.

Expected use is for Keys to be memory block indexes (e.g. addr/64) and values to be block objects.

Todo:: Improve iteration to reduce memory use. Instead of maintaining a separate list of pairs, walk the tree itself. However, reasonably fast iteration is needed for checkpointing, so the extra memory use may be somewhat justified

Definition at line 39 of file TieredMap.hpp.

Member Typedef Documentation

◆ node_t

template<typename KeyT = uint64_t, typename ValT = void*>

typedef std::vector<void*> sparta::TieredMap< KeyT, ValT >::node_t

Node in the map tree. Each node contains up to node_size children, any of which may be.

Todo:

Memory can be further saved by making this sparse itself. Most easily, a start index can be stored in addition to the vector's size.

More memory might be saved by making this a simple array instead of a vector. Performance in debug mode would definitely increase because of the removed bounds checking

Definition at line 64 of file TieredMap.hpp.

◆ pair_t

template<typename KeyT = uint64_t, typename ValT = void*>

typedef std::pair<const KeyT, ValT> sparta::TieredMap< KeyT, ValT >::pair_t

This map contains mappings between a unique set of keys to values. This type represents that mapping for the purposes of iteration and some queries.

Definition at line 52 of file TieredMap.hpp.

Constructor & Destructor Documentation

◆ TieredMap()

template<typename KeyT = uint64_t, typename ValT = void*>

sparta::TieredMap< KeyT, ValT >::TieredMap ( uint64_t node_size = 512 )

inline

Constructor.

Parameters

tier_size Size of each node

Definition at line 176 of file TieredMap.hpp.

Here is the call graph for this function:

◆ ~TieredMap()

template<typename KeyT = uint64_t, typename ValT = void*>

sparta::TieredMap< KeyT, ValT >::~TieredMap ( )

inline

Destructor.

Definition at line 193 of file TieredMap.hpp.

Member Function Documentation

◆ begin() [1/2]

template<typename KeyT = uint64_t, typename ValT = void*>

iterator sparta::TieredMap< KeyT, ValT >::begin ( )

inline

Definition at line 244 of file TieredMap.hpp.

◆ begin() [2/2]

template<typename KeyT = uint64_t, typename ValT = void*>

const_iterator sparta::TieredMap< KeyT, ValT >::begin ( ) const

inline

Definition at line 242 of file TieredMap.hpp.

◆ clear()

template<typename KeyT = uint64_t, typename ValT = void*>

void sparta::TieredMap< KeyT, ValT >::clear ( )

inline

Clears the map. Frees all mappings and data structures.

Postcondition: size() will report 0

Definition at line 258 of file TieredMap.hpp.

◆ end() [1/2]

template<typename KeyT = uint64_t, typename ValT = void*>

iterator sparta::TieredMap< KeyT, ValT >::end ( )

inline

Definition at line 245 of file TieredMap.hpp.

◆ end() [2/2]

template<typename KeyT = uint64_t, typename ValT = void*>

const_iterator sparta::TieredMap< KeyT, ValT >::end ( ) const

inline

Definition at line 243 of file TieredMap.hpp.

◆ find() [1/2]

template<typename KeyT = uint64_t, typename ValT = void*>

pair_t * sparta::TieredMap< KeyT, ValT >::find ( const KeyT & k )

inline

Overload for find.

Definition at line 284 of file TieredMap.hpp.

Here is the call graph for this function:

◆ find() [2/2]

template<typename KeyT = uint64_t, typename ValT = void*>

const pair_t * sparta::TieredMap< KeyT, ValT >::find ( const KeyT & k ) const

inline

Finds a mapping for key k if one exists in this map.

Parameters

k	Key for which a mapping will be located if one exists

Returns: Pair associating key k and some ValT

Note: This is not how std::map (or other STL containers) work so this class is not quite a drop-in replacement.

Definition at line 275 of file TieredMap.hpp.

Here is the call graph for this function:

◆ getEstimatedMemory()

template<typename KeyT = uint64_t, typename ValT = void*>

uint64_t sparta::TieredMap< KeyT, ValT >::getEstimatedMemory ( ) const

inline

Returns the estimated memory use by this map in bytes.

Definition at line 225 of file TieredMap.hpp.

◆ getNumNodes()

template<typename KeyT = uint64_t, typename ValT = void*>

uint64_t sparta::TieredMap< KeyT, ValT >::getNumNodes ( ) const

inline

Returns the number of nodes allocated within this map.

Definition at line 220 of file TieredMap.hpp.

◆ getNumTiers()

template<typename KeyT = uint64_t, typename ValT = void*>

uint64_t sparta::TieredMap< KeyT, ValT >::getNumTiers ( ) const

inline

Number of tiers used by this map to represent the entire space containing the largest key added. Because this map is sparse, has no consistent relationship with memory use.

Definition at line 215 of file TieredMap.hpp.

◆ operator[]() [1/2]

template<typename KeyT = uint64_t, typename ValT = void*>

ValT & sparta::TieredMap< KeyT, ValT >::operator[] ( const KeyT & k )

inline

Finds a value by its key.

Returns: ValT reference

This can be used to get or set the value

Definition at line 298 of file TieredMap.hpp.

Here is the call graph for this function:

◆ operator[]() [2/2]

template<typename KeyT = uint64_t, typename ValT = void*>

const ValT & sparta::TieredMap< KeyT, ValT >::operator[] ( const KeyT & k ) const

inline

const-qualified index operator

Definition at line 307 of file TieredMap.hpp.

Here is the call graph for this function:

◆ size()

template<typename KeyT = uint64_t, typename ValT = void*>

uint64_t sparta::TieredMap< KeyT, ValT >::size ( ) const

inline

Number of elements allocated in this map.

Definition at line 208 of file TieredMap.hpp.

◆ tryGet() [1/2]

template<typename KeyT = uint64_t, typename ValT = void*>

pair_t * sparta::TieredMap< KeyT, ValT >::tryGet ( const KeyT & k )

inline

Attempts to get a pair_t associated with the key k without modifying the data structure.

Parameters

k	Key for which a result pair will be located if present.

Returns: nullptr if none found

Note: At least 1 tier is guaranteed at entry

Definition at line 322 of file TieredMap.hpp.

◆ tryGet() [2/2]

template<typename KeyT = uint64_t, typename ValT = void*>

const pair_t * sparta::TieredMap< KeyT, ValT >::tryGet ( const KeyT & k ) const

inline

const-qualified version of tryGet.

Definition at line 352 of file TieredMap.hpp.

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

/github/workspace/sparta/sparta/utils/TieredMap.hpp

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ node_t

◆ pair_t

Constructor & Destructor Documentation

◆ TieredMap()

◆ ~TieredMap()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ clear()

◆ end() [1/2]

◆ end() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ getEstimatedMemory()

◆ getNumNodes()

◆ getNumTiers()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ size()

◆ tryGet() [1/2]

◆ tryGet() [2/2]