A thread-safe hash map which stores indexed shared items. More...

#include <UT_IndexedHashMapT.h>

Inheritance diagram for UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >:

Public Member Functions
	UT_IndexedHashMapT (bool store_ids=true)

	~UT_IndexedHashMapT () override

int64	getMemoryUsage (bool inclusive) const

ITEM *	add (const KEY &key, ITEM item=NULL, UT_IndexedHashMapItemId id=NULL)

ITEM *	find (const KEY &key) const

UT_IndexedHashMapItemId	findId (const KEY &key) const

ITEM *	find (const KEY &key, UT_IndexedHashMapItemId &id) const

ITEM *	get (UT_IndexedHashMapItemId id) const

ITEM *	getOrderedItem (exint index, UT_IndexedHashMapItemId *id=NULL) const

const KEY *	getKey (UT_IndexedHashMapItemId id) const

bool	remove (const KEY &key)

bool	remove (UT_IndexedHashMapItemId id)

UT_IndexedHashMapItemId	replaceItem (UT_IndexedHashMapItemId id, const KEY &key, ITEM *item=NULL)

UT_IndexedHashMapItemId	replaceItem (const KEY &old_key, const KEY &new_key)

exint	extractItems (UT_Array< UT_IndexedHashMapItemId > &ids, UT_Array< ITEM * > &items) const

exint	extractItems (UT_Array< UT_IndexedHashMapItemId > &ids, UT_Array< ITEM * > &items, exint maxitems) const

exint	extractItems (UT_Array< ITEM * > &items) const

void	replace (const UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC > &src)
	Replaces the content of this with the content of src. More...


ITEM *	addReference (UT_IndexedHashMapItemId id, int inc)

ITEM *	addReference (UT_IndexedHashMapItemId id)


ITEM *	operator[] (UT_IndexedHashMapItemId id) const

ITEM *	operator[] (const KEY &k) const

ITEM *	operator() (UT_IndexedHashMapItemId id) const

ITEM *	operator() (const KEY &k) const

Public Member Functions inherited from UT_IndexedHashMap
	UT_IndexedHashMap (bool store_ids)

virtual	~UT_IndexedHashMap ()

void	clear ()

exint	entries () const

bool	empty () const
	Return whether the map is empty. More...

int64	getMemoryUsage (bool inclusive) const
	Return approximate memory usage (not including key or item storage) More...

UT_IndexedHashMapItemId	getItemIdUpperBound () const

fpreal	getOccupancy () const

bool	compactIds (IdRemapping &remapping)

bool	sortItems ()

exint	getReferenceCount (UT_IndexedHashMapItemId id) const

unsafe_iterator	begin () const

unsafe_iterator	end () const

unsafe_listiterator	beginList () const

unsafe_listiterator	endList () const

Protected Member Functions
SYS_FORCE_INLINE KEY *	castKEY (InternalKeyT *key) const

SYS_FORCE_INLINE const KEY *	castKEY (const InternalKeyT *key) const

SYS_FORCE_INLINE ITEM *	castITEM (InternalItemT *item) const

SYS_FORCE_INLINE const ITEM *	castITEM (const InternalItemT *item) const

uint	hash (const InternalKeyT *key) const override
	Methods for keys. More...

bool	areKeysEqual (const InternalKeyT k1, const InternalKeyT k2) const override

InternalKeyT *	copyKey (const InternalKeyT *key) const override

void	deleteKey (InternalKeyT *key) const override

InternalItemT *	newItem (const InternalKeyT *key) const override

void	deleteItem (InternalItemT *item) const override

bool	isItemLessThan (const InternalItemT a, const InternalItemT b) const override

Protected Member Functions inherited from UT_IndexedHashMap
void	_replace (const UT_IndexedHashMap &src)

InternalItemT *	_add (const InternalKeyT key, InternalItemT item=NULL, UT_IndexedHashMapItemId *id=NULL)

InternalItemT *	_addReference (UT_IndexedHashMapItemId id, int inc)

InternalItemT *	_addReference (UT_IndexedHashMapItemId id)

InternalItemT *	_find (const InternalKeyT *key) const

exint	_findId (const InternalKeyT *key) const

InternalItemT *	_findItemAndId (const InternalKeyT *key, UT_IndexedHashMapItemId &id) const

InternalItemT *	_get (UT_IndexedHashMapItemId id) const

const InternalKeyT *	_getKey (UT_IndexedHashMapItemId id) const

InternalItemT *	_getOrderedItem (exint index, UT_IndexedHashMapItemId *id) const

bool	_remove (const InternalKeyT *key)

bool	_remove (UT_IndexedHashMapItemId id)

UT_IndexedHashMapItemId	_replaceItem (UT_IndexedHashMapItemId id, const InternalKeyT key, InternalItemT new_item=NULL)

exint	_extractItems (UT_Array< UT_IndexedHashMapItemId > &ids, UT_Array< InternalItemT * > &items, exint maxitems) const

exint	_extractItems (UT_Array< UT_IndexedHashMapItemId > &ids, UT_Array< InternalItemT * > &items) const

