ucx: ucx/map.c@ecfdc1c4a552

     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_elmlist(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 }

    46 void ucx_map_free(UcxMap *map) {

    47     ucx_map_free_elmlist(map);

    48     free(map);

    49 }

    51 int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to,

    52         copy_func fnc, void *data) {

    53     UcxMapIterator i = ucx_map_iterator(from);

    54     void *value;

    55     UCX_MAP_FOREACH(value, i) {

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

    57         if(ret != 0) {

    58             return 1;

    59         }

    60     }

    61     return 0;

    62 }

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

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

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

    67     if(newmap == NULL) {

    68         return NULL;

    69     }

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

    71     return newmap;

    72 }

    74 int ucx_map_rehash(UcxMap *map) {

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

    76     if (map->count > load) {

    77         UcxMap oldmap;

    78         oldmap.map = map->map;

    79         oldmap.size = map->size;

    80         oldmap.count = map->count;

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

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

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

    85             *map = oldmap;

    86             return 1;

    87         }

    88         map->count = 0;

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

    91         /* free the UcxMapElement list of oldmap */

    92         ucx_map_free_elmlist(&oldmap);

    93     }

    94     return 0;

    95 }

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

    98     if(key.hash == 0) {

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

   100     }

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

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

   104     UcxMapElement *restrict prev = NULL;

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

   107         prev = elm;

   108         elm = elm->next;

   109     }

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

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

   113         if(e == NULL) {

   114             return -1;

   115         }

   116         e->key.data = NULL;

   117         if (prev) {

   118             prev->next = e;

   119         } else {

   120             map->map[slot] = e;

   121         }

   122         e->next = elm;

   123         elm = e;

   124     }

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

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

   128         if (kd == NULL) {

   129             return -1;

   130         }

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

   132         key.data = kd;

   133         elm->key = key;

   134         map->count++;

   135     }

   136     elm->data = data;

   138     return 0;

   139 }

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

   142     if(key.hash == 0) {

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

   144     }

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

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

   148     UcxMapElement *restrict pelm = NULL;

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

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

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

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

   153                 void *data = elm->data;

   154                 if (remove) {

   155                     if (pelm) {

   156                         pelm->next = elm->next;

   157                     } else {

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

   159                     }

   160                     free(elm);

   161                     map->count--;

   162                 }

   164                 return data;

   165             }

   166         }

   167         pelm = elm;

   168         elm = pelm->next;

   169     }

   171     return NULL;

   172 }

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

   175     return ucx_map_get_and_remove(map, key, 0);

   176 }

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

   179     return ucx_map_get_and_remove(map, key, 1);

   180 }

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

   183     UcxKey key;

   184     key.data = data;

   185     key.len = len;

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

   187     return key;

   188 }

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

   192     /* murmur hash 2 */

   194     int m = 0x5bd1e995;

   195     int r = 24;

   197     int h = 25 ^ len;

   199     int i = 0;

   200     while (len >= 4) {

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

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

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

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

   206         k *= m;

   207         k ^= k >> r;

   208         k *= m;

   210         h *= m;

   211         h ^= k;

   213         i += 4;

   214         len -= 4;

   215     }

   217     switch (len) {

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

   219         /* no break */

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

   221         /* no break */

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

   223         /* no break */

   224     }

   226     h ^= h >> 13;

   227     h *= m;

   228     h ^= h >> 15;

   230     return h;

   231 }

   233 UcxMapIterator ucx_map_iterator(UcxMap *map) {

   234     UcxMapIterator i;

   235     i.map = map;

   236     i.cur = NULL;

   237     i.index = 0;

   238     return i;

   239 }

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

   242     UcxMapElement *e = i->cur;

   244     if(e == NULL) {

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

   246     } else {

   247         e = e->next;

   248     }

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

   251         if(e != NULL) {

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

   253                 i->cur = e;

   254                 *elm = e->data;

   255                 return 0;

   256             }

   258             e = e->next;

   259         } else {

   260             i->index++;

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

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

   264             }

   265         }

   266     }

   268     return 1;

   269 }

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

   272         ucx_map_coder decoder, void* decdata) {

   274     int c; int r, n;

   276     char *key, *value;

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

   279         /* Discard leading spaces and comments */

   280         if (c < 33) continue;

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

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

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

   284             }

   285             continue;

   286         }

   288         /* read into key buffer */

   289         n = 16;

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

   291         r = 0;

   292         do {

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

   294             if (r > n - 2) {

   295                 n *= 2;

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

   297             }

   298             key[r] = c;

   299             r++;

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

   301         if (c <= 0) {

   302             free(key);

   303             return 1;

   304         }

   305         key[r] = 0;

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

   308         /* skip whitespaces */

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

   310             if (c > 32) break;

   311         }

   312         if (c <= 0) {

   313             free(key);

   314             return 1;

   315         }

   317         /* read into value buffer */

   318         n = 64;

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

   320         r = 0;

   321         do {

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

   323             if (r > n - 2) {

   324                 n *= 2;

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

   326             }

   327             value[r] = c;

   328             r++;

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

   330         value[r] = 0;

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

   333         if (decoder) {

   334             size_t decodedSize;

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

   336             free(value);

   337             value = (char*) decoded;

   338             r = decodedSize;

   339         } else {

   340             r += 2;

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

   342         }

   344         if (allocator.pool) {

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

   346             memcpy(pooledValue, value, r);

   347             free(value);

   348             value = (char*) pooledValue;

   349         }

   351         ucx_map_cstr_put(map, key, value);

   352         free(key);

   353     }

   355     return 0;

   356 }

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

   359         ucx_map_coder encoder, void *encdata) {

   360     UcxMapIterator iter = ucx_map_iterator(map);

   361     char *k, *v;

   362     sstr_t key, value;

   363     size_t written;

   365     UCX_MAP_FOREACH(v, iter) {

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

   367         key = sstrn(k, iter.cur->key.len);

   368         if (encoder) {

   369             size_t encodedSize;

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

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

   372         } else {

   373             value = sstr(v);

   374         }

   376         written = 0;

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

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

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

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

   382         if (encoder) {

   383             free(value.ptr);

   384         }

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

   387     }

   389     return 0;

   390 }

Mercurial > hg > ucx / file revision

ucx/map.c@ecfdc1c4a552

ucx/map.c