1 18824b58 2008-08-03 rsc #include "a.h"
5 18824b58 2008-08-03 rsc CEntry **hash;
10 18824b58 2008-08-03 rsc int maxentry;
11 18824b58 2008-08-03 rsc int sizeofentry;
12 18824b58 2008-08-03 rsc void (*cefree)(CEntry*);
16 18824b58 2008-08-03 rsc nop(CEntry *ce)
21 18824b58 2008-08-03 rsc hash(const char *s)
27 18824b58 2008-08-03 rsc for(p=(uchar*)s; *p; p++)
28 18824b58 2008-08-03 rsc h = h*37 + *p;
33 18824b58 2008-08-03 rsc newcache(int sizeofentry, int maxentry, void (*cefree)(CEntry*))
38 18824b58 2008-08-03 rsc assert(sizeofentry >= sizeof(CEntry));
39 18824b58 2008-08-03 rsc c = emalloc(sizeof *c);
40 18824b58 2008-08-03 rsc c->sizeofentry = sizeofentry;
41 18824b58 2008-08-03 rsc c->maxentry = maxentry;
42 18824b58 2008-08-03 rsc c->nentry = 0;
43 18824b58 2008-08-03 rsc for(i=1; i<maxentry; i<<=1)
45 18824b58 2008-08-03 rsc c->nhash = i;
46 18824b58 2008-08-03 rsc c->hash = emalloc(c->nhash * sizeof c->hash[0]);
47 18824b58 2008-08-03 rsc if(cefree == nil)
48 18824b58 2008-08-03 rsc cefree = nop;
49 18824b58 2008-08-03 rsc c->cefree = cefree;
54 18824b58 2008-08-03 rsc popout(Cache *c, CEntry *e)
56 18824b58 2008-08-03 rsc if(e->list.prev)
57 18824b58 2008-08-03 rsc e->list.prev->list.next = e->list.next;
59 18824b58 2008-08-03 rsc c->head = e->list.next;
60 18824b58 2008-08-03 rsc if(e->list.next)
61 18824b58 2008-08-03 rsc e->list.next->list.prev = e->list.prev;
63 18824b58 2008-08-03 rsc c->tail = e->list.prev;
67 18824b58 2008-08-03 rsc insertfront(Cache *c, CEntry *e)
69 18824b58 2008-08-03 rsc e->list.next = c->head;
71 18824b58 2008-08-03 rsc if(e->list.next)
72 18824b58 2008-08-03 rsc e->list.next->list.prev = e;
78 18824b58 2008-08-03 rsc movetofront(Cache *c, CEntry *e)
80 18824b58 2008-08-03 rsc popout(c, e);
81 18824b58 2008-08-03 rsc insertfront(c, e);
84 18824b58 2008-08-03 rsc static CEntry*
85 18824b58 2008-08-03 rsc evict(Cache *c)
90 18824b58 2008-08-03 rsc popout(c, e);
91 18824b58 2008-08-03 rsc c->cefree(e);
92 18824b58 2008-08-03 rsc free(e->name);
93 18824b58 2008-08-03 rsc e->name = nil;
94 18824b58 2008-08-03 rsc memset(e, 0, c->sizeofentry);
95 18824b58 2008-08-03 rsc insertfront(c, e);
100 18824b58 2008-08-03 rsc cachelookup(Cache *c, char *name, int create)
105 18824b58 2008-08-03 rsc h = hash(name) % c->nhash;
106 18824b58 2008-08-03 rsc for(e=c->hash[h]; e; e=e->hash.next){
107 18824b58 2008-08-03 rsc if(strcmp(name, e->name) == 0){
108 18824b58 2008-08-03 rsc movetofront(c, e);
116 18824b58 2008-08-03 rsc if(c->nentry >= c->maxentry)
117 18824b58 2008-08-03 rsc e = evict(c);
119 18824b58 2008-08-03 rsc e = emalloc(c->sizeofentry);
120 18824b58 2008-08-03 rsc insertfront(c, e);
121 18824b58 2008-08-03 rsc c->nentry++;
123 18824b58 2008-08-03 rsc e->name = estrdup(name);
124 18824b58 2008-08-03 rsc h = hash(name) % c->nhash;
125 18824b58 2008-08-03 rsc e->hash.next = c->hash[h];
126 18824b58 2008-08-03 rsc c->hash[h] = e;
131 18824b58 2008-08-03 rsc cacheflush(Cache *c, char *substr)
133 18824b58 2008-08-03 rsc CEntry **l, *e;
136 18824b58 2008-08-03 rsc for(i=0; i<c->nhash; i++){
137 18824b58 2008-08-03 rsc for(l=&c->hash[i]; (e=*l); ){
138 18824b58 2008-08-03 rsc if(substr == nil || strstr(e->name, substr)){
139 18824b58 2008-08-03 rsc *l = e->hash.next;
140 18824b58 2008-08-03 rsc c->nentry--;
141 18824b58 2008-08-03 rsc popout(c, e);
142 18824b58 2008-08-03 rsc c->cefree(e);
143 18824b58 2008-08-03 rsc free(e->name);
146 18824b58 2008-08-03 rsc l = &e->hash.next;