exint	_extractItems (UT_Array< InternalItemT * > &items) const

Additional Inherited Members
Public Types inherited from UT_IndexedHashMap
typedef void	InternalKeyT

typedef void	InternalItemT

Protected Types inherited from UT_IndexedHashMap
typedef UT_ConcurrentHashMap < keyContainer, itemContainer *, keyCompare >	UT_IndexedHashMapTable

typedef UT_ConcurrentVector < listContainer >	UT_IndexedHashMapVector

typedef UT_ConcurrentQueue < UT_IndexedHashMapItemId >	UT_IndexedHashMapHoleQueue

Detailed Description

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>
class UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >

A thread-safe hash map which stores indexed shared items.

Each item in the hash map is reference counted. That is, if objects are added multiple times, only a single object will be stored in the map.

Removing an item from the hash map (by id or key) will decrement the reference count on the item. When no longer referenced, the map will automatically delete the item.

As items are added to the map, each is assigned a unique id (UT_IndexedHashMapItemId). Items can then be retrieved efficiently from the map using the id (UT_IndexedHashMapT::get()).

Many methods on the map are thread-safe, though some are not. The thread safety of the methods is described in the comments.

The KEY template parameter needs to have:

KEY(const KEY &src);                        // The copy constructor
uint        hash() const;                   // A hash method
bool        isEqual(const KEY &src) const;  // A comparison operator

For sorting, there should be a < operator defined on items.

