Blob
1 #include <u.h>2 #include <libc.h>3 #include <fcall.h>4 #include <thread.h>5 #include <9p.h>7 enum {8 NHASH = 1289 };11 typedef struct Intlist Intlist;12 struct Intlist13 {14 ulong id;15 void* aux;16 Intlist* link;17 };19 struct Intmap20 {21 RWLock rwlock;22 Intlist* hash[NHASH];23 void (*inc)(void*);24 };26 static ulong27 hashid(ulong id)28 {29 return id%NHASH;30 }32 static void33 nop(void *v)34 {35 USED(v);36 }38 Intmap*39 allocmap(void (*inc)(void*))40 {41 Intmap *m;43 m = emalloc9p(sizeof(*m));44 if(inc == nil)45 inc = nop;46 m->inc = inc;47 return m;48 }50 void51 freemap(Intmap *map, void (*destroy)(void*))52 {53 int i;54 Intlist *p, *nlink;56 if(destroy == nil)57 destroy = nop;58 for(i=0; i<NHASH; i++){59 for(p=map->hash[i]; p; p=nlink){60 nlink = p->link;61 destroy(p->aux);62 free(p);63 }64 }66 free(map);67 }69 static Intlist**70 llookup(Intmap *map, ulong id)71 {72 Intlist **lf;74 for(lf=&map->hash[hashid(id)]; *lf; lf=&(*lf)->link)75 if((*lf)->id == id)76 break;77 return lf;78 }80 /*81 * The RWlock is used as expected except that we allow82 * inc() to be called while holding it. This is because we're83 * locking changes to the tree structure, not to the references.84 * Inc() is expected to have its own locking.85 */86 void*87 lookupkey(Intmap *map, ulong id)88 {89 Intlist *f;90 void *v;92 rlock(&map->rwlock);93 if(f = *llookup(map, id)){94 v = f->aux;95 map->inc(v);96 }else97 v = nil;98 runlock(&map->rwlock);99 return v;100 }102 void*103 insertkey(Intmap *map, ulong id, void *v)104 {105 Intlist *f;106 void *ov;107 ulong h;109 wlock(&map->rwlock);110 if(f = *llookup(map, id)){111 /* no decrement for ov because we're returning it */112 ov = f->aux;113 f->aux = v;114 }else{115 f = emalloc9p(sizeof(*f));116 f->id = id;117 f->aux = v;118 h = hashid(id);119 f->link = map->hash[h];120 map->hash[h] = f;121 ov = nil;122 }123 wunlock(&map->rwlock);124 return ov;125 }127 int128 caninsertkey(Intmap *map, ulong id, void *v)129 {130 Intlist *f;131 int rv;132 ulong h;134 wlock(&map->rwlock);135 if(*llookup(map, id))136 rv = 0;137 else{138 f = emalloc9p(sizeof *f);139 f->id = id;140 f->aux = v;141 h = hashid(id);142 f->link = map->hash[h];143 map->hash[h] = f;144 rv = 1;145 }146 wunlock(&map->rwlock);147 return rv;148 }150 void*151 deletekey(Intmap *map, ulong id)152 {153 Intlist **lf, *f;154 void *ov;156 wlock(&map->rwlock);157 if(f = *(lf = llookup(map, id))){158 ov = f->aux;159 *lf = f->link;160 free(f);161 }else162 ov = nil;163 wunlock(&map->rwlock);164 return ov;165 }