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
__inline unsigned	GetTraceContextIdentifier () const
	Get PTRACE context identifier. More...

__inline void	SetTraceContextIdentifier (unsigned id)

__inline void	SetTraceContextIdentifier (const PObject &obj)

__inline void	SetTraceContextIdentifier (const PObject *obj)

__inline void	CopyTraceContextIdentifier (PObject &obj) const

__inline void	CopyTraceContextIdentifier (PObject *obj) const

virtual	~PObject ()

__inline const char *	GetClass () const

__inline bool	IsClass (const char *name) const

__inline const PObject *	PTraceObjectInstance () const

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 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 __inline void	CopyTraceContextIdentifier (PObject &to, const PObject &from)

static __inline void	CopyTraceContextIdentifier (PObject &to, const PObject *from)

static __inline void	CopyTraceContextIdentifier (PObject *to, const PObject &from)

static __inline void	CopyTraceContextIdentifier (PObject to, const PObject from)

static __inline const char *	Class ()

static __inline const PObject *	PTraceObjectInstance (const char *)

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

template<typename T >
static Comparison	Compare2 (T v1, T v2)
	Compare two types, returning Comparison type. More...

static Comparison	InternalCompareObjectMemoryDirect (const PObject obj1, const PObject obj2, PINDEX size)
	Internal function caled from CompareObjectMemoryDirect() More...

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

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

	PContainer (PContainerReference &reference)
	Construct using static PContainerReference. More...

virtual void	DestroyContents ()=0
	Destroy the container contents. More...

virtual void	AssignContents (const PContainer &c)
	Copy the container contents. More...

void	CopyContents (const PContainer &c)
	Copy the container contents. More...

void	CloneContents (const PContainer *src)
	Create a duplicate of the container contents. More...

void	Destruct ()
	Internal function called from container destructors. More...

virtual void	DestroyReference ()
	Destroy the PContainerReference instance. More...

Protected Member Functions inherited from PObject
	PObject ()
	Constructor for PObject, made protected so cannot ever create one on its own. More...

Protected Attributes inherited from PContainer
PContainerReference *	reference

Protected Attributes inherited from PObject
unsigned	m_traceContextIdentifier

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