Cache of alias to node id mappings. More...

#include <AliasCache.hxx>

Classes
class	AliasComparator
	Comparator object comparing the aliases stored in the pool. More...

class	IdComparator
	Comparator object comparing the aliases stored in the pool. More...

struct	Metadata
	Interesting information about a given cache entry. More...

class	PoolIdx
	Encapsulation of a pointer into the pool array. More...

Public Member Functions
	AliasCache (NodeID seed, size_t _entries, void(remove_callback)(NodeID id, NodeAlias alias, void )=NULL, void *context=NULL)
	Constructor.

void	clear ()
	Reinitializes the entire map.

void	add (NodeID id, NodeAlias alias)
	Add an alias to an alias cache.

void	remove (NodeAlias alias)
	Remove an alias from an alias cache.

NodeAlias	lookup (NodeID id)
	Lookup a node's alias based on its Node ID.

NodeID	lookup (NodeAlias alias)
	Lookup a node's ID based on its alias.

void	for_each (void(callback)(void , NodeID, NodeAlias), void *context)
	Call the given callback function once for each alias tracked.

size_t	size ()
	Returns the total number of aliases that can be cached.

bool	retrieve (unsigned entry, NodeID node, NodeAlias alias)
	Retrieves an entry by index.

bool	next_entry (NodeID bound, NodeID node, NodeAlias alias)
	Retrieves the next entry by increasing node ID.

NodeAlias	generate ()
	Generate a 12-bit pseudo-random alias for a given alias cache.

	~AliasCache ()
	Default destructor.

int	check_consistency ()
	Visible for testing.

Static Public Attributes
static constexpr uint16_t	NONE_ENTRY = 0xFFFFu
	Sentinel entry for empty lists.

Private Types
typedef SortedListSet< PoolIdx, AliasComparator >	AliasMap
	Short hand for the alias Map type.

typedef SortedListSet< PoolIdx, IdComparator >	IdMap
	Short hand for the ID Map type.

Private Member Functions
void	touch (Metadata *metadata)
	Update the time stamp for a given entry.

	DISALLOW_COPY_AND_ASSIGN (AliasCache)

Private Attributes
Metadata *	pool
	pointer to allocated Metadata pool

AliasMap	aliasMap
	Map of alias to corresponding Metadata.

IdMap	idMap
	Map of Node ID to corresponding Metadata.

PoolIdx	freeList
	list of unused mapping entries (index into pool)

PoolIdx	oldest
	oldest untouched entry (index into pool)

PoolIdx	newest
	newest, most recently touched entry (index into pool)

NodeID	seed
	Seed for the generation of the next alias.

size_t	entries
	How many metadata entries have we allocated.

void(*	removeCallback )(NodeID id, NodeAlias alias, void *)
	callback function to be used when we remove an entry from the cache

void *	context
	context pointer to pass in with remove_callback

Friends
class	PoolIdx

Detailed Description

Cache of alias to node id mappings.

The cache is limited to a fixed number of entries at construction. All the memory for the cache will be allocated at construction time, limited by the maximum number of entries. Note, there is no mutual exclusion locking mechanism built into this class. Mutual exclusion must be handled by the user as needed.

This data structure is sometimes used with very large entry count (hundreds), therefore we must be careful about memory efficiency!

Theory of operation:

The data structure has three access patterns:

lookup of alias -> ID
lookup of ID -> alias
eviction of oldest entry from the cache

We have three data structures to match these use-cases:

The struct Metadata stores the actual NodeID and NodeAlias values. This is laid out in the pre-allocated C array pool. A freeList shows where unused entries are.

To support the eviction of oldest entry, an LRU doubly-linked list is created in these Metadata entries. The links are represented by indexes into the pool array.

Indexes into the pool are encapsulated into the PoolIdx struct to make them a unique C++ type. This is needed for template disambiguation. We also have a dereference function on PoolIdx that turns it into a Metadata pointer.

