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; 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*) 35 { 36 } 37 38 Intmap* 39 allocmap(void (*inc)(void*)) 40 { 41 Intmap *m; 42 43 m = mallocz(sizeof(Intmap), 1); 44 if(inc == nil) 45 inc = nop; 46 m->inc = inc; 47 return m; 48 } 49 50 void 51 freemap(Intmap *map) 52 { 53 free(map); 54 } 55 56 static Intlist** 57 llookup(Intmap *map, ulong id) 58 { 59 Intlist **lf; 60 61 for(lf=&map->hash[hashid(id)]; *lf; lf=&(*lf)->link) 62 if((*lf)->id == id) 63 break; 64 return lf; 65 } 66 67 /* 68 * The RWlock is used as expected except that we allow 69 * inc() to be called while holding it. This is because we're 70 * locking changes to the tree structure, not to the references. 71 * Inc() is expected to have its own locking. 72 */ 73 void* 74 lookupkey(Intmap *map, ulong id) 75 { 76 Intlist *f; 77 void *v; 78 79 rlock(map); 80 if(f = *llookup(map, id)){ 81 v = f->aux; 82 map->inc(v); 83 }else 84 v = nil; 85 runlock(map); 86 return v; 87 } 88 89 void* 90 insertkey(Intmap *map, ulong id, void *v) 91 { 92 Intlist *f; 93 void *ov; 94 ulong h; 95 96 wlock(map); 97 if(f = *llookup(map, id)){ 98 /* no decrement for ov because we're returning it */ 99 ov = f->aux; 100 map->inc(v); 101 f->aux = v; 102 }else if((f = mallocz(sizeof *f, 1)) == nil) 103 ov = nil; 104 else{ 105 f->id = id; 106 map->inc(v); 107 f->aux = v; 108 h = hashid(id); 109 f->link = map->hash[h]; 110 map->hash[h] = f; 111 ov = nil; 112 } 113 wunlock(map); 114 return ov; 115 } 116 117 int 118 caninsertkey(Intmap *map, ulong id, void *v) 119 { 120 Intlist *f; 121 int rv; 122 ulong h; 123 124 wlock(map); 125 if(*llookup(map, id)) 126 rv = 0; 127 else if((f = mallocz(sizeof *f, 1)) == nil) 128 rv = 0; 129 else{ 130 f->id = id; 131 map->inc(v); 132 f->aux = v; 133 h = hashid(id); 134 f->link = map->hash[h]; 135 map->hash[h] = f; 136 rv = 1; 137 } 138 wunlock(map); 139 return rv; 140 } 141 142 void* 143 deletekey(Intmap *map, ulong id) 144 { 145 Intlist **lf, *f; 146 void *ov; 147 148 wlock(map); 149 if(f = *(lf = llookup(map, id))){ 150 /* no decrement because we're returning it */ 151 ov = f->aux; 152 *lf = f->link; 153 free(f); 154 } 155 else 156 ov = nil; 157 wunlock(map); 158 return ov; 159 } 160