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
9 hash createHash (uint n, uint vbits, float factor)
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;
18 H->table = malloc ((((H->size+1)*vbits+W-1)/W)*sizeof(uint));
20 printf (" Also created hash table of %i bits\n",
21 (((H->size+1)*vbits+W-1)/W)*W);
23 for (i=(((H->size+1)*vbits+W-1)/W)-1;i>=0;i--) H->table[i] = 0;
27 // frees the structure
29 void destroyHash (hash H)
31 { if (H == NULL) return;
36 // inserts an entry, not prepared for overflow
38 void insertHash (hash H, uint key, uint value)
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);
45 bitput(H->table,pos*H->bits,H->bits,value);
48 // looks for a key, returns first value (zero => no values)
49 // writes in pos a handle to get next values
51 uint searchHash (hash H, uint key, handle *h)
53 { *h = (key*PRIME1) & H->size;
54 return bitget(H->table,*h*H->bits,H->bits);
57 // gets following values using handle *pos, which is rewritten
58 // returns next value (zero => no more values)
60 uint nextHash (hash H, handle *h)
62 { *h = (*h +PRIME2) & H->size;
63 return bitget(H->table,*h*H->bits,H->bits);
67 uint sizeofHash(hash H)
69 if (H) return sizeof(struct shash) +
70 (((H->size+1)*H->bits+W-1)/W)*sizeof(uint);