cgul_hash.h File Reference

hash implementation More...

#include "cgul_common.h"
#include "cgul_exception.h"
#include "cgul_hash_node.h"

Include dependency graph for cgul_hash.h:

This graph shows which files directly or indirectly include this file:

Typedefs
typedef typedefCGUL_BEGIN_C struct cgul_hash *	cgul_hash_t
typedef unsigned int(*	cgul_hash__hash_t) (void *key, void *data)
typedef int(*	cgul_hash__compare_t) (const void *key1, const void *key2)
typedef int(*	cgul_hash__fold_key_t) (cgul_exception_t *cex, const void *key, void *data)
typedef int(*	cgul_hash__fold_value_t) (cgul_exception_t *cex, void *value, void *data)
typedef int(*	cgul_hash__fold_pair_t) (cgul_exception_t *cex, const void *key, void *value, void *data)
typedef int(*	cgul_hash__traverse_t) (cgul_exception_t *cex, cgul_hash_t h, cgul_hash_node_t n, void *data)

Functions
CGUL_EXPORT unsigned int	cgul_hash__hash_block (void *block, unsigned int block_size)
CGUL_EXPORT cgul_hash_t	cgul_hash__new (cgul_exception_t *cex)
CGUL_EXPORT cgul_hash_t	cgul_hash__new_custom (cgul_exception_t *cex, cgul_hash__hash_t hf, void *hf_data, cgul_hash__compare_t cf)
CGUL_EXPORT void	cgul_hash__delete (cgul_hash_t h)
CGUL_EXPORT void	cgul_hash__free_keys (cgul_hash_t h)
CGUL_EXPORT void	cgul_hash__free_values (cgul_hash_t h)
CGUL_EXPORT float	cgul_hash__get_load_factor (cgul_exception_t *cex, cgul_hash_t h)
CGUL_EXPORT void	cgul_hash__set_load_factor (cgul_exception_t *cex, cgul_hash_t h, float load_factor)
CGUL_EXPORT void	cgul_hash__swap (cgul_exception_t *cex, cgul_hash_t h1, cgul_hash_t h2)
CGUL_EXPORT int	cgul_hash__is_empty (cgul_exception_t *cex, cgul_hash_t h)
CGUL_EXPORT const void **	cgul_hash__get_keys (cgul_exception_t *cex, cgul_hash_t h, size_t *key_count)
CGUL_EXPORT const void **	cgul_hash__get_sorted_keys (cgul_exception_t *cex, cgul_hash_t h, size_t *key_count)
CGUL_EXPORT cgul_hash_node_t	cgul_hash__get_front (cgul_exception_t *cex, cgul_hash_t h)
CGUL_EXPORT cgul_hash_node_t	cgul_hash__get_back (cgul_exception_t *cex, cgul_hash_t h)
CGUL_EXPORT cgul_hash_node_t	cgul_hash__get_oldest (cgul_exception_t *cex, cgul_hash_t h)
CGUL_EXPORT void	cgul_hash__set_oldest (cgul_exception_t *cex, cgul_hash_t h, cgul_hash_node_t n)
CGUL_EXPORT cgul_hash_node_t	cgul_hash__get_youngest (cgul_exception_t *cex, cgul_hash_t h)
CGUL_EXPORT void	cgul_hash__set_youngest (cgul_exception_t *cex, cgul_hash_t h, cgul_hash_node_t n)
CGUL_EXPORT int	cgul_hash__insert (cgul_exception_t *cex, cgul_hash_t h, const void *key, cgul_hash_node_t *n)
CGUL_EXPORT cgul_hash_node_t	cgul_hash__find (cgul_exception_t *cex, cgul_hash_t h, const void *key)
CGUL_EXPORT int	cgul_hash__remove (cgul_exception_t *cex, cgul_hash_t h, const void *key_in, void **key_out, void **value_out)
CGUL_EXPORT void	cgul_hash__remove_node (cgul_exception_t *cex, cgul_hash_t h, cgul_hash_node_t n)
CGUL_EXPORT int	cgul_hash__remove_front (cgul_exception_t *cex, cgul_hash_t h, void **key_out, void **value_out)
CGUL_EXPORT int	cgul_hash__remove_back (cgul_exception_t *cex, cgul_hash_t h, void **key_out, void **value_out)
CGUL_EXPORT int	cgul_hash__remove_oldest (cgul_exception_t *cex, cgul_hash_t h, void **key_out, void **value_out)
CGUL_EXPORT int	cgul_hash__remove_youngest (cgul_exception_t *cex, cgul_hash_t h, void **key_out, void **value_out)
CGUL_EXPORT void	cgul_hash__clear (cgul_exception_t *cex, cgul_hash_t h)
CGUL_EXPORT size_t	cgul_hash__get_size (cgul_exception_t *cex, cgul_hash_t h)
CGUL_EXPORT size_t	cgul_hash__get_total_collisions (cgul_exception_t *cex, cgul_hash_t h)
CGUL_EXPORT char *	cgul_hash__get_stats (cgul_exception_t *cex, cgul_hash_t h)
CGUL_EXPORT void	cgul_hash__foldl_keys (cgul_exception_t *cex, cgul_hash_t h, cgul_hash__fold_key_t f, void *data)
CGUL_EXPORT void	cgul_hash__foldr_keys (cgul_exception_t *cex, cgul_hash_t h, cgul_hash__fold_key_t f, void *data)
CGUL_EXPORT void	cgul_hash__foldl_values (cgul_exception_t *cex, cgul_hash_t h, cgul_hash__fold_value_t f, void *data)
CGUL_EXPORT void	cgul_hash__foldr_values (cgul_exception_t *cex, cgul_hash_t h, cgul_hash__fold_value_t f, void *data)
CGUL_EXPORT void	cgul_hash__foldl_pairs (cgul_exception_t *cex, cgul_hash_t h, cgul_hash__fold_pair_t f, void *data)
CGUL_EXPORT void	cgul_hash__foldr_pairs (cgul_exception_t *cex, cgul_hash_t h, cgul_hash__fold_pair_t f, void *data)
CGUL_EXPORT void	cgul_hash__traverse (cgul_exception_t *cex, cgul_hash_t h, cgul_hash__traverse_t f, void *data)
CGUL_EXPORT void	cgul_hash__traverse_range (cgul_exception_t *cex, cgul_hash_t h, cgul_hash_node_t first, cgul_hash_node_t last, cgul_hash__traverse_t f, void *data)

