Hashtable
[Utilities]


Data Structures

struct  tag_hash_bin
struct  hashtable_t

Typedefs

typedef khm_int32(*) hash_function_t (const void *key)
 A hash function.
typedef khm_int32(*) comp_function_t (const void *key1, const void *key2)
 A comparison function.
typedef void(*) add_ref_function_t (const void *key, void *data)
 Add-reference function.
typedef void(*) del_ref_function_t (const void *key, void *data)
 Delete-reference function.
typedef tag_hash_bin hash_bin
typedef hashtable_t hashtable

Functions

KHMEXP hashtable *KHMAPI hash_new_hashtable (khm_int32 n, hash_function_t hash, comp_function_t comp, add_ref_function_t addr, del_ref_function_t delr)
 Create a new hashtable.
KHMEXP void KHMAPI hash_del_hashtable (hashtable *h)
 Delete a hashtable.
KHMEXP void KHMAPI hash_add (hashtable *h, const void *key, void *data)
 Add an object to a hashtable.
KHMEXP void KHMAPI hash_del (hashtable *h, const void *key)
 Delete an object from a hashtable.
KHMEXP void *KHMAPI hash_lookup (hashtable *h, const void *key)
 Resolve and association.
KHMEXP khm_boolean KHMAPI hash_exist (hashtable *h, const void *key)
 Check for the presence of an association.
KHMEXP khm_int32 hash_string (const void *str)
 Compute a hashvalue for a unicode string.
KHMEXP khm_int32 hash_string_comp (const void *vs1, const void *vs2)
 Compare two strings.


Typedef Documentation

typedef void(*) add_ref_function_t(const void *key, void *data)

Add-reference function.

When an object is successfully added to a hashtable, this function will be called with the key and data used to add the object. The function is allowed to modify data, however, the modification should not alter the key or the relationship between key and data.

typedef khm_int32(*) comp_function_t(const void *key1, const void *key2)

A comparison function.

The function takes two keys and returns a value indicating the relative ordering of the two keys.

The return value should be:

typedef void(*) del_ref_function_t(const void *key, void *data)

Delete-reference function.

When an object is successfully removed from the hashtable, this function will be called. As with the add-ref function, the object can be modified, but the key and the relationship between key and data should remain intact.

An object is removed if it is explicitly removed from the hashtable or another object with the same key is added to the hashtable. There should be a 1-1 correspondence with keys and objects in the hashtable. The delete-reference function will be called on all the remaining objects in the hashtable when the hashtable is deleted.

typedef khm_int32(*) hash_function_t(const void *key)

A hash function.

The function should take a key as a parameter and return an khm_int32 that serves as the hash of the key.


Function Documentation

KHMEXP void KHMAPI hash_add ( hashtable *  h,
const void *  key,
void *  data 
)

Add an object to a hashtable.

Creates an association between the key and data in the hashtable h. If there is an add-ref function defined for the hashtable, it will be called with key and after the object is added. If there is already an object with the same key in the hashtable, that object will be removed (and the del-ref function called, if appilcable) before adding the new object and before the add-ref function is called for the new object.

Note that two keys key1 and key2 are equal (or same) in a hashtable if the comparator returns zero when called with key1 and key2.

Also note that all additions and removals to the hashtable are done by reference. No data is copied. Any objects pointed to are expected to exist for the duration that the object and key are contained in the hashtable.

Parameters:
[in] h Hashtable
[in] key A key. If key points to a location in memory, it should be within the object pointed to by data, or be a constant. Can be NULL.
[in] data Data. Cannot be NULL.
Note:
Not thread-safe. Applications must serialize calls that reference the same hashtable.

KHMEXP void KHMAPI hash_del ( hashtable *  h,
const void *  key 
)

Delete an object from a hashtable.

Deletes the object in the hashtable h that is associated with key key. An object is associated with key key if the key key_o that the object is associated with is the same as key as determined by the comparator. If the del-ref function is defined for the hash-table, it will be called with the key_o and data that was used to add the object.

Note:
Not thread-safe. Applications must serialize calls that reference the same hashtable.

KHMEXP void KHMAPI hash_del_hashtable ( hashtable *  h  ) 

Delete a hashtable.

Note:
Not thread-safe. Applications must serialize calls that reference the same hashtable.

KHMEXP khm_boolean KHMAPI hash_exist ( hashtable *  h,
const void *  key 
)

Check for the presence of an association.

Returns non-zero if there exists an association between key key and some object in hashtable h. See hash_lookup() for definition of "association".

Returns zero if there is no association.

Note:
(hash_lookup(h,key) == NULL) iff (hash_exist(h,key)==0)

Not thead-safe. Application must serialize calls that reference the same hashtable.

KHMEXP void* KHMAPI hash_lookup ( hashtable *  h,
const void *  key 
)

Resolve and association.

Return the object that is associated with key key in hashtable h. An object data is associated with key key in h if the key key_o that was used to add data to h is equal to key as determined by the comparator.

Returns NULL if no association is found.

Note:
Not thread-safe. Applications must serialize calls that reference the same hashtable.

KHMEXP hashtable* KHMAPI hash_new_hashtable ( khm_int32  n,
hash_function_t  hash,
comp_function_t  comp,
add_ref_function_t  addr,
del_ref_function_t  delr 
)

Create a new hashtable.

Parameters:
[in] n Number of bins in hashtable.
[in] hash A hash function. Required.
[in] comp A comparator. Required.
[in] addr An add-ref function. Optional; can be NULL.
[in] delr A del-ref function. Optional; can be NULL.

KHMEXP khm_int32 hash_string ( const void *  str  ) 

Compute a hashvalue for a unicode string.

The hash value is computed using DJB with parameter 13331.

This function is suitable for use as the hash function for a hashtable if the keys are NULL terminated safe unicode strings that are either part of the data objects or are constants.

Parameters:
[in] str A pointer to a NULL terminated wchar_t string cast as (void *).
Note:
This function does not check the length of the string str. If the string is not NULL terminated, the behavior is undefined.

KHMEXP khm_int32 hash_string_comp ( const void *  vs1,
const void *  vs2 
)

Compare two strings.

Compares two strings are returns a value that is in accordance with the comparator for a hashtable.

Parameters:
[in] vs1 A pointer to a NULL terminated wchar_t string cast as (void *).
[in] vs2 A pointer to a NULL terminated wchar_t string cast as (void *).
Note:
This function does not check the length of the strings vs1 and vs2. If the strings are not NULL terminated, the behavior is undefined.


Generated on Fri Aug 3 08:27:14 2007 for Network Identity Manager by Doxygen 1.5.2
© 2004-2007 Massachusetts Institute of Technology.
© 2005-2007 Secure Endpoints Inc.
Contact khimaira@mit.edu