home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / Programming / ICU / src / icu / source / common / uhash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-10-19  |  14.3 KB  |  569 lines
  1. /*
  2. *******************************************************************************
  3. *                                                                             *
  4. * COPYRIGHT:                                                                  *
  5. *   (C) Copyright Taligent, Inc.,  1997                                       *
  6. *   (C) Copyright International Business Machines Corporation,  1997-1999     *
  7. *   Licensed Material - Program-Property of IBM - All Rights Reserved.        *
  8. *   US Government Users Restricted Rights - Use, duplication, or disclosure   *
  9. *   restricted by GSA ADP Schedule Contract with IBM Corp.                    *
  10. *                                                                             *
  11. *******************************************************************************
  12. *
  13. * File uhash.c
  14. *
  15. * Modification History:
  16. *
  17. *   Date        Name        Description
  18. *   03/12/99    stephen     Creation.
  19. *******************************************************************************
  20. */
  21.  
  22. #include "uhash.h"
  23. #include "ustring.h"
  24. #include "cmemory.h"
  25.  
  26. /* Private function prototypes */
  27. void
  28. uhash_initialize(UHashtable *hash,
  29.          int32_t primeIndex,
  30.          UErrorCode *status);
  31.  
  32. int32_t 
  33. uhash_leastGreaterPrimeIndex(int32_t source);
  34.  
  35. void
  36. uhash_rehash(UHashtable *hash,
  37.          UErrorCode *status);
  38.  
  39. void
  40. uhash_putInternal(UHashtable *hash,
  41.           int32_t hashCode, 
  42.           void *value);
  43.  
  44. int32_t 
  45. uhash_find(const UHashtable *hash,
  46.        int32_t hashCode);
  47.  
  48.  
  49.  
  50. /*
  51.   INVARIANT: the size of the table MUST be prime for this algorithm to work!
  52.   Prime table can be tuned for different performance/storage characteristics
  53.   We avoid computing primes by precomputing a table that we use.
  54. */
  55. int32_t UHASH_PRIMES [] =
  56. {
  57.   17, 37, 67, 131, 257,
  58.   521, 1031, 2053, 4099, 8209, 16411, 32771, 65537,
  59.   131101, 262147, 524309, 1048583, 2097169, 4194319, 8388617, 16777259,
  60.   33554467, 67108879, 134217757, 268435459, 536870923, 1073741827, 2147483647
  61. };
  62.  
  63. #define UHASH_PRIMES_LENGTH 28
  64.  
  65. #define UHASH_SLOT_DELETED      ((int32_t) 0x80000000)
  66. #define UHASH_SLOT_EMPTY      ((int32_t) UHASH_SLOT_DELETED + 1)
  67. #define UHASH_MAX_UNUSED      ((int32_t) UHASH_SLOT_EMPTY)
  68.  
  69. /*
  70.   INVARIANTS:
  71.   DELETED <= MAX_UNUSED
  72.   EMPTY <= MAX_UNUSED
  73.   Any hash > MAX_UNUSED*
  74.   * hashcodes may not start out this way, but internally, 
  75.   they are adjusted so that they are always positive, and this is always true.
  76.   Note here that we are assuming 32-bit ints.
  77. */
  78.  
  79. U_CAPI UHashtable*
  80. uhash_open(UHashFunction func,
  81.        UErrorCode *status)
  82. {
  83.   UHashtable* myUHT =  uhash_openSize(func, 3, status);
  84.   if (U_SUCCESS(*status)) myUHT->isGrowable = TRUE;
  85.  
  86.   return myUHT;
  87. }
  88.  
  89. U_CAPI UHashtable*
  90. uhash_openSize(UHashFunction func,
  91.            int32_t size,
  92.            UErrorCode *status)
  93. {
  94.   UHashtable *result;
  95.   
  96.   if(U_FAILURE(*status)) return NULL;
  97.   
  98.   result = (UHashtable*) icu_malloc(sizeof(UHashtable));
  99.   if(result == 0) {
  100.     *status = U_MEMORY_ALLOCATION_ERROR;
  101.     return 0;
  102.   }
  103.   
  104.   result->highWaterFactor     = 0.5F;
  105.   result->lowWaterFactor     = 0.0F;
  106.   result->hashFunction         = func;
  107.   result->valueDelete        = NULL;
  108.   result->toBeDeleted        = NULL;
  109.   result->toBeDeletedCount    = 0;
  110.   result->isGrowable    = FALSE;
  111.  
  112.   uhash_initialize(result, uhash_leastGreaterPrimeIndex(size), status);
  113.  
  114.   if(U_FAILURE(*status)) {
  115.     icu_free(result);
  116.     return 0;
  117.   }
  118.  
  119.   return result;
  120. }
  121.  
  122. U_CAPI void
  123. uhash_setValueDeleter(UHashtable *hash, ValueDeleter del )
  124. {
  125.     hash->valueDelete = del;
  126. }
  127.  
  128. U_CAPI void
  129. uhash_close(UHashtable *hash)
  130. {
  131.   if (hash->valueDelete)
  132.   {
  133.       ValueDeleter my_free = hash->valueDelete;
  134.       void** vals = hash->values;
  135.       void** toBeDeleted = hash->toBeDeleted;
  136.       int32_t i;
  137.       int32_t count = hash->count;
  138.       int32_t toBeDeletedCount = hash->toBeDeletedCount;
  139.       for (i = 0; i < count; i++)  my_free(vals[i]);
  140.       while (toBeDeletedCount--)    my_free(toBeDeleted[toBeDeletedCount]);
  141.  
  142.   }
  143.   icu_free(hash->values);
  144.   icu_free(hash->hashes);
  145.   icu_free(hash->toBeDeleted);
  146. }
  147.  
  148. U_CAPI int32_t
  149. uhash_size(const UHashtable *hash)
  150. {
  151.   return hash->count;
  152. }
  153. U_CAPI int32_t
  154. uhash_putKey(UHashtable *hash,
  155.          int32_t valueKey,
  156.          void *value,
  157.          UErrorCode *status)
  158. {
  159.   /* Put finds the position in the table for the new value. */
  160.   
  161.   int32_t hashCode;
  162.   int32_t index;
  163.   
  164.   if(U_FAILURE(*status)) return UHASH_INVALID;
  165.  
  166.   if(hash->count > hash->highWaterMark) {
  167.     if (hash->isGrowable)    uhash_rehash(hash, status);
  168.     else  {
  169.       *status = U_INDEX_OUTOFBOUNDS_ERROR;
  170.       return UHASH_INVALID;
  171.     }
  172.   }
  173.  
  174.   hashCode     = valueKey;
  175.   index     = uhash_find(hash, hashCode);
  176.   
  177.   /* deleted or empty */
  178.   if(hash->hashes[index] <= UHASH_MAX_UNUSED) {
  179.     /* make new object */
  180.     hash->hashes[index] = hashCode;
  181.     ++(hash->count);
  182.   }
  183.   
  184.   /* delete old value? */
  185.   if (hash->valueDelete) 
  186.     {
  187.       void * result = hash->values[index];
  188.     if (result != value) /*Make sure the same object isn't scheduled for a double deletion*/
  189.       {
  190.         hash->toBeDeleted = (void**) icu_realloc(hash->toBeDeleted, sizeof(void*)*(++(hash->toBeDeletedCount)));
  191.         hash->toBeDeleted[(hash->toBeDeletedCount)-1] = result;
  192.       }
  193.       hash->values[index] = 0;
  194.     }
  195.   
  196.   
  197.   /* store value */
  198.   hash->values[index] = value;
  199.   
  200.   /* return the hash code to the user */
  201.   return hashCode;
  202. }
  203.  
  204. U_CAPI int32_t
  205. uhash_put(UHashtable *hash,
  206.       void *value,
  207.       UErrorCode *status)
  208. {
  209.   /* Put finds the position in the table for the new value. */
  210.   
  211.   int32_t hashCode;
  212.   int32_t index;
  213.   
  214.   if(U_FAILURE(*status)) return UHASH_INVALID;
  215.  
  216.   if(hash->count > hash->highWaterMark) {
  217.     if (hash->isGrowable)    uhash_rehash(hash, status);
  218.     else  {
  219.       *status = U_INDEX_OUTOFBOUNDS_ERROR;
  220.       return UHASH_INVALID;
  221.     }
  222.   }
  223.  
  224.   hashCode     = (hash->hashFunction)(value);
  225.   index     = uhash_find(hash, hashCode);
  226.   
  227.   /* deleted or empty */
  228.   if(hash->hashes[index] <= UHASH_MAX_UNUSED) {
  229.     /* make new object */
  230.     hash->hashes[index] = hashCode;
  231.     ++(hash->count);
  232.   }
  233.   
  234.   /* delete old value? */
  235.   if (hash->valueDelete) 
  236.     {
  237.       void* result = hash->values[index];
  238.     if (result != value) /*Make sure the same object isn't scheduled for a double deletion*/
  239.       {
  240.         hash->toBeDeleted = (void**) icu_realloc(hash->toBeDeleted,
  241.                          sizeof(void*)*(++(hash->toBeDeletedCount)));
  242.         hash->toBeDeleted[(hash->toBeDeletedCount)-1] = result;
  243.       }
  244.       hash->values[index] = 0;
  245.     }
  246.   
  247.     
  248.   /* store value */
  249.   hash->values[index] = value;
  250.  
  251.   /* return the hash code to the user */
  252.   return hashCode;
  253. }
  254.  
  255. U_CAPI void*
  256. uhash_get(const UHashtable *hash, 
  257.       int32_t key)
  258. {
  259.     /* srl: Shouldn't we check to see if hash->hashes[uhash_find(hash, key)] == UHASH_SLOT_DELETED ?
  260.         Perhaps in theory hash->values[...] should have been set to 0, but can we depend
  261.         on this?
  262.      */
  263.  
  264.   void *result         = hash->values[uhash_find(hash, key)];
  265.   return result;  
  266. }
  267.  
  268. U_CAPI void*
  269. uhash_remove(UHashtable *hash,
  270.          int32_t key,
  271.          UErrorCode *status)
  272. {
  273.   /*
  274.     First find the position of the key in the table
  275.     If the object has not be removed already, remove it.
  276.     We have to put a special value in that position that means that
  277.     something has been deleted, since when we do a find,
  278.     we have to continue PAST any deleted values
  279.   */
  280.   int32_t index     = uhash_find(hash, key);
  281.   void *result         = 0;
  282.  
  283.   /* neither deleted nor empty */
  284.   if(hash->hashes[index] > UHASH_MAX_UNUSED) {
  285.     /* set to deleted */
  286.     hash->hashes[index] = UHASH_SLOT_DELETED;
  287.     result = hash->values[index];
  288.  
  289.     /* delete old value? */
  290.     if (hash->valueDelete) 
  291.     {
  292.         hash->valueDelete(result);
  293.     }
  294.     hash->values[index] = 0; /* srl .. always null out the value even if there's no deletor!! */
  295.  
  296.     --(hash->count);
  297.  
  298.     if(hash->count < hash->lowWaterMark) {
  299.       uhash_rehash(hash, status);
  300.     }
  301.   }
  302.   
  303.   return result;
  304. }
  305.  
  306. U_CAPI void*
  307. uhash_nextElement(const UHashtable *hash,
  308.           int32_t *pos)
  309. {
  310.   /*
  311.     Walk through the array until you find an element that is not EMPTY and 
  312.     not DELETED
  313.   */
  314.   
  315.   int32_t i;
  316.   void *value;
  317.   
  318.   for(i = *pos + 1; i < hash->length; ++i) {
  319.     if(hash->hashes[i] > UHASH_MAX_UNUSED) {
  320.       *pos = i;
  321.       value = hash->values[i];
  322.       return value;
  323.     }
  324.   }
  325.   
  326.   /* No more elements */
  327.   return 0; 
  328. }
  329.  
  330. /* ================================================== */
  331. /* Private functions */
  332. /* ================================================== */
  333. void
  334. uhash_initialize(UHashtable *hash,
  335.          int32_t primeIndex,
  336.          UErrorCode *status)
  337. {
  338.   int32_t i;
  339.   
  340.   if(U_FAILURE(*status)) return;
  341.  
  342.   if(primeIndex < 0) {
  343.     primeIndex = 0;
  344.   }
  345.   else if(primeIndex >= UHASH_PRIMES_LENGTH) {
  346.     primeIndex = UHASH_PRIMES_LENGTH - 1;
  347.   }
  348.   
  349.   hash->primeIndex     = primeIndex;
  350.   hash->length         = UHASH_PRIMES[primeIndex];
  351.  
  352.   hash->values         = (void**) icu_malloc(sizeof(void*) * hash->length);
  353.   if(hash->values == 0) {
  354.     *status = U_MEMORY_ALLOCATION_ERROR;
  355.     return;
  356.   }
  357.  
  358.   hash->hashes         = (int32_t*) icu_malloc(sizeof(int32_t) * hash->length);
  359.   if(hash->values == 0) {
  360.     *status = U_MEMORY_ALLOCATION_ERROR;
  361.     icu_free(hash->values);
  362.     return;
  363.   }
  364.  
  365.   for(i = 0; i < hash->length; ++i) {
  366.     hash->hashes[i]     = UHASH_SLOT_EMPTY;
  367.     hash->values[i]     = 0;
  368.   }
  369.   
  370.   hash->count         = 0;
  371.   hash->lowWaterMark     = (int32_t)(hash->length * hash->lowWaterFactor);
  372.   hash->highWaterMark     = (int32_t)(hash->length * hash->highWaterFactor);
  373. }
  374.  
  375. int32_t 
  376. uhash_leastGreaterPrimeIndex(int32_t source)
  377. {
  378.   int32_t i;
  379.   for(i = 0; i < UHASH_PRIMES_LENGTH; ++i) {
  380.     if(source < UHASH_PRIMES[i]) {
  381.       break;
  382.     }
  383.   }
  384.   return (i == 0 ? 0 : (i - 1));
  385. }
  386.  
  387. void
  388. uhash_rehash(UHashtable *hash,
  389.          UErrorCode *status)
  390. {
  391.   /*
  392.     Rebuild the table from the start. This clears out deadwood, in case
  393.     we have a lot of deleted values. See Find
  394.     It is also used when the table grows or shrinks a lot.
  395.     INVARIANT: The size of the table MUST be prime for this algorithm to work!
  396.   */
  397.   
  398.   void         **oldValues     = hash->values;
  399.   int32_t     *oldHashList     = hash->hashes;
  400.   int32_t     old_length     = hash->length;
  401.   int32_t     newPrimeIndex     = hash->primeIndex;
  402.   int32_t     i;
  403.  
  404.   if(U_FAILURE(*status)) return;
  405.  
  406.   if(hash->count > hash->highWaterMark) {
  407.     ++newPrimeIndex;
  408.   }
  409.   else if(hash->count < hash->lowWaterMark) {
  410.     newPrimeIndex -= 2;
  411.   }
  412.  
  413.   uhash_initialize(hash, newPrimeIndex, status);
  414.   for(i = old_length - 1; i >= 0; --i) {
  415.     void *value = oldValues[i];
  416.     if(value != 0) {
  417.       uhash_putInternal(hash, oldHashList[i], value);
  418.     }
  419.   }
  420.   
  421.   icu_free(oldValues);
  422.   icu_free(oldHashList);
  423. }
  424.  
  425. void
  426. uhash_putInternal(UHashtable *hash,
  427.           int32_t hashCode, 
  428.           void *value)
  429. {
  430.   int32_t index = uhash_find(hash, hashCode);
  431.   if(hash->hashes[index] <= UHASH_MAX_UNUSED) {  
  432.     /* deleted or empty */
  433.     hash->hashes[index] = hashCode;               
  434.     ++(hash->count);
  435.   }
  436.   
  437.   /* reset value */
  438.   hash->values[index] = value; 
  439. }
  440.  
  441. int32_t 
  442. uhash_find(const UHashtable *hash,
  443.        int32_t hashCode)
  444. {
  445.   /*
  446.     This is the key routine. It looks for a particular key in the following 
  447.     way. First find the start position, which is basically the key modulo the
  448.     length. Test it to see if it is 
  449.     a. Identical (same hash values)
  450.     b. Deleted
  451.     c. Empty
  452.     Stop if it is identical or empty, otherwise continue by adding a "jump"
  453.     value (moduloing by the length again to keep it within range) and
  454.     retesting. For efficiency, it needs enough empty values so that the
  455.     searches stop within a reasonable amount of time. This can be changed by
  456.     changing the high/low water marks.
  457.     INVARIANT: the size of the table MUST be prime for this algorithm to work!
  458.   */
  459.  
  460.   int32_t firstDeleted     = -1; 
  461.   int32_t index     = (hashCode ^ 0x4000000) % hash->length;
  462.   int32_t jump         = 0;
  463.  
  464.   while(TRUE) {
  465.     int32_t tableHash = hash->hashes[index];
  466.  
  467.     /* Compare hash codes */
  468.     if(tableHash == hashCode) {     
  469.       return index;
  470.     } 
  471.     
  472.     /* neither correct nor unused */
  473.     else if(tableHash > UHASH_MAX_UNUSED) {   
  474.       /* ignore */
  475.     }
  476.  
  477.     /* empty, end o' the line */
  478.     else if(tableHash == UHASH_SLOT_EMPTY) {   
  479.       if(firstDeleted >= 0) {
  480.     /* reset if had deleted slot */
  481.     index = firstDeleted;   
  482.       }
  483.       return index;
  484.     }
  485.     
  486.     /* remember first deleted */
  487.     else if(firstDeleted < 0) { 
  488.       firstDeleted = index;
  489.     }
  490.     
  491.     /* lazy compute jump */
  492.     if(jump == 0) {
  493.       jump = (hashCode % (hash->length - 1)) + 1;
  494.     }
  495.     
  496.     index = (index + jump) % hash->length;
  497.   }
  498.  
  499.   /* This never happens -- just make the compiler happy */
  500.   return -1;
  501. }
  502.  
  503. /* Predefined hash functions */
  504.  
  505. U_CAPI int32_t
  506. uhash_hashUString(const void *parm)
  507. {
  508.   const UChar *key     = (const UChar*) parm;
  509.   int32_t len         = u_strlen(key);
  510.   int32_t hash         = UHASH_INVALID;
  511.   const UChar *limit     = key + len;
  512.   int32_t inc         = (len >= 128 ? len/64 : 1);
  513.  
  514.   /*
  515.     We compute the hash by iterating sparsely over 64 (at most) characters
  516.     spaced evenly through the string.  For each character, we multiply the
  517.     previous hash value by a prime number and add the new character in,
  518.     in the manner of a additive linear congruential random number generator,
  519.     thus producing a pseudorandom deterministic value which should be well
  520.     distributed over the output range. [LIU]
  521.   */
  522.   
  523.   while(key < limit) {
  524.     hash = (hash * 37) + *key;
  525.     key += inc;
  526.   }
  527.   
  528.   if(hash == UHASH_INVALID)
  529.     hash = UHASH_EMPTY;
  530.   
  531.   return hash & 0x7FFFFFFF;
  532. }
  533.  
  534. U_CAPI int32_t
  535. uhash_hashString(const void *parm)
  536. {
  537.   const char *key     = (const char*) parm;
  538.   int32_t len         = strlen(key);
  539.   int32_t hash         = UHASH_INVALID;
  540.   const char *limit     = key + len;
  541.   int32_t inc         = (len >= 128 ? len/64 : 1);
  542.  
  543.   /*
  544.     We compute the hash by iterating sparsely over 64 (at most) characters
  545.     spaced evenly through the string.  For each character, we multiply the
  546.     previous hash value by a prime number and add the new character in,
  547.     in the manner of a additive linear congruential random number generator,
  548.     thus producing a pseudorandom deterministic value which should be well
  549.     distributed over the output range. [LIU]
  550.   */
  551.   
  552.   while(key < limit) {
  553.     hash = (hash * 37) + *key;
  554.     key += inc;
  555.   }
  556.   
  557.   if(hash == UHASH_INVALID)
  558.     hash = UHASH_EMPTY;
  559.   
  560.   return hash & 0x7FFFFFFF;
  561. }
  562.  
  563. U_CAPI int32_t
  564. uhash_hashLong(const void *parm)
  565. {
  566.   int32_t hash = (int32_t) parm;
  567.   return (int32_t) (hash & 0x7FFFFFFF);
  568. }
  569.