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	rwlock;
23 	Intlist*	hash[NHASH];
24 	void (*inc)(void*);
25 };
26 
27 static ulong
28 hashid(ulong id)
29 {
30 	return id%NHASH;
31 }
32 
33 static void
34 nop(void *v)
35 {
36 	USED(v);
37 }
38 
39 Intmap*
40 allocmap(void (*inc)(void*))
41 {
42 	Intmap *m;
43 
44 	m = emalloc9p(sizeof(*m));
45 	if(inc == nil)
46 		inc = nop;
47 	m->inc = inc;
48 	return m;
49 }
50 
51 void
52 freemap(Intmap *map, void (*destroy)(void*))
53 {
54 	int i;
55 	Intlist *p, *nlink;
56 
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 	}
66 			
67 	free(map);
68 }
69 
70 static Intlist**
71 llookup(Intmap *map, ulong id)
72 {
73 	Intlist **lf;
74 
75 	for(lf=&map->hash[hashid(id)]; *lf; lf=&(*lf)->link)
76 		if((*lf)->id == id)
77 			break;
78 	return lf;	
79 }
80 
81 /*
82  * The RWlock is used as expected except that we allow
83  * inc() to be called while holding it.  This is because we're
84  * 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;
92 
93 	rlock(&map->rwlock);
94 	if(f = *llookup(map, id)){
95 		v = f->aux;
96 		map->inc(v);
97 	}else
98 		v = nil;
99 	runlock(&map->rwlock);
100 	return v;
101 }
102 
103 void*
104 insertkey(Intmap *map, ulong id, void *v)
105 {
106 	Intlist *f;
107 	void *ov;
108 	ulong h;
109 
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 }
127 
128 int
129 caninsertkey(Intmap *map, ulong id, void *v)
130 {
131 	Intlist *f;
132 	int rv;
133 	ulong h;
134 
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 }
150 
151 void*
152 deletekey(Intmap *map, ulong id)
153 {
154 	Intlist **lf, *f;
155 	void *ov;
156 
157 	wlock(&map->rwlock);
158 	if(f = *(lf = llookup(map, id))){
159 		ov = f->aux;
160 		*lf = f->link;
161 		free(f);
162 	}else
163 		ov = nil;
164 	wunlock(&map->rwlock);
165 	return ov;
166 }