rlib/rmap.c

   1 /*
   2  *  Regular Pattern Analyzer (RPA)
   3  *  Copyright (c) 2009-2010 Martin Stoilov
   4  *
   5  *  This program is free software: you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation, either version 3 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  *
  18  *  Martin Stoilov <martin@rpasearch.com>
  19  */
  20
  21 #include "rtypes.h"
  22 #include "rlib/rmap.h"
  23 #include "rlib/rstring.h"
  24 #include "rlib/rmem.h"
  25
  26
  27 typedef struct r_mapnode_s {
  28         rlink_t active;
  29         rlink_t hash;
  30         rsize_t index;
  31         long nbucket;
  32         rstring_t *key;
  33         union {
  34                 rpointer p;
  35                 char data[0];
  36         } value;
  37 } r_mapnode_t;
  38
  39
  40 static rboolean r_map_rstrequal(rstr_t *key1, rstr_t *key2)
  41 {
  42         return (key1->size == key2->size && r_strncmp((const char*)key1->str, (const char*)key2->str, key1->size) == 0) ? TRUE : FALSE;
  43 }
  44
  45
  46 static unsigned long r_map_rstrhash(const rstr_t *key)
  47 {
  48         const char *str = (const char*) key->str;
  49         unsigned long i;
  50         unsigned long size = key->size;
  51         unsigned long hash = 0;
  52
  53         for (i = 0; i < size; i++, str++) {
  54                 hash = *str + (hash << 6) + (hash << 16) - hash;
  55         }
  56         return hash;
  57 }
  58
  59 void r_mapnode_init(r_mapnode_t *node, const char *key, rsize_t size)
  60 {
  61 //      node->key = r_rstrdup(key, size);
  62         node->key = r_string_create_strsize(key, size);
  63         r_list_init(&node->active);
  64         r_list_init(&node->hash);
  65 }
  66
  67
  68 r_mapnode_t *r_map_getfreenode(rmap_t *map, const char *key, rsize_t size)
  69 {
  70         r_mapnode_t *node = NULL;
  71
  72         if (r_list_empty(&map->inactive)) {
  73                 long index = r_carray_add(map->data, NULL);
  74                 node = (r_mapnode_t*)r_carray_slot(map->data, index);
  75                 r_mapnode_init(node, key, size);
  76                 node->index = index;
  77         } else {
  78                 node = r_list_entry(r_list_first(&map->inactive), r_mapnode_t, active);
  79                 r_list_del(&node->active);
  80                 r_mapnode_init(node, key, size);
  81         }
  82         return node;
  83 }
  84
  85
  86 robject_t *r_map_copy(const robject_t *obj)
  87 {
  88         return (robject_t*)NULL;
  89 }
  90
  91
  92 void r_map_cleanup(robject_t *obj)
  93 {
  94         r_mapnode_t *node;
  95         rmap_t *map = (rmap_t*)obj;
  96
  97         while (!r_list_empty(&map->active)) {
  98                 node = r_list_entry(r_list_first(&map->active), r_mapnode_t, active);
  99                 if (!r_object_gcget((robject_t*)node->key))
 100                         r_string_destroy(node->key);
 101                 r_list_del(&node->active);
 102         }
 103         while (!r_list_empty(&map->inactive)) {
 104                 node = r_list_entry(r_list_first(&map->inactive), r_mapnode_t, active);
 105                 if (!r_object_gcget((robject_t*)node->key))
 106                         r_string_destroy(node->key);
 107                 r_list_del(&node->active);
 108         }
 109
 110         r_carray_destroy(map->data);
 111         r_free(map->hash);
 112         r_object_cleanup(&map->obj);
 113 }
 114
 115
 116 robject_t *r_map_init(robject_t *obj, ruint32 type, r_object_cleanupfun cleanup, r_object_copyfun copy, unsigned int elt_size, unsigned int nbits)
 117 {
 118         rsize_t elt_realsize = R_SIZE_ALIGN(elt_size + sizeof(r_mapnode_t), sizeof(ruword));
 119         rsize_t hashsize, i;
 120         rmap_t *map = (rmap_t*)obj;
 121         if (nbits == 0 || nbits > 16) {
 122                 R_ASSERT(0);
 123                 return NULL;
 124         }
 125         r_object_init(obj, type, cleanup, copy);
 126         map->data = r_carray_create(elt_realsize);
 127         map->nbits = nbits;
 128         map->elt_size = elt_size;
 129         r_list_init(&map->active);
 130         r_list_init(&map->inactive);
 131         hashsize = r_map_hashsize(map);
 132         map->hash = (rlist_t*)r_malloc(sizeof(rlist_t) * hashsize);
 133         R_ASSERT(map->hash);
 134         for (i = 0; i < hashsize; i++) {
 135                 r_list_init(&map->hash[i]);
 136         }
 137
 138         return obj;
 139 }
 140
 141 rmap_t *r_map_create(unsigned int elt_size, unsigned int nbits)
 142 {
 143         rmap_t *map;
 144         map = (rmap_t*)r_object_create(sizeof(*map));
 145         r_map_init((robject_t*)map, R_OBJECT_MAP, r_map_cleanup, r_map_copy, elt_size, nbits);
 146         return map;
 147
 148 }
 149
 150
 151 void r_map_destroy(rmap_t *map)
 152 {
 153         r_object_destroy((robject_t*)map);
 154 }
 155
 156
 157 long r_map_gckey_add(rmap_t *map, rgc_t* gc, const char *name, rsize_t namesize, rconstpointer pval)
 158 {
 159         r_mapnode_t *node;
 160
 161         node = r_map_getfreenode(map, name, namesize);
 162         if (pval)
 163                 r_memcpy(node->value.data, pval, map->elt_size);
 164         node->nbucket = (r_map_rstrhash(R_STRING2RSTR(node->key)) & r_map_hashmask(map));
 165         r_list_addt(&map->hash[node->nbucket], &node->hash);
 166         r_list_addt(&map->active, &node->active);
 167         if (gc)
 168                 r_gc_add(gc, (robject_t*)node->key);
 169         return node->index;
 170 }
 171
 172
 173 long r_map_gckey_add_s(rmap_t *map, rgc_t* gc, const char *name, rconstpointer pval)
 174 {
 175         return r_map_gckey_add(map, gc, name, r_strlen(name), pval);
 176 }
 177
 178
 179 long r_map_gckey_add_d(rmap_t *map, rgc_t* gc, double name, rconstpointer pval)
 180 {
 181         char key[128];
 182         r_memset(key, 0, sizeof(key));
 183         r_snprintf(key, sizeof(key) - 1, "%.15f", name);
 184         return r_map_gckey_add_s(map, gc, key, pval);
 185 }
 186
 187
 188 long r_map_gckey_add_l(rmap_t *map, rgc_t* gc, long name, rconstpointer pval)
 189 {
 190         char key[128];
 191         r_memset(key, 0, sizeof(key));
 192         r_snprintf(key, sizeof(key) - 1, "%ld", name);
 193         return r_map_gckey_add_s(map, gc, key, pval);
 194 }
 195
 196
 197 long r_map_add(rmap_t *map, const char *name, rsize_t namesize, rconstpointer pval)
 198 {
 199         return r_map_gckey_add(map, NULL, name, namesize, pval);
 200 }
 201
 202
 203 long r_map_add_s(rmap_t *map, const char *name, rconstpointer pval)
 204 {
 205         return r_map_gckey_add_s(map, NULL, name, pval);
 206 }
 207
 208
 209 long r_map_add_l(rmap_t *map, long name, rconstpointer pval)
 210 {
 211         return r_map_gckey_add_l(map, NULL, name, pval);
 212 }
 213
 214
 215 long r_map_add_d(rmap_t *map, double name, rconstpointer pval)
 216 {
 217         return r_map_gckey_add_d(map, NULL, name, pval);
 218 }
 219
 220
 221 r_mapnode_t *r_map_node(rmap_t *map, unsigned long index)
 222 {
 223         r_mapnode_t *node;
 224         if (index >= r_carray_length(map->data))
 225                 return NULL;
 226         node = (r_mapnode_t*)r_carray_slot(map->data, index);
 227         if (r_list_empty(&node->hash))
 228                 return NULL;
 229         return node;
 230 }
 231
 232
 233 rstring_t *r_map_key(rmap_t *map, unsigned long index)
 234 {
 235         r_mapnode_t *node = r_map_node(map, index);
 236         if (!node)
 237                 return NULL;
 238         return node->key;
 239 }
 240
 241
 242 rpointer r_map_value(rmap_t *map, unsigned long index)
 243 {
 244         r_mapnode_t *node = r_map_node(map, index);
 245         if (!node)
 246                 return NULL;
 247         return (rpointer)node->value.data;
 248 }
 249
 250
 251 long r_map_setvalue(rmap_t *map, long index, rconstpointer pval)
 252 {
 253         r_mapnode_t *node = r_map_node(map, index);
 254         if (!node)
 255                 return -1;
 256         r_memcpy(node->value.data, pval, map->elt_size);
 257         return index;
 258 }
 259
 260
 261 int r_map_delete(rmap_t *map, unsigned long index)
 262 {
 263         r_mapnode_t *node = r_map_node(map, index);
 264         if (!node)
 265                 return -1;
 266         if (!r_object_gcget((robject_t*)node->key))
 267                 r_string_destroy(node->key);
 268         node->key = NULL;
 269         r_list_del(&node->hash);
 270         r_list_init(&node->hash);
 271         r_list_del(&node->active);
 272         r_list_addt(&map->inactive, &node->active);
 273         return 0;
 274 }
 275
 276
 277 long r_map_lookup(rmap_t *map, long current, const char *name, rsize_t namesize)
 278 {
 279         long found = -1;
 280         r_mapnode_t *node;
 281         rstr_t lookupstr = {(char*)name, namesize};
 282         unsigned long nbucket;
 283         rhead_t *bucket;
 284         rlink_t *pos;
 285
 286         if (current >= 0) {
 287                 r_mapnode_t *curnode = r_map_node(map, current);
 288                 if (!curnode)
 289                         return -1;
 290                 nbucket = curnode->nbucket;
 291                 bucket = &map->hash[nbucket];
 292                 pos = r_list_next(bucket, &curnode->hash);
 293         } else {
 294                 nbucket = (r_map_rstrhash(&lookupstr) & r_map_hashmask(map));
 295                 bucket = &map->hash[nbucket];
 296                 pos = r_list_first(bucket);
 297         }
 298         for ( ; pos ; pos = r_list_next(bucket, pos)) {
 299                 node = r_list_entry(pos, r_mapnode_t, hash);
 300                 if (r_map_rstrequal(R_STRING2RSTR(node->key), &lookupstr)) {
 301                         found = node->index;
 302                         break;
 303                 }
 304         }
 305
 306         return (long)found;
 307 }
 308
 309
 310 long r_map_lookup_s(rmap_t *map, long current, const char *name)
 311 {
 312         return r_map_lookup(map, current, name, r_strlen(name));
 313 }
 314
 315
 316 long r_map_lookup_l(rmap_t *map, long current, long name)
 317 {
 318         char key[128];
 319         r_memset(key, 0, sizeof(key));
 320         r_snprintf(key, sizeof(key) - 1, "%ld", name);
 321         return r_map_lookup_s(map, current, key);
 322 }
 323
 324
 325 long r_map_lookup_d(rmap_t *map, long current, double name)
 326 {
 327         char key[128];
 328         r_memset(key, 0, sizeof(key));
 329         r_snprintf(key, sizeof(key) - 1, "%.15f", name);
 330         return r_map_lookup_s(map, current, key);
 331 }
 332
 333
 334 long r_map_taillookup(rmap_t *map, long current, const char *name, rsize_t namesize)
 335 {
 336         long found = -1;
 337         r_mapnode_t *node;
 338         rstr_t lookupstr = {(char*)name, namesize};
 339         unsigned long nbucket;
 340         rhead_t *bucket;
 341         rlink_t *pos;
 342
 343         if (current >= 0) {
 344                 r_mapnode_t *curnode = r_map_node(map, current);
 345                 if (!curnode)
 346                         return -1;
 347                 nbucket = curnode->nbucket;
 348                 bucket = &map->hash[nbucket];
 349                 pos = r_list_prev(bucket, &curnode->hash);
 350         } else {
 351                 nbucket = (r_map_rstrhash(&lookupstr) & r_map_hashmask(map));
 352                 bucket = &map->hash[nbucket];
 353                 pos = r_list_last(bucket);
 354         }
 355         for ( ; pos ; pos = r_list_prev(bucket, pos)) {
 356                 node = r_list_entry(pos, r_mapnode_t, hash);
 357                 if (r_map_rstrequal(R_STRING2RSTR(node->key), &lookupstr)) {
 358                         found = node->index;
 359                         break;
 360                 }
 361         }
 362
 363         return (long)found;
 364 }
 365
 366
 367 long r_map_taillookup_s(rmap_t *map, long current, const char *name)
 368 {
 369         return r_map_taillookup(map, current, name, r_strlen(name));
 370 }
 371
 372
 373 long r_map_first(rmap_t *map)
 374 {
 375         r_mapnode_t *node;
 376         rlink_t *pos = r_list_first(&map->active);
 377
 378         if (!pos)
 379                 return -1;
 380         node = r_list_entry(pos, r_mapnode_t, active);
 381         return node->index;
 382 }
 383
 384
 385 long r_map_last(rmap_t *map)
 386 {
 387         r_mapnode_t *node;
 388         rlink_t *pos = r_list_last(&map->active);
 389
 390         if (!pos)
 391                 return -1;
 392         node = r_list_entry(pos, r_mapnode_t, active);
 393         return node->index;
 394 }
 395
 396
 397 long r_map_next(rmap_t *map, long current)
 398 {
 399         r_mapnode_t *node = r_map_node(map, current);
 400         rlink_t *pos;
 401
 402         if (!node)
 403                 return -1;
 404         pos = r_list_next(&map->active, &node->active);
 405         if (!pos)
 406                 return -1;
 407         node = r_list_entry(pos, r_mapnode_t, active);
 408         return node->index;
 409 }
 410
 411
 412 long r_map_prev(rmap_t *map, long current)
 413 {
 414         r_mapnode_t *node = r_map_node(map, current);
 415         rlink_t *pos;
 416
 417         if (!node)
 418                 return -1;
 419         pos = r_list_prev(&map->active, &node->active);
 420         if (!pos)
 421                 return -1;
 422         node = r_list_entry(pos, r_mapnode_t, active);
 423         return node->index;
 424 }