1 /*---------------------------------------------------------------------------* 2 * phashtable.h * 3 * * 4 * Copyright 2007, 2008 Nuance Communciations, Inc. * 5 * * 6 * Licensed under the Apache License, Version 2.0 (the 'License'); * 7 * you may not use this file except in compliance with the License. * 8 * * 9 * You may obtain a copy of the License at * 10 * http://www.apache.org/licenses/LICENSE-2.0 * 11 * * 12 * Unless required by applicable law or agreed to in writing, software * 13 * distributed under the License is distributed on an 'AS IS' BASIS, * 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * 15 * See the License for the specific language governing permissions and * 16 * limitations under the License. * 17 * * 18 *---------------------------------------------------------------------------*/ 19 20 #ifndef PHASHTABLE_H 21 #define PHASHTABLE_H 22 23 24 25 #include "PortPrefix.h" 26 #include "ptypes.h" 27 #include "ESR_ReturnCode.h" 28 29 /** 30 * The default initial capacity of a hash table. 31 */ 32 #define PHASH_TABLE_DEFAULT_CAPACITY 11 33 34 /** 35 * 36 * The default maximum load factor 37 */ 38 #define PHASH_TABLE_DEFAULT_MAX_LOAD_FACTOR (0.75f) 39 40 /** 41 * Default hash function used for hashing keys. The default function assumes 42 * the key is a 0-terminated LSTRING. 43 */ 44 #define PHASH_TABLE_DEFAULT_HASH_FUNCTION NULL 45 46 /** 47 * Default compare function used for hashing keys. The default function 48 * assumes the key are 0-terminated LSTRING and uses LSTRCMP. 49 */ 50 #define PHASH_TABLE_DEFAULT_COMP_FUNCTION NULL 51 52 /** 53 * @addtogroup HashTableModule HashTable API functions 54 * Abstract hash table operations. The keys of the Map are strings and values 55 * are plain void pointers. The keys and values are only stored as pointers 56 * and it is the responsibility of the user to ensure proper memory management 57 * for the keys and values. 58 * 59 * The HashTable is implemented using an array of linked lists. The capacity 60 * of the HashTable is the number of entries in this array. The load factor 61 * of the HashTable is the ratio of the total number of entries in the table 62 * vs the capacity of the table. The lower the load factor, the faster the 63 * look-up is. However, a lower load factor calls for a bigger capacity, 64 * hence it increases the memory requirement. 65 * 66 * When the load factor exceeds the maximum load factor, the capacity of the 67 * hash table is increased and each entry is put in its new linked list based 68 * on the new capacity. 69 * 70 * @{ 71 */ 72 73 /** 74 * Signature for hashing functions. 75 */ 76 typedef unsigned int(*PHashFunction)(const void *key); 77 78 /** 79 * Signature for comparison functions. Must return 0 if key1 is identical to 80 * key2 and non-zero otherwise. The hash function and the comparison function 81 * are related in the sense that if the comparison function for two keys 82 * return 0, then the values returned by the hash function when given these 83 * keys as arguments must be equal. 84 */ 85 typedef int (*PHashCompFunction)(const LCHAR *key1, const LCHAR *key2); 86 87 /** Typedef */ 88 typedef struct PHashTable_t PHashTable; 89 /** Typedef */ 90 typedef struct PHashTableEntry_t PHashTableEntry; 91 92 /** 93 * Structure specified to specify initialization parameters for the hash 94 * table. 95 */ 96 typedef struct PHashTableArgs_t 97 { 98 /** 99 * Total capacity. 100 */ 101 size_t capacity; 102 103 /** 104 * Maximum load-factor before hashtable is rehashed. 105 */ 106 float maxLoadFactor; 107 108 /** 109 * Hashing function used to compute the hashcode of a key. 110 */ 111 PHashFunction hashFunction; 112 113 /** 114 * Function used to compare two keys. 115 */ 116 PHashCompFunction compFunction; 117 } 118 PHashTableArgs; 119 120 /** 121 * Creates an hash table. The hash table is created with specified capacity 122 * and maximum load factor. 123 * 124 * @param hashArgs Specifies the arguments controlling the hashtable. If 125 * NULL, all arguments are assumed to be the default value. This value is 126 * copied. This is the responsibility of the caller to delete the 127 * HashTableArgs if required. 128 * 129 * @param memTag Memory tag to be used for the internal memory allocation 130 * calls. Since this string is used by the memory allocation tag, it is not 131 * copied internally and it must remain valid for the lifetime of the hash 132 * table including the call to the HashTableDestroy function. Most likely, 133 * this string is a static string or is allocated from the stack. 134 * 135 * @param hashtable A pointer to the returned hash table. This parameter may 136 * not be NULL. 137 * @return ESR_INVALID_ARGUMENT if hashArgs, or hashTable is null or 138 * hashArgs->maxLoadFactor <= 0; ESR_OUT_OF_MEMORY if system is out of memory 139 */ 140 PORTABLE_API ESR_ReturnCode PHashTableCreate(PHashTableArgs *hashArgs, 141 const LCHAR *memTag, 142 PHashTable **hashtable); 143 144 /** 145 * Destructor. The keys and values need to be deleted (if necessary) before 146 * deleting the table to avoid memory leak. 147 * 148 * @param ESR_INVALID_ARGUMENT if hashtable is null 149 */ 150 PORTABLE_API ESR_ReturnCode PHashTableDestroy(PHashTable *hashtable); 151 152 /** 153 * Retrieves the size (number of entries) of the hashtable. 154 * 155 * @return ESR_INVALID_ARGUMENT if hashtable or size is null 156 */ 157 PORTABLE_API ESR_ReturnCode PHashTableGetSize(PHashTable *hashtable, 158 size_t *size); 159 160 161 /** 162 * Retrieves the value associated with a key. 163 * 164 * @param hashtable The hashtable 165 * @param key The key for which to retrieve the value. 166 * @param value The value associated with the key. 167 * @return If no match, ESR_NO_MATCH_ERROR is returned. 168 */ 169 PORTABLE_API ESR_ReturnCode PHashTableGetValue(PHashTable *hashtable, 170 const void *key, void **value); 171 172 /** 173 * Indicates if hashtable contains the specified key. 174 * 175 * @param hashtable The hashtable 176 * @param key The key for which to retrieve the value. 177 * @param exists [out] True if the key was found 178 * @return ESR_INVALID_ARGUMENT if self is null 179 */ 180 PORTABLE_API ESR_ReturnCode PHashTableContainsKey(PHashTable *hashtable, 181 const void *key, ESR_BOOL* exists); 182 /** 183 * Associates a value with a key. 184 * 185 * @param hashtable The hashtable 186 * 187 * @param key The key to associate a value with. 188 * 189 * @param value The value to associate with a key. 190 * 191 * @param oldValue If this pointer is non-NULL, it will be set to the 192 * value previously associated with the key. 193 * @return ESR_INVALID_STATE if hashtable is null 194 */ 195 PORTABLE_API ESR_ReturnCode PHashTablePutValue(PHashTable *hashtable, 196 const void *key, 197 const void *value, 198 void **oldValue); 199 200 /** 201 * Removes the value with associated with a key. Note that calling this 202 * function might cause a leak in the event that the key needs to be deleted. 203 * In those situations, use PHashTableGetEntry, then retrieve the key by 204 * PHashTableEntryGetKeyValue, destroy the key and value and then use 205 * PHashTableEntryRemove. 206 * 207 * @param hashtable The hashtable 208 * @param key The key for which to remove the associated value. 209 * @param oldValue If this pointer is non-NULL, it will be set to the value 210 * previously associated with the key and that was removed. 211 * @return ESR_INVALID_ARGUMENT if hashtable is null 212 */ 213 PORTABLE_API ESR_ReturnCode PHashTableRemoveValue(PHashTable *hashtable, 214 const void *key, 215 void **oldValue); 216 217 /** 218 * Retrieves the hash entry corresponding to the key. 219 * 220 * @param hashtable The hashtable 221 * @param key The key for which to retrieve the hash entry. 222 * @param entry The entry associated with the key. Cannot be NULL. 223 * @return If no match, ESR_NO_MATCH_ERROR is returned. 224 */ 225 PORTABLE_API ESR_ReturnCode PHashTableGetEntry(PHashTable *hashtable, 226 const void *key, 227 PHashTableEntry **entry); 228 229 /** 230 * Returns the key and value associated with this entry. Both key and values 231 * can be deleted after removing the entry from the table. 232 * 233 * @param entry The hashtable entry 234 * @param key If non-NULL, returns the key associated with the entry. 235 * @param value If non-NULL, returns the value associated with the entry. 236 * @return ESR_INVALID_ARGUMENT if entry is null 237 */ 238 PORTABLE_API ESR_ReturnCode PHashTableEntryGetKeyValue(PHashTableEntry *entry, 239 void **key, 240 void **value); 241 242 /** 243 * Sets the value associated with this entry. 244 * 245 * @param entry The hashtable entry. 246 * @param value The value to associate with the entry. 247 * @param oldValue If this pointer is non-NULL, it will be set to the value 248 * previously associated with this entry. 249 */ 250 PORTABLE_API ESR_ReturnCode PHashTableEntrySetValue(PHashTableEntry *entry, 251 const void *value, 252 void **oldValue); 253 254 /** 255 * Removes the entry from its hash table. 256 * 257 * POST-CONDITION: 'entry' variable is invalid 258 * 259 * @param entry The hashtable entry. 260 * @return ESR_INVALID_ARGUMENT if entry is null 261 */ 262 PORTABLE_API ESR_ReturnCode PHashTableEntryRemove(PHashTableEntry *entry); 263 264 /** 265 * Resets the iterator at the beginning. 266 */ 267 PORTABLE_API 268 ESR_ReturnCode PHashTableEntryGetFirst(PHashTable *table, 269 PHashTableEntry **entry); 270 271 /** 272 * Advance to the next entry in the hash table. 273 * 274 * @param entry the current entry. 275 * @return ESR_INVALID_ARGUMENT if entry or the value it points to is null. 276 */ 277 PORTABLE_API ESR_ReturnCode PHashTableEntryAdvance(PHashTableEntry** entry); 278 279 /** 280 * @} 281 */ 282 283 #endif 284