ICU-57165.0.1.tar.gz

[apple/icu.git] / icuSources / common / uhash.c

diff --git a/icuSources/common/uhash.c b/icuSources/common/uhash.c
index ce06d2ca86a680145fccb7ebed3e1f8a257d73eb..d4a99038b7e67f9916f70e461ec87c39f99c0ebf 100644 (file)
--- a/icuSources/common/uhash.c
+++ b/icuSources/common/uhash.c
@@ -1,6 +1,6 @@
 /*
 ******************************************************************************
 /*
 ******************************************************************************

-*   Copyright (C) 1997-2008, International Business Machines
+*   Copyright (C) 1997-2016, International Business Machines

 *   Corporation and others.  All Rights Reserved.
 ******************************************************************************
 *   Date        Name        Description
 *   Corporation and others.  All Rights Reserved.
 ******************************************************************************
 *   Date        Name        Description


@@ -15,6 +15,7 @@
 #include "cstring.h"
 #include "cmemory.h"
 #include "uassert.h"
 #include "cstring.h"
 #include "cmemory.h"
 #include "uassert.h"

+#include "ustr_imp.h"

 
 /* This hashtable is implemented as a double hash.  All elements are
  * stored in a single array with no secondary storage for collision
 
 /* This hashtable is implemented as a double hash.  All elements are
  * stored in a single array with no secondary storage for collision


@@ -76,14 +77,14 @@
  * prime number while being less than a power of two.
  */
 static const int32_t PRIMES[] = {
  * prime number while being less than a power of two.
  */
 static const int32_t PRIMES[] = {

-    13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749,
+    7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749,

     65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593,
     16777213, 33554393, 67108859, 134217689, 268435399, 536870909,
     1073741789, 2147483647 /*, 4294967291 */
 };
 
     65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593,
     16777213, 33554393, 67108859, 134217689, 268435399, 536870909,
     1073741789, 2147483647 /*, 4294967291 */
 };
 

