1 #include <u.h>
2 #include <libc.h>
3 #include <fcall.h>
4 #include <thread.h>
5 #include <9p.h>
6 
7 enum {
8 	NHASH = 128
9 };
10 
11 typedef struct Intlist	Intlist;
12 struct Intlist
13 {
14 	ulong	id;
15 	void*	aux;
16 	Intlist*	link;
17 };
18 
19 struct Intmap
20 {
21 	RWLock	rwlock;
22 	Intlist*	hash[NHASH];
23 	void (*inc)(void*);
24 };
25 
26 static ulong
27 hashid(ulong id)
28 {
29 	return id%NHASH;
30 }
31 
32 static void
33 nop(void *v)
34 {
35 	USED(v);
36 }
37 
38 Intmap*
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
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**
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*
87 lookupkey(Intmap *map, ulong id)
88 {
89 	Intlist *f;
90 	void *v;
91 
92 	rlock(&map->rwlock);
93 	if(f = *llookup(map, id)){
94 		v = f->aux;
95 		map->inc(v);
96 	}else
97 		v = nil;
98 	runlock(&map->rwlock);
99 	return v;
100 }
101 
102 void*
103 insertkey(Intmap *map, ulong id, void *v)
104 {
105 	Intlist *f;
106 	void *ov;
107 	ulong h;
108 
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 }
126 
127 int
128 caninsertkey(Intmap *map, ulong id, void *v)
129 {
130 	Intlist *f;
131 	int rv;
132 	ulong h;
133 
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 }
149 
150 void*
151 deletekey(Intmap *map, ulong id)
152 {
153 	Intlist **lf, *f;
154 	void *ov;
155 
156 	wlock(&map->rwlock);
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->rwlock);
164 	return ov;
165 }