Detailed Description

Hash implementation.

Author

Paul Serice

Typedef Documentation

cgul_hash_t

typedef typedefCGUL_BEGIN_C struct cgul_hash* cgul_hash_t

Opaque pointer to a cgul_hash instance.

cgul_hash__hash_t

typedef unsigned int(* cgul_hash__hash_t) (void *key, void *data)

This typedef defines the interface for hash functions that can be used with custom cgul_hash objects. The hash function returns the hash of key which should be in the range of [0 - UINT_MAX]. The cgul_hash object will then use the hash value to map to the correct bucket.

It may not be necessary to write your own hash function as cgul_hash__hash_block() is a good choice, but you will still need to write an adaptor because cgul_hash__hash_block() needs to know the size of the key which is not something intrinsically stored in the hash itself.

The data pointer is just a copy of the same pointer that was registered when the custom cgul_hash object was instantiated.

Parameters

[in]	key	key
[in]	data	client data

Returns

hash of key

cgul_hash__compare_t

typedef int(* cgul_hash__compare_t) (const void *key1, const void *key2)

This typedef defines the interface for comparison functions that can be used with custom cgul_hash objects. After the hash function selects a bucket, the comparison function is used to compare keys within the same bucket in order to determine if a key exists in the hash.

When you define your comparison function, you should compare key1 to key2 and return less than zero, zero, or greater than zero if key1 is less than, equal to, or greater than key2. The reason the comparison function needs to be complete is so cgul_hash__get_sorted_keys() can work.

Parameters

[in]	key1	first key
[in]	key2	second key

Returns

result of comparison

cgul_hash__fold_key_t

