Generic abstract class to manage a hash table. A hash table is a data structure that organizes the node into several buckets, according to a hash function. The number of buckets, or table's capacity, can be adjusted anytime and is closely related to the table performance. If well defined, the hash table is capable of O(1) searches. This class provides self adjusting loads: number of elements / number of buckets. The minimum load is checked whenever a node is removed. It is useful to define how many buckets (if any) are allowed to be empty, waiting to be populated. The maximum load is checked whenever a node is inserted in the table. It is useful to limit the maximum number of elements per bucket, in average. The performance of the hash table during insertions, deletes, and searches are strongly dependent on the gcgHASHTABLE::hash() method. To solve the unavoidable collisions, fast data structures are used for each bucket. The nodes in this table must be comparable. As such, a class specialization must provide gcgHASHTABLE::compare() method that has the function of determining if two gcgORDEREDNODE nodes are equal, greater or smaller. Use the gcgHASHTABLE::getIterator() to obtain a fast iterator to traverse all table entries. More...

#include <gcg.h>

Inheritance diagram for gcgHASHTABLE:

Public Member Functions
	gcgHASHTABLE (uintptr_t capacity=0, float minload=0.8, float maxload=16.0)
	Constructs a valid hash table. All the parameters of the constructor are crucial for table performance. More...

virtual	~gcgHASHTABLE ()
	Destroys the hash table, releasing all nodes. All entries are deleted. More...

bool	setCapacity (uintptr_t capacity)
	Sets the number of buckets of the table. If the table is already populated with nodes, it adjusts the table to the new capacity. If capacity is zero and the table is not populated, all hash table resources are released. If capacity is zero and the table is populated, a warning is issued. More...

bool	setLoadLimits (float minload, float maxload)
	Sets the minimum and maximum loads that the table is allowed to have after removals and insertions, respectively. Minimum value must be smaller than maximum value. If they are close to another, insertions and removals might become very inefficient because of frequent table capacity adjustments. If minimum and maximum loads are valid, the current load is checked against them. If outside the load interval, the capacity of the table is adjusted. More...

uintptr_t	getCounter ()
	Returns the number of elements stored in the hash table. More...

bool	deleteAll ()
	Deletes and removes all entries from the hash table. All resources used by the hash table are also released. More...

gcgITERATOR *	getIterator (int traversemode=0)
	Returns an iterator for traversing the elements of the hash table. The traversal order is defined by the parameter traversemode. Currently, the order of iteration depends on the internal data structure (AVL trees). The parameter traversemode is just passed to the secondary data structures whenever a sub-iterator is needed. The hash table must not be changed by insertions, removals or moves while the iterator is being used. You must delete the returned iterator after use. The iterator copies a minimal information from the internal hash table. Note that deleting an iterator does not affect the nodes. More...

gcgITERATOR *	detach (int traversemode=0)
	Force the hash table to be empty. It has the same effect as removing all entries from the hash table but keeping their chaining (which must be used by the returned iterator). The entries are NOT deleted. In order to retrieve the detached entries, a gcgITERATOR is returned. This is useful to process the nodes freely and without the possible restrictions of the underlying hash table. Thus, the gcgITERATOR returned by gcgHASHTABLE::detach() MUST be used to delete all the entries or reinsert them into another data structure. The traversal order of the returned iterator is defined by the parameter traversemode. Currently, the order of iteration depends on the internal data structure (AVL trees). The parameter traversemode is just passed to the secondary data structures. All resources currently used by the hash table are released (becomes empty) but it can be reused normally. You must delete the gcgITERATOR after its use. More...

gcgORDEREDNODE *	insert (gcgORDEREDNODE *newnode)
	Inserts a new entry newnode in the hash table. All nodes in the table must be unique, i.e., they are mutually different in respect to gcgHASHTABLE::compare() method. More...

gcgORDEREDNODE *	search (gcgORDEREDNODE *key)
	Retrieves the entry of the hash table that is similar to the key in respect to the gcgHASHTABLE::compare() method. The gcgHASHTABLE::compare() method must return zero only for an unique node of the tree. The method gcgHASHTABLE::hash() is called once to find node's bucket. More...

