Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members  

uhash.c

00001 /*
00002 *******************************************************************************
00003 *   Copyright (C) 1997-2000, International Business Machines
00004 *   Corporation and others.  All Rights Reserved.
00005 *******************************************************************************
00006 *   Date        Name        Description
00007 *   03/22/00    aliu        Adapted from original C++ ICU Hashtable.
00008 *******************************************************************************
00009 */
00010 
00011 #include "uhash.h"
00012 #include "unicode/ustring.h"
00013 #include "cstring.h"
00014 #include "cmemory.h"
00015 
00016 /* This hashtable is implemented as a double hash.  All elements are
00017  * stored in a single array with no secondary storage for collision
00018  * resolution (no linked list, etc.).  When there is a hash collision
00019  * (when two unequal keys have the same hashcode) we resolve this by
00020  * using a secondary hash.  The secondary hash is an increment
00021  * computed as a hash function (a different one) of the primary
00022  * hashcode.  This increment is added to the initial hash value to
00023  * obtain further slots assigned to the same hash code.  For this to
00024  * work, the length of the array and the increment must be relatively
00025  * prime.  The easiest way to achieve this is to have the length of
00026  * the array be prime, and the increment be any value from
00027  * 1..length-1.
00028  *
00029  * Hashcodes are 32-bit integers.  We make sure all hashcodes are
00030  * non-negative by masking off the top bit.  This has two effects: (1)
00031  * modulo arithmetic is simplified.  If we allowed negative hashcodes,
00032  * then when we computed hashcode % length, we could get a negative
00033  * result, which we would then have to adjust back into range.  It's
00034  * simpler to just make hashcodes non-negative. (2) It makes it easy
00035  * to check for empty vs. occupied slots in the table.  We just mark
00036  * empty or deleted slots with a negative hashcode.
00037  *
00038  * The central function is _uhash_find().  This function looks for a
00039  * slot matching the given key and hashcode.  If one is found, it
00040  * returns a pointer to that slot.  If the table is full, and no match
00041  * is found, it returns NULL -- in theory.  This would make the code
00042  * more complicated, since all callers of _uhash_find() would then
00043  * have to check for a NULL result.  To keep this from happening, we
00044  * don't allow the table to fill.  When there is only one
00045  * empty/deleted slot left, uhash_put() will refuse to increase the
00046  * count, and fail.  This simplifies the code.  In practice, one will
00047  * seldom encounter this using default UHashtables.  However, if a
00048  * hashtable is set to a U_FIXED resize policy, or if memory is
00049  * exhausted, then the table may fill.
00050  *
00051  * High and low water ratios control rehashing.  They establish levels
00052  * of fullness (from 0 to 1) outside of which the data array is
00053  * reallocated and repopulated.  Setting the low water ratio to zero
00054  * means the table will never shrink.  Setting the high water ratio to
00055  * one means the table will never grow.  The ratios should be
00056  * coordinated with the ratio between successive elements of the
00057  * PRIMES table, so that when the primeIndex is incremented or
00058  * decremented during rehashing, it brings the ratio of count / length
00059  * back into the desired range (between low and high water ratios).
00060  */
00061 
00062 /********************************************************************
00063  * PRIVATE Constants, Macros
00064  ********************************************************************/
00065 
00066 /* This is a list of non-consecutive primes chosen such that
00067  * PRIMES[i+1] ~ 2*PRIMES[i].  (Currently, the ratio ranges from 1.81
00068  * to 2.18; the inverse ratio ranges from 0.459 to 0.552.)  If this
00069  * ratio is changed, the low and high water ratios should also be
00070  * adjusted to suit.
00071  */
00072 static int32_t PRIMES[] = {
00073     17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411, 32771,
00074     65537, 131101, 262147, 524309, 1048583, 2097169, 4194319, 8388617,
00075     16777259, 33554467, 67108879, 134217757, 268435459, 536870923,
00076     1073741827, 2147483647
00077 };
00078 
00079 #define PRIMES_LENGTH (sizeof(PRIMES) / sizeof(PRIMES[0]))
00080 
00081 /* These ratios are tuned to the PRIMES array such that a resize
00082  * places the table back into the zone of non-resizing.  That is,
00083  * after a call to _uhash_rehash(), a subsequent call to
00084  * _uhash_rehash() should do nothing (should not churn).  This is only
00085  * a potential problem with U_GROW_AND_SHRINK.
00086  */
00087 static const float RESIZE_POLICY_RATIO_TABLE[6] = {
00088     /* low, high water ratio */
00089     0.0F, 0.5F, /* U_GROW: Grow on demand, do not shrink */
00090     0.1F, 0.5F, /* U_GROW_AND_SHRINK: Grow and shrink on demand */
00091     0.0F, 1.0F  /* U_FIXED: Never change size */
00092 };
00093 
00094 /*
00095   Invariants for hashcode values:
00096 
00097   * DELETED < 0
00098   * EMPTY < 0
00099   * Real hashes >= 0
00100 
00101   Hashcodes may not start out this way, but internally they are
00102   adjusted so that they are always positive.  We assume 32-bit
00103   hashcodes; adjust these constants for other hashcode sizes.
00104 */
00105 #define HASH_DELETED    ((int32_t) 0x80000000)
00106 #define HASH_EMPTY      ((int32_t) HASH_DELETED + 1)
00107 
00108 #define IS_EMPTY_OR_DELETED(x) ((x) < 0)
00109 
00110 #define HASH_DELETE_KEY_VALUE(hash, key, value) \
00111             if (hash->keyDeleter != NULL && key != NULL) { \
00112                 (*hash->keyDeleter)(key); \
00113             } \
00114             if (hash->valueDeleter != NULL && value != NULL) { \
00115                 (*hash->valueDeleter)(value); \
00116             }
00117 
00118 /********************************************************************
00119  * Debugging
00120  ********************************************************************/
00121 
00122 /* Enable this section to compile in runtime assertion checking. */
00123 
00124 /* #define HASH_DEBUG */
00125 #ifdef HASH_DEBUG
00126 
00127   #include <stdio.h>
00128 
00129   #define assert(exp) (void)( (exp) || (_assert(#exp, __FILE__, __LINE__), 0) )
00130 
00131   static void _assert(const char* exp, const char* file, int line) {
00132       printf("ERROR: assert(%s) failed: %s, line %d\n",
00133              exp, file, line);
00134   }
00135 
00136 #else
00137 
00138   #define assert(exp)
00139 
00140 #endif
00141 
00142 /********************************************************************
00143  * PRIVATE Prototypes
00144  ********************************************************************/
00145 
00146 static UHashtable* _uhash_create(UHashFunction keyHash, UKeyComparator keyComp,
00147                                  int32_t primeIndex, UErrorCode *status);
00148 
00149 static void _uhash_allocate(UHashtable *hash, int32_t primeIndex,
00150                             UErrorCode *status);
00151 
00152 static void _uhash_rehash(UHashtable *hash);
00153 
00154 static UHashElement* _uhash_find(const UHashtable *hash, const void* key,
00155                                  int32_t hashcode);
00156 
00157 static void* _uhash_internalRemoveElement(UHashtable *hash, UHashElement* e);
00158 
00159 static void* _uhash_setElement(UHashtable* hash, UHashElement* e,
00160                                int32_t hashcode, void* key, void* value);
00161 
00162 static void _uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy);
00163 
00164 /********************************************************************
00165  * PUBLIC API
00166  ********************************************************************/
00167 
00168 U_CAPI UHashtable*
00169 uhash_open(UHashFunction keyHash, UKeyComparator keyComp,
00170            UErrorCode *status) {
00171 
00172     return _uhash_create(keyHash, keyComp, 3, status);
00173 }
00174 
00175 U_CAPI UHashtable*
00176 uhash_openSize(UHashFunction keyHash, UKeyComparator keyComp,
00177                int32_t size,
00178                UErrorCode *status) {
00179 
00180     /* Find the smallest index i for which PRIMES[i] >= size. */
00181     int32_t i = 0;
00182     while (i<(PRIMES_LENGTH-1) && PRIMES[i]<size) {
00183         ++i;
00184     }
00185 
00186     return _uhash_create(keyHash, keyComp, i, status);
00187 }
00188 
00189 U_CAPI void
00190 uhash_close(UHashtable *hash) {
00191     assert(hash != NULL);
00192     if (hash->elements != NULL) {
00193         if (hash->keyDeleter != NULL || hash->valueDeleter != NULL) {
00194             int32_t pos=-1;
00195             UHashElement *e;
00196             while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != NULL) {
00197                 HASH_DELETE_KEY_VALUE(hash, e->key, e->value);
00198             }
00199         }
00200         uprv_free(hash->elements);
00201         hash->elements = NULL;
00202     }
00203     uprv_free(hash);
00204 }
00205 
00206 U_CAPI UHashFunction
00207 uhash_setKeyHasher(UHashtable *hash, UHashFunction fn) {
00208     UHashFunction result = hash->keyHasher;
00209     hash->keyHasher = fn;
00210     return result;
00211 }
00212 
00213 U_CAPI UKeyComparator
00214 uhash_setKeyComparator(UHashtable *hash, UKeyComparator fn) {
00215     UKeyComparator result = hash->keyComparator;
00216     hash->keyComparator = fn;
00217     return result;
00218 }
00219 
00220 U_CAPI UObjectDeleter
00221 uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter fn) {
00222     UObjectDeleter result = hash->keyDeleter;
00223     hash->keyDeleter = fn;
00224     return result;
00225 }
00226 
00227 U_CAPI UObjectDeleter
00228 uhash_setValueDeleter(UHashtable *hash, UObjectDeleter fn) {
00229     UObjectDeleter result = hash->valueDeleter;
00230     hash->valueDeleter = fn;
00231     return result;
00232 }
00233 
00234 U_CAPI void
00235 uhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {
00236     _uhash_internalSetResizePolicy(hash, policy);
00237     hash->lowWaterMark  = (int32_t)(hash->length * hash->lowWaterRatio);
00238     hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);    
00239     _uhash_rehash(hash);
00240 }
00241 
00242 U_CAPI int32_t
00243 uhash_count(const UHashtable *hash) {
00244     return hash->count;
00245 }
00246 
00247 U_CAPI void*
00248 uhash_get(const UHashtable *hash,
00249           const void* key) {
00250     return _uhash_find(hash, key, hash->keyHasher(key))->value;
00251 }
00252 
00253 U_CAPI void*
00254 uhash_put(UHashtable *hash,
00255           void* key,
00256           void* value,
00257           UErrorCode *status) {
00258 
00259     /* Put finds the position in the table for the new value.  If the
00260      * key is already in the table, it is deleted, if there is a
00261      * non-NULL keyDeleter.  Then the key, the hash and the value are
00262      * all put at the position in their respective arrays.
00263      */
00264     int32_t hashcode;
00265     UHashElement* e;
00266 
00267     if (U_FAILURE(*status)) {
00268         goto err;
00269     }
00270     assert(hash != NULL);
00271     if (value == NULL) {
00272         /* Disallow storage of NULL values, since NULL is returned by
00273          * get() to indicate an absent key.  Storing NULL == removing.
00274          */
00275         return uhash_remove(hash, key);
00276     }
00277     if (hash->count > hash->highWaterMark) {
00278         _uhash_rehash(hash);
00279     }
00280 
00281     hashcode = (*hash->keyHasher)(key);
00282     e = _uhash_find(hash, key, hashcode);
00283     assert(e != NULL);
00284 
00285     if (IS_EMPTY_OR_DELETED(e->hashcode)) {
00286         /* Important: We must never actually fill the table up.  If we
00287          * do so, then _uhash_find() will return NULL, and we'll have
00288          * to check for NULL after every call to _uhash_find().  To
00289          * avoid this we make sure there is always at least one empty
00290          * or deleted slot in the table.  This only is a problem if we
00291          * are out of memory and rehash isn't working.
00292          */
00293         ++hash->count;
00294         if (hash->count == hash->length) {
00295             /* Don't allow count to reach length */
00296             --hash->count;
00297             *status = U_MEMORY_ALLOCATION_ERROR;
00298             goto err;
00299         }
00300     }
00301 
00302     /* We must in all cases handle storage properly.  If there was an
00303      * old key, then it must be deleted (if the deleter != NULL).
00304      * Make hashcodes stored in table positive.
00305      */
00306     return _uhash_setElement(hash, e, hashcode & 0x7FFFFFFF, key, value);
00307 
00308  err:
00309     /* If the deleters are non-NULL, this method adopts its key and/or
00310      * value arguments, and we must be sure to delete the key and/or
00311      * value in all cases, even upon failure.
00312      */
00313     HASH_DELETE_KEY_VALUE(hash, key, value);
00314     return NULL;
00315 }
00316 
00317 U_CAPI void*
00318 uhash_remove(UHashtable *hash,
00319              const void* key) {
00320     /* First find the position of the key in the table.  If the object
00321      * has not been removed already, remove it.  If the user wanted
00322      * keys deleted, then delete it also.  We have to put a special
00323      * hashcode in that position that means that something has been
00324      * deleted, since when we do a find, we have to continue PAST any
00325      * deleted values.
00326      */
00327     void* result = NULL;
00328     UHashElement* e = _uhash_find(hash, key, hash->keyHasher(key));
00329     assert(e != NULL);
00330     if (!IS_EMPTY_OR_DELETED(e->hashcode)) {
00331         result = _uhash_internalRemoveElement(hash, e);
00332         if (hash->count < hash->lowWaterMark) {
00333             _uhash_rehash(hash);
00334         }
00335     }
00336     return result;
00337 }
00338 
00339 U_CAPI void
00340 uhash_removeAll(UHashtable *hash) {
00341     int32_t pos = -1;
00342     const UHashElement *e;
00343     assert(hash != NULL);
00344     if (hash->count != 0) {
00345         while ((e = uhash_nextElement(hash, &pos)) != NULL) {
00346             uhash_removeElement(hash, e);
00347         }
00348     }
00349     assert(hash->count == 0);
00350 }
00351 
00352 U_CAPI const UHashElement*
00353 uhash_nextElement(const UHashtable *hash, int32_t *pos) {
00354     /* Walk through the array until we find an element that is not
00355      * EMPTY and not DELETED.
00356      */
00357     int32_t i;
00358     assert(hash != NULL);
00359     for (i = *pos + 1; i < hash->length; ++i) {
00360         if (!IS_EMPTY_OR_DELETED(hash->elements[i].hashcode)) {
00361             *pos = i;
00362             return &(hash->elements[i]);
00363         }
00364     }
00365 
00366     /* No more elements */
00367     return NULL;
00368 }
00369 
00370 U_CAPI void*
00371 uhash_removeElement(UHashtable *hash, const UHashElement* e) {
00372     assert(hash != NULL);
00373     assert(e != NULL);
00374     if (!IS_EMPTY_OR_DELETED(e->hashcode)) {
00375         return _uhash_internalRemoveElement(hash, (UHashElement*) e);
00376     }
00377     return NULL;
00378 }
00379 
00380 /********************************************************************
00381  * PUBLIC Key Hash Functions
00382  ********************************************************************/
00383 
00384 /*
00385   Compute the hash by iterating sparsely over about 32 (up to 63)
00386   characters spaced evenly through the string.  For each character,
00387   multiply the previous hash value by a prime number and add the new
00388   character in, like a linear congruential random number generator,
00389   producing a pseudorandom deterministic value well distributed over
00390   the output range. [LIU]
00391 */
00392 
00393 #define STRING_HASH(TYPE, STRLEN, DEREF)      \
00394     int32_t hash = 0;                         \
00395     if (key != NULL) {                        \
00396         const TYPE *p = (const TYPE*) key;    \
00397         int32_t len = STRLEN;                 \
00398         int32_t inc = ((len - 32) / 32) + 1;  \
00399         const TYPE *limit = p + len;          \
00400         while (p<limit) {                     \
00401             hash = (hash * 37) + DEREF;       \
00402             p += inc;                         \
00403         }                                     \
00404     }                                         \
00405     return hash
00406 
00407 U_CAPI int32_t
00408 uhash_hashUChars(const void *key) {
00409     STRING_HASH(UChar, u_strlen(p), *p);
00410 }
00411 
00412 /* Used by UnicodeString to compute its hashcode - Not public API. */
00413 U_CAPI int32_t
00414 uhash_hashUCharsN(const UChar *key, int32_t length) {
00415     STRING_HASH(UChar, length, *p);
00416 }
00417 
00418 U_CAPI int32_t
00419 uhash_hashChars(const void *key) {
00420     STRING_HASH(uint8_t, uprv_strlen((char*)p), *p);
00421 }
00422 
00423 U_CAPI int32_t
00424 uhash_hashIChars(const void *key) {
00425     STRING_HASH(uint8_t, uprv_strlen((char*)p), uprv_tolower(*p));
00426 }
00427 
00428 /********************************************************************
00429  * PUBLIC Comparator Functions
00430  ********************************************************************/
00431 
00432 U_CAPI UBool
00433 uhash_compareUChars(const void *key1, const void *key2) {
00434     const UChar *p1 = (const UChar*) key1;
00435     const UChar *p2 = (const UChar*) key2;
00436     if (p1 == p2) {
00437         return TRUE;
00438     }
00439     if (p1 == NULL || p2 == NULL) {
00440         return FALSE;
00441     }
00442     while (*p1 != 0 && *p1 == *p2) {
00443         ++p1;
00444         ++p2;
00445     }
00446     return (UBool)(*p1 == *p2);
00447 }
00448 
00449 U_CAPI UBool
00450 uhash_compareChars(const void *key1, const void *key2) {
00451     const char *p1 = (const char*) key1;
00452     const char *p2 = (const char*) key2;
00453     if (p1 == p2) {
00454         return TRUE;
00455     }
00456     if (p1 == NULL || p2 == NULL) {
00457         return FALSE;
00458     }
00459     while (*p1 != 0 && *p1 == *p2) {
00460         ++p1;
00461         ++p2;
00462     }
00463     return (UBool)(*p1 == *p2);
00464 }
00465 
00466 U_CAPI UBool
00467 uhash_compareIChars(const void *key1, const void *key2) {
00468     const char *p1 = (const char*) key1;
00469     const char *p2 = (const char*) key2;
00470     if (p1 == p2) {
00471         return TRUE;
00472     }
00473     if (p1 == NULL || p2 == NULL) {
00474         return FALSE;
00475     }
00476     while (*p1 != 0 && uprv_tolower(*p1) == uprv_tolower(*p2)) {
00477         ++p1;
00478         ++p2;
00479     }
00480     return (UBool)(*p1 == *p2);
00481 }
00482 
00483 /********************************************************************
00484  * PUBLIC int32_t Support Functions
00485  ********************************************************************/
00486 
00487 U_CAPI int32_t
00488 uhash_hashLong(const void *key) {
00489     return (int32_t) key;
00490 }
00491 
00492 U_CAPI UBool
00493 uhash_compareLong(const void *key1, const void *key2) {
00494     return (UBool)(key1 == key2);
00495 }
00496 
00497 /********************************************************************
00498  * PUBLIC Deleter Functions
00499  ********************************************************************/
00500 
00501 U_CAPI void
00502 uhash_freeBlock(void *obj) {
00503     uprv_free(obj);
00504 }
00505 
00506 /********************************************************************
00507  * PRIVATE Implementation
00508  ********************************************************************/
00509 
00510 static UHashtable*
00511 _uhash_create(UHashFunction keyHash, UKeyComparator keyComp,
00512               int32_t primeIndex,
00513               UErrorCode *status) {
00514     UHashtable *result;
00515 
00516     if (U_FAILURE(*status)) return NULL;
00517     assert(keyHash != NULL);
00518     assert(keyComp != NULL);
00519 
00520     result = (UHashtable*) uprv_malloc(sizeof(UHashtable));
00521     if (result == NULL) {
00522         *status = U_MEMORY_ALLOCATION_ERROR;
00523         return NULL;
00524     }
00525 
00526     result->keyHasher      = keyHash;
00527     result->keyComparator  = keyComp;
00528     result->keyDeleter     = NULL;
00529     result->valueDeleter   = NULL;
00530     _uhash_internalSetResizePolicy(result, U_GROW);
00531 
00532     _uhash_allocate(result, primeIndex, status);
00533 
00534     if (U_FAILURE(*status)) {
00535         uprv_free(result);
00536         return NULL;
00537     }
00538 
00539     return result;
00540 }
00541 
00551 static void
00552 _uhash_allocate(UHashtable *hash,
00553                 int32_t primeIndex,
00554                 UErrorCode *status) {
00555 
00556     UHashElement *p, *limit;
00557 
00558     if (U_FAILURE(*status)) return;
00559 
00560     assert(primeIndex >= 0 && primeIndex < PRIMES_LENGTH);
00561 
00562     hash->primeIndex = primeIndex;
00563     hash->length = PRIMES[primeIndex];
00564 
00565     p = hash->elements = (UHashElement*)
00566         uprv_malloc(sizeof(UHashElement) * hash->length);
00567 
00568     if (hash->elements == NULL) {
00569         *status = U_MEMORY_ALLOCATION_ERROR;
00570         return;
00571     }
00572 
00573     limit = p + hash->length;
00574     while (p < limit) {
00575         p->key = NULL;
00576         p->value = NULL;
00577         p->hashcode = HASH_EMPTY;
00578         ++p;
00579     }
00580 
00581     hash->count = 0;
00582     hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio);
00583     hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);
00584 }
00585 
00595 static void
00596 _uhash_rehash(UHashtable *hash) {
00597 
00598     UHashElement *old = hash->elements;
00599     int32_t oldLength = hash->length;
00600     int32_t newPrimeIndex = hash->primeIndex;
00601     int32_t i;
00602     UErrorCode status = U_ZERO_ERROR;
00603 
00604     if (hash->count > hash->highWaterMark) {
00605         if (++newPrimeIndex >= PRIMES_LENGTH) {
00606             return;
00607         }
00608     } else if (hash->count < hash->lowWaterMark) {
00609         if (--newPrimeIndex < 0) {
00610             return;
00611         }
00612     } else {
00613         return;
00614     }
00615 
00616     _uhash_allocate(hash, newPrimeIndex, &status);
00617 
00618     if (U_FAILURE(status)) {
00619         hash->elements = old;
00620         hash->length = oldLength;       
00621         return;
00622     }
00623 
00624     for (i = oldLength - 1; i >= 0; --i) {
00625         if (!IS_EMPTY_OR_DELETED(old[i].hashcode)) {
00626             UHashElement *e = _uhash_find(hash, old[i].key, old[i].hashcode);
00627             assert(e != NULL);
00628             assert(e->hashcode == HASH_EMPTY);
00629             e->key = old[i].key;
00630             e->value = old[i].value;
00631             e->hashcode = old[i].hashcode;
00632             ++hash->count;
00633         }
00634     }
00635 
00636     uprv_free(old);
00637 }
00638 
00667 static UHashElement*
00668 _uhash_find(const UHashtable *hash, const void* key,
00669             int32_t hashcode) {
00670 
00671     int32_t firstDeleted = -1;  /* assume invalid index */
00672     int32_t theIndex, startIndex;
00673     int32_t jump = 0; /* lazy evaluate */
00674     int32_t tableHash;
00675 
00676     hashcode &= 0x7FFFFFFF; /* must be positive */
00677     startIndex = theIndex = (hashcode ^ 0x4000000) % hash->length;
00678 
00679     do {
00680         tableHash = hash->elements[theIndex].hashcode;
00681         if (tableHash == hashcode) {          /* quick check */
00682             if ((*hash->keyComparator)(key, hash->elements[theIndex].key)) {
00683                 return &(hash->elements[theIndex]);
00684             }
00685         } else if (!IS_EMPTY_OR_DELETED(tableHash)) {
00686             /* We have hit a slot which contains a key-value pair,
00687              * but for which the hash code does not match.  Keep
00688              * looking.
00689              */
00690         } else if (tableHash == HASH_EMPTY) { /* empty, end o' the line */
00691             break;
00692         } else if (firstDeleted < 0) { /* remember first deleted */
00693             firstDeleted = theIndex;
00694         }
00695         if (jump == 0) { /* lazy compute jump */
00696             /* The jump value must be relatively prime to the table
00697              * length.  As long as the length is prime, then any value
00698              * 1..length-1 will be relatively prime to it.
00699              */
00700             jump = (hashcode % (hash->length - 1)) + 1;
00701         }
00702         theIndex = (theIndex + jump) % hash->length;
00703     } while (theIndex != startIndex);
00704 
00705     if (firstDeleted >= 0) {
00706         theIndex = firstDeleted; /* reset if had deleted slot */
00707     } else if (tableHash != HASH_EMPTY) {
00708         /* We get to this point if the hashtable is full (no empty or
00709          * deleted slots), and we've failed to find a match.  THIS
00710          * WILL NEVER HAPPEN as long as uhash_put() makes sure that
00711          * count is always < length.
00712          */
00713         assert(FALSE);
00714         return NULL; /* Never happens if uhash_put() behaves */
00715     }
00716     return &(hash->elements[theIndex]);
00717 }
00718 
00719 static void*
00720 _uhash_setElement(UHashtable *hash, UHashElement* e,
00721                   int32_t hashcode, void* key, void* value) {
00722 
00723     void* oldKey = e->key;
00724     void* oldValue = e->value;
00725     if (hash->keyDeleter != NULL && oldKey != NULL &&
00726         oldKey != key) { /* Avoid double deletion */
00727         (*hash->keyDeleter)(oldKey);
00728     }
00729     if (oldValue == value) { /* Avoid double deletion */
00730         oldValue = NULL;
00731     }
00732     if (hash->valueDeleter != NULL && oldValue != NULL) {
00733         (*hash->valueDeleter)(oldValue);
00734         oldValue = NULL;
00735     }
00736     e->key = key;
00737     e->value = value;
00738     e->hashcode = hashcode;
00739     return oldValue;
00740 }
00741 
00745 static void*
00746 _uhash_internalRemoveElement(UHashtable *hash, UHashElement* e) {
00747     assert(!IS_EMPTY_OR_DELETED(e->hashcode));
00748     --hash->count;
00749     return _uhash_setElement(hash, e, HASH_DELETED, NULL, NULL);
00750 }
00751 
00752 static void
00753 _uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {
00754     assert(hash == 0);
00755     assert(((int32_t)policy) >= 0);
00756     assert(((int32_t)policy) < 3);
00757     hash->lowWaterRatio  = RESIZE_POLICY_RATIO_TABLE[policy * 2];
00758     hash->highWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2 + 1];
00759 }

Generated at Tue Dec 5 10:48:06 2000 for ICU by doxygen1.2.3 written by Dimitri van Heesch, © 1997-2000