typedef int(* cgul_hash__fold_key_t) (cgul_exception_t *cex, const void *key, void *data)

This typedef is the interface for the combining function used by the following methods:

    cgul_hash__foldl_keys()
    cgul_hash__foldr_keys()

The client must not alter key.

Parameters

[in,out]	cex	c-style exception
[in]	key	key
[in]	data	client data

Returns

whether to continue

cgul_hash__fold_value_t

typedef int(* cgul_hash__fold_value_t) (cgul_exception_t *cex, void *value, void *data)

This typedef is the interface for the combining function used by the following methods:

    cgul_hash__foldl_values()
    cgul_hash__foldr_values()

Parameters

[in,out]	cex	c-style exception
[in]	value	value
[in]	data	client data

Returns

whether to continue

cgul_hash__fold_pair_t

typedef int(* cgul_hash__fold_pair_t) (cgul_exception_t *cex, const void *key, void *value, void *data)

This typedef is the interface for the combining function used by the following methods:

    cgul_hash__foldl_pairs()
    cgul_hash__foldr_pairs()

The client must not alter key.

Parameters

[in,out]	cex	c-style exception
[in]	key	key
[in]	value	value
[in]	data	client data

Returns

whether to continue

cgul_hash__traverse_t

typedef int(* cgul_hash__traverse_t) (cgul_exception_t *cex, cgul_hash_t h, cgul_hash_node_t n, void *data)

This typedef is the interface for the callback function used by the following methods:

    cgul_hash__traverse()
    cgul_hash__traverse_range()

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	n	node
[in]	data	client data

Returns

whether to continue

Function Documentation

cgul_hash__hash_block()

CGUL_EXPORT unsigned int cgul_hash__hash_block	(	void *	block,
		unsigned int	block_size
	)

This function computes the hash for block which can be any arbitrary data extending for block_size bytes.

With the help of an adaptor, this function can be used as the hash function for custom cgul_hash objects. An adaptor is needed because the block size is not a value that is intrinsically stored in cgul_hash objects.

Parameters

[in]	block	block
[in]	block_size	block size

Returns

hash of block

See also

cgul_rolling_hash__hash()

Referenced by cgul_hash_cxx::hash_block().

cgul_hash__new()

CGUL_EXPORT cgul_hash_t cgul_hash__new

(

cgul_exception_t *

cex

)

Create a new default cgul_hash object that is already configured to use C-style strings as keys. The caller is responsible for freeing the object by calling cgul_hash__delete(). If memory cannot be allocated, NULL is returned, and an exception is thrown.

Parameters

[in,out]

cex

c-style exception

Returns

new cgul_hash instance

See also

cgul_hash__set_load_factor()

Referenced by cgul_hash_cxx::cgul_hash_cxx().

cgul_hash__new_custom()

CGUL_EXPORT cgul_hash_t cgul_hash__new_custom	(	cgul_exception_t *	cex,
		cgul_hash__hash_t	hf,
		void *	hf_data,
		cgul_hash__compare_t	cf
	)

Create a new custom cgul_hash object that uses hf as the hash function and cf as the comparison function. With the help of an adaptor, the cgul_hash__hash_block() function is a good choice for hf. The caller is responsible for freeing the object by calling cgul_hash__delete(). If memory cannot be allocated, NULL is returned, and an exception is thrown.

Parameters

[in,out]	cex	c-style exception
[in]	hf	hash function
[in]	hf_data	hash function client data
[in]	cf	comparison function

Returns

new cgul_hash instance

See also

cgul_hash__set_load_factor()

Referenced by cgul_hash_cxx::cgul_hash_cxx().

cgul_hash__delete()

CGUL_EXPORT void cgul_hash__delete

(

cgul_hash_t

h

)

The method frees all internally allocated memory. Do not try to access h after calling this method.

Parameters

[in]

h

cgul_hash instance

See also

cgul_hash__free_keys()

cgul_hash__free_values()

Referenced by cgul_hash_cxx::set_obj(), and cgul_hash_cxx::~cgul_hash_cxx().

cgul_hash__free_keys()

