ucx: ucx/map.c@fb59270b1de3

     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 *restrict from, UcxMap *restrict to,

    48         copy_func fnc, void *data) {

    49     UcxMapIterator i = ucx_map_iterator(from);

    50     void *value;

    51     UCX_MAP_FOREACH(value, i) {

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

    53         if(ret != 0) {

    54             return 1;

    55         }

    56     }

    57     return 0;

    58 }

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

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

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

    63     if(newmap == NULL) {

    64         return NULL;

    65     }

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

    67     return newmap;

    68 }

    70 int ucx_map_rehash(UcxMap *map) {

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

    72     if (map->count > load) {

    73         UcxMap oldmap;

    74         oldmap.map = map->map;

    75         oldmap.size = map->size;

    76         oldmap.count = map->count;

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

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

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

    81             *map = oldmap;

    82             return 1;

    83         }

    84         map->count = 0;

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

    86         /* TODO: free the UcxMapElement list of oldmap */

    87     }

    88     return 0;

    89 }

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

    92     if(key.hash == 0) {

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

    94     }

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

    97     UcxMapElement *restrict elm = map->map[slot];

    98     UcxMapElement *restrict prev = NULL;

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

   101         prev = elm;

   102         elm = elm->next;

   103     }

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

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

   107         if(e == NULL) {

   108             return -1;

   109         }

   110         e->key.data = NULL;

   111         if (prev) {

   112             prev->next = e;

   113         } else {

   114             map->map[slot] = e;

   115         }

   116         e->next = elm;

   117         elm = e;

   118     }

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

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

   122         if (kd == NULL) {

   123             return -1;

   124         }

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

   126         key.data = kd;

   127         elm->key = key;

   128         map->count++;

   129     }

   130     elm->data = data;

   132     return 0;

   133 }

   135 void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) {

   136     if(key.hash == 0) {

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

   138     }

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

   141     UcxMapElement *restrict elm = map->map[slot];

   142     UcxMapElement *restrict pelm = NULL;

   143     while (elm && elm->key.hash <= key.hash) {

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

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

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

   147                 void *data = elm->data;

   148                 if (remove) {

   149                     if (pelm) {

   150                         pelm->next = elm->next;

   151                     } else {

   152                         map->map[slot] = elm->next;

   153                     }

   154                     free(elm);

   155                     map->count--;

   156                 }

   158                 return data;

   159             }

   160         }

   161         pelm = elm;

   162         elm = pelm->next;

   163     }

   165     return NULL;

   166 }

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

   169     return ucx_map_get_and_remove(map, key, 0);

   170 }

   172 void *ucx_map_remove(UcxMap *map, UcxKey key) {

   173     return ucx_map_get_and_remove(map, key, 1);

   174 }

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

   177     UcxKey key;

   178     key.data = data;

   179     key.len = len;

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

   181     return key;

   182 }

   185 int ucx_hash(const char *data, size_t len) {

   186     /* murmur hash 2 */

   188     int m = 0x5bd1e995;

   189     int r = 24;

   191     int h = 25 ^ len;

   193     int i = 0;

   194     while (len >= 4) {

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

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

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

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

   200         k *= m;

   201         k ^= k >> r;

   202         k *= m;

   204         h *= m;

   205         h ^= k;

   207         i += 4;

   208         len -= 4;

   209     }

   211     switch (len) {

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

   213         /* no break */

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

   215         /* no break */

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

   217         /* no break */

   218     }

   220     h ^= h >> 13;

   221     h *= m;

   222     h ^= h >> 15;

   224     return h;

   225 }

   227 UcxMapIterator ucx_map_iterator(UcxMap *map) {

   228     UcxMapIterator i;

   229     i.map = map;

   230     i.cur = NULL;

   231     i.index = 0;

   232     return i;

   233 }

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

   236     UcxMapElement *e = i->cur;

   238     if(e == NULL) {

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

   240     } else {

   241         e = e->next;

   242     }

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

   245         if(e != NULL) {

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

   247                 i->cur = e;

   248                 *elm = e->data;

   249                 return 0;

   250             }

   252             e = e->next;

   253         } else {

   254             i->index++;

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

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

   258             }

   259         }

   260     }

   262     return 1;

   263 }

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

   266         ucx_map_coder decoder, void* decdata) {

   268     int c; int r, n;

   270     char *key, *value;

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

   273         /* Discard leading spaces and comments */

   274         if (c < 33) continue;

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

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

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

   278             }

   279             continue;

   280         }

   282         /* read into key buffer */

   283         n = 16;

   284         key = (char*) malloc(n);

   285         r = 0;

   286         do {

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

   288             if (r > n - 2) {

   289                 n *= 2;

   290                 key = (char*) realloc(key, n);

   291             }

   292             key[r] = c;

   293             r++;

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

   295         if (c <= 0) {

   296             free(key);

   297             return 1;

   298         }

   299         key[r] = 0;

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

   302         /* skip whitespaces */

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

   304             if (c > 32) break;

   305         }

   306         if (c <= 0) {

   307             free(key);

   308             return 1;

   309         }

   311         /* read into value buffer */

   312         n = 64;

   313         value = (char*) malloc(n);

   314         r = 0;

   315         do {

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

   317             if (r > n - 2) {

   318                 n *= 2;

   319                 value = (char*) realloc(value, n);

   320             }

   321             value[r] = c;

   322             r++;

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

   324         value[r] = 0;

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

   327         if (decoder) {

   328             size_t decodedSize;

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

   330             free(value);

   331             value = (char*) decoded;

   332             r = decodedSize;

   333         } else {

   334             r += 2;

   335             value = (char*) realloc(value, r);

   336         }

   338         if (allocator.pool) {

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

   340             memcpy(pooledValue, value, r);

   341             free(value);

   342             value = (char*) pooledValue;

   343         }

   345         ucx_map_cstr_put(map, key, value);

   346         free(key);

   347     }

   349     return 0;

   350 }

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

   353         ucx_map_coder encoder, void *encdata) {

   354     UcxMapIterator iter = ucx_map_iterator(map);

   355     char *k, *v;

   356     sstr_t key, value;

   357     int written;

   359     UCX_MAP_FOREACH(v, iter) {

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

   361         key = sstr(k);

   362         if (encoder) {

   363             size_t encodedSize;

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

   365             value = sstrn((char*) encoded,encodedSize - 1);

   366         } else {

   367             value = sstr(v);

   368         }

   370         written = 0;

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

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

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

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

   376         if (encoder) {

   377             free(value.ptr);

   378         }

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

   381     }

   383     return 0;

   384 }

Mercurial > hg > ucx / file revision

ucx/map.c@fb59270b1de3

ucx/map.c