dict

Dictionary for sd_t's
git clone git://www.tkruger.se/dict.git
Log | Files | Refs | README

dict.c (2867B)

      1 #include "dict.h"
      2 
      3 void dict_init_size(dict_t *d, const size_t alloc) {
      4   d->nalloc = alloc;
      5   d->nelts = 0;
      6   d->keys = calloc(d->nalloc, sizeof(sd_t *));
      7   d->values = calloc(d->nalloc, sizeof(*(d->values)));
      8   d->nvalues = calloc(d->nalloc, sizeof(*(d->nvalues)));
      9   d->value_alloc = calloc(d->nalloc, sizeof(*(d->value_alloc)));
     10 }
     11 
     12 void dict_init(dict_t *d) { dict_init_size(d, DICT_DEFAULT_SIZE); }
     13 
     14 void dict_clear(dict_t *d) {
     15   size_t i,j;
     16   for (i = 0; i < d->nalloc; i++) {
     17     for(j = 0; j < d->nvalues[i]; j++)
     18       sd_clear(&(d->keys[i][j]));
     19     free(d->keys[i]);
     20     free(d->values[i]);
     21   }
     22 
     23   d->nalloc = 0;
     24   d->nelts = 0;
     25   free(d->keys);
     26   free(d->values);
     27   free(d->nvalues);
     28   free(d->value_alloc);
     29   d->keys = NULL;
     30   d->values = NULL;
     31 }
     32 
     33 void *dict_lookup(dict_t *d, sd_t k) {
     34   uint64_t h = sd_hash(&k);
     35   size_t i = h % d->nalloc;
     36   size_t j;
     37 
     38   // linear search for key in d->keys[i]
     39   for (j = 0; j < d->nvalues[i]; j++) {
     40     if(sd_cmp(&(d->keys[i][j]), &k) == 0)
     41       return d->values[i][j];
     42   }
     43 
     44   return NULL;
     45 }
     46 
     47 static inline void dict_basic_insert(dict_t *d, const sd_t * const key, void * const val, const size_t i) {
     48   if (d->value_alloc[i] == 0) {
     49     // create new stacks
     50     d->value_alloc[i] = DICT_SMALLEST_STACK_SIZE;
     51     d->values[i] = calloc(DICT_SMALLEST_STACK_SIZE, sizeof(*(d->values[i])));
     52     d->keys[i] = calloc(DICT_SMALLEST_STACK_SIZE, sizeof(*(d->keys[i])));
     53   } else if(d->value_alloc[i] == d->nvalues[i]) {
     54     // double size
     55     d->value_alloc[i] <<= 1;
     56     d->values[i] = realloc(d->values[i], d->value_alloc[i] * sizeof(*(d->values[i])));
     57     d->keys[i] = realloc(d->keys[i], d->value_alloc[i] * sizeof(*(d->keys[i])));
     58   }
     59 
     60   size_t j = d->nvalues[i];
     61   d->keys[i][j] = *key;
     62   d->values[i][j] = val;
     63   d->nvalues[i]++;
     64   d->nelts++;
     65 }
     66 
     67 static inline void dict_copy_insert(dict_t *d, const sd_t key, void * const val, const size_t i) {
     68   // copy the key
     69   sd_t key_copy;
     70   sd_init(&key_copy, key.size);
     71   memcpy(key_copy.data, key.data, key.size);
     72 
     73   dict_basic_insert(d, &key_copy, val, i);
     74 }
     75 
     76 static inline void dict_resize(dict_t *d, const size_t nalloc) {
     77   dict_t e;
     78   dict_init_size(&e, nalloc);
     79   size_t i,j, new_index;
     80 
     81   // insert the elements into e
     82   for (i = 0; i < d->nalloc; i++) {
     83     for(j = 0; j < d->nvalues[i]; j++) {
     84       new_index = sd_hash(&(d->keys[i][j])) % e.nalloc;
     85       dict_basic_insert(&e, &(d->keys[i][j]), d->values[i][j], new_index);
     86     }
     87 
     88     // free the old stack with index i
     89     free(d->keys[i]);
     90     free(d->values[i]);
     91   }
     92 
     93   // free the list of stacks
     94   free(d->keys);
     95   free(d->values);
     96 
     97   // change d to point where d pointed
     98   *d = e;
     99 }
    100 
    101 void dict_insert(dict_t *d, sd_t k, void *value) {
    102   size_t i;
    103 
    104   while(DICT_FACTOR * d->nelts > d->nalloc)
    105     dict_resize(d, d->nalloc * DICT_FACTOR);
    106 
    107   i = sd_hash(&k) % d->nalloc;
    108 
    109   dict_copy_insert(d, k, value, i);
    110 }