CGUL_EXPORT void cgul_hash__free_keys

(

cgul_hash_t

h

)

This method calls free() on all the keys in the hash h. Because this is such a common operation, it is an exception to the rule that cgul containers never free keys. This method should only ever be called immediately before calling cgul_hash__delete() because it otherwise invalidates the hash. Because this function is basically an extension of cgul_hash__delete(), it does not accept a cgul_exception object as an input parameter.

Parameters

[in]

h

cgul_hash instance

Referenced by cgul_hash_cxx::free_keys().

cgul_hash__free_values()

CGUL_EXPORT void cgul_hash__free_values

(

cgul_hash_t

h

)

This method calls free() on all the values in the hash h. Because this is such a common operation, it is an exception to the rule that cgul containers never free values. This method should only ever be called immediately before calling cgul_hash__delete() because it otherwise invalidates the hash. Because this function is basically an extension of cgul_hash__delete(), it does not take a cgul_exception object.

Parameters

[in]

h

cgul_hash instance

Referenced by cgul_hash_cxx::free_values().

cgul_hash__get_load_factor()

CGUL_EXPORT float cgul_hash__get_load_factor	(	cgul_exception_t *	cex,
		cgul_hash_t	h
	)

Get the load factor.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance

Returns

load factor

See also

cgul_hash__set_load_factor()

Referenced by cgul_hash_cxx::get_load_factor().

cgul_hash__set_load_factor()

CGUL_EXPORT void cgul_hash__set_load_factor	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		float	load_factor
	)

The load_factor is the main parameter that governs the speed/space tradeoff. It is the ratio of number of keys to buckets.

This is an important value because each key hashes to a particular bucket. Then the hash has to perform a linear search of the keys in the bucket. Because the load factor limits the average number of keys per bucket, it controls how deep the linear search is allowed to get (on average).

The default load factor is 0.75.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	load_factor	load factor

Referenced by cgul_hash_cxx::set_load_factor().

cgul_hash__swap()

CGUL_EXPORT void cgul_hash__swap	(	cgul_exception_t *	cex,
		cgul_hash_t	h1,
		cgul_hash_t	h2
	)

Swap the internal data for h1 and h2. This is much faster in general than trying to do the same thing by iterating over the hash elements.

Parameters

[in]	cex	c-style exception
[in]	h1	cgul_hash instance
[in]	h2	second cgul_hash instance

Referenced by cgul_hash_cxx::swap().

cgul_hash__is_empty()

CGUL_EXPORT int cgul_hash__is_empty	(	cgul_exception_t *	cex,
		cgul_hash_t	h
	)

Return true if the hash h is empty.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance

Returns

whether the hash is empty

Referenced by cgul_hash_cxx::is_empty().

cgul_hash__get_keys()

CGUL_EXPORT const void** cgul_hash__get_keys	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		size_t *	key_count
	)

Return an array of keys in insertion order. A NULL pointer is appended to the array that is returned and can be used as a sentinel.

If key_count is not NULL, *key_count is set to the number of keys returned in the array.

The caller is responsible for calling free() on the array that is returned but must not attempt to free the keys themselves.

The main reason for calling this method is because you want to sort the keys in the hash. If you need the keys sorted using the comparison function, as a convenience, you can call cgul_hash__get_sorted_keys() instead. If you need to sort by some other criteria, you can use cgul_merge_sort_pointers() directly on the array returned by this method.

It is wasteful to use this method if all you want to do is iterate over the keys in insertion order. Use cgul_hash__get_oldest() and cgul_hash_node__get_younger() to do this instead.

If possible, cgul_rbtree should be used instead of cgul_hash if the caller needs frequent access to the keys in sorted order.

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance
[out]	key_count	number of keys returned in the array

Returns

array of keys in chronological order

Referenced by cgul_hash_cxx::get_keys().

cgul_hash__get_sorted_keys()

CGUL_EXPORT const void** cgul_hash__get_sorted_keys	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		size_t *	key_count
	)

Return an array of keys sorted using the comparison function. A NULL pointer is appended to the array that is returned and can be used as a sentinel.

