cache.c (2189B)
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 }