UtlHashBag Class Reference

#include <UtlHashBag.h>

Inheritance diagram for UtlHashBag:

Collaboration diagram for UtlHashBag:

Public Member Functions
	UtlHashBag ()
virtual	~UtlHashBag ()
virtual UtlContainable *	insert (UtlContainable *object)
virtual UtlContainable *	remove (UtlContainable *object)
virtual UtlContainable *	removeReference (const UtlContainable *object)
virtual UtlBoolean	destroy (UtlContainable *object)
virtual void	destroyAll ()
virtual void	removeAll ()
virtual UtlContainable *	find (const UtlContainable *object) const
size_t	entries () const
UtlBoolean	isEmpty () const
UtlBoolean	contains (const UtlContainable *object) const
virtual UtlContainableType	getContainableType () const
size_t	numberOfBuckets () const
	The current number of buckets in the hash. More...
Public Member Functions inherited from UtlContainer
	UtlContainer ()
virtual	~UtlContainer ()
virtual unsigned	hash () const
virtual int	compareTo (const UtlContainable *otherObject) const
Public Member Functions inherited from UtlContainable
virtual	~UtlContainable ()
unsigned	directHash () const
	Provides a hash function that uses the object pointer as the hash value. More...
virtual UtlBoolean	isEqual (UtlContainable const *) const
	Test this object to another object for equality. More...
virtual UtlBoolean	isInstanceOf (const UtlContainableType type) const
	Determine if this object is a derivative of the specified UtlContainableType. More...

Static Public Attributes
static UtlContainableType	TYPE = "UtlHashBag"
Static Public Attributes inherited from UtlContainer
static const UtlContainableType	TYPE = "UtlContainer"
Static Public Attributes inherited from UtlContainable
static const UtlContainableType	TYPE = "UtlContainable"

Protected Member Functions
void	notifyIteratorsOfRemove (const UtlLink *pair)
void	resizeIfNeededAndSafe ()
	If the Hash is too full, add additional buckets. More...
Protected Member Functions inherited from UtlContainer
void	addIterator (UtlIterator *newIterator) const
	Add an iterator to the list to be notified of changes to this container. More...
void	removeIterator (UtlIterator *existingIterator) const
	Called from iterator destructor to prevent further notices. More...
void	invalidateIterators ()
	Call the invalidate method on all iterators. More...

Protected Attributes
size_t	mElements
	number of UtlContainable objects in this UtlHashMap More...
size_t	mBucketBits
	number of bits used to index the buckets More...
UtlChain *	mpBucket
	an array of 2**n UtlChain elements, each used as a list header. More...
Protected Attributes inherited from UtlContainer
OsBSem	mContainerLock
	Must be taken when making any change to container state. More...
UtlChain	mIteratorList

Friends
class	UtlHashBagIterator

Additional Inherited Members
Static Public Member Functions inherited from UtlContainer
static void	acquireIteratorConnectionLock ()
	Lock the linkage between containers and iterators. More...
static void	releaseIteratorConnectionLock ()
	Unlock the linkage between containers and iterators. More...
Static Public Member Functions inherited from UtlContainable
static unsigned	stringHash (char const *value)
	Provides a hash function appropriate for null-terminated string values. More...
static UtlBoolean	areSameTypes (const UtlContainableType type1, const UtlContainableType type2)
	Are UtlContainable types the same. More...

Detailed Description

A UtlHashBag is an orderless container that efficiently allows for both random access and iteration.

Constructor & Destructor Documentation

UtlHashBag

(

)

Constructor

Design Notes

Each entry in the dynamic mBucket array is a list header for the items in that bucket. The bucket number for an item is its hash code, XOR-folded to the mBucketBits The entries in each bucket list are sorted into ascending order, so that the worst case lookup performance (when all items hash to the same bucket) is no worse than a linear search (if the hash functions are any good, it should almost always be better).

~UtlHashBag ( )

virtual

Destructor

Member Function Documentation

UtlContainable * insert ( UtlContainable *  object )

virtual

Insert the designated object into this container.

Returns

the given object on success otherwise null.

Implements UtlContainer.

UtlContainable * remove ( UtlContainable *  object )

virtual

Remove one matching object from this container.

Returns

the removed object if a match was found, otherwise NULL.

UtlContainable * removeReference ( const UtlContainable *  object )

virtual

Remove the designated object by reference (as opposed to searching for an equality match).

Returns

the object if successful, otherwise null

Removed the designated object by reference (as opposed to searching for an equality match).

Returns

the object if successful, otherwise null

Implements UtlContainer.

UtlBoolean destroy ( UtlContainable *  object )

virtual

Removes one matching object from the bag and deletes the object

Returns

true if a match was found, false if not

Implements UtlContainer.

void destroyAll ( )

virtual

Removes all elements from the container and deletes each one.

Implements UtlContainer.

void removeAll ( )

virtual

Removes all elements from the container without freeing the objects.

Implements UtlContainer.

UtlContainable * find ( const UtlContainable *  object ) const

virtual

Return the designated object if found, otherwise null.

Implements UtlContainer.

size_t entries ( ) const

virtual

Return the total number of elements within the container.

Implements UtlContainer.

UtlBoolean isEmpty ( void  ) const

virtual

Return true of the container is empty (entries() == 0), otherwise false.

Implements UtlContainer.

UtlBoolean contains ( const UtlContainable *  object ) const

virtual

Return true if the container includes the designated object. Each element within the list is tested for equality against the designated object using the equals() method.

Implements UtlContainer.

UtlContainableType getContainableType ( ) const

virtual

Get the ContainableType for the hash bag as a contained object.

Reimplemented from UtlContainer.

size_t numberOfBuckets ( ) const

inline

The current number of buckets in the hash.

void notifyIteratorsOfRemove ( const UtlLink *  pair )

protected

void resizeIfNeededAndSafe ( )

inlineprotected

If the Hash is too full, add additional buckets.

Assumes that the caller is holding the mContainerLock.

This calls resize to actually do the resize if it is safe.

Friends And Related Function Documentation

friend class UtlHashBagIterator

friend

Member Data Documentation

const UtlContainableType TYPE = "UtlHashBag"

static

size_t mElements

protected

number of UtlContainable objects in this UtlHashMap

size_t mBucketBits

protected

number of bits used to index the buckets

UtlChain* mpBucket

protected

an array of 2**n UtlChain elements, each used as a list header.