ucx: ucx/map.c@34f50d0bada4

     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 int ucx_map_copy(UcxMap *from, UcxMap *to, copy_func fnc, void *data) {

    48     UcxMapIterator i = ucx_map_iterator(from);

    49     void *value;

    50     UCX_MAP_FOREACH(value, i) {

    51         int ret = ucx_map_put(to, i.cur->key, fnc ? fnc(value, data) : value);

    52         if(ret != 0) {

    53             return 1;

    54         }

    55     }

    56     return 0;

    57 }

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

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

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

    62     if(newmap == NULL) {

    63         return NULL;

    64     }

    65     ucx_map_copy(map, newmap, fnc, data);

    66     return newmap;

    67 }

    69 int ucx_map_rehash(UcxMap *map) {

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

    71     if (map->count > load) {

    72         UcxMap oldmap;

    73         oldmap.map = map->map;

    74         oldmap.size = map->size;

    75         oldmap.count = map->count;

    77         map->size = (map->count * 5) >> 1;

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

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

    80             *map = oldmap;

    81             return 1;

    82         }

    83         map->count = 0;

    84         ucx_map_copy(&oldmap, map, NULL, NULL);

    85     }

    86     return 0;

    87 }

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

    90     if(key.hash == 0) {

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

    92     }

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

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

    96     UcxMapElement *prev = NULL;

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

    99         prev = elm;

   100         elm = elm->next;

   101     }

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

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

   105         if(e == NULL) {

   106             return -1;

   107         }

   108         e->key.data = NULL;

   109         if (prev == NULL) {

   110             map->map[slot] = e;

   111         } else {

   112             prev->next = e;

   113         }

   114         e->next = elm;

   115         elm = e;

   116     }

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

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

   120         if (kd == NULL) {

   121             return -1;

   122         }

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

   124         key.data = kd;

   125         elm->key = key;

   126         map->count++;

   127     }

   128     elm->data = data;

   130     return 0;

   131 }

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

   134     if(key.hash == 0) {

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

   136     }

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

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

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

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

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

   143                 return elm->data;

   144             }

   145         }

   146         elm = elm->next;

   147     }

   149     return NULL;

   150 }

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

   153     UcxKey key;

   154     key.data = data;

   155     key.len = len;

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

   157     return key;

   158 }

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

   162     /* murmur hash 2 */

   164     int m = 0x5bd1e995;

   165     int r = 24;

   167     int h = 25 ^ len;

   169     int i = 0;

   170     while (len >= 4) {

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

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

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

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

   176         k *= m;

   177         k ^= k >> r;

   178         k *= m;

   180         h *= m;

   181         h ^= k;

   183         i += 4;

   184         len -= 4;

   185     }

   187     switch (len) {

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

   189         /* no break */

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

   191         /* no break */

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

   193         /* no break */

   194     }

   196     h ^= h >> 13;

   197     h *= m;

   198     h ^= h >> 15;

   200     return h;

   201 }

   203 UcxMapIterator ucx_map_iterator(UcxMap *map) {

   204     UcxMapIterator i;

   205     i.map = map;

   206     i.cur = NULL;

   207     i.index = 0;

   208     return i;

   209 }

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

   212     UcxMapElement *e = i->cur;

   214     if(e == NULL) {

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

   216     } else {

   217         e = e->next;

   218     }

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

   221         if(e != NULL) {

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

   223                 i->cur = e;

   224                 *elm = e->data;

   225                 return 0;

   226             }

   228             e = e->next;

   229         } else {

   230             i->index++;

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

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

   234             }

   235         }

   236     }

   238     return 1;

   239 }

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

   242         ucx_map_coder decoder, void* decdata) {

   244     int c; int r, n;

   246     char *key, *value;

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

   249         /* Discard leading spaces and comments */

   250         if (c < 33) continue;

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

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

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

   254             }

   255             continue;

   256         }

   258         /* read into key buffer */

   259         n = 16;

   260         key = malloc(n);

   261         r = 0;

   262         do {

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

   264             if (r > n - 2) {

   265                 n *= 2;

   266                 key = realloc(key, n);

   267             }

   268             key[r] = c;

   269             r++;

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

   271         if (c <= 0) {

   272             free(key);

   273             return 1;

   274         }

   275         key[r] = 0;

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

   278         /* skip whitespaces */

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

   280             if (c > 32) break;

   281         }

   282         if (c <= 0) {

   283             free(key);

   284             return 1;

   285         }

   287         /* read into value buffer */

   288         n = 64;

   289         value = malloc(n);

   290         r = 0;

   291         do {

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

   293             if (r > n - 2) {

   294                 n *= 2;

   295                 value = realloc(value, n);

   296             }

   297             value[r] = c;

   298             r++;

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

   300         value[r] = 0;

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

   303         if (decoder) {

   304             size_t decodedSize;

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

   306             free(value);

   307             value = decoded;

   308             r = decodedSize;

   309         } else {

   310             r += 2;

   311             value = realloc(value, r);

   312         }

   314         if (allocator.pool) {

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

   316             memcpy(pooledValue, value, r);

   317             free(value);

   318             value = pooledValue;

   319         }

   321         ucx_map_cstr_put(map, key, value);

   322         free(key);

   323     }

   325     return 0;

   326 }

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

   329         ucx_map_coder encoder, void *encdata) {

   330     UcxMapIterator iter = ucx_map_iterator(map);

   331     char *k, *v;

   332     sstr_t key, value;

   333     int written;

   335     UCX_MAP_FOREACH(v, iter) {

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

   337         key = sstr(k);

   338         if (encoder) {

   339             size_t encodedSize;

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

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

   342         } else {

   343             value = sstr(v);

   344         }

   346         written = 0;

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

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

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

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

   352         if (encoder) {

   353             free(value.ptr);

   354         }

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

   357     }

   359     return 0;

   360 }

Mercurial > hg > ucx / file revision

ucx/map.c@34f50d0bada4

ucx/map.c