gcgORDEREDNODE *	remove (gcgORDEREDNODE *key)
	Removes the entry of the hash table that is similar to the key in respect to the gcgHASHTABLE::compare() method. The gcgHASHTABLE::compare() method must return zero only for an unique node of the table. The internal data structures are automatically adjusted after the removal. If a minimum value for table load is positive (see gcgHASHTABLE::setLoadLimits()), the current load is computed and checked against that minimum load. If the current load is lesser, the table's capacity is reduced in order to put the current load in the valid interval. The method gcgHASHTABLE::hash() might be called several times to find node and to adjust the table load. More...

virtual int	compare (gcgORDEREDNODE refnode1, gcgORDEREDNODE refnode2)=0
	Method that must be furnished by a specialization of gcgHASHTABLE and is responsible for comparing two gcgORDEREDNODE nodes. This is necessary for all operations of insertion, retrieval and removal. It must compare the two nodes pointed by refnode1 and refnode2 and return zero if they are equal, -1 if refnode1 is smaller or precedes refnode2, or 1 if refnode1 is greater or succeeds refnode2. More...

virtual long	hash (gcgORDEREDNODE *node)=0
	Method that must be furnished by a specialization of gcgHASHTABLE and is responsible for computing an integer hash value for the node node. This is necessary for all operations of insertion, retrieval and removal. The performance of the hash table is highly dependent on the capacity of the gcgHASHTABLE::hash() method to spread distinct nodes over the long integer numbers. More...

Public Member Functions inherited from gcgCLASS
void *	operator new (size_t size)
	Defines a new operator to be used by instatiations of GCGlib classes instead the global one. More...

void *	operator new (size_t size, const std::nothrow_t &) throw ()
	Defines a new operator to be used by instantiations of GCGlib classes instead the global one. Returns a NULL pointer instead of throwing an exception if an error occurs. More...

void *	operator new[] (size_t size)
	Defines a new operator to be used by GCGlib array allocations instead the global one. More...

void *	operator new[] (size_t size, const std::nothrow_t &) throw ()
	Defines a new operator to be used by vector allocations instead the global one. More...

void	operator delete (void *p)
	Defines a delete operator to free instances of GCGlib classes instead the global one. It is designed to match the new operator. More...

void	operator delete (void *p, const std::nothrow_t &) throw ()
	Defines a delete operator to free instances of GCGlib classes instead the global one. It is designed to match the new operator. More...

void	operator delete[] (void *p)
	Defines a delete operator to free instances of arrays for GCGlib classes instead the global one. It is designed to match the new[] operator. More...

void	operator delete[] (void *p, const std::nothrow_t &) throw ()
	Defines a delete operator to free instances of arrays for GCGlib classes instead the global one. It is designed to match the new[] operator. More...

Public Attributes
uintptr_t	counter
	Number of elements in this table. Read-only.

uintptr_t	capacity
	Capacity of this table or maximum number of elements of the table without collisions. Read-only.

float	minimumload
	Minimum load of this table. The table capacity will be adjusted to this minimum counter/capacity ratio. Read-only.

float	maximumload
	Maximum load of this table. The table capacity will be adjusted to this maximum counter/capacity ratio. Read-only.

gcgCLASS **	table
	Table of data structures. Internal use only.

Detailed Description

Generic abstract class to manage a hash table. A hash table is a data structure that organizes the node into several buckets, according to a hash function. The number of buckets, or table's capacity, can be adjusted anytime and is closely related to the table performance. If well defined, the hash table is capable of O(1) searches. This class provides self adjusting loads: number of elements / number of buckets. The minimum load is checked whenever a node is removed. It is useful to define how many buckets (if any) are allowed to be empty, waiting to be populated. The maximum load is checked whenever a node is inserted in the table. It is useful to limit the maximum number of elements per bucket, in average. The performance of the hash table during insertions, deletes, and searches are strongly dependent on the gcgHASHTABLE::hash() method. To solve the unavoidable collisions, fast data structures are used for each bucket. The nodes in this table must be comparable. As such, a class specialization must provide gcgHASHTABLE::compare() method that has the function of determining if two gcgORDEREDNODE nodes are equal, greater or smaller. Use the gcgHASHTABLE::getIterator() to obtain a fast iterator to traverse all table entries.

Since: 0.02.113

Constructor & Destructor Documentation

◆ gcgHASHTABLE()

