1 #include <u.h>
2 #include <libc.h>
3 #include <auth.h>
4 #include <fcall.h>
5 #include <thread.h>
6 #include <9p.h>
7
8 enum {
9 NHASH = 128
10 };
11
12 typedef struct Intlist Intlist;
13 struct Intlist
14 {
15 ulong id;
16 void* aux;
17 Intlist* link;
18 };
19
20 struct Intmap
21 {
22 RWLock;
23 Intlist* hash[NHASH];
24 void (*inc)(void*);
25 };
26
27 static ulong
hashid(ulong id)28 hashid(ulong id)
29 {
30 return id%NHASH;
31 }
32
33 static void
nop(void *)34 nop(void*)
35 {
36 }
37
38 Intmap*
allocmap(void (* inc)(void *))39 allocmap(void (*inc)(void*))
40 {
41 Intmap *m;
42
43 m = emalloc9p(sizeof(*m));
44 if(inc == nil)
45 inc = nop;
46 m->inc = inc;
47 return m;
48 }
49
50 void
freemap(Intmap * map,void (* destroy)(void *))51 freemap(Intmap *map, void (*destroy)(void*))
52 {
53 int i;
54 Intlist *p, *nlink;
55
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 }
65
66 free(map);
67 }
68
69 static Intlist**
llookup(Intmap * map,ulong id)70 llookup(Intmap *map, ulong id)
71 {
72 Intlist **lf;
73
74 for(lf=&map->hash[hashid(id)]; *lf; lf=&(*lf)->link)
75 if((*lf)->id == id)
76 break;
77 return lf;
78 }
79
80 /*
81 * The RWlock is used as expected except that we allow
82 * inc() to be called while holding it. This is because we're
83 * locking changes to the tree structure, not to the references.
84 * Inc() is expected to have its own locking.
85 */
86 void*
lookupkey(Intmap * map,ulong id)87 lookupkey(Intmap *map, ulong id)
88 {
89 Intlist *f;
90 void *v;
91
92 rlock(map);
93 if(f = *llookup(map, id)){
94 v = f->aux;
95 map->inc(v);
96 }else
97 v = nil;
98 runlock(map);
99 return v;
100 }
101
102 void*
insertkey(Intmap * map,ulong id,void * v)103 insertkey(Intmap *map, ulong id, void *v)
104 {
105 Intlist *f;
106 void *ov;
107 ulong h;
108
109 wlock(map);
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);
124 return ov;
125 }
126
127 int
caninsertkey(Intmap * map,ulong id,void * v)128 caninsertkey(Intmap *map, ulong id, void *v)
129 {
130 Intlist *f;
131 int rv;
132 ulong h;
133
134 wlock(map);
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);
147 return rv;
148 }
149
150 void*
deletekey(Intmap * map,ulong id)151 deletekey(Intmap *map, ulong id)
152 {
153 Intlist **lf, *f;
154 void *ov;
155
156 wlock(map);
157 if(f = *(lf = llookup(map, id))){
158 ov = f->aux;
159 *lf = f->link;
160 free(f);
161 }else
162 ov = nil;
163 wunlock(map);
164 return ov;
165 }
166