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 <fcall.h>
4 2277c5d7 2004-03-21 devnull #include <thread.h>
5 2277c5d7 2004-03-21 devnull #include <9p.h>
8 2277c5d7 2004-03-21 devnull NHASH = 128
11 2277c5d7 2004-03-21 devnull typedef struct Intlist Intlist;
12 2277c5d7 2004-03-21 devnull struct Intlist
14 2277c5d7 2004-03-21 devnull ulong id;
15 2277c5d7 2004-03-21 devnull void* aux;
16 2277c5d7 2004-03-21 devnull Intlist* link;
19 2277c5d7 2004-03-21 devnull struct Intmap
21 2277c5d7 2004-03-21 devnull RWLock rwlock;
22 2277c5d7 2004-03-21 devnull Intlist* hash[NHASH];
23 2277c5d7 2004-03-21 devnull void (*inc)(void*);
26 2277c5d7 2004-03-21 devnull static ulong
27 2277c5d7 2004-03-21 devnull hashid(ulong id)
29 2277c5d7 2004-03-21 devnull return id%NHASH;
32 2277c5d7 2004-03-21 devnull static void
33 2277c5d7 2004-03-21 devnull nop(void *v)
39 2277c5d7 2004-03-21 devnull allocmap(void (*inc)(void*))
41 2277c5d7 2004-03-21 devnull Intmap *m;
43 2277c5d7 2004-03-21 devnull m = emalloc9p(sizeof(*m));
44 2277c5d7 2004-03-21 devnull if(inc == nil)
45 2277c5d7 2004-03-21 devnull inc = nop;
46 2277c5d7 2004-03-21 devnull m->inc = inc;
47 2277c5d7 2004-03-21 devnull return m;
51 2277c5d7 2004-03-21 devnull freemap(Intmap *map, void (*destroy)(void*))
54 2277c5d7 2004-03-21 devnull Intlist *p, *nlink;
56 2277c5d7 2004-03-21 devnull if(destroy == nil)
57 2277c5d7 2004-03-21 devnull destroy = nop;
58 2277c5d7 2004-03-21 devnull for(i=0; i<NHASH; i++){
59 2277c5d7 2004-03-21 devnull for(p=map->hash[i]; p; p=nlink){
60 2277c5d7 2004-03-21 devnull nlink = p->link;
61 2277c5d7 2004-03-21 devnull destroy(p->aux);
66 2277c5d7 2004-03-21 devnull free(map);
69 2277c5d7 2004-03-21 devnull static Intlist**
70 2277c5d7 2004-03-21 devnull llookup(Intmap *map, ulong id)
72 2277c5d7 2004-03-21 devnull Intlist **lf;
74 2277c5d7 2004-03-21 devnull for(lf=&map->hash[hashid(id)]; *lf; lf=&(*lf)->link)
75 2277c5d7 2004-03-21 devnull if((*lf)->id == id)
77 2277c5d7 2004-03-21 devnull return lf;
81 2277c5d7 2004-03-21 devnull * The RWlock is used as expected except that we allow
82 2277c5d7 2004-03-21 devnull * inc() to be called while holding it. This is because we're
83 2277c5d7 2004-03-21 devnull * locking changes to the tree structure, not to the references.
84 2277c5d7 2004-03-21 devnull * Inc() is expected to have its own locking.
87 2277c5d7 2004-03-21 devnull lookupkey(Intmap *map, ulong id)
89 2277c5d7 2004-03-21 devnull Intlist *f;
92 2277c5d7 2004-03-21 devnull rlock(&map->rwlock);
93 2277c5d7 2004-03-21 devnull if(f = *llookup(map, id)){
94 2277c5d7 2004-03-21 devnull v = f->aux;
95 2277c5d7 2004-03-21 devnull map->inc(v);
98 2277c5d7 2004-03-21 devnull runlock(&map->rwlock);
99 2277c5d7 2004-03-21 devnull return v;
103 2277c5d7 2004-03-21 devnull insertkey(Intmap *map, ulong id, void *v)
105 2277c5d7 2004-03-21 devnull Intlist *f;
106 2277c5d7 2004-03-21 devnull void *ov;
107 2277c5d7 2004-03-21 devnull ulong h;
109 2277c5d7 2004-03-21 devnull wlock(&map->rwlock);
110 2277c5d7 2004-03-21 devnull if(f = *llookup(map, id)){
111 2277c5d7 2004-03-21 devnull /* no decrement for ov because we're returning it */
112 2277c5d7 2004-03-21 devnull ov = f->aux;
113 2277c5d7 2004-03-21 devnull f->aux = v;
115 2277c5d7 2004-03-21 devnull f = emalloc9p(sizeof(*f));
116 2277c5d7 2004-03-21 devnull f->id = id;
117 2277c5d7 2004-03-21 devnull f->aux = v;
118 2277c5d7 2004-03-21 devnull h = hashid(id);
119 2277c5d7 2004-03-21 devnull f->link = map->hash[h];
120 2277c5d7 2004-03-21 devnull map->hash[h] = f;
121 2277c5d7 2004-03-21 devnull ov = nil;
123 2277c5d7 2004-03-21 devnull wunlock(&map->rwlock);
124 2277c5d7 2004-03-21 devnull return ov;
128 2277c5d7 2004-03-21 devnull caninsertkey(Intmap *map, ulong id, void *v)
130 2277c5d7 2004-03-21 devnull Intlist *f;
132 2277c5d7 2004-03-21 devnull ulong h;
134 2277c5d7 2004-03-21 devnull wlock(&map->rwlock);
135 2277c5d7 2004-03-21 devnull if(*llookup(map, id))
138 2277c5d7 2004-03-21 devnull f = emalloc9p(sizeof *f);
139 2277c5d7 2004-03-21 devnull f->id = id;
140 2277c5d7 2004-03-21 devnull f->aux = v;
141 2277c5d7 2004-03-21 devnull h = hashid(id);
142 2277c5d7 2004-03-21 devnull f->link = map->hash[h];
143 2277c5d7 2004-03-21 devnull map->hash[h] = f;
146 2277c5d7 2004-03-21 devnull wunlock(&map->rwlock);
147 2277c5d7 2004-03-21 devnull return rv;
151 2277c5d7 2004-03-21 devnull deletekey(Intmap *map, ulong id)
153 2277c5d7 2004-03-21 devnull Intlist **lf, *f;
154 2277c5d7 2004-03-21 devnull void *ov;
156 2277c5d7 2004-03-21 devnull wlock(&map->rwlock);
157 2277c5d7 2004-03-21 devnull if(f = *(lf = llookup(map, id))){
158 2277c5d7 2004-03-21 devnull ov = f->aux;
159 2277c5d7 2004-03-21 devnull *lf = f->link;
160 2277c5d7 2004-03-21 devnull free(f);
162 2277c5d7 2004-03-21 devnull ov = nil;
163 2277c5d7 2004-03-21 devnull wunlock(&map->rwlock);
164 2277c5d7 2004-03-21 devnull return ov;