ucx: ucx/map.c@621a4430c404

map can now load values from file into pooled memory

use with care when using a decoder that also allocates memory

     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) >> 2;

    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 int ucx_map_put(UcxMap *map, UcxKey key, void *data) {

    59     if(key.hash == 0) {

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

    61     }

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

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

    65     UcxMapElement *prev = NULL;

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

    68         prev = elm;

    69         elm = elm->next;

    70     }

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

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

    74         if(e == NULL) {

    75             return -1;

    76         }

    77         e->key.data = NULL;

    78         if (prev == NULL) {

    79             map->map[slot] = e;

    80         } else {

    81             prev->next = e;

    82         }

    83         e->next = elm;

    84         elm = e;

    85     }

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

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

    89         if (kd == NULL) {

    90             return -1;

    91         }

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

    93         key.data = kd;

    94         elm->key = key;

    95         map->count++;

    96     }

    97     elm->data = data;

    99     return 0;

   100 }

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

   103     if(key.hash == 0) {

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

   105     }

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

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

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

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

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

   112                 return elm->data;

   113             }

   114         }

   115         elm = elm->next;

   116     }

   118     return NULL;

   119 }

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

   122     UcxKey key;

   123     key.data = data;

   124     key.len = len;

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

   126     return key;

   127 }

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

   131     /* murmur hash 2 */

   133     int m = 0x5bd1e995;

   134     int r = 24;

   136     int h = 25 ^ len;

   138     int i = 0;

   139     while (len >= 4) {

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

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

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

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

   145         k *= m;

   146         k ^= k >> r;

   147         k *= m;

   149         h *= m;

   150         h ^= k;

   152         i += 4;

   153         len -= 4;

   154     }

   156     switch (len) {

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

   158         /* no break */

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

   160         /* no break */

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

   162         /* no break */

   163     }

   165     h ^= h >> 13;

   166     h *= m;

   167     h ^= h >> 15;

   169     return h;

   170 }

   172 UcxMapIterator ucx_map_iterator(UcxMap *map) {

   173     UcxMapIterator i;

   174     i.map = map;

   175     i.cur = NULL;

   176     i.index = 0;

   177     return i;

   178 }

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

   181     UcxMapElement *e = i->cur;

   183     if(e == NULL) {

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

   185     } else {

   186         e = e->next;

   187     }

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

   190         if(e != NULL) {

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

   192                 i->cur = e;

   193                 *elm = e->data;

   194                 return 0;

   195             }

   197             e = e->next;

   198         } else {

   199             i->index++;

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

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

   203             }

   204         }

   205     }

   207     return 1;

   208 }

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

   211         ucx_map_coder decoder, void* decdata) {

   213     int c; int r, n;

   215     char *key, *value;

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

   218         /* Discard leading spaces and comments */

   219         if (c < 33) continue;

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

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

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

   223             }

   224             continue;

   225         }

   227         /* read into key buffer */

   228         n = 16;

   229         key = malloc(n);

   230         r = 0;

   231         do {

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

   233             if (r > n - 2) {

   234                 n *= 2;

   235                 key = realloc(key, n);

   236             }

   237             key[r] = c;

   238             r++;

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

   240         if (c <= 0) {

   241             free(key);

   242             return 1;

   243         }

   244         key[r] = 0;

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

   247         /* skip whitespaces */

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

   249             if (c > 32) break;

   250         }

   251         if (c <= 0) {

   252             free(key);

   253             return 1;

   254         }

   256         /* read into value buffer */

   257         n = 64;

   258         value = malloc(n);

   259         r = 0;

   260         do {

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

   262             if (r > n - 2) {

   263                 n *= 2;

   264                 value = realloc(value, n);

   265             }

   266             value[r] = c;

   267             r++;

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

   269         value[r] = 0;

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

   272         if (decoder) {

   273             size_t decodedSize;

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

   275             free(value);

   276             value = decoded;

   277             r = decodedSize;

   278         } else {

   279             r += 2;

   280             value = realloc(value, r);

   281         }

   283         if (allocator.pool) {

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

   285             memcpy(pooledValue, value, r);

   286             free(value);

   287             value = pooledValue;

   288         }

   290         ucx_map_cstr_put(map, key, value);

   291         free(key);

   292     }

   294     return 0;

   295 }

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

   298         ucx_map_coder encoder, void *encdata) {

   299     UcxMapIterator iter = ucx_map_iterator(map);

   300     char *k, *v;

   301     sstr_t key, value;

   302     int written;

   304     UCX_MAP_FOREACH(v, iter) {

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

   306         key = sstr(k);

   307         if (encoder) {

   308             size_t encodedSize;

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

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

   311         } else {

   312             value = sstr(v);

   313         }

   315         written = 0;

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

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

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

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

   321         if (encoder) {

   322             free(value.ptr);

   323         }

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

   326     }

   328     return 0;

   329 }

Mercurial > hg > ucx / file revision

ucx/map.c@621a4430c404

ucx/map.c