If key_count is not NULL, *key_count is set to the number of keys returned in the array.

The caller is responsible for calling free() on the array that is returned but must not attempt to free the keys themselves.

If possible, cgul_rbtree should be used instead of cgul_hash if the caller needs frequent access to the keys in sorted order.

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance
[out]	key_count	number of keys returned in the array

Returns

sorted array of keys

Referenced by cgul_hash_cxx::get_sorted_keys().

cgul_hash__get_front()

CGUL_EXPORT cgul_hash_node_t cgul_hash__get_front	(	cgul_exception_t *	cex,
		cgul_hash_t	h
	)

Return the front node or NULL if the hash is empty. The "front" node is just a synonym for the "oldest" node. You can use the return value to iterate over all the nodes in the hash by calling cgul_hash_node__get_next().

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance

Returns

front node

See also

cgul_hash__get_oldest()

Referenced by cgul_hash_cxx::foldl_keys(), cgul_hash_cxx::foldl_pairs(), cgul_hash_cxx::foldl_values(), cgul_hash_cxx::get_front(), and cgul_hash_cxx::traverse_range().

cgul_hash__get_back()

CGUL_EXPORT cgul_hash_node_t cgul_hash__get_back	(	cgul_exception_t *	cex,
		cgul_hash_t	h
	)

Return the back node or NULL if the hash is empty. The "back" node is just a synonym for the "youngest" node. You can use the return value to iterate over all the nodes in the hash by calling cgul_hash_node__get_prev().

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance

Returns

back node

See also

cgul_hash__get_youngest()

Referenced by cgul_hash_cxx::foldr_keys(), cgul_hash_cxx::foldr_pairs(), cgul_hash_cxx::foldr_values(), cgul_hash_cxx::get_back(), and cgul_hash_cxx::traverse_range().

cgul_hash__get_oldest()

CGUL_EXPORT cgul_hash_node_t cgul_hash__get_oldest	(	cgul_exception_t *	cex,
		cgul_hash_t	h
	)

Get the oldest node. This operation is O(1). If the hash is empty, NULL is returned. This class does not have to search the hash in order to find the oldest node because it efficiently keeps a direct pointer to the oldest node up to date.