gcgHASHTABLE::gcgHASHTABLE	(	uintptr_t	capacity = `0`,
		float	minload = `0.8`,
		float	maxload = `16.0`
	)

Constructs a valid hash table. All the parameters of the constructor are crucial for table performance.

Parameters

[in]	capacity	Initial number of buckets of the hash table. Note that the capacity will possibly be changed by the first call to gcgHASHTABLE::insert() if the maxload is positive.
[in]	minload	Minimum load (counter/capacity ratio) that the table must keep after removals. if minload is positive, when a node is removed, the current load is checked against minload. If current load is lesser, the table's capacity is reduced to keep minimum load valid. If negative or zero, no minimum value is defined and the table's capacity is not affected by removals. It must be smaller than maxload and is generally a positive number smaller or equal to 1, meaning the percentage of entries that must not be empty.
[in]	maxload	Maximum load (counter/capacity ratio) that the table must keep after insertions. if maxload is positive, when a node is inserted, the current load is checked against maxload. If current load is greater, the table's capacity is augmented to keep maximum load valid. If negative or zero, no maximum value is defined and the table's capacity is not affected by insertions. It must be greater than minload and is generally a number greater than 1, meaning how many elements is allowed per bucket.

See also: setCapacity; setLoadLimits; ~gcgHASHTABLE

◆ ~gcgHASHTABLE()

virtual gcgHASHTABLE::~gcgHASHTABLE ( )

virtual

Destroys the hash table, releasing all nodes. All entries are deleted.

See also: gcgHASHTABLE

Member Function Documentation

◆ compare()

virtual int gcgHASHTABLE::compare	(	gcgORDEREDNODE *	refnode1,
		gcgORDEREDNODE *	refnode2
	)

pure virtual

Method that must be furnished by a specialization of gcgHASHTABLE and is responsible for comparing two gcgORDEREDNODE nodes. This is necessary for all operations of insertion, retrieval and removal. It must compare the two nodes pointed by refnode1 and refnode2 and return zero if they are equal, -1 if refnode1 is smaller or precedes refnode2, or 1 if refnode1 is greater or succeeds refnode2.

Parameters

[in]	refnode1	pointer to a gcgORDEREDNODE, generally specialized, object that must be compared with refnode2.
[in]	refnode2	pointer to a gcgORDEREDNODE, generally specialized, object that must be compared with refnode1.

Returns: It must compare the two nodes pointed by refnode1 and refnode2 and return zero if they are equal, a negative integer if refnode1 is smaller or precedes refnode2, or a positive integer if refnode1 is grater or succeeds refnode2.

See also: insert(); remove(); search()

Implements gcgORDEREDSTRUCTURE.

◆ deleteAll()

bool gcgHASHTABLE::deleteAll ( )

virtual

Deletes and removes all entries from the hash table. All resources used by the hash table are also released.

Returns: Returns true if all entries were deleted and removed from the hash table. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: detach()

Implements gcgDATASTRUCTURE.

◆ detach()

gcgITERATOR* gcgHASHTABLE::detach ( int traversemode = 0 )

virtual

Force the hash table to be empty. It has the same effect as removing all entries from the hash table but keeping their chaining (which must be used by the returned iterator). The entries are NOT deleted. In order to retrieve the detached entries, a gcgITERATOR is returned. This is useful to process the nodes freely and without the possible restrictions of the underlying hash table. Thus, the gcgITERATOR returned by gcgHASHTABLE::detach() MUST be used to delete all the entries or reinsert them into another data structure. The traversal order of the returned iterator is defined by the parameter traversemode. Currently, the order of iteration depends on the internal data structure (AVL trees). The parameter traversemode is just passed to the secondary data structures. All resources currently used by the hash table are released (becomes empty) but it can be reused normally. You must delete the gcgITERATOR after its use.

Parameters

traversemode Specifies the order that the available elements in the hash table must be traversed by the returned iterator. Currently, the order of iteration depends on the internal data structure (AVL trees). The parameter traversemode is just passed to the secondary data structures.

Returns: Returns an iterator for traversing the elements that were detached from the hash table. The hash table becomes empty and can be reused. You MUST delete the returned gcgITERATOR object after use. If it returns NULL, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: deleteAll(); getIterator()

