ucx: ucx/map.c@48ca036d7d9c

     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, copy_func decoder, void* decdata) {

   212     int c; int r, n;

   214     char *key, *value;

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

   217         /* Discard leading spaces and comments */

   218         if (c < 33) continue;

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

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

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

   222             }

   223             continue;

   224         }

   226         /* read into key buffer */

   227         n = 16;

   228         key = malloc(n);

   229         r = 0;

   230         do {

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

   232             if (r > n - 2) {

   233                 n *= 2;

   234                 key = realloc(key, n);

   235             }

   236             key[r] = c;

   237             r++;

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

   239         if (c <= 0) {

   240             free(key);

   241             return 1;

   242         }

   243         key[r] = 0;

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

   246         /* skip whitespaces */

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

   248             if (c > 32) break;

   249         }

   250         if (c <= 0) {

   251             free(key);

   252             return 1;

   253         }

   255         /* read into value buffer */

   256         n = 64;

   257         value = malloc(n);

   258         r = 0;

   259         do {

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

   261             if (r > n - 2) {

   262                 n *= 2;

   263                 value = realloc(value, n);

   264             }

   265             value[r] = c;

   266             r++;

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

   268         value[r] = 0;

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

   271         if (decoder == NULL) {

   272             value = realloc(value, r+2);

   273         } else {

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

   275             free(value);

   276             value = decoded;

   277         }

   279         ucx_map_cstr_put(map, key, value);

   280         free(key);

   281     }

   283     return 0;

   284 }

   286 int ucx_map_store_enc(UcxMap *map, FILE *f, copy_func encoder, void *encdata) {

   287     UcxMapIterator iter = ucx_map_iterator(map);

   288     char *k, *v;

   289     sstr_t key, value;

   290     int written;

   292     UCX_MAP_FOREACH(v, iter) {

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

   294         key = sstr(k);

   295         if (encoder == NULL) {

   296             value = sstr(v);

   297         } else {

   298             value = sstr(encoder(v, encdata));

   299         }

   301         written = 0;

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

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

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

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

   307         if (encoder != NULL) {

   308             free(value.ptr);

   309         }

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

   312     }

   314     return 0;

   315 }

Mercurial > hg > ucx / file revision

ucx/map.c@48ca036d7d9c

ucx/map.c