The following example shows how to iterate over the entire hash in insertion order:

    cgul_hash_node_t n = cgul_hash__get_oldest(cex, h);
    for ( ; n ; n = cgul_hash_node__get_younger(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance

Returns

oldest node

See also

cgul_hash_node__get_younger()

Referenced by cgul_hash_cxx::get_oldest().

cgul_hash__set_oldest()

CGUL_EXPORT void cgul_hash__set_oldest	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		cgul_hash_node_t	n
	)

Set the oldest node in the hash to be n. Calling this method has the potential to confuse iterators and should be handled with roughly the same level of caution as calling cgul_hash__remove_node().

This method could be used, for example, if your code expires the oldest node in the hash and you want to force n to be the next node to expire.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	n	node

See also

cgul_hash__set_youngest()

Referenced by cgul_hash_cxx::set_oldest().

cgul_hash__get_youngest()

CGUL_EXPORT cgul_hash_node_t cgul_hash__get_youngest	(	cgul_exception_t *	cex,
		cgul_hash_t	h
	)

Get the youngest node. This operation is O(1). If the hash is empty, NULL is returned. This class does not have to search the hash in order to find the youngest node because it efficiently keeps a direct pointer to the youngest node up to date.

The following example shows how to iterate over the entire hash in reverse chronological order:

    cgul_hash_node_t n = cgul_hash__get_youngest(cex, h);
    for ( ; n ; n = cgul_hash_node__get_older(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance

Returns

youngest node

See also

cgul_hash_node__get_older()

Referenced by cgul_hash_cxx::get_youngest().

cgul_hash__set_youngest()

CGUL_EXPORT void cgul_hash__set_youngest	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		cgul_hash_node_t	n
	)

Set the youngest node in the hash to be n. Calling this method has the potential to confuse iterators and should be handled with roughly the same level of caution as calling cgul_hash__remove_node().

This method could be used, for example, if your code expires the least-recently used (LRU) node. By calling cgul_hash__set_youngest() each time a node is used, the least-recently used node will be the oldest node in the hash.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	n	node

See also

cgul_hash__set_oldest()

Referenced by cgul_hash_cxx::set_youngest().

cgul_hash__insert()

CGUL_EXPORT int cgul_hash__insert	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		const void *	key,
		cgul_hash_node_t *	n
	)

Insert key into the hash h. If key already exists, another node with the same key is not created. The new or pre-existing node is returned in n if n is not NULL. If an error occurs, 0 is returned, *n is set to NULL (if n is not NULL), and an exception is thrown.

An important thing to notice is that there is no way to pass in the value pointer that makes up the key/value pair. This is by design. The reason is that find() and insert() share the same basic code to search to see if the key already exists. Thus, if you want to see if a key already exists before inserting a new key (which is very common), you could call cgul_hash__find() followed by cgul_hash__insert(), but this inefficiently causes cgul_hash to do the same lookup twice.

By not allowing cgul_hash__insert() to set the value pointer, it allows you to easily use this method in those places where you want cgul_hash__find() to fail before you call cgul_hash__insert(); instead, you just call cgul_hash__insert() and check the return value. Here is an example:

   int insert_rv = 0;
   cgul_hash_node_t* n = NULL;

   key = cgul_string__get_value(cex, s);
   insert_rv = cgul_hash__insert(cex, h, (void*)key, &n);
   if (*cex) {
       goto out;
   }
   if (insert_rv) {
       cgul_string__take_value(cex, s);
       . . .
   } else {
       . . .
   }

As with all the cgul containers, the client is responsible for deallocating both key and value. If before inserting the new node the hash detects that the load factor has been exceeded, the hash will be resized.

Note

The cgul_hash does not make a duplicate copy of the key. Thus, it is the callers responsibility to make sure key continues to exist until it is removed from the hash.

Note

An insert operation could cause the average search distance to grow too large which triggers a resize operation. Resizing the hash is relatively expensive, but the amortized cost should be minimal. It is possible for the program to run out of memory during a resize operation. In this case, the hash will still be valid, but it will not be resized.

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	key	key
[out]	n	newly inserted node if successful; otherwise, unaltered

Returns

whether the insertion operation succeeded

Referenced by cgul_hash_cxx::insert().

cgul_hash__find()

CGUL_EXPORT cgul_hash_node_t cgul_hash__find	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		const void *	key
	)

Return the hash node associated with key. You can use cgul_hash_node__get_value() and cgul_hash_node__set_value() to get and set the value associated with the node. If no node is found, NULL is returned.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	key	key

Returns

node associated with key

Referenced by cgul_hash_cxx::find().

cgul_hash__remove()

CGUL_EXPORT int cgul_hash__remove	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		const void *	key_in,
		void **	key_out,
		void **	value_out
	)

Remove the node associated with the key key_in from the hash h. If key_out is not NULL, the key that is currently stored in the node to be removed will be returned. If value_out is not NULL, the value stored in the node to be removed will be returned. The return value is 1 if the node for key_in was removed; otherwise, it is 0.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	key_in	key to find
[out]	key_out	actual key stored in node
[out]	value_out	actual value stored in node

Returns

whether the node associated with key was removed

Referenced by cgul_hash_cxx::remove().

cgul_hash__remove_node()

CGUL_EXPORT void cgul_hash__remove_node	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		cgul_hash_node_t	n
	)

Remove the node n from the hash h. Calling this method has the potential to invalidate iterators. If you need to remove nodes while simultaneously iterating over the tree, you must call cgul_hash__get_next() (or the equivalent) before removing the current node because, once the node is removed, you cannot use it safely.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	n	node

Referenced by cgul_hash_cxx::remove_node().

cgul_hash__remove_front()

CGUL_EXPORT int cgul_hash__remove_front	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		void **	key_out,
		void **	value_out
	)

