HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC > Class Template Reference

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)
 
virtual ~UT_IndexedHashMapT ()
 
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
 
virtual uint hash (const InternalKeyT *key) const
 Methods for keys. More...
 
virtual bool areKeysEqual (const InternalKeyT *k1, const InternalKeyT *k2) const
 
virtual InternalKeyTcopyKey (const InternalKeyT *key) const
 
virtual void deleteKey (InternalKeyT *key) const
 
virtual InternalItemTnewItem (const InternalKeyT *key) const
 
virtual void deleteItem (InternalItemT *item) const
 
virtual bool isItemLessThan (const InternalItemT *a, const InternalItemT *b) const
 
- 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 152 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 189 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>
virtual UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::~UT_IndexedHashMapT ( )
inlinevirtual

Definition at line 192 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 218 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
idItem index
incThe 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 229 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
idItem index
incThe 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 231 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>
virtual bool UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::areKeysEqual ( const InternalKeyT k1,
const InternalKeyT k2 
) const
inlineprotectedvirtual

Implements UT_IndexedHashMap.

Definition at line 170 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 162 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 164 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 158 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 160 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>
virtual InternalKeyT* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::copyKey ( const InternalKeyT key) const
inlineprotectedvirtual

Implements UT_IndexedHashMap.

Definition at line 173 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>
virtual void UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::deleteItem ( InternalItemT item) const
inlineprotectedvirtual

Implements UT_IndexedHashMap.

Definition at line 182 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>
virtual void UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::deleteKey ( InternalKeyT key) const
inlineprotectedvirtual

Implements UT_IndexedHashMap.

Definition at line 175 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 333 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 341 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 363 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 237 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 249 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 242 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 254 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 277 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 202 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)
{
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 271 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>
virtual uint UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::hash ( const InternalKeyT key) const
inlineprotectedvirtual

Methods for keys.

Implements UT_IndexedHashMap.

Definition at line 168 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>
virtual bool UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::isItemLessThan ( const InternalItemT a,
const InternalItemT b 
) const
inlineprotectedvirtual

Implements UT_IndexedHashMap.

Definition at line 184 of file UT_IndexedHashMapT.h.

template<typename KEY, typename ITEM, typename DEFER_ALLOC = ut_IndexedHashMapDeferNullAlloc>
virtual InternalItemT* UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC >::newItem ( const InternalKeyT key) const
inlineprotectedvirtual

Implements UT_IndexedHashMap.

Definition at line 178 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 376 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 378 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 372 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 374 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 284 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 289 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 383 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 308 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 325 of file UT_IndexedHashMapT.h.


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