Implements gcgDATASTRUCTURE.

◆ getCounter()

uintptr_t gcgHASHTABLE::getCounter ( )

virtual

Returns the number of elements stored in the hash table.

Returns: Returns the number of elements currently stored in the hash table.

See also: insert(); remove()

Implements gcgDATASTRUCTURE.

◆ getIterator()

gcgITERATOR* gcgHASHTABLE::getIterator ( int traversemode = 0 )

virtual

Returns an iterator for traversing the elements of the hash table. The traversal order is defined by the parameter traversemode. Currently, the order of iteration depends on the internal data structure (AVL trees). The parameter traversemode is just passed to the secondary data structures whenever a sub-iterator is needed. The hash table must not be changed by insertions, removals or moves while the iterator is being used. You must delete the returned iterator after use. The iterator copies a minimal information from the internal hash table. Note that deleting an iterator does not affect the nodes.

Parameters

traversemode Specifies the order that the available elements in the hash table must be traversed. Currently, the order of iteration depends on the internal data structure (AVL trees). The parameter traversemode is just passed to the secondary data structures whenever a sub-iterator is needed.

Returns: Returns an iterator for traversing the elements of the hash table. The traversal order in the internal secondary data structures is defined by traversemode. The hash table must not be changed by insertions, removals or moves while the iterator is being used. You MUST delete the returned gcgITERATOR object after use. If it returns NULL, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: detach()

Implements gcgDATASTRUCTURE.

◆ hash()

virtual long gcgHASHTABLE::hash ( gcgORDEREDNODE * node )

pure virtual

Method that must be furnished by a specialization of gcgHASHTABLE and is responsible for computing an integer hash value for the node node. This is necessary for all operations of insertion, retrieval and removal. The performance of the hash table is highly dependent on the capacity of the gcgHASHTABLE::hash() method to spread distinct nodes over the long integer numbers.

Parameters

[in] node pointer to a gcgORDEREDNODE, generally specialized, object that must have a hash value to be used in the table.

Returns: It must return an integer number that represents the node. It generally makes some arithmetic with the contents of the object node. Better is the capacity of the hash function to spread distinct nodes over the long integers, better is the performance of the hash table.

See also: insert(); remove(); search(); compare()

◆ insert()

gcgORDEREDNODE* gcgHASHTABLE::insert ( gcgORDEREDNODE * newnode )

virtual

Inserts a new entry newnode in the hash table. All nodes in the table must be unique, i.e., they are mutually different in respect to gcgHASHTABLE::compare() method.

Parameters

[in] newnode a pointer to a comparable node (gcgORDEREDNODE) to be inserted in the hash table. It is generally an object of a specialization of gcgORDEREDNODE that carries the node information. If a similar node is already in the table (the gcgHASHTABLE::compare() method returns zero for an existing node), it returns the pointer of the node in the table. The insertion operation might call the gcgHASHTABLE::compare() method several times to correctly position the new node. The internal data structures are automatically adjusted after the removal. If a maximum value for table load is positive (see gcgHASHTABLE::setLoadLimits()), the current load is computed and checked against that maximum load. If the current load is greater, the table's capacity is augmented in order to put the current load in the valid interval. The method gcgHASHTABLE::hash() might be called several times to find an existing node and to adjust the table load.

Returns: if newnode is similar to an existing node of the hash table (the gcgHASHTABLE::compare() method returns zero for an existing node), the method returns the pointer of that node. If newnode is correctly inserted, it returns the pointer newnode. If it returns NULL, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: compare(); remove(); search()

Implements gcgORDEREDSTRUCTURE.

◆ remove()

gcgORDEREDNODE* gcgHASHTABLE::remove ( gcgORDEREDNODE * key )

virtual

Removes the entry of the hash table that is similar to the key in respect to the gcgHASHTABLE::compare() method. The gcgHASHTABLE::compare() method must return zero only for an unique node of the table. The internal data structures are automatically adjusted after the removal. If a minimum value for table load is positive (see gcgHASHTABLE::setLoadLimits()), the current load is computed and checked against that minimum load. If the current load is lesser, the table's capacity is reduced in order to put the current load in the valid interval. The method gcgHASHTABLE::hash() might be called several times to find node and to adjust the table load.

Parameters