This method removes the front node from the hash h. The "front" node is just a synonym for the "oldest" node. The key and value pointers stored in the node that is to be removed will be returned in key_out and value_out if you pass in pointers that are not NULL. If h is not empty, the front node will be removed, and 1 will be returned; otherwise, 0 will be returned.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns

whether the node was removed

Referenced by cgul_hash_cxx::remove_front().

cgul_hash__remove_back()

CGUL_EXPORT int cgul_hash__remove_back	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		void **	key_out,
		void **	value_out
	)

This method removes the back node from the hash h. The "back" node is just a synonym for the "youngest" node. The key and value pointers stored in the node that is to be removed will be returned in key_out and value_out if you pass in pointers that are not NULL. If h is not empty, the back node will be removed, and 1 will be returned; otherwise, 0 will be returned.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns

whether the node was removed

Referenced by cgul_hash_cxx::remove_back().

cgul_hash__remove_oldest()

CGUL_EXPORT int cgul_hash__remove_oldest	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		void **	key_out,
		void **	value_out
	)

This method removes the oldest node from the hash h. The key and value pointers stored in the node that is to be removed will be returned in key_out and value_out if you pass in pointers that are not NULL. If h is not empty, the oldest node will be removed and 1 will be returned; otherwise, 0 will be returned.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns

whether the node was removed

Referenced by cgul_hash_cxx::remove_oldest().

cgul_hash__remove_youngest()

CGUL_EXPORT int cgul_hash__remove_youngest	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		void **	key_out,
		void **	value_out
	)

This method removes the youngest node from the hash h. The key and value pointers stored in the node that is to be removed will be returned in key_out and value_out if you pass in pointers that are not NULL. If h is not empty, the youngest node will be removed and 1 will be returned; otherwise, 0 will be returned.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns

whether the node was removed

Referenced by cgul_hash_cxx::remove_youngest().

cgul_hash__clear()

CGUL_EXPORT void cgul_hash__clear	(	cgul_exception_t *	cex,
		cgul_hash_t	h
	)

Remove all elements from the hash h. You should be careful to deallocate the key/value pairs (if necessary) before calling this method.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance

Referenced by cgul_hash_cxx::clear().

cgul_hash__get_size()

CGUL_EXPORT size_t cgul_hash__get_size	(	cgul_exception_t *	cex,
		cgul_hash_t	h
	)

Return the total number of elements stored in the hash.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance

Returns

total number of elements stored in the hash

Referenced by cgul_hash_cxx::get_size().

cgul_hash__get_total_collisions()

CGUL_EXPORT size_t cgul_hash__get_total_collisions	(	cgul_exception_t *	cex,
		cgul_hash_t	h
	)

Get the total number of collisions. Note that the total number of collisions can be more than the size of the hash because the total number of collisions includes all the extra collisions that occur when the hash is resized.

Parameters

[in]	cex	c-style exception
[in]	h	cgul_hash instance

cgul_hash__get_stats()

CGUL_EXPORT char* cgul_hash__get_stats	(	cgul_exception_t *	cex,
		cgul_hash_t	h
	)

Return a string with statistics for the cgul_hash. The caller is responsible for freeing the string by calling free(). If an error occurs while generating the stats, NULL is returned, and an exception is thrown.

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance

Returns

statics for h

Referenced by cgul_hash_cxx::get_stats().

cgul_hash__foldl_keys()

CGUL_EXPORT void cgul_hash__foldl_keys	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		cgul_hash__fold_key_t	f,
		void *	data
	)

This method performs a left fold of the hash h with the combining function f. f is called once for each key in the hash starting at the front of the hash and iterating forward to the end of the hash.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current key. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	f	combining function
[in]	data	client data passed to f

cgul_hash__foldr_keys()

CGUL_EXPORT void cgul_hash__foldr_keys	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		cgul_hash__fold_key_t	f,
		void *	data
	)

This method performs a right fold of the hash h with the combining function f. f is called once for each key in the hash starting at the back of the hash and iterating backward to the front of the hash.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current key. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	f	combining function
[in]	data	client data passed to f

cgul_hash__foldl_values()

