HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_IndexedHashMap Class Referenceabstract

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

#include <UT_IndexedHashMap.h>

+ Inheritance diagram for UT_IndexedHashMap:

Classes

class  IdRemapping
 
class  itemCompare
 
class  itemContainer
 
class  keyCompare
 
class  keyContainer
 
class  listContainer
 
class  unsafe_iterator
 Iterate over items in the map - this is arbitrary order. More...
 
class  unsafe_listiterator
 

Public Types

typedef void InternalKeyT
 
typedef void InternalItemT
 

Public Member Functions

 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 Types

typedef UT_ConcurrentHashMap
< keyContainer, itemContainer
*, keyCompare
UT_IndexedHashMapTable
 
typedef UT_ConcurrentVector
< listContainer
UT_IndexedHashMapVector
 
typedef UT_ConcurrentQueue
< UT_IndexedHashMapItemId
UT_IndexedHashMapHoleQueue
 

Protected Member Functions

virtual uint hash (const InternalKeyT *key) const =0
 
virtual bool areKeysEqual (const InternalKeyT *k1, const InternalKeyT *k2) const =0
 
virtual InternalKeyTcopyKey (const InternalKeyT *key) const =0
 
virtual void deleteKey (InternalKeyT *key) const =0
 
virtual InternalItemTnewItem (const InternalKeyT *key) const =0
 
virtual void deleteItem (InternalItemT *item) const =0
 
virtual bool isItemLessThan (const InternalItemT *a, const InternalItemT *b) const =0
 
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
 

Friends

class itemContainer
 
class keyContainer
 
class itemCompare
 

Detailed Description

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 delete the item.

When the map stores 'ids', each item is assigned a unique id (UT_IndexedHashMapItemId). The item can then be retrieved efficiently from the map using the id (UT_IndexedHashMap::get())

Many methods on the map are thread-safe. Some methods are not (and are noted 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

Definition at line 47 of file UT_IndexedHashMap.h.

Member Typedef Documentation

Definition at line 51 of file UT_IndexedHashMap.h.

Definition at line 50 of file UT_IndexedHashMap.h.

Constructor & Destructor Documentation

UT_IndexedHashMap::UT_IndexedHashMap ( bool  store_ids)

If store_ids is true, each item stored in the map will be given a unique id of type UT_IndexedHashMapItemId. These id's can be used to perform efficient lookup of items in the map.

If the store_ids parameter is false, then elements in the shared map will not store id's. The ids for the elements will always be -1 (invalid). The map won't store the structures required for indexed lookup, saving some memory and allowing some operations to be slightly more efficient. Operations which are invalid for maps that don't store id's are noted in the comments).

virtual UT_IndexedHashMap::~UT_IndexedHashMap ( )
virtual

Member Function Documentation

InternalItemT* UT_IndexedHashMap::_add ( const InternalKeyT key,
InternalItemT item = NULL,
UT_IndexedHashMapItemId id = NULL 
)
protected
InternalItemT* UT_IndexedHashMap::_addReference ( UT_IndexedHashMapItemId  id,
int  inc 
)
protected
InternalItemT* UT_IndexedHashMap::_addReference ( UT_IndexedHashMapItemId  id)
inlineprotected

Definition at line 173 of file UT_IndexedHashMap.h.

exint UT_IndexedHashMap::_extractItems ( UT_Array< UT_IndexedHashMapItemId > &  ids,
UT_Array< InternalItemT * > &  items,
exint  maxitems 
) const
protected
exint UT_IndexedHashMap::_extractItems ( UT_Array< UT_IndexedHashMapItemId > &  ids,
UT_Array< InternalItemT * > &  items 
) const
protected
exint UT_IndexedHashMap::_extractItems ( UT_Array< InternalItemT * > &  items) const
protected
InternalItemT* UT_IndexedHashMap::_find ( const InternalKeyT key) const
inlineprotected

