plan9port

fork of plan9port with libvec, libstr and libsdb
Log | Files | Refs | README | LICENSE

intmap.c (2322B)

      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 }