To support lookup by alias, we have a SortedListSet which contains all used indexes as PoolIdx, sorted by the alias property in the respective entry in pool. This is achieved by a custom comparator that dereferences the PoolIdx object and fetches the alias from the Metadata struct. The sorted vector is maintained using the SortedListSet<> template, and takes a total of only 2 bytes per entry.

A similar sorted vector is kept sorted by the NodeID values. This also takes only 2 bytes per entry.

Definition at line 86 of file AliasCache.hxx.

Member Typedef Documentation

◆ AliasMap

typedef SortedListSet<PoolIdx, AliasComparator> openlcb::AliasCache::AliasMap

private

Short hand for the alias Map type.

Definition at line 337 of file AliasCache.hxx.

◆ IdMap

typedef SortedListSet<PoolIdx, IdComparator> openlcb::AliasCache::IdMap

private

Short hand for the ID Map type.

Definition at line 340 of file AliasCache.hxx.

Constructor & Destructor Documentation

◆ AliasCache()

openlcb::AliasCache::AliasCache	(	NodeID	seed,
		size_t	_entries,
		void()(NodeID id, NodeAlias alias, void )	remove_callback = `NULL`,
		void *	context = `NULL`
	)

inline

Constructor.

Parameters

seed	starting seed for generation of aliases
entries	maximum number of entries in this cache
remove_callback	callback to call when we remove a mapping from the cache however it will not be called in the remove() method
context	context pointer to pass to remove_callback

Definition at line 96 of file AliasCache.hxx.

◆ ~AliasCache()

openlcb::AliasCache::~AliasCache ( )

inline

Default destructor.

Definition at line 181 of file AliasCache.hxx.

Member Function Documentation

◆ add()

void openlcb::AliasCache::add	(	NodeID	id,
		NodeAlias	alias
	)

Add an alias to an alias cache.

Parameters

id	48-bit NMRAnet Node ID to associate alias with
alias	12-bit alias associated with Node ID

Definition at line 297 of file AliasCache.cxx.

◆ check_consistency()

int openlcb::AliasCache::check_consistency ( )

Visible for testing.

Check internal consistency.

◆ clear()

void openlcb::AliasCache::clear ( )

Reinitializes the entire map.

Definition at line 266 of file AliasCache.cxx.

◆ for_each()

void openlcb::AliasCache::for_each	(	void()(void , NodeID, NodeAlias)	callback,
		void *	context
	)

Call the given callback function once for each alias tracked.

The order will be in last "touched" order.

Parameters

callback	method to call
context	context pointer to pass to callback

Definition at line 549 of file AliasCache.cxx.

◆ generate()

NodeAlias openlcb::AliasCache::generate ( )

Generate a 12-bit pseudo-random alias for a given alias cache.

Generate a 12-bit pseudo-random alias for a givin alias cache.

Returns: pseudo-random 12-bit alias, an alias of zero is invalid

Definition at line 564 of file AliasCache.cxx.

◆ lookup() [1/2]

NodeID openlcb::AliasCache::lookup ( NodeAlias alias )

Lookup a node's ID based on its alias.

Parameters

alias alias to look for

Returns: Node ID that matches the alias, else 0 if not found

Definition at line 522 of file AliasCache.cxx.

◆ lookup() [2/2]

NodeAlias openlcb::AliasCache::lookup ( NodeID id )

Lookup a node's alias based on its Node ID.

Parameters

id	Node ID to look for

Returns: alias that matches the Node ID, else 0 if not found

Definition at line 499 of file AliasCache.cxx.

◆ next_entry()

bool openlcb::AliasCache::next_entry	(	NodeID	bound,
		NodeID *	node,
		NodeAlias *	alias
	)

Retrieves the next entry by increasing node ID.

Parameters

bound	is a Node ID. Will search for the next largest node ID (upper bound of this key).
node	will be filled with the node ID. May be null.
alias	will be filled with the alias. May be null.

Returns: true if a larger element is found and node and alias were filled, otherwise false if bound is >= the largest node ID in the cache.

Definition at line 476 of file AliasCache.cxx.

◆ remove()