CGUL_EXPORT void cgul_hash__foldl_values	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		cgul_hash__fold_value_t	f,
		void *	data
	)

This method performs a left fold of the hash h with the combining function f. f is called once for each value in the hash starting at the front of the hash and iterating forward to the end of the hash.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current value. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	f	combining function
[in]	data	client data passed to f

cgul_hash__foldr_values()

CGUL_EXPORT void cgul_hash__foldr_values	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		cgul_hash__fold_value_t	f,
		void *	data
	)

This method performs a right fold of the hash h with the combining function f. f is called once for each value in the hash starting at the back of the hash and iterating backward to the front of the hash.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current value. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	f	combining function
[in]	data	client data passed to f

cgul_hash__foldl_pairs()

CGUL_EXPORT void cgul_hash__foldl_pairs	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		cgul_hash__fold_pair_t	f,
		void *	data
	)

This method performs a left fold of the hash h with the combining function f. f is called once for each key/value pair in the hash starting at the front of the hash and iterating forward to the end of the hash.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current key. The third parameter passed into f is the current value. The fourth parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	f	combining function
[in]	data	client data passed to f

cgul_hash__foldr_pairs()

CGUL_EXPORT void cgul_hash__foldr_pairs	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		cgul_hash__fold_pair_t	f,
		void *	data
	)

This method performs a right fold of the hash h with the combining function f. f is called once for each key/value pair in the hash starting at the back of the hash and iterating backward to the front of the hash.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current key. The third parameter passed into f is the current value. The fourth parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	f	combining function
[in]	data	client data passed to f

cgul_hash__traverse()

CGUL_EXPORT void cgul_hash__traverse	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		cgul_hash__traverse_t	f,
		void *	data
	)

Traverse all nodes passing each node to the function f.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the hash h. The third paramenter passed into f is the node for this iteration. The fourth parameter passed into f is the client data data.

f is provided with a safe context in which it can remove the node that is passed into f by calling cgul_hash__remove_node().

f must return true after each iteration in order for the traversal to continue.

NOTE: It is not strictly necessary that you use cgul_hash__traverse() or cgul_hash__traverse_range() in order to iterate over the hash elements. In fact, I would recommend that you use cgul_hash_node__get_next() for most of your iteration needs. If you need to remove nodes though, you should probably use this method. If you look at this method's source however, you will see that the cgul_hash_node class provides all the public methods you need to safely remove nodes while you are iterating over the hash, but you do have to be careful.

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	f	traversal callback function
[in]	data	passed to f

cgul_hash__traverse_range()

CGUL_EXPORT void cgul_hash__traverse_range	(	cgul_exception_t *	cex,
		cgul_hash_t	h,
		cgul_hash_node_t	first,
		cgul_hash_node_t	last,
		cgul_hash__traverse_t	f,
		void *	data
	)

Traverse all nodes starting with first (inclusive) and ending with last (inclusive) passing each node to the function f. If you know the first node, but are not sure of the last node, just use NULL as the last node. This will cause this method to iterate until it reaches the end of the hash. You can than have f return 0 when it determines that the last node has been reached.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the hash h. The third paramenter passed into f is the node for this iteration. The fourth parameter passed into f is the client data data.

f is provided with a safe context in which it can remove the node that is passed into f by calling cgul_hash__remove_node().

f must return true after each iteration in order for the traversal to continue.

If first is NULL, iteration starts at the beginning of the hash. If last is NULL, iteration stops at the end of the hash.

NOTE: It is not strictly necessary that you use cgul_hash__traverse() or cgul_hash__traverse_range() in order to iterate over the hash elements. In fact, I would recommend that you use cgul_hash_node__get_next() for most of your iteration needs. If you need to remove nodes though, you should probably use this method. If you look at this method's source however, you will see that the cgul_hash_node class provides all the public methods you need to safely remove nodes while you are iterating over the hash, but you do have to be careful.

Parameters

[in,out]	cex	c-style exception
[in]	h	cgul_hash instance
[in]	first	first node in range
[in]	last	last node in range
[in]	f	traversal callback function
[in]	data	client data passed to f

See also

cgul_hash__traverse