1 /* $Id: ht.c 338 2004-01-23 20:26:46Z dvd $ */
2
3 #include <stdlib.h> /*NULL*/
4 #include <assert.h> /*assert*/
5 #include "m.h"
6 #include "ht.h"
7
8 #define LOAD_FACTOR 2
9
ht_init(struct hashtable * ht,int len,int (* hash)(int),int (* equal)(int,int))10 void ht_init(struct hashtable *ht,int len,int (*hash)(int),int (*equal)(int,int)) {
11 assert(len>0);
12 ht->tablen=1; len*=LOAD_FACTOR;
13 while(ht->tablen<len) ht->tablen<<=1;
14 ht->limit=ht->tablen/LOAD_FACTOR;
15 ht->table=(int*)m_alloc(ht->tablen<<1,sizeof(int)); /* the second half is hash values */
16 ht->hash=hash; ht->equal=equal;
17 ht_clear(ht);
18 }
19
ht_clear(struct hashtable * ht)20 void ht_clear(struct hashtable *ht) {
21 int i;
22 ht->used=0; for(i=0;i!=ht->tablen;++i) ht->table[i]=-1;
23 }
24
ht_dispose(struct hashtable * ht)25 void ht_dispose(struct hashtable *ht) {
26 m_free(ht->table); ht->table=NULL;
27 }
28
29 #define first(ht,hv) (hv&(ht->tablen-1))
30 #define next(ht,i) (i==0?ht->tablen-1:i-1)
31
ht_get(struct hashtable * ht,int i)32 int ht_get(struct hashtable *ht,int i) {
33 int hv=ht->hash(i),j;
34 for(j=first(ht,hv);;j=next(ht,j)) {
35 int tj=ht->table[j];
36 if(tj==-1) break;
37 if(ht->equal(i,tj)) return tj;
38 }
39 return -1;
40 }
41
ht_put(struct hashtable * ht,int i)42 void ht_put(struct hashtable *ht,int i) {
43 int hv=ht->hash(i),j;
44 if(ht->used==ht->limit) {
45 int tablen=ht->tablen; int *table=ht->table;
46 ht->tablen<<=1; ht->limit<<=1;
47 ht->table=(int*)m_alloc(ht->tablen<<1,sizeof(int));
48 for(j=0;j!=ht->tablen;++j) ht->table[j]=-1;
49 for(j=0;j!=tablen;++j) {
50 if(table[j]!=-1) {
51 int hvj=table[j|tablen]; int k;
52 for(k=first(ht,hvj);ht->table[k]!=-1;k=next(ht,k));
53 ht->table[k]=table[j]; ht->table[k|ht->tablen]=hvj;
54 }
55 }
56 m_free(table);
57 }
58 for(j=first(ht,hv);ht->table[j]!=-1;j=next(ht,j)) assert(!ht->equal(i,ht->table[j]));
59 ht->table[j]=i;
60 ht->table[ht->tablen|j]=hv;
61 ++ht->used;
62 }
63
del(struct hashtable * ht,int i,int eq)64 static int del(struct hashtable *ht,int i,int eq) {
65 if(ht->used!=0) {
66 int hv=ht->hash(i),j;
67 for(j=first(ht,hv);;j=next(ht,j)) {
68 int tj=ht->table[j];
69 if(tj==-1) break;
70 if(eq?i==tj:ht->equal(i,tj)) {
71 do {
72 int k=j,j0;
73 ht->table[j]=-1;
74 for(;;) {
75 j=next(ht,j);
76 if(ht->table[j]==-1) break;
77 j0=first(ht,ht->table[j|ht->tablen]);
78 if((k<=j0||j0<j)&&(j0<j||j<=k)&&(j<=k||k<=j0)) break;
79 }
80 ht->table[k]=ht->table[j]; ht->table[k|ht->tablen]=ht->table[j|ht->tablen];
81 } while(ht->table[j]!=-1);
82 --ht->used;
83 return tj;
84 }
85 }
86 }
87 return -1;
88 }
ht_del(struct hashtable * ht,int i)89 int ht_del(struct hashtable *ht,int i) {return del(ht,i,0);}
ht_deli(struct hashtable * ht,int i)90 int ht_deli(struct hashtable *ht,int i) {return del(ht,i,1);}
91