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