The hash table class is the basis for implementing the PSet and PDictionary classes. More...

#include <dict.h>

Inheritance diagram for PHashTable:

Collaboration diagram for PHashTable:

Public Member Functions
Construction
	PHashTable ()
	Create a new, empty, hash table. More...

Overrides from class PObject
virtual Comparison	Compare (const PObject &obj) const
	Get the relative rank of the two hash tables. More...

Overrides from class PContainer
virtual PBoolean	SetSize (PINDEX newSize)
	This function is meaningless for hash table. More...

New functions for class
PINLINE PBoolean	AbstractContains (const PObject &key) const
	Determine if the value of the object is contained in the hash table. More...

virtual const PObject &	AbstractGetKeyAt (PINDEX index) const
	Get the key in the hash table at the ordinal index position. More...

virtual PObject &	AbstractGetDataAt (PINDEX index) const
	Get the data in the hash table at the ordinal index position. More...

Public Member Functions inherited from PCollection
	PCollection (PINDEX initialSize=0)
	Create a new collection. More...

virtual void	PrintOn (ostream &strm) const
	Print the collection on the stream. More...

virtual PINDEX	Append (PObject *obj)=0
	Append a new object to the collection. More...

virtual PINDEX	Insert (const PObject &before, PObject *obj)=0
	Insert a new object immediately before the specified object. More...

virtual PINDEX	InsertAt (PINDEX index, PObject *obj)=0
	Insert a new object at the specified ordinal index. More...

virtual PBoolean	Remove (const PObject *obj)=0
	Remove the object from the collection. More...

__inline void	remove (const PObject *obj)

virtual PObject *	RemoveAt (PINDEX index)=0
	Remove the object at the specified ordinal index from the collection. More...

virtual void	RemoveAll ()
	Remove all of the elements in the collection. More...

__inline void	clear ()

virtual PBoolean	SetAt (PINDEX index, PObject *val)=0
	Set the object at the specified ordinal position to the new value. More...

virtual PObject *	GetAt (PINDEX index) const =0
	Get the object at the specified ordinal position. More...

virtual PINDEX	GetObjectsIndex (const PObject *obj) const =0
	Search the collection for the specific instance of the object. More...

virtual PINDEX	GetValuesIndex (const PObject &obj) const =0
	Search the collection for the specified value of the object. More...

PINLINE void	AllowDeleteObjects (PBoolean yes=true)
	Allow or disallow the deletion of the objects contained in the collection. More...

void	DisallowDeleteObjects ()
	Disallow the deletion of the objects contained in the collection. More...

Public Member Functions inherited from PContainer
	PContainer (PINDEX initialSize=0)
	Create a new unique container. More...

	PContainer (const PContainer &cont)
	Create a new refernce to container. More...

PContainer &	operator= (const PContainer &cont)
	Assign one container reference to another. More...

virtual	~PContainer ()
	Destroy the container class. More...

virtual PINDEX	GetSize () const
	Get the current size of the container. More...

__inline size_t	size () const

PBoolean	SetMinSize (PINDEX minSize)
	Set the minimum size of container. More...

virtual PBoolean	IsEmpty () const
	Determine if the container is empty. More...

__inline bool	empty () const

PBoolean	IsUnique () const
	Determine if container is unique reference. More...

virtual PBoolean	MakeUnique ()
	Make this instance to be the one and only reference to the container contents. More...

Public Member Functions inherited from PObject
unsigned	GetTraceContextIdentifier () const
	Get PTRACE context identifier. More...

void	SetTraceContextIdentifier (unsigned id)

void	GetTraceContextIdentifier (PObject &obj)

void	GetTraceContextIdentifier (PObject *obj)

void	SetTraceContextIdentifier (const PObject &obj)

void	SetTraceContextIdentifier (const PObject *obj)

virtual	~PObject ()

virtual PObject *	Clone () const
	Create a copy of the class on the heap. More...

template<class CLS >
CLS *	CloneAs () const
	As for Clone() but converts to specified type. More...

virtual PINDEX	HashFunction () const
	This function yields a hash value required by the `PDictionary` class. More...

virtual Comparison	CompareObjectMemoryDirect (const PObject &obj) const
	Determine the byte wise comparison of two objects. More...

bool	operator== (const PObject &obj) const
	Compare the two objects. More...

bool	operator!= (const PObject &obj) const
	Compare the two objects. More...

bool	operator< (const PObject &obj) const
	Compare the two objects. More...

bool	operator> (const PObject &obj) const
	Compare the two objects. More...

bool	operator<= (const PObject &obj) const
	Compare the two objects. More...

bool	operator>= (const PObject &obj) const
	Compare the two objects. More...

