1 #include "a.h"
2 
3 struct Cache
4 {
5 	CEntry **hash;
6 	int nhash;
7 	CEntry *head;
8 	CEntry *tail;
9 	int nentry;
10 	int maxentry;
11 	int sizeofentry;
12 	void (*cefree)(CEntry*);
13 };
14 
15 static void
16 nop(CEntry *ce)
17 {
18 }
19 
20 static uint
21 hash(const char *s)
22 {
23 	uint h;
24 	uchar *p;
25 
26 	h = 0;
27 	for(p=(uchar*)s; *p; p++)
28 		h = h*37 + *p;
29 	return h;
30 }
31 
32 Cache*
33 newcache(int sizeofentry, int maxentry, void (*cefree)(CEntry*))
34 {
35 	Cache *c;
36 	int i;
37 
38 	assert(sizeofentry >= sizeof(CEntry));
39 	c = emalloc(sizeof *c);
40 	c->sizeofentry = sizeofentry;
41 	c->maxentry = maxentry;
42 	c->nentry = 0;
43 	for(i=1; i<maxentry; i<<=1)
44 		;
45 	c->nhash = i;
46 	c->hash = emalloc(c->nhash * sizeof c->hash[0]);
47 	if(cefree == nil)
48 		cefree = nop;
49 	c->cefree = cefree;
50 	return c;
51 }
52 
53 static void
54 popout(Cache *c, CEntry *e)
55 {
56 	if(e->list.prev)
57 		e->list.prev->list.next = e->list.next;
58 	else
59 		c->head = e->list.next;
60 	if(e->list.next)
61 		e->list.next->list.prev = e->list.prev;
62 	else
63 		c->tail = e->list.prev;
64 }
65 
66 static void
67 insertfront(Cache *c, CEntry *e)
68 {
69 	e->list.next = c->head;
70 	c->head = e;
71 	if(e->list.next)
72 		e->list.next->list.prev = e;
73 	else
74 		c->tail = e;
75 }
76 
77 static void
78 movetofront(Cache *c, CEntry *e)
79 {
80 	popout(c, e);
81 	insertfront(c, e);	
82 }
83 
84 static CEntry*
85 evict(Cache *c)
86 {
87 	CEntry *e;
88 	
89 	e = c->tail;
90 	popout(c, e);
91 	c->cefree(e);
92 	free(e->name);
93 	e->name = nil;
94 	memset(e, 0, c->sizeofentry);
95 	insertfront(c, e);
96 	return e;
97 }
98 
99 CEntry*
100 cachelookup(Cache *c, char *name, int create)
101 {
102 	int h;
103 	CEntry *e;
104 	
105 	h = hash(name) % c->nhash;
106 	for(e=c->hash[h]; e; e=e->hash.next){
107 		if(strcmp(name, e->name) == 0){
108 			movetofront(c, e);
109 			return e;
110 		}
111 	}
112 	
113 	if(!create)
114 		return nil;
115 	
116 	if(c->nentry >= c->maxentry)
117 		e = evict(c);
118 	else{
119 		e = emalloc(c->sizeofentry);
120 		insertfront(c, e);
121 		c->nentry++;
122 	}
123 	e->name = estrdup(name);
124 	h = hash(name) % c->nhash;
125 	e->hash.next = c->hash[h];
126 	c->hash[h] = e;
127 	return e;	
128 }
129 
130 void
131 cacheflush(Cache *c, char *substr)
132 {
133 	CEntry **l, *e;
134 	int i;
135 	
136 	for(i=0; i<c->nhash; i++){
137 		for(l=&c->hash[i]; (e=*l); ){
138 			if(substr == nil || strstr(e->name, substr)){
139 				*l = e->hash.next;
140 				c->nentry--;
141 				popout(c, e);
142 				c->cefree(e);
143 				free(e->name);
144 				free(e);
145 			}else
146 				l = &e->hash.next;
147 		}
148 	}
149 }