dvander@2226: #ifndef _INCLUDE_KNIGHT_KE_HASHTABLE_H_
dvander@2226: #define _INCLUDE_KNIGHT_KE_HASHTABLE_H_
dvander@2226: 
dvander@2226: #include <KeStdTypes.h>
dvander@2226: #include <KnightAllocator.h>
dvander@2226: 
dvander@2226: namespace Knight
dvander@2226: {
dvander@2226: 	class KeHashTable;
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * @brief Must generate a hash function given a key.
dvander@2226: 	 *
dvander@2226: 	 * @param key				Pointer to the key.
dvander@2226: 	 * @return					Hash value.
dvander@2226: 	 */
dvander@2226: 	typedef uint32_t (*KeHashGenerator)(const void *key);
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * @brief Must compare two values.
dvander@2226: 	 *
dvander@2226: 	 * @param val1				First value.
dvander@2226: 	 * @param val2				Second value.
dvander@2226: 	 * @return					True if equal, false if not.
dvander@2226: 	 */
dvander@2226: 	typedef bool (*KeHashComparator)(const void *val1, const void *val2);
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * @brief Must call the destructor of the given data, and free if necessary.
dvander@2226: 	 *
dvander@2226: 	 * @param val				Pointer to data.
dvander@2226: 	 */
dvander@2226: 	typedef void (*KeHashDestructor)(const void *val);
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * @brief Must transfer the contents of an object from the source to the destination.
dvander@2226: 	 *
dvander@2226: 	 * @param dest				Destination address.
dvander@2226: 	 * @param source			Source address.
dvander@2226: 	 */
dvander@2226: 	typedef void (*KeHashCopyCtor)(void *dest, const void *source);
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * @brief Contains information about how to process keys and values in a hash table.
dvander@2226: 	 */
dvander@2226: 	struct KeHashMarshal
dvander@2226: 	{
dvander@2226: 		size_t bytes;				/**< Bytes of storage needed (0 to use pointers). */
dvander@2226: 		KeHashComparator cmp;		/**< Comparator (if NULL, void * comparison used) */
dvander@2226: 		KeHashDestructor dtor;		/**< Optional function for performing dtor cleanup. */
dvander@2226: 		KeHashCopyCtor ctor;		/**< If bytes != 0, must be a valid function 
dvander@2226: 										 (ignored otherwise). */
dvander@2226: 	};
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * @brief Creates a new hash table structure.
dvander@2226: 	 *
dvander@2226: 	 * @param bits				Dictates starting number of buckets as a power of two.
dvander@2226: 	 *							Pass 0 for the default (which is 4).
dvander@2226: 	 * @param key_gen			Key generation function.
dvander@2226: 	 * @param key_marshal		Structure detailing how to marshal keys.
dvander@2226: 	 * @param vak_marshal		Structure detailing how to marshal values.
dvander@2226: 	 * @param nodeAlloc			Node allocator (can be NULL for malloc/free).
dvander@2226: 	 * @param keep_free_list	True to keep a free list of nodes, false otherwise.
dvander@2226: 	 * @return					New hash table container.
dvander@2226: 	 */
dvander@2226: 	extern KeHashTable *KE_CreateHashTable(
dvander@2226: 		uint32_t bits,
dvander@2226: 		KeHashGenerator key_gen,
dvander@2226: 		const KeHashMarshal *key_marshal,
dvander@2226: 		const KeHashMarshal *val_marshal,
dvander@2226: 		ke_allocator_t *nodeAlloc,
dvander@2226: 		bool keep_free_list
dvander@2226: 		);
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * @brief Destroys a hash table.
dvander@2226: 	 *
dvander@2226: 	 * @param table				Hash table.
dvander@2226: 	 */
dvander@2226: 	extern void KE_DestroyHashTable(KeHashTable *table);
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * @brief Adds a key/value to the hash table.  If the pair already exists, the old value 
dvander@2226: 	 * is overwritten (calling any destructors as necessary).
dvander@2226: 	 *
dvander@2226: 	 * @param table				Hash table.
dvander@2226: 	 * @param key				Key pointer.
dvander@2226: 	 * @param val				Value pointer.
dvander@2226: 	 */
dvander@2226: 	extern void KE_AddToHashTable(KeHashTable *table, const void *key, void *val);
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * @brief Removes a key entry from the hash table.
dvander@2226: 	 *
dvander@2226: 	 * @param table				Hash table.
dvander@2226: 	 * @param key				Key pointer.
dvander@2226: 	 */
dvander@2226: 	extern void KE_RemoveFromHashTable(KeHashTable *table, const void *key);
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * @brief Finds an entry in the hash table.
dvander@2226: 	 *
dvander@2226: 	 * @param table				Hash table.
dvander@2226: 	 * @param key				Key pointer.
dvander@2226: 	 * @param value				Pointer to store the value (optional).
dvander@2226: 	 * @return					On success, true is returned and value is filled if given.
dvander@2226: 	 *							On failure, false is failed and outputs are undefined.
dvander@2226: 	 */
dvander@2226: 	extern bool KE_FindInHashTable(KeHashTable *table, const void *key, void **value);
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * @brief Clears all entries in the hash table (caching free entries when possible).
dvander@2226: 	 *
dvander@2226: 	 * @param table				Hash table.
dvander@2226: 	 */
dvander@2226: 	extern void KE_ClearHashTable(KeHashTable *table);
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * @brief Generic function for hasing strings.
dvander@2226: 	 *
dvander@2226: 	 * @param str				Key string.
dvander@2226: 	 * @return					Hash value.
dvander@2226: 	 */
dvander@2226: 	extern uint32_t KE_HashString(const void *str);
dvander@2226: }
dvander@2226: 
dvander@2226: #endif //_INCLUDE_KNIGHT_KE_HASHTABLE_H_