virtual const char *	GetClass (unsigned ancestor=0) const
	Get the current dynamic type of the object instance. More...

PBoolean	IsClass (const char *cls) const

virtual PBoolean	InternalIsDescendant (const char *clsName) const
	Determine if the dynamic type of the current instance is a descendent of the specified class. More...

__inline const PObject *	PTraceObjectInstance () const

virtual void	ReadFrom (istream &strm)
	Input the contents of the object from the stream. More...

Public Attributes
PHashTableInfo *	hashTable

Additional Inherited Members
Public Types inherited from PObject
enum	Comparison { LessThan = -1, EqualTo = 0, GreaterThan = 1 }
	Result of the comparison operation performed by the `Compare()` function. More...

Static Public Member Functions inherited from PObject
static Comparison	InternalCompareObjectMemoryDirect (const PObject obj1, const PObject obj2, PINDEX size)
	Internal function caled from CompareObjectMemoryDirect() More...

static const char *	Class ()
	Get the name of the class as a C string. More...

static __inline const PObject *	PTraceObjectInstance (const char *)

static __inline const PObject *	PTraceObjectInstance (const PObject *obj)

Protected Member Functions inherited from PCollection
PINLINE	PCollection (int dummy, const PCollection *coll)
	Constructor used in support of the Clone() function. More...

Protected Attributes inherited from PContainer
PContainerReference *	reference

Friends inherited from PObject

Detailed Description

The hash table class is the basis for implementing the PSet and PDictionary classes.

The hash table allows for very fast searches for an object based on a "hash function". This function yields an index into an array which is directly looked up to locate the object. When two key values have the same hash function value, then a linear search of a linked list is made to locate the object. Thus the efficiency of the hash table is highly dependent on the quality of the hash function for the data being used as keys.

Constructor & Destructor Documentation

PHashTable::PHashTable ( )

Create a new, empty, hash table.

Member Function Documentation

PINLINE PBoolean PHashTable::AbstractContains ( const PObject & key ) const

Determine if the value of the object is contained in the hash table.

The object values are compared, not the pointers. So the objects in the collection must correctly implement the PObject::Compare() function. The hash table is used to locate the entry.

Returns: true if the object value is in the set.

Parameters

key	Key to look for in the set.

Referenced by PSet< PString >::Contains(), PDictionary< K, PString >::Contains(), and PSet< PString >::operator[]().

virtual PObject& PHashTable::AbstractGetDataAt ( PINDEX index ) const

virtual

Get the data in the hash table at the ordinal index position.

The ordinal position in the hash table is determined by the hash values of the keys and the order of insertion.

WARNING: this code requires a linear search for every operation and will be VERY slow for large data sets. This function is kept for backwards compatibilty only. New code should use the iterator based access methods

This function is primarily used by the descendent template classes, or macro, with the appropriate type conversion.

Returns: reference to key at the index position.

Parameters

index Ordinal position in the hash table.

Referenced by PDictionary< K, PString >::GetDataAt(), and POrdinalDictionary< K >::GetDataAt().

virtual const PObject& PHashTable::AbstractGetKeyAt ( PINDEX index ) const

virtual

Get the key in the hash table at the ordinal index position.

The ordinal position in the hash table is determined by the hash values of the keys and the order of insertion.

WARNING: this code requires a linear search for every operation and will be VERY slow for large data sets. This function is kept for backwards compatibilty only. New code should use the iterator based access methods

This function is primarily used by the descendent template classes, or macro, with the appropriate type conversion.

Returns: reference to key at the index position.

Parameters

index Ordinal position in the hash table.

Referenced by PSet< PString >::GetKeyAt(), PDictionary< K, PString >::GetKeyAt(), POrdinalDictionary< K >::GetKeyAt(), and POrdinalDictionary< K >::SetDataAt().

virtual Comparison PHashTable::Compare ( const PObject & obj ) const

virtual

Get the relative rank of the two hash tables.

Actally ranking hash tables is really meaningless, so only equality is returned by the comparison. Equality is only achieved if the two instances reference the same hash table.

Returns: comparison of the two objects, EqualTo if the same reference and GreaterThan if not.

Parameters

obj	Other PHashTable to compare against.

Reimplemented from PObject.

virtual PBoolean PHashTable::SetSize ( PINDEX newSize )

virtual

This function is meaningless for hash table.

The size of the collection is determined by the addition and removal of objects. The size cannot be set in any other way.

Returns: Always true.

Parameters

newSize New size for the hash table, this is ignored.

Implements PContainer.

Member Data Documentation

PHashTableInfo* PHashTable::hashTable

Referenced by PSet< PString >::begin(), and PSet< PString >::find().

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

dict.h

Public Member Functions

Public Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation