ucx: ucx/map.c@1c78cd19fb6b

     1 /*

     2  *

     3  */

     5 #include <stdlib.h>

     6 #include <string.h>

     8 #include "map.h"

    10 UcxMap *ucx_map_new(size_t size) {

    11     if(size == 0) {

    12         size = 16;

    13     }

    15     UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap));

    16     if(map == NULL) {

    17         return NULL;

    18     }

    20     map->map = (UcxMapElement**)calloc(size, sizeof(UcxMapElement*));

    21     if(map->map == NULL) {

    22         free(map);

    23         return NULL;

    24     }

    25     map->size = size;

    26     map->count = 0;

    28     return map;

    29 }

    31 void ucx_map_free(UcxMap *map) {

    32     for (size_t n = 0 ; n < map->size ; n++) {

    33         UcxMapElement *elem = map->map[n];

    34         if (elem != NULL) {

    35             do {

    36                 UcxMapElement *next = elem->next;

    37                 free(elem->key.data);

    38                 free(elem);

    39                 elem = next;

    40             } while (elem != NULL);

    41         }

    42     }

    43     free(map->map);

    44     free(map);

    45 }

    47 UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) {

    48     size_t bs = (map->count * 5) >> 1;

    49     UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size);

    50     UcxMapIterator i = ucx_map_iterator(map);

    51     void *value;

    52     UCX_MAP_FOREACH(value, i) {

    53         ucx_map_put(newmap, i.cur->key, fnc ? fnc(value, data) : value);

    54     }

    55     return newmap;

    56 }

    58 UcxMap *ucx_map_rehash(UcxMap *map) {

    59     size_t load = (map->size * 3) >> 2;

    60     if (map->count > load) {

    61         UcxMap *newmap = ucx_map_clone(map, NULL, NULL);

    62         ucx_map_free(map);

    63         return newmap;

    64     } else {

    65         return map;

    66     }

    67 }

    69 int ucx_map_put(UcxMap *map, UcxKey key, void *data) {

    70     if(key.hash == 0) {

    71         key.hash = ucx_hash((char*)key.data, key.len);

    72     }

    74     size_t slot = key.hash%map->size;

    75     UcxMapElement *elm = map->map[slot];

    76     UcxMapElement *prev = NULL;

    78     while (elm != NULL && elm->key.hash < key.hash) {

    79         prev = elm;

    80         elm = elm->next;

    81     }

    83     if (elm == NULL || elm->key.hash != key.hash) {

    84         UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement));

    85         if(e == NULL) {

    86             return -1;

    87         }

    88         e->key.data = NULL;

    89         if (prev == NULL) {

    90             map->map[slot] = e;

    91         } else {

    92             prev->next = e;

    93         }

    94         e->next = elm;

    95         elm = e;

    96     }

    98     if(elm->key.data == NULL) {

    99         void *kd = malloc(key.len);

   100         if (kd == NULL) {

   101             return -1;

   102         }

   103         memcpy(kd, key.data, key.len);

   104         key.data = kd;

   105         elm->key = key;

   106         map->count++;

   107     }

   108     elm->data = data;

   110     return 0;

   111 }

   113 void* ucx_map_get(UcxMap *map, UcxKey key) {

   114     if(key.hash == 0) {

   115         key.hash = ucx_hash((char*)key.data, key.len);

   116     }

   118     UcxMapElement *elm = map->map[key.hash%map->size];

   119     while (elm != NULL && elm->key.hash <= key.hash) {

   120         if(elm->key.hash == key.hash) {

   121             int n = (key.len > elm->key.len) ? elm->key.len : key.len;

   122             if (memcmp(elm->key.data, key.data, n) == 0) {

   123                 return elm->data;

   124             }

   125         }

   126         elm = elm->next;

   127     }

   129     return NULL;

   130 }

   132 UcxKey ucx_key(void *data, size_t len) {

   133     UcxKey key;

   134     key.data = data;

   135     key.len = len;

   136     key.hash = ucx_hash(data, len);

   137     return key;

   138 }

   141 int ucx_hash(char *data, size_t len) {

   142     /* murmur hash 2 */

   144     int m = 0x5bd1e995;

   145     int r = 24;

   147     int h = 25 ^ len;

   149     int i = 0;

   150     while (len >= 4) {

   151         int k = data[i + 0] & 0xFF;

   152         k |= (data[i + 1] & 0xFF) << 8;

   153         k |= (data[i + 2] & 0xFF) << 16;

   154         k |= (data[i + 3] & 0xFF) << 24;

   156         k *= m;

   157         k ^= k >> r;

   158         k *= m;

   160         h *= m;

   161         h ^= k;

   163         i += 4;

   164         len -= 4;

   165     }

   167     switch (len) {

   168         case 3: h ^= (data[i + 2] & 0xFF) << 16;

   169         /* no break */

   170         case 2: h ^= (data[i + 1] & 0xFF) << 8;

   171         /* no break */

   172         case 1: h ^= (data[i + 0] & 0xFF); h *= m;

   173         /* no break */

   174     }

   176     h ^= h >> 13;

   177     h *= m;

   178     h ^= h >> 15;

   180     return h;

   181 }

   183 UcxMapIterator ucx_map_iterator(UcxMap *map) {

   184     UcxMapIterator i;

   185     i.map = map;

   186     i.cur = NULL;

   187     i.index = 0;

   188     return i;

   189 }

   191 int ucx_map_iter_next(UcxMapIterator *i, void **elm) {

   192     UcxMapElement *e = i->cur;

   194     if(e == NULL) {

   195         e = i->map->map[0];

   196     } else {

   197         e = e->next;

   198     }

   200     while(i->index < i->map->size) {

   201         if(e != NULL) {

   202             if(e->data != NULL) {

   203                 i->cur = e;

   204                 *elm = e->data;

   205                 return 0;

   206             }

   208             e = e->next;

   209         } else {

   210             i->index++;

   212             if(i->index < i->map->size) {

   213                 e = i->map->map[i->index];

   214             }

   215         }

   216     }

   218     return 1;

   219 }

   221 int ucx_map_load_enc(UcxMap *map, FILE *f, UcxAllocator allocator,

   222         ucx_map_coder decoder, void* decdata) {

   224     int c; int r, n;

   226     char *key, *value;

   228     while ((c = fgetc(f)) > 0) {

   229         /* Discard leading spaces and comments */

   230         if (c < 33) continue;

   231         if (c == '#' || c == '!') {

   232             while ((c = (char) fgetc(f)) > 0) {

   233                 if (c == '\n') break;

   234             }

   235             continue;

   236         }

   238         /* read into key buffer */

   239         n = 16;

   240         key = malloc(n);

   241         r = 0;

   242         do {

   243             if (c == '=') break;

   244             if (r > n - 2) {

   245                 n *= 2;

   246                 key = realloc(key, n);

   247             }

   248             key[r] = c;

   249             r++;

   250         } while ((c = fgetc(f)) > 0);

   251         if (c <= 0) {

   252             free(key);

   253             return 1;

   254         }

   255         key[r] = 0;

   256         while (key[--r] == ' ') key[r] = 0;

   258         /* skip whitespaces */

   259         while ((c = fgetc(f)) > 0) {

   260             if (c > 32) break;

   261         }

   262         if (c <= 0) {

   263             free(key);

   264             return 1;

   265         }

   267         /* read into value buffer */

   268         n = 64;

   269         value = malloc(n);

   270         r = 0;

   271         do {

   272             if (c == '\n') break;

   273             if (r > n - 2) {

   274                 n *= 2;

   275                 value = realloc(value, n);

   276             }

   277             value[r] = c;

   278             r++;

   279         } while ((c = fgetc(f)) > 0);

   280         value[r] = 0;

   281         while (value[--r] < 33) value[r] = 0;

   283         if (decoder) {

   284             size_t decodedSize;

   285             void *decoded = decoder(value, decdata, &decodedSize);

   286             free(value);

   287             value = decoded;

   288             r = decodedSize;

   289         } else {

   290             r += 2;

   291             value = realloc(value, r);

   292         }

   294         if (allocator.pool) {

   295             void *pooledValue = allocator.malloc(allocator.pool, r);

   296             memcpy(pooledValue, value, r);

   297             free(value);

   298             value = pooledValue;

   299         }

   301         ucx_map_cstr_put(map, key, value);

   302         free(key);

   303     }

   305     return 0;

   306 }

   308 int ucx_map_store_enc(UcxMap *map, FILE *f,

   309         ucx_map_coder encoder, void *encdata) {

   310     UcxMapIterator iter = ucx_map_iterator(map);

   311     char *k, *v;

   312     sstr_t key, value;

   313     int written;

   315     UCX_MAP_FOREACH(v, iter) {

   316         k = (char*) iter.cur->key.data;

   317         key = sstr(k);

   318         if (encoder) {

   319             size_t encodedSize;

   320             void *encoded = encoder(v, encdata, &encodedSize);

   321             value = sstrn(encoded,encodedSize - 1);

   322         } else {

   323             value = sstr(v);

   324         }

   326         written = 0;

   327         written += fwrite(key.ptr, 1, key.length, f);

   328         written += fwrite(" = ", 1, 3, f);

   329         written += fwrite(value.ptr, 1, value.length, f);

   330         written += fwrite("\n", 1, 1, f);

   332         if (encoder) {

   333             free(value.ptr);

   334         }

   336         if (written != key.length + value.length + 4) return 1;

   337     }

   339     return 0;

   340 }

Mercurial > hg > ucx / file revision

ucx/map.c@1c78cd19fb6b

ucx/map.c