tcache.c - plan9port - [fork] Plan 9 from user space
  HTML git clone git://src.adamsgaard.dk/plan9port
   DIR Log
   DIR Files
   DIR Refs
   DIR README
   DIR LICENSE
       ---
       tcache.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 }