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>
  6 2277c5d7 2004-03-21 devnull 
  7 2277c5d7 2004-03-21 devnull enum {
  8 2277c5d7 2004-03-21 devnull 	NHASH = 128
  9 2277c5d7 2004-03-21 devnull };
 10 2277c5d7 2004-03-21 devnull 
 11 2277c5d7 2004-03-21 devnull typedef struct Intlist	Intlist;
 12 2277c5d7 2004-03-21 devnull struct Intlist
 13 2277c5d7 2004-03-21 devnull {
 14 2277c5d7 2004-03-21 devnull 	ulong	id;
 15 2277c5d7 2004-03-21 devnull 	void*	aux;
 16 2277c5d7 2004-03-21 devnull 	Intlist*	link;
 17 2277c5d7 2004-03-21 devnull };
 18 2277c5d7 2004-03-21 devnull 
 19 2277c5d7 2004-03-21 devnull struct Intmap
 20 2277c5d7 2004-03-21 devnull {
 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*);
 24 2277c5d7 2004-03-21 devnull };
 25 2277c5d7 2004-03-21 devnull 
 26 2277c5d7 2004-03-21 devnull static ulong
 27 2277c5d7 2004-03-21 devnull hashid(ulong id)
 28 2277c5d7 2004-03-21 devnull {
 29 2277c5d7 2004-03-21 devnull 	return id%NHASH;
 30 2277c5d7 2004-03-21 devnull }
 31 2277c5d7 2004-03-21 devnull 
 32 2277c5d7 2004-03-21 devnull static void
 33 2277c5d7 2004-03-21 devnull nop(void *v)
 34 2277c5d7 2004-03-21 devnull {
 35 2277c5d7 2004-03-21 devnull 	USED(v);
 36 2277c5d7 2004-03-21 devnull }
 37 2277c5d7 2004-03-21 devnull 
 38 2277c5d7 2004-03-21 devnull Intmap*
 39 2277c5d7 2004-03-21 devnull allocmap(void (*inc)(void*))
 40 2277c5d7 2004-03-21 devnull {
 41 2277c5d7 2004-03-21 devnull 	Intmap *m;
 42 2277c5d7 2004-03-21 devnull 
 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;
 48 2277c5d7 2004-03-21 devnull }
 49 2277c5d7 2004-03-21 devnull 
 50 2277c5d7 2004-03-21 devnull void
 51 2277c5d7 2004-03-21 devnull freemap(Intmap *map, void (*destroy)(void*))
 52 2277c5d7 2004-03-21 devnull {
 53 2277c5d7 2004-03-21 devnull 	int i;
 54 2277c5d7 2004-03-21 devnull 	Intlist *p, *nlink;
 55 2277c5d7 2004-03-21 devnull 
 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);
 62 2277c5d7 2004-03-21 devnull 			free(p);
 63 2277c5d7 2004-03-21 devnull 		}
 64 2277c5d7 2004-03-21 devnull 	}
 65 fa325e9b 2020-01-10 cross 
 66 2277c5d7 2004-03-21 devnull 	free(map);
 67 2277c5d7 2004-03-21 devnull }
 68 2277c5d7 2004-03-21 devnull 
 69 2277c5d7 2004-03-21 devnull static Intlist**
 70 2277c5d7 2004-03-21 devnull llookup(Intmap *map, ulong id)
 71 2277c5d7 2004-03-21 devnull {
 72 2277c5d7 2004-03-21 devnull 	Intlist **lf;
 73 2277c5d7 2004-03-21 devnull 
 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)
 76 2277c5d7 2004-03-21 devnull 			break;
 77 fa325e9b 2020-01-10 cross 	return lf;
 78 2277c5d7 2004-03-21 devnull }
 79 2277c5d7 2004-03-21 devnull 
 80 2277c5d7 2004-03-21 devnull /*
 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.
 85 2277c5d7 2004-03-21 devnull  */
 86 2277c5d7 2004-03-21 devnull void*
 87 2277c5d7 2004-03-21 devnull lookupkey(Intmap *map, ulong id)
 88 2277c5d7 2004-03-21 devnull {
 89 2277c5d7 2004-03-21 devnull 	Intlist *f;
 90 2277c5d7 2004-03-21 devnull 	void *v;
 91 2277c5d7 2004-03-21 devnull 
 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);
 96 2277c5d7 2004-03-21 devnull 	}else
 97 2277c5d7 2004-03-21 devnull 		v = nil;
 98 2277c5d7 2004-03-21 devnull 	runlock(&map->rwlock);
 99 2277c5d7 2004-03-21 devnull 	return v;
100 2277c5d7 2004-03-21 devnull }
101 2277c5d7 2004-03-21 devnull 
102 2277c5d7 2004-03-21 devnull void*
103 2277c5d7 2004-03-21 devnull insertkey(Intmap *map, ulong id, void *v)
104 2277c5d7 2004-03-21 devnull {
105 2277c5d7 2004-03-21 devnull 	Intlist *f;
106 2277c5d7 2004-03-21 devnull 	void *ov;
107 2277c5d7 2004-03-21 devnull 	ulong h;
108 2277c5d7 2004-03-21 devnull 
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;
114 2277c5d7 2004-03-21 devnull 	}else{
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;
122 2277c5d7 2004-03-21 devnull 	}
123 2277c5d7 2004-03-21 devnull 	wunlock(&map->rwlock);
124 fa325e9b 2020-01-10 cross 	return ov;
125 2277c5d7 2004-03-21 devnull }
126 2277c5d7 2004-03-21 devnull 
127 2277c5d7 2004-03-21 devnull int
128 2277c5d7 2004-03-21 devnull caninsertkey(Intmap *map, ulong id, void *v)
129 2277c5d7 2004-03-21 devnull {
130 2277c5d7 2004-03-21 devnull 	Intlist *f;
131 2277c5d7 2004-03-21 devnull 	int rv;
132 2277c5d7 2004-03-21 devnull 	ulong h;
133 2277c5d7 2004-03-21 devnull 
134 2277c5d7 2004-03-21 devnull 	wlock(&map->rwlock);
135 2277c5d7 2004-03-21 devnull 	if(*llookup(map, id))
136 2277c5d7 2004-03-21 devnull 		rv = 0;
137 2277c5d7 2004-03-21 devnull 	else{
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;
144 2277c5d7 2004-03-21 devnull 		rv = 1;
145 2277c5d7 2004-03-21 devnull 	}
146 2277c5d7 2004-03-21 devnull 	wunlock(&map->rwlock);
147 fa325e9b 2020-01-10 cross 	return rv;
148 2277c5d7 2004-03-21 devnull }
149 2277c5d7 2004-03-21 devnull 
150 2277c5d7 2004-03-21 devnull void*
151 2277c5d7 2004-03-21 devnull deletekey(Intmap *map, ulong id)
152 2277c5d7 2004-03-21 devnull {
153 2277c5d7 2004-03-21 devnull 	Intlist **lf, *f;
154 2277c5d7 2004-03-21 devnull 	void *ov;
155 2277c5d7 2004-03-21 devnull 
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);
161 2277c5d7 2004-03-21 devnull 	}else
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;
165 2277c5d7 2004-03-21 devnull }