void openlcb::AliasCache::remove ( NodeAlias alias )

Remove an alias from an alias cache.

This method does not call the remove_callback method passed in at construction since it is a deliberate call not requiring notification.

Parameters

alias 12-bit alias associated with Node ID

Definition at line 416 of file AliasCache.cxx.

◆ retrieve()

bool openlcb::AliasCache::retrieve	(	unsigned	entry,
		NodeID *	node,
		NodeAlias *	alias
	)

Retrieves an entry by index.

Allows stable iteration in the face of changes.

Parameters

entry	is between 0 and size() - 1.
node	will be filled with the node ID. May be null.
alias	will be filled with the alias. May be null.

Returns: true if the entry is valid, and node and alias were filled, otherwise false if the entry is not allocated.

Definition at line 457 of file AliasCache.cxx.

◆ size()

size_t openlcb::AliasCache::size ( )

inline

Returns the total number of aliases that can be cached.

Definition at line 151 of file AliasCache.hxx.

◆ touch()

void openlcb::AliasCache::touch ( Metadata * metadata )

private

Update the time stamp for a given entry.

Parameters

metadata metadata associated with the entry

Definition at line 584 of file AliasCache.cxx.

Friends And Related Symbol Documentation

◆ PoolIdx

friend class PoolIdx

friend

Definition at line 192 of file AliasCache.hxx.

Member Data Documentation

◆ aliasMap

AliasMap openlcb::AliasCache::aliasMap

private

Map of alias to corresponding Metadata.

Definition at line 343 of file AliasCache.hxx.

◆ context

void* openlcb::AliasCache::context

private

context pointer to pass in with remove_callback

Definition at line 367 of file AliasCache.hxx.

◆ entries

size_t openlcb::AliasCache::entries

private

How many metadata entries have we allocated.

Definition at line 361 of file AliasCache.hxx.

◆ freeList

PoolIdx openlcb::AliasCache::freeList

private

list of unused mapping entries (index into pool)

Definition at line 349 of file AliasCache.hxx.

◆ idMap

IdMap openlcb::AliasCache::idMap

private

Map of Node ID to corresponding Metadata.

Definition at line 346 of file AliasCache.hxx.

◆ newest

PoolIdx openlcb::AliasCache::newest

private

newest, most recently touched entry (index into pool)

Definition at line 355 of file AliasCache.hxx.

◆ NONE_ENTRY

constexpr uint16_t openlcb::AliasCache::NONE_ENTRY = 0xFFFFu

staticconstexpr

Sentinel entry for empty lists.

Definition at line 113 of file AliasCache.hxx.

◆ oldest

PoolIdx openlcb::AliasCache::oldest

private

oldest untouched entry (index into pool)

Definition at line 352 of file AliasCache.hxx.

◆ pool

Metadata* openlcb::AliasCache::pool

private

pointer to allocated Metadata pool

Definition at line 253 of file AliasCache.hxx.

◆ removeCallback

void(* openlcb::AliasCache::removeCallback) (NodeID id, NodeAlias alias, void *)

private

callback function to be used when we remove an entry from the cache

Definition at line 364 of file AliasCache.hxx.

◆ seed

NodeID openlcb::AliasCache::seed

private

Seed for the generation of the next alias.

Definition at line 358 of file AliasCache.hxx.

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

Classes

Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ AliasMap

◆ IdMap

Constructor & Destructor Documentation

◆ AliasCache()

◆ ~AliasCache()

Member Function Documentation

◆ add()

◆ check_consistency()

◆ clear()

◆ for_each()

◆ generate()

◆ lookup() [1/2]

◆ lookup() [2/2]

◆ next_entry()

◆ remove()

◆ retrieve()

◆ size()

◆ touch()

Friends And Related Symbol Documentation

◆ PoolIdx

Member Data Documentation

◆ aliasMap

◆ context

◆ entries

◆ freeList

◆ idMap

◆ newest

◆ NONE_ENTRY

◆ oldest

◆ pool

◆ removeCallback

◆ seed