Definition at line 176 of file UT_IndexedHashMap.h.

exint UT_IndexedHashMap::_findId ( const InternalKeyT key) const
inlineprotected

Definition at line 181 of file UT_IndexedHashMap.h.

InternalItemT* UT_IndexedHashMap::_findItemAndId ( const InternalKeyT key,
UT_IndexedHashMapItemId id 
) const
protected
InternalItemT* UT_IndexedHashMap::_get ( UT_IndexedHashMapItemId  id) const
protected
const InternalKeyT* UT_IndexedHashMap::_getKey ( UT_IndexedHashMapItemId  id) const
protected
InternalItemT* UT_IndexedHashMap::_getOrderedItem ( exint  index,
UT_IndexedHashMapItemId id 
) const
protected
bool UT_IndexedHashMap::_remove ( const InternalKeyT key)
protected
bool UT_IndexedHashMap::_remove ( UT_IndexedHashMapItemId  id)
protected
void UT_IndexedHashMap::_replace ( const UT_IndexedHashMap src)
protected
UT_IndexedHashMapItemId UT_IndexedHashMap::_replaceItem ( UT_IndexedHashMapItemId  id,
const InternalKeyT key,
InternalItemT new_item = NULL 
)
protected
unsafe_iterator UT_IndexedHashMap::begin ( void  ) const
inline

Definition at line 530 of file UT_IndexedHashMap.h.

unsafe_listiterator UT_IndexedHashMap::beginList ( ) const
inline

Definition at line 534 of file UT_IndexedHashMap.h.

void UT_IndexedHashMap::clear ( )

Clear the map

Note
This is not thread-safe
bool UT_IndexedHashMap::compactIds ( IdRemapping remapping)

Compact the list. This fills out the integer map of old id's and their new id's. If no compaction was done, the function returns false.

Note
This is not thread-safe
This is a no-op if id's are not stored in the map
bool UT_IndexedHashMap::empty ( void  ) const
inline

Return whether the map is empty.

Definition at line 88 of file UT_IndexedHashMap.h.

unsafe_iterator UT_IndexedHashMap::end ( void  ) const
inline

Definition at line 532 of file UT_IndexedHashMap.h.

unsafe_listiterator UT_IndexedHashMap::endList ( ) const
inline

Definition at line 536 of file UT_IndexedHashMap.h.

exint UT_IndexedHashMap::entries ( void  ) const
inline

Return the number of entries in the map.

Note
This is not thread-safe

Definition at line 85 of file UT_IndexedHashMap.h.

UT_IndexedHashMapItemId UT_IndexedHashMap::getItemIdUpperBound ( ) const
inline

Return the maximum possible UT_IndexedHashMapItemId stored in the map. This returns an upper bound and is not exact.

Note
This is not thread-safe
Not supported if id's are not stored in the map

Definition at line 97 of file UT_IndexedHashMap.h.

int64 UT_IndexedHashMap::getMemoryUsage ( bool  inclusive) const

Return approximate memory usage (not including key or item storage)

fpreal UT_IndexedHashMap::getOccupancy ( ) const
inline

Return the "occupancy" of the map.

Note
This is not thread-safe
Not supported if id's are not stored in the map

Definition at line 103 of file UT_IndexedHashMap.h.

exint UT_IndexedHashMap::getReferenceCount ( UT_IndexedHashMapItemId  id) const
bool UT_IndexedHashMap::sortItems ( )

Sort the list of ids based on the comparator. This method only works if the table has been compacted. Returns false if there are no ids or the list is not compacted.

Note
This is not thread-safe
This is a no-op if id's are not stored in the map

Friends And Related Function Documentation

friend class itemCompare
friend

Definition at line 365 of file UT_IndexedHashMap.h.

friend class itemContainer
friend

Definition at line 216 of file UT_IndexedHashMap.h.

friend class keyContainer
friend

Definition at line 252 of file UT_IndexedHashMap.h.


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