42 static int alloc_ht(T_HashTable *H, size_t size)  in alloc_ht()  argument
61   if(size < H->size)  in alloc_ht()
62 	  size = H->size; /* never shrink the table */  in alloc_ht()
63   H->max = size * 4 / 5 - 2;  in alloc_ht()
64   H->size = size;  in alloc_ht()
65   H->fill = 0;  in alloc_ht()
66   H->inuse = 0;  in alloc_ht()
67   H->entries = NewArray(size, T_HashTableEl);  in alloc_ht()
68   if (H->entries == NULL)  in alloc_ht()
72     H->entries[ii] = &unallocated;  in alloc_ht()
77 	    T_HashTable **H)  in make_ht()  argument
79   *H = New(T_HashTable);  in make_ht()
80   if (*H == NULL){  in make_ht()
84   (*H)->f1 = f1;  in make_ht()
85   (*H)->f2 = f2;  in make_ht()
86   (*H)->compar = c;  in make_ht()
87   (*H)->size = 0;  in make_ht()
88   if(alloc_ht(*H,size))  in make_ht()
93 int free_ht(T_HashTable *H, T_HashFunc entry_free)  in free_ht()  argument
97     for(i=0; i< H->size; i++)  in free_ht()
98       if (H->entries[i] != &unallocated &&  in free_ht()
99 	  H->entries[i] != &deleted)  in free_ht()
100 	entry_free(H->entries[i]);  in free_ht()
101   Free(H->entries);  in free_ht()
102   Free(H);  in free_ht()
107 static int _hash_add(T_HashTable *H,T_HashTableEl *E, size_t *hint)  in _hash_add()  argument
112   pos = H->f1(E) % H->size;  in _hash_add()
115   while(H->entries[pos] != &unallocated &&  in _hash_add()
116 	H->entries[pos] != &deleted){  in _hash_add()
118       f2 = H->f2(E) % (H->size - 1);  in _hash_add()
119     pos = (pos+f2+1) % H->size;  in _hash_add()
122   if(H->entries[pos] == &unallocated)  in _hash_add()
123      H->fill++; /* only increase fill if the previous element was not yet  in _hash_add()
125   H->inuse++;  in _hash_add()
126   H->entries[pos] = E;  in _hash_add()
132 static int rehash(T_HashTable *H)  in rehash()  argument
138   size = H->size;  in rehash()
139   oldentries = H->entries;  in rehash()
140   if(alloc_ht(H,((H->inuse+1)*4+H->fill)/5))  in rehash()
145       _hash_add(H, oldentries[i], 0);  in rehash()
151 int hash_add(T_HashTable *H, T_HashTableEl *E, size_t *hint)  in hash_add()  argument
153   if (H->fill >= H->max)  in hash_add()
154     rehash(H);  in hash_add()
155   if (H->fill == H->size)  in hash_add()
157   return _hash_add(H,E, hint);  in hash_add()
162 static int _hash_lookup(T_HashTable *H,T_HashTableEl *E, T_HashTableEl **E2,  in _hash_lookup()  argument
167   pos = H->f1(E) % H->size;  in _hash_lookup()
168   ttl = H->size;  in _hash_lookup()
172 	H->entries[pos] != &unallocated &&  in _hash_lookup()
173 	(H->entries[pos] == &deleted ||  in _hash_lookup()
174 	 ((isIdentity || H->compar(H->entries[pos], E) != 0) &&  in _hash_lookup()
175 	  (!isIdentity || H->entries[pos] != E)))){  in _hash_lookup()
177       f2 = H->f2(E) % (H->size - 1);  in _hash_lookup()
178     if (upos == (size_t) -1 && H->entries[pos] == &deleted)  in _hash_lookup()
180     pos = (pos+f2+1) % H->size;  in _hash_lookup()
183   if(H->entries[pos] == &unallocated || !ttl)  in _hash_lookup()
186     H->entries[upos] = H->entries[pos];  in _hash_lookup()
187     H->entries[pos] = &deleted;  in _hash_lookup()
192   *E2= H->entries[pos];  in _hash_lookup()
197 int hash_lookup(T_HashTable *H,T_HashTableEl *E, T_HashTableEl **E2,  in hash_lookup()  argument
200 	return _hash_lookup(H, E, E2, hint, 0);  in hash_lookup()
204 int hash_remove(T_HashTable *H,T_HashTableEl *E, size_t hint)  in hash_remove()  argument
208   if (hint >=0 && hint < H->size &&  in hash_remove()
209       H->entries[hint] == E){  in hash_remove()
210     H->inuse--;  in hash_remove()
211     H->entries[hint] = &deleted;  in hash_remove()
215   if(_hash_lookup(H, E, &E2, &hint, 1)) {  in hash_remove()
219   H->inuse--;  in hash_remove()
220   H->entries[hint] = &deleted;  in hash_remove()