[in] key a pointer to a comparable node (gcgORDEREDNODE) that carries the information to be found and removed from the hash table. It is generally an object of a specialization of gcgORDEREDNODE that carries the information to be removed. If a similar node is in the table (the gcgHASHTABLE::compare() method returns zero for an existing node), that node is removed from the hash table and returned. The removed node is NOT deleted. The remove operation might call the gcgHASHTABLE::compare() method several times to find the node before its removal.

Returns: if newnode is similar to an existing node of the table (the gcgHASHTABLE::compare() method returns zero for an existing node), the method removes that node from the table and returns its pointer. The node is NOT deleted by the method. If a similar node was not found or an error occurred, it returns NULL. Check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insert(); search(); compare()

Implements gcgORDEREDSTRUCTURE.

◆ search()

gcgORDEREDNODE* gcgHASHTABLE::search ( gcgORDEREDNODE * key )

virtual

Retrieves the entry of the hash table that is similar to the key in respect to the gcgHASHTABLE::compare() method. The gcgHASHTABLE::compare() method must return zero only for an unique node of the tree. The method gcgHASHTABLE::hash() is called once to find node's bucket.

Parameters

[in] key a pointer to a comparable node (gcgORDEREDNODE) that carries the information to be searched in the hash table. It is generally an object of a specialization of gcgORDEREDNODE that carries the requested information. If a similar node is in the table (the gcgHASHTABLE::compare() method returns zero for an existing node), it returns the pointer of that node. The search operation might call the gcgHASHTABLE::compare() method several times to retrieve the node.

Returns: if key is similar to an existing node of the table (the gcgAVLTREE::compare() method returns zero), the method returns the pointer of that node. If a similar node was not found or an error occurred, it returns NULL. Check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem, if any.

See also: insert(); remove(); compare()

Implements gcgORDEREDSTRUCTURE.

◆ setCapacity()

bool gcgHASHTABLE::setCapacity ( uintptr_t capacity )

Sets the number of buckets of the table. If the table is already populated with nodes, it adjusts the table to the new capacity. If capacity is zero and the table is not populated, all hash table resources are released. If capacity is zero and the table is populated, a warning is issued.

Parameters

[in] capacity Number of buckets of the hash table. Note that the capacity will possibly be changed by the next call to gcgHASHTABLE::insert(), if the maxload is positive, or gcgHASHTABLE::remove(), if the minload is positive. If the table is already populated with nodes, the table is adjusted to the new capacity. If capacity is zero and the table is not populated, all hash table resources are released. If capacity is zero and the table is populated, a warning is issued.

Returns: true if the capacity was correctly changed. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: setLoadLimits; insert; remove

◆ setLoadLimits()

bool gcgHASHTABLE::setLoadLimits	(	float	minload,
		float	maxload
	)

Sets the minimum and maximum loads that the table is allowed to have after removals and insertions, respectively. Minimum value must be smaller than maximum value. If they are close to another, insertions and removals might become very inefficient because of frequent table capacity adjustments. If minimum and maximum loads are valid, the current load is checked against them. If outside the load interval, the capacity of the table is adjusted.

Parameters

[in]	minload	Minimum load (counter/capacity ratio) that the table must keep after removals. if minload is positive, when a node is removed, the current load is checked against minload. If current load is lesser, the table's capacity is reduced to keep minimum load valid. If negative or zero, no minimum value is defined and the table's capacity is not affected by removals. It must be smaller than maxload.
[in]	maxload	Maximum load (counter/capacity ratio) that the table must keep after insertions. if maxload is positive, when a node is inserted, the current load is checked against maxload. If current load is greater, the table's capacity is augmented to keep maximum load valid. If negative or zero, no maximum value is defined and the table's capacity is not affected by insertions. It must be greater than minload.

Returns: true if the limits were successfully changed. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: setCapacity; insert; remove

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

M:/Documentos/Projetos/Projetos/GCGlib/src/gcg.h

Public Member Functions

Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ gcgHASHTABLE()

◆ ~gcgHASHTABLE()

Member Function Documentation

◆ compare()

◆ deleteAll()

◆ detach()

◆ getCounter()

◆ getIterator()

◆ hash()

◆ insert()

◆ remove()

◆ search()

◆ setCapacity()

◆ setLoadLimits()