sys/src/lib9p/intmap.c

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