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 */
76typedef 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 */
85typedef int (*PHashCompFunction)(const LCHAR *key1, const LCHAR *key2);
86
87/** Typedef */
88typedef struct PHashTable_t PHashTable;
89/** Typedef */
90typedef struct PHashTableEntry_t PHashTableEntry;
91
92/**
93 * Structure specified to specify initialization parameters for the hash
94 * table.
95 */
96typedef 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}
118PHashTableArgs;
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 */
140PORTABLE_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 */
150PORTABLE_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 */
157PORTABLE_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 */
169PORTABLE_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 */
180PORTABLE_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 */
195PORTABLE_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 */
213PORTABLE_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 */
225PORTABLE_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 */
238PORTABLE_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 */
250PORTABLE_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 */
262PORTABLE_API ESR_ReturnCode PHashTableEntryRemove(PHashTableEntry *entry);
263
264/**
265 * Resets the iterator at the beginning.
266 */
267PORTABLE_API
268ESR_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 */
277PORTABLE_API ESR_ReturnCode PHashTableEntryAdvance(PHashTableEntry** entry);
278
279/**
280 * @}
281 */
282
283#endif
284