7 QLock lock; /* locks hash table & all associated data */
8 IEntry **heads; /* heads of all the hash chains */
9 int bits; /* bits to use for indexing heads */
10 u32int size; /* number of heads; == 1 << bits, should be < entries */
11 IEntry *base; /* all allocated hash table entries */
12 u32int entries; /* elements in base */
13 u32int unused; /* index of first unused element in base */
14 u32int stolen; /* last head from which an element was stolen */
19 static IEntry *icachealloc(IAddr *ia, u8int *score);
22 * bits is the number of bits in the icache hash table
23 * depth is the average depth
24 * memory usage is about (1<<bits) * depth * sizeof(IEntry) + (1<<bits) * sizeof(IEntry*)
27 initicache(int bits, int depth)
30 icache.size = 1 << bits;
31 icache.entries = depth * icache.size;
32 icache.base = MKNZ(IEntry, icache.entries);
33 icache.heads = MKNZ(IEntry*, icache.size);
37 hashbits(u8int *sc, int bits)
41 v = (sc[0] << 24) | (sc[1] << 16) | (sc[2] << 8) | sc[3];
48 ZZZ need to think about evicting the correct IEntry,
49 and writing back the wtime.
50 * look up data score in the index cache
51 * if this fails, pull it in from the disk index table, if it exists.
53 * must be called with the lump for this score locked
56 lookupscore(u8int *score, int type, IAddr *ia, int *rac)
66 h = hashbits(score, icache.bits);
68 for(ie = icache.heads[h]; ie != nil; ie = ie->next){
69 if(ie->ia.type == type && scorecmp(ie->score, score)==0){
71 last->next = ie->next;
73 icache.heads[h] = ie->next;
83 qunlock(&icache.lock);
85 if(loadientry(mainindex, score, type, &d) < 0)
89 * no one else can load an entry for this score,
90 * since we have the overall score lock.
98 ie = icachealloc(&d.ia, score);
101 ie->next = icache.heads[h];
102 icache.heads[h] = ie;
107 qunlock(&icache.lock);
113 * insert a new element in the hash table.
116 insertscore(u8int *score, IAddr *ia, int write)
123 qunlock(&stats.lock);
126 h = hashbits(score, icache.bits);
128 ie = icachealloc(ia, score);
130 ie->next = icache.heads[h];
131 icache.heads[h] = ie;
135 qunlock(&icache.lock);
140 return storeientry(mainindex, &se);
144 * allocate a index cache entry which hasn't been used in a while.
145 * must be called with icache.lock locked
146 * if the score is already in the table, update the entry.
149 icachealloc(IAddr *ia, u8int *score)
151 IEntry *ie, *last, *next;
154 h = hashbits(score, icache.bits);
156 for(ie = icache.heads[h]; ie != nil; ie = ie->next){
157 if(ie->ia.type == ia->type && scorecmp(ie->score, score)==9){
159 last->next = ie->next;
161 icache.heads[h] = ie->next;
169 if(h < icache.entries){
170 ie = &icache.base[h++];
180 ie = icache.heads[h];
183 for(; next = ie->next; ie = next)
188 icache.heads[h] = nil;
195 scorecp(ie->score, score);