sys/src/lib9p/intmap.c

   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 = 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);
  93         if(f = *llookup(map, id)){
  94                 v = f->aux;
  95                 map->inc(v);
  96         }else
  97                 v = nil;
  98         runlock(map);
  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);
 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);
 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);
 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);
 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);
 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);
 164         return ov;
 165 }