Blob
1 #include <u.h>2 #include <libc.h>3 #include <auth.h>4 #include <fcall.h>5 #include <thread.h>6 #include <9p.h>8 enum {9 NHASH = 12810 };12 typedef struct Intlist Intlist;13 struct Intlist14 {15 ulong id;16 void* aux;17 Intlist* link;18 };20 struct Intmap21 {22 RWLock rwlock;23 Intlist* hash[NHASH];24 void (*inc)(void*);25 };27 static ulong28 hashid(ulong id)29 {30 return id%NHASH;31 }33 static void34 nop(void *v)35 {36 USED(v);37 }39 Intmap*40 allocmap(void (*inc)(void*))41 {42 Intmap *m;44 m = emalloc9p(sizeof(*m));45 if(inc == nil)46 inc = nop;47 m->inc = inc;48 return m;49 }51 void52 freemap(Intmap *map, void (*destroy)(void*))53 {54 int i;55 Intlist *p, *nlink;57 if(destroy == nil)58 destroy = nop;59 for(i=0; i<NHASH; i++){60 for(p=map->hash[i]; p; p=nlink){61 nlink = p->link;62 destroy(p->aux);63 free(p);64 }65 }67 free(map);68 }70 static Intlist**71 llookup(Intmap *map, ulong id)72 {73 Intlist **lf;75 for(lf=&map->hash[hashid(id)]; *lf; lf=&(*lf)->link)76 if((*lf)->id == id)77 break;78 return lf;79 }81 /*82 * The RWlock is used as expected except that we allow83 * inc() to be called while holding it. This is because we're84 * locking changes to the tree structure, not to the references.85 * Inc() is expected to have its own locking.86 */87 void*88 lookupkey(Intmap *map, ulong id)89 {90 Intlist *f;91 void *v;93 rlock(&map->rwlock);94 if(f = *llookup(map, id)){95 v = f->aux;96 map->inc(v);97 }else98 v = nil;99 runlock(&map->rwlock);100 return v;101 }103 void*104 insertkey(Intmap *map, ulong id, void *v)105 {106 Intlist *f;107 void *ov;108 ulong h;110 wlock(&map->rwlock);111 if(f = *llookup(map, id)){112 /* no decrement for ov because we're returning it */113 ov = f->aux;114 f->aux = v;115 }else{116 f = emalloc9p(sizeof(*f));117 f->id = id;118 f->aux = v;119 h = hashid(id);120 f->link = map->hash[h];121 map->hash[h] = f;122 ov = nil;123 }124 wunlock(&map->rwlock);125 return ov;126 }128 int129 caninsertkey(Intmap *map, ulong id, void *v)130 {131 Intlist *f;132 int rv;133 ulong h;135 wlock(&map->rwlock);136 if(*llookup(map, id))137 rv = 0;138 else{139 f = emalloc9p(sizeof *f);140 f->id = id;141 f->aux = v;142 h = hashid(id);143 f->link = map->hash[h];144 map->hash[h] = f;145 rv = 1;146 }147 wunlock(&map->rwlock);148 return rv;149 }151 void*152 deletekey(Intmap *map, ulong id)153 {154 Intlist **lf, *f;155 void *ov;157 wlock(&map->rwlock);158 if(f = *(lf = llookup(map, id))){159 ov = f->aux;160 *lf = f->link;161 free(f);162 }else163 ov = nil;164 wunlock(&map->rwlock);165 return ov;166 }