1 2277c5d7 2004-03-21 devnull #include <u.h>
2 2277c5d7 2004-03-21 devnull #include <libc.h>
3 2277c5d7 2004-03-21 devnull #include <auth.h>
4 2277c5d7 2004-03-21 devnull #include <fcall.h>
5 2277c5d7 2004-03-21 devnull #include <thread.h>
6 2277c5d7 2004-03-21 devnull #include <9p.h>
9 2277c5d7 2004-03-21 devnull NHASH = 128
12 2277c5d7 2004-03-21 devnull typedef struct Intlist Intlist;
13 2277c5d7 2004-03-21 devnull struct Intlist
15 2277c5d7 2004-03-21 devnull ulong id;
16 2277c5d7 2004-03-21 devnull void* aux;
17 2277c5d7 2004-03-21 devnull Intlist* link;
20 2277c5d7 2004-03-21 devnull struct Intmap
22 2277c5d7 2004-03-21 devnull RWLock rwlock;
23 2277c5d7 2004-03-21 devnull Intlist* hash[NHASH];
24 2277c5d7 2004-03-21 devnull void (*inc)(void*);
27 2277c5d7 2004-03-21 devnull static ulong
28 2277c5d7 2004-03-21 devnull hashid(ulong id)
30 2277c5d7 2004-03-21 devnull return id%NHASH;
33 2277c5d7 2004-03-21 devnull static void
34 2277c5d7 2004-03-21 devnull nop(void *v)
40 2277c5d7 2004-03-21 devnull allocmap(void (*inc)(void*))
42 2277c5d7 2004-03-21 devnull Intmap *m;
44 2277c5d7 2004-03-21 devnull m = emalloc9p(sizeof(*m));
45 2277c5d7 2004-03-21 devnull if(inc == nil)
46 2277c5d7 2004-03-21 devnull inc = nop;
47 2277c5d7 2004-03-21 devnull m->inc = inc;
48 2277c5d7 2004-03-21 devnull return m;
52 2277c5d7 2004-03-21 devnull freemap(Intmap *map, void (*destroy)(void*))
55 2277c5d7 2004-03-21 devnull Intlist *p, *nlink;
57 2277c5d7 2004-03-21 devnull if(destroy == nil)
58 2277c5d7 2004-03-21 devnull destroy = nop;
59 2277c5d7 2004-03-21 devnull for(i=0; i<NHASH; i++){
60 2277c5d7 2004-03-21 devnull for(p=map->hash[i]; p; p=nlink){
61 2277c5d7 2004-03-21 devnull nlink = p->link;
62 2277c5d7 2004-03-21 devnull destroy(p->aux);
67 2277c5d7 2004-03-21 devnull free(map);
70 2277c5d7 2004-03-21 devnull static Intlist**
71 2277c5d7 2004-03-21 devnull llookup(Intmap *map, ulong id)
73 2277c5d7 2004-03-21 devnull Intlist **lf;
75 2277c5d7 2004-03-21 devnull for(lf=&map->hash[hashid(id)]; *lf; lf=&(*lf)->link)
76 2277c5d7 2004-03-21 devnull if((*lf)->id == id)
78 2277c5d7 2004-03-21 devnull return lf;
82 2277c5d7 2004-03-21 devnull * The RWlock is used as expected except that we allow
83 2277c5d7 2004-03-21 devnull * inc() to be called while holding it. This is because we're
84 2277c5d7 2004-03-21 devnull * locking changes to the tree structure, not to the references.
85 2277c5d7 2004-03-21 devnull * Inc() is expected to have its own locking.
88 2277c5d7 2004-03-21 devnull lookupkey(Intmap *map, ulong id)
90 2277c5d7 2004-03-21 devnull Intlist *f;
93 2277c5d7 2004-03-21 devnull rlock(&map->rwlock);
94 2277c5d7 2004-03-21 devnull if(f = *llookup(map, id)){
95 2277c5d7 2004-03-21 devnull v = f->aux;
96 2277c5d7 2004-03-21 devnull map->inc(v);
99 2277c5d7 2004-03-21 devnull runlock(&map->rwlock);
100 2277c5d7 2004-03-21 devnull return v;
104 2277c5d7 2004-03-21 devnull insertkey(Intmap *map, ulong id, void *v)
106 2277c5d7 2004-03-21 devnull Intlist *f;
107 2277c5d7 2004-03-21 devnull void *ov;
108 2277c5d7 2004-03-21 devnull ulong h;
110 2277c5d7 2004-03-21 devnull wlock(&map->rwlock);
111 2277c5d7 2004-03-21 devnull if(f = *llookup(map, id)){
112 2277c5d7 2004-03-21 devnull /* no decrement for ov because we're returning it */
113 2277c5d7 2004-03-21 devnull ov = f->aux;
114 2277c5d7 2004-03-21 devnull f->aux = v;
116 2277c5d7 2004-03-21 devnull f = emalloc9p(sizeof(*f));
117 2277c5d7 2004-03-21 devnull f->id = id;
118 2277c5d7 2004-03-21 devnull f->aux = v;
119 2277c5d7 2004-03-21 devnull h = hashid(id);
120 2277c5d7 2004-03-21 devnull f->link = map->hash[h];
121 2277c5d7 2004-03-21 devnull map->hash[h] = f;
122 2277c5d7 2004-03-21 devnull ov = nil;
124 2277c5d7 2004-03-21 devnull wunlock(&map->rwlock);
125 2277c5d7 2004-03-21 devnull return ov;
129 2277c5d7 2004-03-21 devnull caninsertkey(Intmap *map, ulong id, void *v)
131 2277c5d7 2004-03-21 devnull Intlist *f;
133 2277c5d7 2004-03-21 devnull ulong h;
135 2277c5d7 2004-03-21 devnull wlock(&map->rwlock);
136 2277c5d7 2004-03-21 devnull if(*llookup(map, id))
139 2277c5d7 2004-03-21 devnull f = emalloc9p(sizeof *f);
140 2277c5d7 2004-03-21 devnull f->id = id;
141 2277c5d7 2004-03-21 devnull f->aux = v;
142 2277c5d7 2004-03-21 devnull h = hashid(id);
143 2277c5d7 2004-03-21 devnull f->link = map->hash[h];
144 2277c5d7 2004-03-21 devnull map->hash[h] = f;
147 2277c5d7 2004-03-21 devnull wunlock(&map->rwlock);
148 2277c5d7 2004-03-21 devnull return rv;
152 2277c5d7 2004-03-21 devnull deletekey(Intmap *map, ulong id)
154 2277c5d7 2004-03-21 devnull Intlist **lf, *f;
155 2277c5d7 2004-03-21 devnull void *ov;
157 2277c5d7 2004-03-21 devnull wlock(&map->rwlock);
158 2277c5d7 2004-03-21 devnull if(f = *(lf = llookup(map, id))){
159 2277c5d7 2004-03-21 devnull ov = f->aux;
160 2277c5d7 2004-03-21 devnull *lf = f->link;
161 2277c5d7 2004-03-21 devnull free(f);
163 2277c5d7 2004-03-21 devnull ov = nil;
164 2277c5d7 2004-03-21 devnull wunlock(&map->rwlock);
165 2277c5d7 2004-03-21 devnull return ov;