1 18824b58 2008-08-03 rsc #include "a.h"
  2 18824b58 2008-08-03 rsc 
  3 18824b58 2008-08-03 rsc struct Cache
  4 18824b58 2008-08-03 rsc {
  5 18824b58 2008-08-03 rsc 	CEntry **hash;
  6 18824b58 2008-08-03 rsc 	int nhash;
  7 18824b58 2008-08-03 rsc 	CEntry *head;
  8 18824b58 2008-08-03 rsc 	CEntry *tail;
  9 18824b58 2008-08-03 rsc 	int nentry;
 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*);
 13 18824b58 2008-08-03 rsc };
 14 18824b58 2008-08-03 rsc 
 15 18824b58 2008-08-03 rsc static void
 16 18824b58 2008-08-03 rsc nop(CEntry *ce)
 17 18824b58 2008-08-03 rsc {
 18 18824b58 2008-08-03 rsc }
 19 18824b58 2008-08-03 rsc 
 20 18824b58 2008-08-03 rsc static uint
 21 18824b58 2008-08-03 rsc hash(const char *s)
 22 18824b58 2008-08-03 rsc {
 23 18824b58 2008-08-03 rsc 	uint h;
 24 18824b58 2008-08-03 rsc 	uchar *p;
 25 18824b58 2008-08-03 rsc 
 26 18824b58 2008-08-03 rsc 	h = 0;
 27 18824b58 2008-08-03 rsc 	for(p=(uchar*)s; *p; p++)
 28 18824b58 2008-08-03 rsc 		h = h*37 + *p;
 29 18824b58 2008-08-03 rsc 	return h;
 30 18824b58 2008-08-03 rsc }
 31 18824b58 2008-08-03 rsc 
 32 18824b58 2008-08-03 rsc Cache*
 33 18824b58 2008-08-03 rsc newcache(int sizeofentry, int maxentry, void (*cefree)(CEntry*))
 34 18824b58 2008-08-03 rsc {
 35 18824b58 2008-08-03 rsc 	Cache *c;
 36 18824b58 2008-08-03 rsc 	int i;
 37 18824b58 2008-08-03 rsc 
 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)
 44 18824b58 2008-08-03 rsc 		;
 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;
 50 18824b58 2008-08-03 rsc 	return c;
 51 18824b58 2008-08-03 rsc }
 52 18824b58 2008-08-03 rsc 
 53 18824b58 2008-08-03 rsc static void
 54 18824b58 2008-08-03 rsc popout(Cache *c, CEntry *e)
 55 18824b58 2008-08-03 rsc {
 56 18824b58 2008-08-03 rsc 	if(e->list.prev)
 57 18824b58 2008-08-03 rsc 		e->list.prev->list.next = e->list.next;
 58 18824b58 2008-08-03 rsc 	else
 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;
 62 18824b58 2008-08-03 rsc 	else
 63 18824b58 2008-08-03 rsc 		c->tail = e->list.prev;
 64 18824b58 2008-08-03 rsc }
 65 18824b58 2008-08-03 rsc 
 66 18824b58 2008-08-03 rsc static void
 67 18824b58 2008-08-03 rsc insertfront(Cache *c, CEntry *e)
 68 18824b58 2008-08-03 rsc {
 69 18824b58 2008-08-03 rsc 	e->list.next = c->head;
 70 18824b58 2008-08-03 rsc 	c->head = e;
 71 18824b58 2008-08-03 rsc 	if(e->list.next)
 72 18824b58 2008-08-03 rsc 		e->list.next->list.prev = e;
 73 18824b58 2008-08-03 rsc 	else
 74 18824b58 2008-08-03 rsc 		c->tail = e;
 75 18824b58 2008-08-03 rsc }
 76 18824b58 2008-08-03 rsc 
 77 18824b58 2008-08-03 rsc static void
 78 18824b58 2008-08-03 rsc movetofront(Cache *c, CEntry *e)
 79 18824b58 2008-08-03 rsc {
 80 18824b58 2008-08-03 rsc 	popout(c, e);
 81 fa325e9b 2020-01-10 cross 	insertfront(c, e);
 82 18824b58 2008-08-03 rsc }
 83 18824b58 2008-08-03 rsc 
 84 18824b58 2008-08-03 rsc static CEntry*
 85 18824b58 2008-08-03 rsc evict(Cache *c)
 86 18824b58 2008-08-03 rsc {
 87 18824b58 2008-08-03 rsc 	CEntry *e;
 88 fa325e9b 2020-01-10 cross 
 89 18824b58 2008-08-03 rsc 	e = c->tail;
 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);
 96 18824b58 2008-08-03 rsc 	return e;
 97 18824b58 2008-08-03 rsc }
 98 18824b58 2008-08-03 rsc 
 99 18824b58 2008-08-03 rsc CEntry*
100 18824b58 2008-08-03 rsc cachelookup(Cache *c, char *name, int create)
101 18824b58 2008-08-03 rsc {
102 18824b58 2008-08-03 rsc 	int h;
103 18824b58 2008-08-03 rsc 	CEntry *e;
104 fa325e9b 2020-01-10 cross 
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);
109 18824b58 2008-08-03 rsc 			return e;
110 18824b58 2008-08-03 rsc 		}
111 18824b58 2008-08-03 rsc 	}
112 fa325e9b 2020-01-10 cross 
113 18824b58 2008-08-03 rsc 	if(!create)
114 18824b58 2008-08-03 rsc 		return nil;
115 fa325e9b 2020-01-10 cross 
116 18824b58 2008-08-03 rsc 	if(c->nentry >= c->maxentry)
117 18824b58 2008-08-03 rsc 		e = evict(c);
118 18824b58 2008-08-03 rsc 	else{
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++;
122 18824b58 2008-08-03 rsc 	}
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;
127 fa325e9b 2020-01-10 cross 	return e;
128 18824b58 2008-08-03 rsc }
129 18824b58 2008-08-03 rsc 
130 18824b58 2008-08-03 rsc void
131 18824b58 2008-08-03 rsc cacheflush(Cache *c, char *substr)
132 18824b58 2008-08-03 rsc {
133 18824b58 2008-08-03 rsc 	CEntry **l, *e;
134 18824b58 2008-08-03 rsc 	int i;
135 fa325e9b 2020-01-10 cross 
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);
144 18824b58 2008-08-03 rsc 				free(e);
145 18824b58 2008-08-03 rsc 			}else
146 18824b58 2008-08-03 rsc 				l = &e->hash.next;
147 18824b58 2008-08-03 rsc 		}
148 18824b58 2008-08-03 rsc 	}
149 18824b58 2008-08-03 rsc }