hash.c

   1 /*  Copyright 1996,1997,2001,2002,2009 Alain Knaff.
   2  *  This file is part of mtools.
   3  *
   4  *  Mtools is free software: you can redistribute it and/or modify
   5  *  it under the terms of the GNU General Public License as published by
   6  *  the Free Software Foundation, either version 3 of the License, or
   7  *  (at your option) any later version.
   8  *
   9  *  Mtools is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *  GNU General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU General Public License
  15  *  along with Mtools.  If not, see <http://www.gnu.org/licenses/>.
  16  *
  17  * hash.c - hash table.
  18  */
  19
  20 #include "sysincludes.h"
  21 #include "htable.h"
  22 #include "mtools.h"
  23
  24 struct hashtable {
  25   T_HashFunc f1,f2;
  26   T_ComparFunc compar;
  27   int size;  /* actual size of the array */
  28   int fill;  /* number of deleted or in use slots */
  29   int inuse; /* number of slots in use */
  30   int max;   /* maximal number of elements to keep efficient */
  31   T_HashTableEl *entries;
  32 };
  33
  34 static int sizes[]={5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853,
  35                     25717, 51437, 102877, 205759, 411527, 823117, 1646237,
  36                     3292489, 6584983, 13169977, 26339969, 52679969, 105359939,
  37                     210719881, 421439783, 842879579, 1685759167, 0 };
  38 static int deleted=0;
  39 static int unallocated=0;
  40
  41 static int alloc_ht(T_HashTable *H, int size)
  42 {
  43   int i;
  44
  45   for(i=0; sizes[i]; i++)
  46     if (sizes[i] > size*4 )
  47       break;
  48   if (!sizes[i])
  49     for(i=0; sizes[i]; i++)
  50       if (sizes[i] > size*2 )
  51         break;
  52   if (!sizes[i])
  53     for(i=0; sizes[i]; i++)
  54       if (sizes[i] > size)
  55         break;
  56   if(!sizes[i])
  57     return -1;
  58   size = sizes[i];
  59   if(size < H->size)
  60           size = H->size; /* never shrink the table */
  61   H->max = size * 4 / 5 - 2;
  62   H->size = size;
  63   H->fill = 0;
  64   H->inuse = 0;
  65   H->entries = NewArray(size, T_HashTableEl);
  66   if (H->entries == NULL)
  67     return -1; /* out of memory error */
  68
  69   for(i=0; i < size; i++)
  70     H->entries[i] = &unallocated;
  71   return 0;
  72 }
  73
  74 int make_ht(T_HashFunc f1, T_HashFunc f2, T_ComparFunc c, int size,
  75             T_HashTable **H)
  76 {
  77   *H = New(T_HashTable);
  78   if (*H == NULL){
  79     return -1; /* out of memory error */
  80   }
  81
  82   (*H)->f1 = f1;
  83   (*H)->f2 = f2;
  84   (*H)->compar = c;
  85   (*H)->size = 0;
  86   if(alloc_ht(*H,size))
  87     return -1;
  88   return 0;
  89 }
  90
  91 int free_ht(T_HashTable *H, T_HashFunc entry_free)
  92 {
  93   int i;
  94   if(entry_free)
  95     for(i=0; i< H->size; i++)
  96       if (H->entries[i] != &unallocated &&
  97           H->entries[i] != &deleted)
  98         entry_free(H->entries[i]);
  99   Free(H->entries);
 100   Free(H);
 101   return 0;
 102 }
 103
 104 /* add into hash table without checking for repeats */
 105 static int _hash_add(T_HashTable *H,T_HashTableEl *E, int *hint)
 106 {
 107   int f2, pos, ctr;
 108
 109   pos = H->f1(E) % H->size;
 110   f2 = -1;
 111   ctr = 0;
 112   while(H->entries[pos] != &unallocated &&
 113         H->entries[pos] != &deleted){
 114     if (f2 == -1)
 115       f2 = H->f2(E) % (H->size - 1);
 116     pos = (pos+f2+1) % H->size;
 117     ctr++;
 118   }
 119   if(H->entries[pos] == &unallocated)
 120      H->fill++; /* only increase fill if the previous element was not yet
 121                  * counted, i.e. unallocated */
 122   H->inuse++;
 123   H->entries[pos] = E;
 124   if(hint)
 125           *hint = pos;
 126   return 0;
 127 }
 128
 129 static int rehash(T_HashTable *H)
 130 {
 131   int size,i;
 132   T_HashTableEl *oldentries;
 133   /* resize the table */
 134
 135   size = H->size;
 136   oldentries = H->entries;
 137   if(alloc_ht(H,((H->inuse+1)*4+H->fill)/5))
 138           return -1;
 139
 140   for(i=0; i < size; i++){
 141     if(oldentries[i] != &unallocated && oldentries[i] != &deleted)
 142       _hash_add(H, oldentries[i], 0);
 143   }
 144   Free(oldentries);
 145   return 0;
 146 }
 147
 148 int hash_add(T_HashTable *H, T_HashTableEl *E, int *hint)
 149 {
 150   if (H->fill >= H->max)
 151     rehash(H);
 152   if (H->fill == H->size)
 153     return -1; /*out of memory error */
 154   return _hash_add(H,E, hint);
 155 }
 156
 157
 158 /* add into hash table without checking for repeats */
 159 static int _hash_lookup(T_HashTable *H,T_HashTableEl *E, T_HashTableEl **E2,
 160                         int *hint, int isIdentity)
 161 {
 162   int f2, pos, upos, ttl;
 163
 164   pos = H->f1(E) % H->size;
 165   ttl = H->size;
 166   f2 = -1;
 167   upos = -1;
 168   while(ttl &&
 169         H->entries[pos] != &unallocated &&
 170         (H->entries[pos] == &deleted ||
 171          ((isIdentity || H->compar(H->entries[pos], E) != 0) &&
 172           (!isIdentity || H->entries[pos] != E)))){
 173     if (f2 == -1)
 174       f2 = H->f2(E) % (H->size - 1);
 175     if (upos == -1 && H->entries[pos] == &deleted)
 176       upos = pos;
 177     pos = (pos+f2+1) % H->size;
 178     ttl--;
 179   }
 180   if(H->entries[pos] == &unallocated || !ttl)
 181     return -1;
 182   if (upos != -1){
 183     H->entries[upos] = H->entries[pos];
 184     H->entries[pos] = &deleted;
 185     pos = upos;
 186   }
 187   if(hint)
 188     *hint = pos;
 189   *E2= H->entries[pos];
 190   return 0;
 191 }
 192
 193
 194 int hash_lookup(T_HashTable *H,T_HashTableEl *E, T_HashTableEl **E2,
 195                 int *hint)
 196 {
 197         return _hash_lookup(H, E, E2, hint, 0);
 198 }
 199
 200 /* add into hash table without checking for repeats */
 201 int hash_remove(T_HashTable *H,T_HashTableEl *E, int hint)
 202 {
 203   T_HashTableEl *E2;
 204
 205   if (hint >=0 && hint < H->size &&
 206       H->entries[hint] == E){
 207     H->inuse--;
 208     H->entries[hint] = &deleted;
 209     return 0;
 210   }
 211
 212   if(_hash_lookup(H, E, &E2, &hint, 1)) {
 213           fprintf(stderr, "Removing non-existent entry\n");
 214           exit(1);
 215           return -1;
 216   }
 217   H->inuse--;
 218   H->entries[hint] = &deleted;
 219   return 0;
 220 }