portable/include/phashtable.h

/*---------------------------------------------------------------------------*
 *  phashtable.h  *
 *                                                                           *
 *  Copyright 2007, 2008 Nuance Communciations, Inc.                               *
 *                                                                           *
 *  Licensed under the Apache License, Version 2.0 (the 'License');          *
 *  you may not use this file except in compliance with the License.         *
 *                                                                           *
 *  You may obtain a copy of the License at                                  *
 *      http://www.apache.org/licenses/LICENSE-2.0                           *
 *                                                                           *
 *  Unless required by applicable law or agreed to in writing, software      *
 *  distributed under the License is distributed on an 'AS IS' BASIS,        *
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * 
 *  See the License for the specific language governing permissions and      *
 *  limitations under the License.                                           *
 *                                                                           *
 *---------------------------------------------------------------------------*/

#ifndef PHASHTABLE_H
#define PHASHTABLE_H



#include "PortPrefix.h"
#include "ptypes.h"
#include "ESR_ReturnCode.h"

/**
 * The default initial capacity of a hash table.
 */
#define PHASH_TABLE_DEFAULT_CAPACITY 11

/**
 *
 * The default maximum load factor
 */
#define PHASH_TABLE_DEFAULT_MAX_LOAD_FACTOR (0.75f)

/**
 * Default hash function used for hashing keys.  The default function assumes
 * the key is a 0-terminated LSTRING.
 */
#define PHASH_TABLE_DEFAULT_HASH_FUNCTION NULL

/**
 * Default compare function used for hashing keys.  The default function
 * assumes the key are 0-terminated LSTRING and uses LSTRCMP.
 */
#define PHASH_TABLE_DEFAULT_COMP_FUNCTION NULL

/**
 * @addtogroup HashTableModule HashTable API functions
 * Abstract hash table operations.  The keys of the Map are strings and values
 * are plain void pointers.  The keys and values are only stored as pointers
 * and it is the responsibility of the user to ensure proper memory management
 * for the keys and values.
 *
 * The HashTable is implemented using an array of linked lists.  The capacity
 * of the HashTable is the number of entries in this array.  The load factor
 * of the HashTable is the ratio of the total number of entries in the table
 * vs the capacity of the table.  The lower the load factor, the faster the
 * look-up is.  However, a lower load factor calls for a bigger capacity,
 * hence it increases the memory requirement.
 *
 * When the load factor exceeds the maximum load factor, the capacity of the
 * hash table is increased and each entry is put in its new linked list based
 * on the new capacity.
 *
 * @{
 */

/**
 * Signature for hashing functions.
 */
typedef unsigned int(*PHashFunction)(const void *key);

/**
 * Signature for comparison functions.  Must return 0 if key1 is identical to
 * key2 and non-zero otherwise.  The hash function and the comparison function
 * are related in the sense that if the comparison function for two keys
 * return 0, then the values returned by the hash function when given these
 * keys as arguments must be equal.
 */
typedef int (*PHashCompFunction)(const LCHAR *key1, const LCHAR *key2);

/** Typedef */
typedef struct PHashTable_t PHashTable;
/** Typedef */
typedef struct PHashTableEntry_t PHashTableEntry;

/**
 * Structure specified to specify initialization parameters for the hash
 * table.
 */
typedef struct PHashTableArgs_t
{
  /**
   * Total capacity.
   */
  size_t capacity;
  
  /**
   * Maximum load-factor before hashtable is rehashed.
   */
  float maxLoadFactor;
  
  /**
   * Hashing function used to compute the hashcode of a key.
   */
  PHashFunction hashFunction;
  
  /**
   * Function used to compare two keys.
   */
  PHashCompFunction compFunction;
}
PHashTableArgs;

/**
 * Creates an hash table.  The hash table is created with specified capacity
 * and maximum load factor.
 *
 * @param hashArgs Specifies the arguments controlling the hashtable.  If
 * NULL, all arguments are assumed to be the default value.  This value is
 * copied. This is the responsibility of the caller to delete the
 * HashTableArgs if required.
 *
 * @param memTag Memory tag to be used for the internal memory allocation
 * calls.  Since this string is used by the memory allocation tag, it is not
 * copied internally and it must remain valid for the lifetime of the hash
 * table including the call to the HashTableDestroy function.  Most likely,
 * this string is a static string or is allocated from the stack.
 *
 * @param hashtable A pointer to the returned hash table. This parameter may
 * not be NULL.
 * @return ESR_INVALID_ARGUMENT if hashArgs, or hashTable is null or
 * hashArgs->maxLoadFactor <= 0; ESR_OUT_OF_MEMORY if system is out of memory
 */
PORTABLE_API ESR_ReturnCode PHashTableCreate(PHashTableArgs *hashArgs,
    const LCHAR *memTag,
    PHashTable **hashtable);
    
