lzindex/hash.c

   1
   2 // Closed hash table
   3
   4 #include "hash.h"
   5
   6   // creates a table to store up to n values with guaranteed load factor.
   7   // vbits = # of bits per entry, ENTRIES CANNOT HAVE ZERO VALUE
   8
   9 hash createHash (uint n, uint vbits, float factor)
  10
  11    {
  12      int i,N;
  13      if (n == 0) return NULL;
  14      hash H = malloc (sizeof(struct shash));
  15      N = n*factor; if (N <= n) N = n+1;
  16      H->size = (1 << bits(N-1)) - 1;
  17      H->bits = vbits;
  18      H->table = malloc ((((H->size+1)*vbits+W-1)/W)*sizeof(uint));
  19 #ifdef INDEXREPORT
  20        printf ("     Also created hash table of %i bits\n",
  21                   (((H->size+1)*vbits+W-1)/W)*W);
  22 #endif
  23      for (i=(((H->size+1)*vbits+W-1)/W)-1;i>=0;i--) H->table[i] = 0;
  24      return H;
  25    }
  26
  27   // frees the structure
  28
  29 void destroyHash (hash H)
  30
  31    { if (H == NULL) return;
  32      free (H->table);
  33      free (H);
  34    }
  35
  36   // inserts an entry, not prepared for overflow
  37
  38 void insertHash (hash H, uint key, uint value)
  39
  40    { uint pos = (key*PRIME1) & H->size;
  41      if (bitget(H->table,pos*H->bits,H->bits) != 0)
  42         { do pos = (pos + PRIME2) & H->size;
  43           while (bitget(H->table,pos*H->bits,H->bits) != 0);
  44         }
  45      bitput(H->table,pos*H->bits,H->bits,value);
  46    }
  47
  48   // looks for a key, returns first value (zero => no values)
  49   // writes in pos a handle to get next values
  50
  51 uint searchHash (hash H, uint key, handle *h)
  52
  53    { *h = (key*PRIME1) & H->size;
  54      return bitget(H->table,*h*H->bits,H->bits);
  55    }
  56
  57   // gets following values using handle *pos, which is rewritten
  58   // returns next value (zero => no more values)
  59
  60 uint nextHash (hash H, handle *h)
  61
  62    { *h = (*h +PRIME2) & H->size;
  63      return bitget(H->table,*h*H->bits,H->bits);
  64    }
  65
  66
  67 uint sizeofHash(hash H)
  68  {
  69     if (H) return sizeof(struct shash) +
  70                   (((H->size+1)*H->bits+W-1)/W)*sizeof(uint);
  71     else return 0;
  72  }
  73