distrib/sources/tas/stm/stm_ht.c

   1 /****************************************************************************/
   2 /*                                                                          */
   3 /*                      Chaine de CAO & VLSI   AVERTEC                      */
   4 /*                                                                          */
   5 /*    Produit : STM Version 1.00                                            */
   6 /*    Fichier : stm_ht.c                                                    */
   7 /*                                                                          */
   8 /*    (c) copyright 2000 AVERTEC                                            */
   9 /*    Tous droits reserves                                                  */
  10 /*                                                                          */
  11 /*    Auteur(s) : Gilles Augustins                                          */
  12 /*                                                                          */
  13 /****************************************************************************/
  14
  15 /****************************************************************************/
  16 /*     includes                                                             */
  17 /****************************************************************************/
  18
  19 #include "stm.h"
  20
  21 /****************************************************************************/
  22 /*     functions                                                            */
  23 /****************************************************************************/
  24
  25 /* Random hash function due to Don. E. Knuth, The Stanford Graph Base.
  26  * Truly better than the previous one from my own experimentations. */
  27 #define STM_HASH_MULT  314159
  28 #define STM_HASH_PRIME 516595003
  29 /* namealloc hash table size: the 1230th prime */
  30 #define STM_HASH_VAL   100007
  31
  32 static int HASH_FUNC (char *inputname)
  33 {
  34     unsigned char c;
  35
  36     int code = 0;
  37     while (*inputname) {
  38         c = *inputname++;
  39         code += (code ^ (code >> 1)) + STM_HASH_MULT * c;
  40         while (code >= STM_HASH_PRIME)
  41             code -= STM_HASH_PRIME;
  42     }
  43     code %= STM_HASH_VAL;
  44
  45     return code;
  46 }
  47
  48 /****************************************************************************/
  49 /* function addht, create a hash table                                      */
  50 /****************************************************************************/
  51
  52 stm_ht *stm_addht (unsigned long len)
  53 {
  54     stm_ht *pTable;
  55     stm_htitem *pEl;
  56     unsigned int i;
  57
  58     if (len == 0) {
  59         avt_errmsg (STM_ERRMSG,"008", AVT_ERROR);
  60         return NULL;
  61     }
  62
  63     pTable = (stm_ht*)mbkalloc (sizeof (struct stm_htable));
  64     pTable->length = len;
  65     pEl = (stm_htitem*)mbkalloc (len * (sizeof (struct stm_htitem)));
  66     pTable->pElem = pEl;
  67     for (i = 0; i < len; i++) {
  68         pEl[i].key = NULL;
  69         pEl[i].value = STM_EMPTYHT;
  70     }
  71     pTable->count = 0;
  72     return pTable;
  73 }
  74
  75 /****************************************************************************/
  76 /* function delht, delete a hash table                                      */
  77 /****************************************************************************/
  78
  79 void stm_delht (stm_ht *pTable)
  80 {
  81     stm_htitem *pEl;
  82
  83     pEl = pTable->pElem;
  84     mbkfree (pEl);
  85     mbkfree (pTable);
  86 }
  87
  88 /****************************************************************************/
  89 /* function gethtitem, get an element in a hash table                       */
  90 /****************************************************************************/
  91
  92 long stm_gethtitem (stm_ht *pTable, char *key)
  93 {
  94     long co = 0;
  95     long indice = 0;
  96     stm_htitem * pEl;
  97
  98     indice = HASH_FUNC (key) % pTable->length;
  99     do {
 100         if (co++ > STM_HMAX_CALLS) {
 101             if ((pTable->count > (pTable->length) * 2 / 10) || (co >= pTable->length)) {
 102                 stm_reallocht (pTable);
 103                 return stm_gethtitem (pTable, key);
 104             }
 105         }
 106
 107         pEl = (pTable->pElem) + indice;
 108         if (pEl->value != STM_EMPTYHT && pEl->value != STM_DELETEHT) {
 109             if (!strcmp (key, pEl->key))
 110                 return pEl->value;
 111         } else if (pEl->value == STM_EMPTYHT)
 112             return STM_EMPTYHT;
 113         indice = (indice + 1) % pTable->length;
 114     } while (1);
 115 }
 116
 117 /****************************************************************************/
 118 /* function addhtitem, get an element in a hash table                       */
 119 /****************************************************************************/
 120
 121 long stm_addhtitem (stm_ht *pTable, char *key, long value)
 122 {
 123     int indice = 0;
 124     stm_htitem *pEl;
 125     int co = 0;
 126
 127     if (value == STM_EMPTYHT || value == STM_DELETEHT) {
 128         avt_errmsg (STM_ERRMSG,"009", AVT_ERROR);
 129         return 0;
 130     }
 131
 132     if (pTable->count++ > (pTable->length) * 8 / 10) {
 133         stm_reallocht (pTable);
 134         return stm_addhtitem (pTable, key, value);
 135     }
 136
 137     indice = HASH_FUNC (key) % pTable->length;
 138     do {
 139         if (co++ > STM_HMAX_CALLS) {
 140                     if (pTable->count > (pTable->length) * 2 / 10 || (co >= pTable->length)) {
 141                 stm_reallocht (pTable);
 142                 return stm_addhtitem (pTable, key, value);
 143             }
 144             }
 145         pEl = (pTable->pElem) + indice;
 146         if (pEl->value == STM_EMPTYHT || pEl->value == STM_DELETEHT) {
 147             pEl->value = value;
 148             pEl->key = strdup (key);
 149             return value;
 150         } else if (!strcmp (pEl->key, key)) {
 151             pTable->count--;
 152             pEl->value = value;
 153             return value;
 154         }
 155         indice = (indice + 1) % pTable->length;
 156     } while (1);
 157 }
 158
 159 /****************************************************************************/
 160 /* function delhtitem, delete an element in a hash table                    */
 161 /****************************************************************************/
 162
 163 long stm_delhtitem (stm_ht *pTable, char *key)
 164 {
 165     int indice = 0;
 166     stm_htitem *pEl;
 167     int co = 0;
 168
 169     indice = HASH_FUNC (key) % pTable->length;
 170     do {
 171         if (co++ > STM_HMAX_CALLS) {
 172               if (pTable->count > (pTable->length) * 2 / 10 || (co >= pTable->length)) {
 173             stm_reallocht (pTable);
 174             return stm_delhtitem (pTable, key);
 175           }
 176         }
 177
 178         pEl = (pTable->pElem) + indice;
 179         if (pEl->value != STM_EMPTYHT && pEl->value != STM_DELETEHT) {
 180             if (!strcmp (key, pEl->key)) {
 181                 pTable->count--;
 182                 pEl->value = STM_DELETEHT;
 183                 mbkfree (pEl->key);
 184                 return pEl->value;
 185             }
 186         } else if (pEl->value == STM_EMPTYHT)
 187             return STM_EMPTYHT;
 188         indice = (indice + 1) % pTable->length;
 189     } while (1);
 190 }
 191
 192 /****************************************************************************/
 193 /* realloc space to adapt hash table size to number of entries              */
 194 /****************************************************************************/
 195
 196 void stm_reallocht (stm_ht *pTable)
 197 {
 198     stm_ht *tabBis;
 199     stm_htitem *pEl;
 200     int i;
 201     double ratio;
 202
 203     pEl = pTable->pElem;
 204
 205     ratio = (double)pTable->count / (double)pTable->length;
 206     if (ratio > 0.8) ratio = 1;
 207     else if (ratio < 0.3) ratio = 0.3;
 208
 209     tabBis = stm_addht ((unsigned long)((double)(pTable->length) * 5.0 * ratio));
 210     for (i = 0; i < pTable->length; i++) {
 211         if (pEl->value != STM_EMPTYHT && pEl->value != STM_DELETEHT)
 212             stm_addhtitem (tabBis, pEl->key, pEl->value);
 213         pEl++;
 214     }
 215     mbkfree (pTable->pElem);
 216     pTable->length = tabBis->length;
 217     pTable->pElem = tabBis->pElem;
 218     pTable->count = tabBis->count;
 219     mbkfree (tabBis);
 220 }
 221