-#define PRIMES_LENGTH (sizeof(PRIMES) / sizeof(PRIMES[0]))
-#define DEFAULT_PRIME_INDEX 3
+#define PRIMES_LENGTH UPRV_LENGTHOF(PRIMES)
+#define DEFAULT_PRIME_INDEX 4

 
 /* These ratios are tuned to the PRIMES array such that a resize
  * places the table back into the zone of non-resizing.  That is,
 
 /* These ratios are tuned to the PRIMES array such that a resize
  * places the table back into the zone of non-resizing.  That is,


@@ -567,12 +568,31 @@ uhash_init(UHashtable *fillinResult,
     return _uhash_init(fillinResult, keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status);
 }
 
     return _uhash_init(fillinResult, keyHash, keyComp, valueComp, DEFAULT_PRIME_INDEX, status);
 }
 

+U_CAPI UHashtable* U_EXPORT2
+uhash_initSize(UHashtable *fillinResult,
+               UHashFunction *keyHash, 
+               UKeyComparator *keyComp,
+               UValueComparator *valueComp,
+               int32_t size,
+               UErrorCode *status) {
+
+    /* Find the smallest index i for which PRIMES[i] >= size. */
+    int32_t i = 0;
+    while (i<(PRIMES_LENGTH-1) && PRIMES[i]<size) {
+        ++i;
+    }
+
+    return _uhash_init(fillinResult, keyHash, keyComp, valueComp, i, status);
+}
+

 U_CAPI void U_EXPORT2
 uhash_close(UHashtable *hash) {
 U_CAPI void U_EXPORT2
 uhash_close(UHashtable *hash) {

-    U_ASSERT(hash != NULL);
+    if (hash == NULL) {
+        return;
+    }

     if (hash->elements != NULL) {
         if (hash->keyDeleter != NULL || hash->valueDeleter != NULL) {
     if (hash->elements != NULL) {
         if (hash->keyDeleter != NULL || hash->valueDeleter != NULL) {

-            int32_t pos=-1;
+            int32_t pos=UHASH_FIRST;

             UHashElement *e;
             while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != NULL) {
                 HASH_DELETE_KEY_VALUE(hash, e->key.pointer, e->value.pointer);
             UHashElement *e;
             while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != NULL) {
                 HASH_DELETE_KEY_VALUE(hash, e->key.pointer, e->value.pointer);


@@ -753,7 +773,7 @@ uhash_iremovei(UHashtable *hash,
 
 U_CAPI void U_EXPORT2
 uhash_removeAll(UHashtable *hash) {
 
 U_CAPI void U_EXPORT2
 uhash_removeAll(UHashtable *hash) {

-    int32_t pos = -1;
+    int32_t pos = UHASH_FIRST;

     const UHashElement *e;
     U_ASSERT(hash != NULL);
     if (hash->count != 0) {
     const UHashElement *e;
     U_ASSERT(hash != NULL);
     if (hash->count != 0) {


@@ -796,7 +816,8 @@ uhash_removeElement(UHashtable *hash, const UHashElement* e) {
     U_ASSERT(hash != NULL);
     U_ASSERT(e != NULL);
     if (!IS_EMPTY_OR_DELETED(e->hashcode)) {
     U_ASSERT(hash != NULL);
     U_ASSERT(e != NULL);
     if (!IS_EMPTY_OR_DELETED(e->hashcode)) {

-        return _uhash_internalRemoveElement(hash, (UHashElement*) e).pointer;
+        UHashElement *nce = (UHashElement *)e;
+        return _uhash_internalRemoveElement(hash, nce).pointer;

     }
     return NULL;
 }
     }
     return NULL;
 }


@@ -829,53 +850,26 @@ uhash_tokp(void* p) {
  * PUBLIC Key Hash Functions
  ********************************************************************/
 
  * PUBLIC Key Hash Functions
  ********************************************************************/
 

-/*
-  Compute the hash by iterating sparsely over about 32 (up to 63)
-  characters spaced evenly through the string.  For each character,
-  multiply the previous hash value by a prime number and add the new
-  character in, like a linear congruential random number generator,
-  producing a pseudorandom deterministic value well distributed over
-  the output range. [LIU]
-*/
-
-#define STRING_HASH(TYPE, STR, STRLEN, DEREF) \
-    int32_t hash = 0;                         \
-    const TYPE *p = (const TYPE*) STR;        \
-    if (p != NULL) {                          \
-        int32_t len = (int32_t)(STRLEN);      \
-        int32_t inc = ((len - 32) / 32) + 1;  \
-        const TYPE *limit = p + len;          \
-        while (p<limit) {                     \
-            hash = (hash * 37) + DEREF;       \
-            p += inc;                         \
-        }                                     \
-    }                                         \
-    return hash
-

 U_CAPI int32_t U_EXPORT2
 uhash_hashUChars(const UHashTok key) {
 U_CAPI int32_t U_EXPORT2
 uhash_hashUChars(const UHashTok key) {

-    STRING_HASH(UChar, key.pointer, u_strlen(p), *p);
-}
-
-/* Used by UnicodeString to compute its hashcode - Not public API. */
-U_CAPI int32_t U_EXPORT2
-uhash_hashUCharsN(const UChar *str, int32_t length) {
-    STRING_HASH(UChar, str, length, *p);
+    const UChar *s = (const UChar *)key.pointer;
+    return s == NULL ? 0 : ustr_hashUCharsN(s, u_strlen(s));

 }
 
 U_CAPI int32_t U_EXPORT2
 uhash_hashChars(const UHashTok key) {
 }
 
 U_CAPI int32_t U_EXPORT2
 uhash_hashChars(const UHashTok key) {

-    STRING_HASH(uint8_t, key.pointer, uprv_strlen((char*)p), *p);
+    const char *s = (const char *)key.pointer;
+    return s == NULL ? 0 : ustr_hashCharsN(s, uprv_strlen(s));

 }
 
 U_CAPI int32_t U_EXPORT2
 uhash_hashIChars(const UHashTok key) {
 }
 
 U_CAPI int32_t U_EXPORT2
 uhash_hashIChars(const UHashTok key) {

-    STRING_HASH(uint8_t, key.pointer, uprv_strlen((char*)p), uprv_tolower(*p));
+    const char *s = (const char *)key.pointer;
+    return s == NULL ? 0 : ustr_hashICharsN(s, uprv_strlen(s));

 }
 
 U_CAPI UBool U_EXPORT2 
 uhash_equals(const UHashtable* hash1, const UHashtable* hash2){
 }
 
 U_CAPI UBool U_EXPORT2 
 uhash_equals(const UHashtable* hash1, const UHashtable* hash2){

-    

     int32_t count1, count2, pos, i;
 
     if(hash1==hash2){
     int32_t count1, count2, pos, i;
 
     if(hash1==hash2){


@@ -908,7 +902,7 @@ uhash_equals(const UHashtable* hash1, const UHashtable* hash2){
         return FALSE;
     }
     
         return FALSE;
     }
     

-    pos=-1;
+    pos=UHASH_FIRST;

     for(i=0; i<count1; i++){
         const UHashElement* elem1 = uhash_nextElement(hash1, &pos);
         const UHashTok key1 = elem1->key;
     for(i=0; i<count1; i++){
         const UHashElement* elem1 = uhash_nextElement(hash1, &pos);
         const UHashTok key1 = elem1->key;


@@ -994,13 +988,3 @@ U_CAPI UBool U_EXPORT2
 uhash_compareLong(const UHashTok key1, const UHashTok key2) {
     return (UBool)(key1.integer == key2.integer);
 }
 uhash_compareLong(const UHashTok key1, const UHashTok key2) {
     return (UBool)(key1.integer == key2.integer);
 }

-
-/********************************************************************
- * PUBLIC Deleter Functions
- ********************************************************************/
-
-U_CAPI void U_EXPORT2
-uhash_freeBlock(void *obj) {
-    uprv_free(obj);
-}
-