ucx: ucx/map.c@46356d74e873

     1 /*

     2  *

     3  */

     5 #include <stdlib.h>

     6 #include <string.h>

     8 #include "map.h"

    10 UcxMap *ucx_map_new(size_t size) {

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

    12     if(map == NULL) {

    13         return NULL;

    14     }

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

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

    18         free(map);

    19         return NULL;

    20     }

    21     map->size = size;

    23     return map;

    24 }

    26 void ucx_map_free(UcxMap *map) {

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

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

    29         if (elem != NULL) {

    30             do {

    31                 UcxMapElement *next = elem->next;

    32                 free(elem->key.data);

    33                 free(elem);

    34                 elem = next;

    35             } while (elem != NULL);

    36         }

    37     }

    38     free(map->map);

    39     free(map);

    40 }

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

    43     UcxMap *newmap = ucx_map_new(map->size);

    44     UcxMapIterator i = ucx_map_iterator(map);

    45     void *value;

    46     UCX_MAP_FOREACH(value, i) {

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

    48     }

    49     return newmap;

    50 }

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

    53     if(key.hash == 0) {

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

    55     }

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

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

    59     UcxMapElement *prev = NULL;

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

    62         prev = elm;

    63         elm = elm->next;

    64     }

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

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

    68         if(e == NULL) {

    69             return -1;

    70         }

    71         e->key.data = NULL;

    72         if (prev == NULL) {

    73             map->map[slot] = e;

    74         } else {

    75             prev->next = e;

    76         }

    77         e->next = elm;

    78         elm = e;

    79     }

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

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

    83         if (kd == NULL) {

    84             return -1;

    85         }

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

    87         key.data = kd;

    88         elm->key = key;

    89     }

    90     elm->data = data;

    92     return 0;

    93 }

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

    96     if(key.hash == 0) {

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

    98     }

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

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

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

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

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

   105                 return elm->data;

   106             }

   107         }

   108         elm = elm->next;

   109     }

   111     return NULL;

   112 }

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

   115     UcxKey key;

   116     key.data = data;

   117     key.len = len;

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

   119     return key;

   120 }

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

   124     /* murmur hash 2 */

   126     int m = 0x5bd1e995;

   127     int r = 24;

   129     int h = 25 ^ len;

   131     int i = 0;

   132     while (len >= 4) {

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

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

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

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

   138         k *= m;

   139         k ^= k >> r;

   140         k *= m;

   142         h *= m;

   143         h ^= k;

   145         i += 4;

   146         len -= 4;

   147     }

   149     switch (len) {

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

   151         /* no break */

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

   153         /* no break */

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

   155         /* no break */

   156     }

   158     h ^= h >> 13;

   159     h *= m;

   160     h ^= h >> 15;

   162     return h;

   163 }

   165 UcxMapIterator ucx_map_iterator(UcxMap *map) {

   166     UcxMapIterator i;

   167     i.map = map;

   168     i.cur = NULL;

   169     i.index = 0;

   170     return i;

   171 }

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

   174     UcxMapElement *e = i->cur;

   176     if(e == NULL) {

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

   178     } else {

   179         e = e->next;

   180     }

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

   183         if(e != NULL) {

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

   185                 i->cur = e;

   186                 *elm = e->data;

   187                 return 0;

   188             }

   190             e = e->next;

   191         } else {

   192             i->index++;

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

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

   196             }

   197         }

   198     }

   200     return 1;

   201 }

   203 int ucx_map_load(UcxMap *map, FILE *f) {

   205     int c; int r, n;

   207     char *key, *value;

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

   210         /* Discard leading spaces and comments */

   211         if (c < 33) continue;

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

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

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

   215             }

   216             continue;

   217         }

   219         /* read into key buffer */

   220         n = 16;

   221         key = malloc(n);

   222         r = 0;

   223         do {

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

   225             if (r > n - 2) {

   226                 n *= 2;

   227                 key = realloc(key, n);

   228             }

   229             key[r] = c;

   230             r++;

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

   232         if (c <= 0) {

   233             free(key);

   234             return 1;

   235         }

   236         key[r] = 0;

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

   239         /* skip whitespaces */

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

   241             if (c > 32) break;

   242         }

   243         if (c <= 0) {

   244             free(key);

   245             return 1;

   246         }

   248         /* read into value buffer */

   249         n = 64;

   250         value = malloc(n);

   251         r = 0;

   252         do {

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

   254             if (r > n - 2) {

   255                 n *= 2;

   256                 value = realloc(value, n);

   257             }

   258             value[r] = c;

   259             r++;

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

   261         value[r] = 0;

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

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

   265         ucx_map_cstr_put(map, key, value);

   266         free(key);

   267     }

   269     return 0;

   270 }

   272 int ucx_map_store(UcxMap *map, FILE *f) {

   273     UcxMapIterator iter = ucx_map_iterator(map);

   274     char *k, *v;

   275     sstr_t key, value;

   276     int written;

   278     UCX_MAP_FOREACH(v, iter) {

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

   280         key = sstr(k); value = sstr(v);

   282         written = 0;

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

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

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

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

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

   289     }

   291     return 0;

   292 }

Mercurial > hg > ucx / file revision