libmixp/intmap.c

   1 /* This file is derived from src/lib9p/intmap.c from plan9port */
   2 /* See LICENCE.p9p for terms of use */
   3
   4 #include <stdlib.h>
   5 #include <stdio.h>
   6 #include <string.h>
   7 #include <9p-mixp/intmap.h>
   8
   9 #include "mixp_local.h"
  10 #include "util.h"
  11
  12 struct Intlist {
  13         unsigned long           id;
  14         void*           aux;
  15         Intlist*        link;
  16         int             magic;
  17 };
  18
  19 static unsigned long
  20 hashid(MIXP_INTMAP *map, unsigned long id) {
  21         return id%map->nhash;
  22 }
  23
  24 static void
  25 nop(void *v) {
  26         USED(v);
  27 }
  28
  29 void mixp_intmap_init(MIXP_INTMAP *m, unsigned long nhash, void *hash, const char* name)
  30 {
  31         m->nhash = nhash;
  32         m->hash = hash;
  33         m->name = name;
  34         memset(hash,0,sizeof(void*)*nhash);
  35         mixp_thread->initrwlock(&m->lk);
  36 }
  37
  38 void mixp_intmap_free(MIXP_INTMAP *map, void (*destroy)(void*))
  39 {
  40         int i;
  41         Intlist *p, *nlink;
  42
  43         if(destroy == NULL)
  44                 destroy = nop;
  45         for(i=0; i<map->nhash; i++)
  46         {
  47                 for(p=map->hash[i]; p; p=nlink)
  48                 {
  49                         nlink = p->link;
  50                         destroy(p->aux);
  51                         MIXP_FREE(p);
  52                 }
  53         }
  54
  55         mixp_thread->rwdestroy(&map->lk);
  56 }
  57
  58 void mixp_intmap_exec(MIXP_INTMAP *map, void (*run)(void*))
  59 {
  60         int i;
  61         Intlist *p, *nlink;
  62
  63         mixp_thread->rlock(&map->lk);
  64         for(i=0; i<map->nhash; i++)
  65         {
  66                 for(p=map->hash[i]; p; p=nlink)
  67                 {
  68                         mixp_thread->runlock(&map->lk);
  69                         nlink = p->link;
  70 //                      printf("execmap: [%s] hid=%d id=%d aux=%ld\n", map->name, i, p->id, p->aux);
  71                         run(p->aux);
  72                         mixp_thread->rlock(&map->lk);
  73                 }
  74         }
  75         mixp_thread->runlock(&map->lk);
  76 }
  77
  78 static void * __real_lookupkey(MIXP_INTMAP* map, unsigned long id)
  79 {
  80         int hid=hashid(map,id);
  81
  82         Intlist * elem = map->hash[hid];
  83         while (elem)
  84         {
  85                 if (elem->id == id)
  86                         return elem->aux;
  87                 elem = elem->link;
  88         }
  89
  90         return NULL;
  91 }
  92
  93 void * mixp_intmap_lookupkey(MIXP_INTMAP *map, unsigned long id)
  94 {
  95         void *v;
  96
  97 //      printf("mixp_intmap_lookupkey [%s] id=%d\n", map->name, id);
  98         mixp_thread->rlock(&map->lk);
  99         v = __real_lookupkey(map,id);
 100         mixp_thread->runlock(&map->lk);
 101         return v;
 102 }
 103
 104 static void * __real_insertkey(MIXP_INTMAP* map, unsigned long id, void* value)
 105 {
 106         int hid = hashid(map,id);
 107         void* ov = NULL;
 108         Intlist* elem = map->hash[hid];
 109
 110         while (elem)
 111         {
 112                 if (elem->id==id)
 113                 {
 114 //                      printf("insertkey [%s] updating id=%d addr=%ld value=%ld\n", map->name, id, elem, value);
 115                         ov = elem->aux;
 116                         elem->aux=value;
 117                         return ov;
 118                 }
 119         }
 120
 121         elem = calloc(1,sizeof(Intlist));
 122         elem->id   = id;
 123         elem->aux  = value;
 124         elem->link = map->hash[hid];
 125         elem->magic = 666777;
 126         map->hash[hid] = elem;
 127
 128 //      printf("insertkey() [%s] added elem: id=%d addr=%ld value=%ld next=%ld\n",
 129 //          map->name, id, elem, value, elem->link);
 130         return NULL;
 131 }
 132
 133 void * mixp_intmap_insertkey(MIXP_INTMAP *map, unsigned long id, void* value)
 134 {
 135 //      printf("insertkey [%s] id=%d value=%ld\n", map->name, id, value);
 136
 137         void* ov;
 138         mixp_thread->wlock(&map->lk);
 139         ov = __real_insertkey(map, id, value);
 140         mixp_thread->wunlock(&map->lk);
 141         return ov;
 142 }
 143
 144 static int __real_caninsertkey(MIXP_INTMAP* map, unsigned long id, void* value)
 145 {
 146         int hid = hashid(map,id);
 147         Intlist* elem=map->hash[hid];
 148
 149         while(elem)
 150         {
 151                 if (elem->id==id)
 152                         return 0;
 153                 elem = elem->link;
 154         }
 155
 156         elem = calloc(1,sizeof(Intlist));
 157         elem->id       = id;
 158         elem->aux      = value;
 159         elem->link     = map->hash[hid];
 160         elem->magic    = 777666;
 161         map->hash[hid] = elem;
 162
 163 //      printf("caninsertkey [%s] added: id=%d elem=%ld nextelem=%ld nn=%ld\n", map->name, id, elem, elem->link,map->hash[hid]->link);
 164         return 1;
 165 }
 166
 167 int mixp_intmap_caninsertkey(MIXP_INTMAP *map, unsigned long id, void *v)
 168 {
 169         mixp_thread->wlock(&map->lk);
 170         int rv = __real_caninsertkey(map,id,v);
 171         mixp_thread->wunlock(&map->lk);
 172         return rv;
 173 }
 174
 175 static void* __real_deletekey(MIXP_INTMAP* map, unsigned long id)
 176 {
 177         void *ov = NULL;
 178         Intlist* elem;
 179
 180         int hid = hashid(map,id);
 181
 182         if (!(elem = map->hash[hid]))
 183         {
 184 //              printf("branch %d not existing. nothing to do\n",hid);
 185                 return NULL;
 186         }
 187
 188         if (elem->id == id)
 189         {
 190                 /* the first in line is our element */
 191                 ov = elem->aux;
 192 //              printf("deletekey [%s] hid=%d id=%d\n", map->name, hid, id);
 193 //              printf("  -> deleting first in line: %ld (magic %d). next is: %ld\n", elem, elem->magic, elem->link);
 194                 map->hash[hid] = elem->link;
 195                 elem->aux = NULL;
 196                 MIXP_FREE(elem);
 197 //              printf(" --> now first: %ld\n", map->hash[hid]);
 198                 return ov;
 199         }
 200
 201 //      printf("deletekey [%s] id=%d hid=%d firstelem=%ld magic=%d\n", map->name,id,hid,elem, elem->magic);
 202
 203         Intlist *next;
 204         while ((next = elem->link))
 205         {
 206 //              printf("trying next: %ld\n", next);
 207 //              printf(" -> next->id=%d\n", next->id);
 208
 209                 /* found it somewhere later in line */
 210                 if (next->id == id)
 211                 {
 212                         ov = next->aux;
 213                         elem->link = next->link;
 214 //                      printf("deleting somewhere. next is %ld\n", next->link);
 215                         next->aux = NULL;
 216                         MIXP_FREE(next);
 217                 }
 218         }
 219         return ov;
 220 }
 221
 222 void* mixp_intmap_deletekey(MIXP_INTMAP *map, unsigned long id)
 223 {
 224         void* ov;
 225         mixp_thread->wlock(&map->lk);
 226         ov = __real_deletekey(map,id);
 227         mixp_thread->wunlock(&map->lk);
 228         return ov;
 229 }