/**
 * Destructor.  The keys and values need to be deleted (if necessary) before
 * deleting the table to avoid memory leak.
 *
 * @param ESR_INVALID_ARGUMENT if hashtable is null
 */
PORTABLE_API ESR_ReturnCode PHashTableDestroy(PHashTable *hashtable);

/**
 * Retrieves the size (number of entries) of the hashtable.
 *
 * @return ESR_INVALID_ARGUMENT if hashtable or size is null
 */
PORTABLE_API ESR_ReturnCode PHashTableGetSize(PHashTable *hashtable,
    size_t *size);
    
    
/**
 * Retrieves the value associated with a key.
 *
 * @param hashtable The hashtable
 * @param key The key for which to retrieve the value.
 * @param value The value associated with the key.
 * @return If no match, ESR_NO_MATCH_ERROR is returned.
 */
PORTABLE_API ESR_ReturnCode PHashTableGetValue(PHashTable *hashtable,
    const void *key, void **value);
    
/**
 * Indicates if hashtable contains the specified key.
 *
 * @param hashtable The hashtable
 * @param key The key for which to retrieve the value.
 * @param exists [out] True if the key was found
 * @return ESR_INVALID_ARGUMENT if self is null
 */
PORTABLE_API ESR_ReturnCode PHashTableContainsKey(PHashTable *hashtable,
    const void *key, ESR_BOOL* exists);
/**
 * Associates a value with a key.
 *
 * @param hashtable The hashtable
 *
 * @param key The key to associate a value with.
 *
 * @param value The value to associate with a key.
 *
 * @param oldValue If this pointer is non-NULL, it will be set to the
 * value previously associated with the key.
 * @return ESR_INVALID_STATE if hashtable is null
 */
PORTABLE_API ESR_ReturnCode PHashTablePutValue(PHashTable *hashtable,
    const void *key,
    const void *value,
    void **oldValue);
    
/**
 * Removes the value with associated with a key.  Note that calling this
 * function might cause a leak in the event that the key needs to be deleted.
 * In those situations, use PHashTableGetEntry, then retrieve the key by
 * PHashTableEntryGetKeyValue, destroy the key and value and then use
 * PHashTableEntryRemove.
 *
 * @param hashtable The hashtable
 * @param key The key for which to remove the associated value.
 * @param oldValue If this pointer is non-NULL, it will be set to the value
 * previously associated with the key and that was removed.
 * @return ESR_INVALID_ARGUMENT if hashtable is null
 */
PORTABLE_API ESR_ReturnCode PHashTableRemoveValue(PHashTable *hashtable,
    const void *key,
    void **oldValue);
    
/**
 * Retrieves the hash entry corresponding to the key.
 *
 * @param hashtable The hashtable
 * @param key The key for which to retrieve the hash entry.
 * @param entry The entry associated with the key. Cannot be NULL.
 * @return If no match, ESR_NO_MATCH_ERROR is returned.
 */
PORTABLE_API ESR_ReturnCode PHashTableGetEntry(PHashTable *hashtable,
    const void *key,
    PHashTableEntry **entry);
    
/**
 * Returns the key and value associated with this entry.  Both key and values
 * can be deleted after removing the entry from the table.
 *
 * @param entry The hashtable entry
 * @param key If non-NULL, returns the key associated with the entry.
 * @param value If non-NULL, returns the value associated with the entry.
 * @return ESR_INVALID_ARGUMENT if entry is null
 */
PORTABLE_API ESR_ReturnCode PHashTableEntryGetKeyValue(PHashTableEntry *entry,
    void **key,
    void **value);
    
/**
 * Sets the value associated with this entry.
 *
 * @param entry The hashtable entry.
 * @param value The value to associate with the entry.
 * @param oldValue If this pointer is non-NULL, it will be set to the value
 * previously associated with this entry.
 */
PORTABLE_API ESR_ReturnCode PHashTableEntrySetValue(PHashTableEntry *entry,
    const void *value,
    void **oldValue);
    
/**
 * Removes the entry from its hash table.
 *
 * POST-CONDITION: 'entry' variable is invalid
 *
 * @param entry The hashtable entry.
 * @return ESR_INVALID_ARGUMENT if entry is null
 */
PORTABLE_API ESR_ReturnCode PHashTableEntryRemove(PHashTableEntry *entry);

/**
 * Resets the iterator at the beginning.
 */
PORTABLE_API
ESR_ReturnCode PHashTableEntryGetFirst(PHashTable *table,
                                       PHashTableEntry **entry);
                                       
/**
 * Advance to the next entry in the hash table.
 *
 * @param entry the current entry.
 * @return ESR_INVALID_ARGUMENT if entry or the value it points to is null.
 */
PORTABLE_API ESR_ReturnCode PHashTableEntryAdvance(PHashTableEntry** entry);

/**
 * @}
 */

#endif