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