When adding items to an indexed hash map, only a single item is every created for duplicate keys. To optimize addition, items can be created only if the item will be added to the map. This is done through the DEFER_ALLOC template parameter. With the default argument (which doesn't allow deferred allocation), ITEM objects must be passed in the add() method.

Definition at line 125 of file UT_IndexedHashMapT.h.

Constructor & Destructor Documentation

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::UT_IndexedHashMapT ( bool store_ids = true )

inline

Definition at line 162 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::~UT_IndexedHashMapT ( )

inlineoverride

Definition at line 165 of file UT_IndexedHashMapT.h.

Member Function Documentation

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::add	(	const KEY &	key,
		ITEM *	item = `NULL`,
		UT_IndexedHashMapItemId *	id = `NULL`
	)

inline

Add a new item to the map, returning the item actually stored in the map. This may not be the item passed in if the map already contains the object.

If the item passed in is NULL, an item will be allocated using the deferred allocator (see the DEFER_ALLOC template argument). The default allocator does not allow for deferred construction and requires the item to be passed in.

Note: This is thread-safe

Definition at line 191 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::addReference	(	UT_IndexedHashMapItemId	id,
		int	inc
	)

inline

Add reference to an existing item.

Parameters

id	Item index
inc	The number of references to add. It defaults to 1. If negative, the item may be removed in which case it returns 0.

Note: This item is thread-safe provided the item is exists in the map

Definition at line 202 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::addReference ( UT_IndexedHashMapItemId id )

inline

Add reference to an existing item.

Parameters

id	Item index
inc	The number of references to add. It defaults to 1. If negative, the item may be removed in which case it returns 0.

Note: This item is thread-safe provided the item is exists in the map

Definition at line 204 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

bool UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::areKeysEqual	(	const InternalKeyT *	k1,
		const InternalKeyT *	k2
	)		const

inlineoverrideprotectedvirtual

Implements UT_IndexedHashMap.

Definition at line 143 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

SYS_FORCE_INLINE ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::castITEM ( InternalItemT * item ) const

inlineprotected

Definition at line 135 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

SYS_FORCE_INLINE const ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::castITEM ( const InternalItemT * item ) const

inlineprotected

Definition at line 137 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

SYS_FORCE_INLINE KEY* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::castKEY ( InternalKeyT * key ) const

inlineprotected

The indexed hash map maintains all operations on internal types. This allows the bulk of the code to be shared between template instantiations.

Definition at line 131 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

SYS_FORCE_INLINE const KEY* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::castKEY ( const InternalKeyT * key ) const

inlineprotected

Definition at line 133 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

InternalKeyT* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::copyKey ( const InternalKeyT * key ) const

inlineoverrideprotectedvirtual

Implements UT_IndexedHashMap.

Definition at line 146 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

void UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::deleteItem ( InternalItemT * item ) const

inlineoverrideprotectedvirtual

Implements UT_IndexedHashMap.

Definition at line 155 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

void UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::deleteKey ( InternalKeyT * key ) const

inlineoverrideprotectedvirtual

Implements UT_IndexedHashMap.

Definition at line 148 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

exint UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::extractItems	(	UT_Array< UT_IndexedHashMapItemId > &	ids,
		UT_Array< ITEM * > &	items
	)		const

inline

Extract the items into a list of ids and pointers to items. Items will be appended to the lists. The function returns the number of items added.

Note: This is not thread-safe

Definition at line 306 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

exint UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::extractItems	(	UT_Array< UT_IndexedHashMapItemId > &	ids,
		UT_Array< ITEM * > &	items,
		exint	maxitems
	)		const

inline

Definition at line 314 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

exint UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::extractItems ( UT_Array< ITEM * > & items ) const

inline

Extract an array of pointers to items.

If there are id's associated with the items, the items will be stored at their indexed location. The list of items may contain NULL pointers for unused index entries.

If there are no id's, the items will be extracted in arbitrary order into a packed array.

The function returns the number of items in the array.

Note: This is not thread-safe

Definition at line 336 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::find ( const KEY & key ) const

inline

Find an item in the map.

Note: This is thread-safe

Definition at line 210 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::find	(	const KEY &	key,
		UT_IndexedHashMapItemId &	id
	)		const

inline

Find an item and its id. This is more efficient than calling find() and findId() separately. Calling find() and findId() is also not always thread-safe.

Note: This is thread-safe

Definition at line 222 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

UT_IndexedHashMapItemId UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::findId ( const KEY & key ) const

inline

Given a key, find an item's id (or -1 if not found)

Note: This is thread-safe

Definition at line 215 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::get ( UT_IndexedHashMapItemId id ) const

inline

Get the item which has the given id

Note: This is thread-safe

Definition at line 227 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

const KEY* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::getKey ( UT_IndexedHashMapItemId id ) const

inline

Get the key associated with the given id

Note: This is thread-safe

Definition at line 250 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

int64 UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::getMemoryUsage ( bool inclusive ) const

inline

Return approximate memory usage NOTE: Not including KEY or ITEM storage, even though the destructor destroys both the KEY and ITEM objects, because the caller should know better what KEY and ITEM are. If they can't vary in size, just multiply by entries(); if they can, use begin() to iterate through.

Definition at line 175 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::getOrderedItem	(	exint	index,
		UT_IndexedHashMapItemId *	id = `NULL`
	)		const

inline

Get the n'th item in the list. This skips over holes and will return items for a contiguous list of integers. For example:

for (int i = 0; ; ++i)
{
   UT_IndexedHashMapItemId    id;
   ITEM *item = map.getOrderedItem(i, &id);
   if (!item)
        break;
}

The UT_IndexedHashMapItemId's returned should be monotonic, but not contiguous. If the id parameter is non-null, the id for the item will be stored there.

Note: This is not thread-safe

Definition at line 244 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

uint UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::hash ( const InternalKeyT * key ) const

inlineoverrideprotectedvirtual

Methods for keys.

Implements UT_IndexedHashMap.

Definition at line 141 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

bool UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::isItemLessThan	(	const InternalItemT *	a,
		const InternalItemT *	b
	)		const

inlineoverrideprotectedvirtual

Implements UT_IndexedHashMap.

Definition at line 157 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

InternalItemT* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::newItem ( const InternalKeyT * key ) const

inlineoverrideprotectedvirtual

Implements UT_IndexedHashMap.

Definition at line 151 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::operator() ( UT_IndexedHashMapItemId id ) const

inline

Convenience operators

Definition at line 349 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::operator() ( const KEY & k ) const

inline

Convenience operators

Definition at line 351 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::operator[] ( UT_IndexedHashMapItemId id ) const

inline

Convenience operators

Definition at line 345 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

ITEM* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::operator[] ( const KEY & k ) const

inline

Convenience operators

Definition at line 347 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

bool UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::remove ( const KEY & key )

inline

Remove an item from the map. This dereferences the item in the map and returns true if the item was deleted from the map. The method will return false if the item was shared and is still in the map.

Note: This is thread-safe

Definition at line 257 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

bool UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::remove ( UT_IndexedHashMapItemId id )

inline

Remove the item with the given id from the map.

Note: This is thread-safe

Definition at line 262 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

void UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::replace ( const UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC > & src )

inline

Replaces the content of this with the content of src.

Definition at line 356 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

UT_IndexedHashMapItemId UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::replaceItem	(	UT_IndexedHashMapItemId	id,
		const KEY &	key,
		ITEM *	item = `NULL`
	)

inline

Replace an item at a given id.

The existing item will be deleted from the table and the new item will replace it. The method will fail if there is currently no item at the given location.

The method will return the new id for the item. Usually, this will be the same as the existing id, unless the new item already exists in the map.

If the item passed in is NULL, a new item will be called using newItem()

Warning: If the returned id does not match the id passed in, it's the user's responsibility to update any references to the new id.

Note: This is thread-safe

Definition at line 281 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>

UT_IndexedHashMapItemId UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::replaceItem	(	const KEY &	old_key,
		const KEY &	new_key
	)

inline

Replace the object given by the old_key with the value given by the new_key.

The old_key will be removed by the map.

If the map stores id's, the new_key will be assigned the same id as the old_key unless the new_key already exists in the map.

The new_key object will inherit all references of the old_key.

This method returns the id of the new item. This will be the same id as the old object unless the new_key already exists in the map.

Note: This is thread-safe

Definition at line 298 of file UT_IndexedHashMapT.h.

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

UT/UT_IndexedHashMapT.h

Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc> class UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >

Constructor & Destructor Documentation

Member Function Documentation

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>
class UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >