The Tor Browser / file comparison

comparison: intl/icu/source/common/uhash.h

intl/icu/source/common/uhash.h

branch
TOR_BUG_3246
changeset 4
fc2d59ddac77
equal deleted inserted replaced
-1:000000000000 0:a4986dcc1540
1 /*
2 ******************************************************************************
3 * Copyright (C) 1997-2011, International Business Machines
4 * Corporation and others. All Rights Reserved.
5 ******************************************************************************
6 * Date Name Description
7 * 03/22/00 aliu Adapted from original C++ ICU Hashtable.
8 * 07/06/01 aliu Modified to support int32_t keys on
9 * platforms with sizeof(void*) < 32.
10 ******************************************************************************
11 */
12
13 #ifndef UHASH_H
14 #define UHASH_H
15
16 #include "unicode/utypes.h"
17 #include "cmemory.h"
18 #include "uelement.h"
19
20 /**
21 * UHashtable stores key-value pairs and does moderately fast lookup
22 * based on keys. It provides a good tradeoff between access time and
23 * storage space. As elements are added to it, it grows to accomodate
24 * them. By default, the table never shrinks, even if all elements
25 * are removed from it.
26 *
27 * Keys and values are stored as void* pointers. These void* pointers
28 * may be actual pointers to strings, objects, or any other structure
29 * in memory, or they may simply be integral values cast to void*.
30 * UHashtable doesn't care and manipulates them via user-supplied
31 * functions. These functions hash keys, compare keys, delete keys,
32 * and delete values. Some function pointers are optional (may be
33 * NULL); others must be supplied. Several prebuilt functions exist
34 * to handle common key types.
35 *
36 * UHashtable ownership of keys and values is flexible, and controlled
37 * by whether or not the key deleter and value deleter functions are
38 * set. If a void* key is actually a pointer to a deletable object,
39 * then UHashtable can be made to delete that object by setting the
40 * key deleter function pointer to a non-NULL value. If this is done,
41 * then keys passed to uhash_put() are owned by the hashtable and will
42 * be deleted by it at some point, either as keys are replaced, or
43 * when uhash_close() is finally called. The same is true of values
44 * and the value deleter function pointer. Keys passed to methods
45 * other than uhash_put() are never owned by the hashtable.
46 *
47 * NULL values are not allowed. uhash_get() returns NULL to indicate
48 * a key that is not in the table, and having a NULL value in the
49 * table would generate an ambiguous result. If a key and a NULL
50 * value is passed to uhash_put(), this has the effect of doing a
51 * uhash_remove() on that key. This keeps uhash_get(), uhash_count(),
52 * and uhash_nextElement() consistent with one another.
53 *
54 * To see everything in a hashtable, use uhash_nextElement() to
55 * iterate through its contents. Each call to this function returns a
56 * UHashElement pointer. A hash element contains a key, value, and
57 * hashcode. During iteration an element may be deleted by calling
58 * uhash_removeElement(); iteration may safely continue thereafter.
59 * The uhash_remove() function may also be safely called in
60 * mid-iteration. However, if uhash_put() is called during iteration
61 * then the iteration will be out of sync. Under no circumstances
62 * should the UHashElement returned by uhash_nextElement be modified
63 * directly.
64 *
65 * By default, the hashtable grows when necessary, but never shrinks,
66 * even if all items are removed. For most applications this is
67 * optimal. However, in a highly dynamic usage where memory is at a
68 * premium, the table can be set to both grow and shrink by calling
69 * uhash_setResizePolicy() with the policy U_GROW_AND_SHRINK. In a
70 * situation where memory is critical and the client wants a table
71 * that does not grow at all, the constant U_FIXED can be used.
72 */
73
74 /********************************************************************
75 * Data Structures
76 ********************************************************************/
77
78 U_CDECL_BEGIN
79
80 /**
81 * A key or value within a UHashtable.
82 * The hashing and comparison functions take a pointer to a
83 * UHashTok, but the deleter receives the void* pointer within it.
84 */
85 typedef UElement UHashTok;
86
87 /**
88 * This is a single hash element.
89 */
90 struct UHashElement {
91 /* Reorder these elements to pack nicely if necessary */
92 int32_t hashcode;
93 UHashTok value;
94 UHashTok key;
95 };
96 typedef struct UHashElement UHashElement;
97
98 /**
99 * A hashing function.
100 * @param key A key stored in a hashtable
101 * @return A NON-NEGATIVE hash code for parm.
102 */
103 typedef int32_t U_CALLCONV UHashFunction(const UHashTok key);
104
105 /**
106 * A key equality (boolean) comparison function.
107 */
108 typedef UElementsAreEqual UKeyComparator;
109
110 /**
111 * A value equality (boolean) comparison function.
112 */
113 typedef UElementsAreEqual UValueComparator;
114
115 /* see cmemory.h for UObjectDeleter and uprv_deleteUObject() */
116
117 /**
118 * This specifies whether or not, and how, the hastable resizes itself.
119 * See uhash_setResizePolicy().
120 */
121 enum UHashResizePolicy {
122 U_GROW, /* Grow on demand, do not shrink */
123 U_GROW_AND_SHRINK, /* Grow and shrink on demand */
124 U_FIXED /* Never change size */
125 };
126
127 /**
128 * The UHashtable struct. Clients should treat this as an opaque data
129 * type and manipulate it only through the uhash_... API.
130 */
131 struct UHashtable {
132
133 /* Main key-value pair storage array */
134
135 UHashElement *elements;
136
137 /* Function pointers */
138
139 UHashFunction *keyHasher; /* Computes hash from key.
140 * Never null. */
141 UKeyComparator *keyComparator; /* Compares keys for equality.
142 * Never null. */
143 UValueComparator *valueComparator; /* Compares the values for equality */
144
145 UObjectDeleter *keyDeleter; /* Deletes keys when required.
146 * If NULL won't do anything */
147 UObjectDeleter *valueDeleter; /* Deletes values when required.
148 * If NULL won't do anything */
149
150 /* Size parameters */
151
152 int32_t count; /* The number of key-value pairs in this table.
153 * 0 <= count <= length. In practice we
154 * never let count == length (see code). */
155 int32_t length; /* The physical size of the arrays hashes, keys
156 * and values. Must be prime. */
157
158 /* Rehashing thresholds */
159
160 int32_t highWaterMark; /* If count > highWaterMark, rehash */
161 int32_t lowWaterMark; /* If count < lowWaterMark, rehash */
162 float highWaterRatio; /* 0..1; high water as a fraction of length */
163 float lowWaterRatio; /* 0..1; low water as a fraction of length */
164
165 int8_t primeIndex; /* Index into our prime table for length.
166 * length == PRIMES[primeIndex] */
167 UBool allocated; /* Was this UHashtable allocated? */
168 };
169 typedef struct UHashtable UHashtable;
170
171 U_CDECL_END
172
173 /********************************************************************
174 * API
175 ********************************************************************/
176
177 /**
178 * Initialize a new UHashtable.
179 * @param keyHash A pointer to the key hashing function. Must not be
180 * NULL.
181 * @param keyComp A pointer to the function that compares keys. Must
182 * not be NULL.
183 * @param status A pointer to an UErrorCode to receive any errors.
184 * @return A pointer to a UHashtable, or 0 if an error occurred.
185 * @see uhash_openSize
186 */
187 U_CAPI UHashtable* U_EXPORT2
188 uhash_open(UHashFunction *keyHash,
189 UKeyComparator *keyComp,
190 UValueComparator *valueComp,
191 UErrorCode *status);
192
193 /**
194 * Initialize a new UHashtable with a given initial size.
195 * @param keyHash A pointer to the key hashing function. Must not be
196 * NULL.
197 * @param keyComp A pointer to the function that compares keys. Must
198 * not be NULL.
199 * @param size The initial capacity of this hash table.
200 * @param status A pointer to an UErrorCode to receive any errors.
201 * @return A pointer to a UHashtable, or 0 if an error occurred.
202 * @see uhash_open
203 */
204 U_CAPI UHashtable* U_EXPORT2
205 uhash_openSize(UHashFunction *keyHash,
206 UKeyComparator *keyComp,
207 UValueComparator *valueComp,
208 int32_t size,
209 UErrorCode *status);
210
211 /**
212 * Initialize an existing UHashtable.
213 * @param keyHash A pointer to the key hashing function. Must not be
214 * NULL.
215 * @param keyComp A pointer to the function that compares keys. Must
216 * not be NULL.
217 * @param status A pointer to an UErrorCode to receive any errors.
218 * @return A pointer to a UHashtable, or 0 if an error occurred.
219 * @see uhash_openSize
220 */
221 U_CAPI UHashtable* U_EXPORT2
222 uhash_init(UHashtable *hash,
223 UHashFunction *keyHash,
224 UKeyComparator *keyComp,
225 UValueComparator *valueComp,
226 UErrorCode *status);
227
228 /**
229 * Close a UHashtable, releasing the memory used.
230 * @param hash The UHashtable to close. If hash is NULL no operation is performed.
231 */
232 U_CAPI void U_EXPORT2
233 uhash_close(UHashtable *hash);
234
235
236
237 /**
238 * Set the function used to hash keys.
239 * @param hash The UHashtable to set
240 * @param fn the function to be used hash keys; must not be NULL
241 * @return the previous key hasher; non-NULL
242 */
243 U_CAPI UHashFunction *U_EXPORT2
244 uhash_setKeyHasher(UHashtable *hash, UHashFunction *fn);
245
246 /**
247 * Set the function used to compare keys. The default comparison is a
248 * void* pointer comparison.
249 * @param hash The UHashtable to set
250 * @param fn the function to be used compare keys; must not be NULL
251 * @return the previous key comparator; non-NULL
252 */
253 U_CAPI UKeyComparator *U_EXPORT2
254 uhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn);
255
256 /**
257 * Set the function used to compare values. The default comparison is a
258 * void* pointer comparison.
259 * @param hash The UHashtable to set
260 * @param fn the function to be used compare keys; must not be NULL
261 * @return the previous key comparator; non-NULL
262 */
263 U_CAPI UValueComparator *U_EXPORT2
264 uhash_setValueComparator(UHashtable *hash, UValueComparator *fn);
265
266 /**
267 * Set the function used to delete keys. If this function pointer is
268 * NULL, this hashtable does not delete keys. If it is non-NULL, this
269 * hashtable does delete keys. This function should be set once
270 * before any elements are added to the hashtable and should not be
271 * changed thereafter.
272 * @param hash The UHashtable to set
273 * @param fn the function to be used delete keys, or NULL
274 * @return the previous key deleter; may be NULL
275 */
276 U_CAPI UObjectDeleter *U_EXPORT2
277 uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn);
278
279 /**
280 * Set the function used to delete values. If this function pointer
281 * is NULL, this hashtable does not delete values. If it is non-NULL,
282 * this hashtable does delete values. This function should be set
283 * once before any elements are added to the hashtable and should not
284 * be changed thereafter.
285 * @param hash The UHashtable to set
286 * @param fn the function to be used delete values, or NULL
287 * @return the previous value deleter; may be NULL
288 */
289 U_CAPI UObjectDeleter *U_EXPORT2
290 uhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn);
291
292 /**
293 * Specify whether or not, and how, the hastable resizes itself.
294 * By default, tables grow but do not shrink (policy U_GROW).
295 * See enum UHashResizePolicy.
296 * @param hash The UHashtable to set
297 * @param policy The way the hashtable resizes itself, {U_GROW, U_GROW_AND_SHRINK, U_FIXED}
298 */
299 U_CAPI void U_EXPORT2
300 uhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy);
301
302 /**
303 * Get the number of key-value pairs stored in a UHashtable.
304 * @param hash The UHashtable to query.
305 * @return The number of key-value pairs stored in hash.
306 */
307 U_CAPI int32_t U_EXPORT2
308 uhash_count(const UHashtable *hash);
309
310 /**
311 * Put a (key=pointer, value=pointer) item in a UHashtable. If the
312 * keyDeleter is non-NULL, then the hashtable owns 'key' after this
313 * call. If the valueDeleter is non-NULL, then the hashtable owns
314 * 'value' after this call. Storing a NULL value is the same as
315 * calling uhash_remove().
316 * @param hash The target UHashtable.
317 * @param key The key to store.
318 * @param value The value to store, may be NULL (see above).
319 * @param status A pointer to an UErrorCode to receive any errors.
320 * @return The previous value, or NULL if none.
321 * @see uhash_get
322 */
323 U_CAPI void* U_EXPORT2
324 uhash_put(UHashtable *hash,
325 void *key,
326 void *value,
327 UErrorCode *status);
328
329 /**
330 * Put a (key=integer, value=pointer) item in a UHashtable.
331 * keyDeleter must be NULL. If the valueDeleter is non-NULL, then the
332 * hashtable owns 'value' after this call. Storing a NULL value is
333 * the same as calling uhash_remove().
334 * @param hash The target UHashtable.
335 * @param key The integer key to store.
336 * @param value The value to store, may be NULL (see above).
337 * @param status A pointer to an UErrorCode to receive any errors.
338 * @return The previous value, or NULL if none.
339 * @see uhash_get
340 */
341 U_CAPI void* U_EXPORT2
342 uhash_iput(UHashtable *hash,
343 int32_t key,
344 void* value,
345 UErrorCode *status);
346
347 /**
348 * Put a (key=pointer, value=integer) item in a UHashtable. If the
349 * keyDeleter is non-NULL, then the hashtable owns 'key' after this
350 * call. valueDeleter must be NULL. Storing a 0 value is the same as
351 * calling uhash_remove().
352 * @param hash The target UHashtable.
353 * @param key The key to store.
354 * @param value The integer value to store.
355 * @param status A pointer to an UErrorCode to receive any errors.
356 * @return The previous value, or 0 if none.
357 * @see uhash_get
358 */
359 U_CAPI int32_t U_EXPORT2
360 uhash_puti(UHashtable *hash,
361 void* key,
362 int32_t value,
363 UErrorCode *status);
364
365 /**
366 * Put a (key=integer, value=integer) item in a UHashtable. If the
367 * keyDeleter is non-NULL, then the hashtable owns 'key' after this
368 * call. valueDeleter must be NULL. Storing a 0 value is the same as
369 * calling uhash_remove().
370 * @param hash The target UHashtable.
371 * @param key The key to store.
372 * @param value The integer value to store.
373 * @param status A pointer to an UErrorCode to receive any errors.
374 * @return The previous value, or 0 if none.
375 * @see uhash_get
376 */
377 U_CAPI int32_t U_EXPORT2
378 uhash_iputi(UHashtable *hash,
379 int32_t key,
380 int32_t value,
381 UErrorCode *status);
382
383 /**
384 * Retrieve a pointer value from a UHashtable using a pointer key,
385 * as previously stored by uhash_put().
386 * @param hash The target UHashtable.
387 * @param key A pointer key stored in a hashtable
388 * @return The requested item, or NULL if not found.
389 */
390 U_CAPI void* U_EXPORT2
391 uhash_get(const UHashtable *hash,
392 const void *key);
393
394 /**
395 * Retrieve a pointer value from a UHashtable using a integer key,
396 * as previously stored by uhash_iput().
397 * @param hash The target UHashtable.
398 * @param key An integer key stored in a hashtable
399 * @return The requested item, or NULL if not found.
400 */
401 U_CAPI void* U_EXPORT2
402 uhash_iget(const UHashtable *hash,
403 int32_t key);
404
405 /**
406 * Retrieve an integer value from a UHashtable using a pointer key,
407 * as previously stored by uhash_puti().
408 * @param hash The target UHashtable.
409 * @param key A pointer key stored in a hashtable
410 * @return The requested item, or 0 if not found.
411 */
412 U_CAPI int32_t U_EXPORT2
413 uhash_geti(const UHashtable *hash,
414 const void* key);
415 /**
416 * Retrieve an integer value from a UHashtable using an integer key,
417 * as previously stored by uhash_iputi().
418 * @param hash The target UHashtable.
419 * @param key An integer key stored in a hashtable
420 * @return The requested item, or 0 if not found.
421 */
422 U_CAPI int32_t U_EXPORT2
423 uhash_igeti(const UHashtable *hash,
424 int32_t key);
425
426 /**
427 * Remove an item from a UHashtable stored by uhash_put().
428 * @param hash The target UHashtable.
429 * @param key A key stored in a hashtable
430 * @return The item removed, or NULL if not found.
431 */
432 U_CAPI void* U_EXPORT2
433 uhash_remove(UHashtable *hash,
434 const void *key);
435
436 /**
437 * Remove an item from a UHashtable stored by uhash_iput().
438 * @param hash The target UHashtable.
439 * @param key An integer key stored in a hashtable
440 * @return The item removed, or NULL if not found.
441 */
442 U_CAPI void* U_EXPORT2
443 uhash_iremove(UHashtable *hash,
444 int32_t key);
445
446 /**
447 * Remove an item from a UHashtable stored by uhash_puti().
448 * @param hash The target UHashtable.
449 * @param key An key stored in a hashtable
450 * @return The item removed, or 0 if not found.
451 */
452 U_CAPI int32_t U_EXPORT2
453 uhash_removei(UHashtable *hash,
454 const void* key);
455
456 /**
457 * Remove an item from a UHashtable stored by uhash_iputi().
458 * @param hash The target UHashtable.
459 * @param key An integer key stored in a hashtable
460 * @return The item removed, or 0 if not found.
461 */
462 U_CAPI int32_t U_EXPORT2
463 uhash_iremovei(UHashtable *hash,
464 int32_t key);
465
466 /**
467 * Remove all items from a UHashtable.
468 * @param hash The target UHashtable.
469 */
470 U_CAPI void U_EXPORT2
471 uhash_removeAll(UHashtable *hash);
472
473 /**
474 * Locate an element of a UHashtable. The caller must not modify the
475 * returned object. The primary use of this function is to obtain the
476 * stored key when it may not be identical to the search key. For
477 * example, if the compare function is a case-insensitive string
478 * compare, then the hash key may be desired in order to obtain the
479 * canonical case corresponding to a search key.
480 * @param hash The target UHashtable.
481 * @param key A key stored in a hashtable
482 * @return a hash element, or NULL if the key is not found.
483 */
484 U_CAPI const UHashElement* U_EXPORT2
485 uhash_find(const UHashtable *hash, const void* key);
486
487 /**
488 * Iterate through the elements of a UHashtable. The caller must not
489 * modify the returned object. However, uhash_removeElement() may be
490 * called during iteration to remove an element from the table.
491 * Iteration may safely be resumed afterwards. If uhash_put() is
492 * called during iteration the iteration will then be out of sync and
493 * should be restarted.
494 * @param hash The target UHashtable.
495 * @param pos This should be set to -1 initially, and left untouched
496 * thereafter.
497 * @return a hash element, or NULL if no further key-value pairs
498 * exist in the table.
499 */
500 U_CAPI const UHashElement* U_EXPORT2
501 uhash_nextElement(const UHashtable *hash,
502 int32_t *pos);
503
504 /**
505 * Remove an element, returned by uhash_nextElement(), from the table.
506 * Iteration may be safely continued afterwards.
507 * @param hash The hashtable
508 * @param e The element, returned by uhash_nextElement(), to remove.
509 * Must not be NULL. Must not be an empty or deleted element (as long
510 * as this was returned by uhash_nextElement() it will not be empty or
511 * deleted). Note: Although this parameter is const, it will be
512 * modified.
513 * @return the value that was removed.
514 */
515 U_CAPI void* U_EXPORT2
516 uhash_removeElement(UHashtable *hash, const UHashElement* e);
517
518 /********************************************************************
519 * UHashTok convenience
520 ********************************************************************/
521
522 /**
523 * Return a UHashTok for an integer.
524 * @param i The given integer
525 * @return a UHashTok for an integer.
526 */
527 /*U_CAPI UHashTok U_EXPORT2
528 uhash_toki(int32_t i);*/
529
530 /**
531 * Return a UHashTok for a pointer.
532 * @param p The given pointer
533 * @return a UHashTok for a pointer.
534 */
535 /*U_CAPI UHashTok U_EXPORT2
536 uhash_tokp(void* p);*/
537
538 /********************************************************************
539 * UChar* and char* Support Functions
540 ********************************************************************/
541
542 /**
543 * Generate a hash code for a null-terminated UChar* string. If the
544 * string is not null-terminated do not use this function. Use
545 * together with uhash_compareUChars.
546 * @param key The string (const UChar*) to hash.
547 * @return A hash code for the key.
548 */
549 U_CAPI int32_t U_EXPORT2
550 uhash_hashUChars(const UHashTok key);
551
552 /**
553 * Generate a hash code for a null-terminated char* string. If the
554 * string is not null-terminated do not use this function. Use
555 * together with uhash_compareChars.
556 * @param key The string (const char*) to hash.
557 * @return A hash code for the key.
558 */
559 U_CAPI int32_t U_EXPORT2
560 uhash_hashChars(const UHashTok key);
561
562 /**
563 * Generate a case-insensitive hash code for a null-terminated char*
564 * string. If the string is not null-terminated do not use this
565 * function. Use together with uhash_compareIChars.
566 * @param key The string (const char*) to hash.
567 * @return A hash code for the key.
568 */
569 U_CAPI int32_t U_EXPORT2
570 uhash_hashIChars(const UHashTok key);
571
572 /**
573 * Comparator for null-terminated UChar* strings. Use together with
574 * uhash_hashUChars.
575 * @param key1 The string for comparison
576 * @param key2 The string for comparison
577 * @return true if key1 and key2 are equal, return false otherwise.
578 */
579 U_CAPI UBool U_EXPORT2
580 uhash_compareUChars(const UHashTok key1, const UHashTok key2);
581
582 /**
583 * Comparator for null-terminated char* strings. Use together with
584 * uhash_hashChars.
585 * @param key1 The string for comparison
586 * @param key2 The string for comparison
587 * @return true if key1 and key2 are equal, return false otherwise.
588 */
589 U_CAPI UBool U_EXPORT2
590 uhash_compareChars(const UHashTok key1, const UHashTok key2);
591
592 /**
593 * Case-insensitive comparator for null-terminated char* strings. Use
594 * together with uhash_hashIChars.
595 * @param key1 The string for comparison
596 * @param key2 The string for comparison
597 * @return true if key1 and key2 are equal, return false otherwise.
598 */
599 U_CAPI UBool U_EXPORT2
600 uhash_compareIChars(const UHashTok key1, const UHashTok key2);
601
602 /********************************************************************
603 * UnicodeString Support Functions
604 ********************************************************************/
605
606 /**
607 * Hash function for UnicodeString* keys.
608 * @param key The string (const char*) to hash.
609 * @return A hash code for the key.
610 */
611 U_CAPI int32_t U_EXPORT2
612 uhash_hashUnicodeString(const UElement key);
613
614 /**
615 * Hash function for UnicodeString* keys (case insensitive).
616 * Make sure to use together with uhash_compareCaselessUnicodeString.
617 * @param key The string (const char*) to hash.
618 * @return A hash code for the key.
619 */
620 U_CAPI int32_t U_EXPORT2
621 uhash_hashCaselessUnicodeString(const UElement key);
622
623 /********************************************************************
624 * int32_t Support Functions
625 ********************************************************************/
626
627 /**
628 * Hash function for 32-bit integer keys.
629 * @param key The string (const char*) to hash.
630 * @return A hash code for the key.
631 */
632 U_CAPI int32_t U_EXPORT2
633 uhash_hashLong(const UHashTok key);
634
635 /**
636 * Comparator function for 32-bit integer keys.
637 * @param key1 The integer for comparison
638 * @param Key2 The integer for comparison
639 * @return true if key1 and key2 are equal, return false otherwise
640 */
641 U_CAPI UBool U_EXPORT2
642 uhash_compareLong(const UHashTok key1, const UHashTok key2);
643
644 /********************************************************************
645 * Other Support Functions
646 ********************************************************************/
647
648 /**
649 * Deleter for Hashtable objects.
650 * @param obj The object to be deleted
651 */
652 U_CAPI void U_EXPORT2
653 uhash_deleteHashtable(void *obj);
654
655 /* Use uprv_free() itself as a deleter for any key or value allocated using uprv_malloc. */
656
657 /**
658 * Checks if the given hash tables are equal or not.
659 * @param hash1
660 * @param hash2
661 * @return true if the hashtables are equal and false if not.
662 */
663 U_CAPI UBool U_EXPORT2
664 uhash_equals(const UHashtable* hash1, const UHashtable* hash2);
665
666 #endif

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial