ucx: ucx/map.c@e533c170bfb8

     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) {

   110             prev->next = e;

   111         } else {

   112             map->map[slot] = 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_and_remove(UcxMap *map, UcxKey key, _Bool remove) {

   134     if(key.hash == 0) {

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

   136     }

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

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

   140     UcxMapElement *pelm = NULL;

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

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

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

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

   145                 void *data = elm->data;

   146                 if (remove) {

   147                     if (pelm) {

   148                         pelm->next = elm->next;

   149                     } else {

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

   151                     }

   152                     free(elm);

   153                     map->count--;

   154                 }

   156                 return data;

   157             }

   158         }

   159         pelm = elm;

   160         elm = pelm->next;

   161     }

   163     return NULL;

   164 }

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

   167     return ucx_map_get_and_remove(map, key, 0);

   168 }

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

   171     return ucx_map_get_and_remove(map, key, 1);

   172 }

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

   175     UcxKey key;

   176     key.data = data;

   177     key.len = len;

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

   179     return key;

   180 }

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

   184     /* murmur hash 2 */

   186     int m = 0x5bd1e995;

   187     int r = 24;

   189     int h = 25 ^ len;

   191     int i = 0;

   192     while (len >= 4) {

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

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

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

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

   198         k *= m;

   199         k ^= k >> r;

   200         k *= m;

   202         h *= m;

   203         h ^= k;

   205         i += 4;

   206         len -= 4;

   207     }

   209     switch (len) {

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

   211         /* no break */

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

   213         /* no break */

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

   215         /* no break */

   216     }

   218     h ^= h >> 13;

   219     h *= m;

   220     h ^= h >> 15;

   222     return h;

   223 }

   225 UcxMapIterator ucx_map_iterator(UcxMap *map) {

   226     UcxMapIterator i;

   227     i.map = map;

   228     i.cur = NULL;

   229     i.index = 0;

   230     return i;

   231 }

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

   234     UcxMapElement *e = i->cur;

   236     if(e == NULL) {

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

   238     } else {

   239         e = e->next;

   240     }

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

   243         if(e != NULL) {

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

   245                 i->cur = e;

   246                 *elm = e->data;

   247                 return 0;

   248             }

   250             e = e->next;

   251         } else {

   252             i->index++;

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

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

   256             }

   257         }

   258     }

   260     return 1;

   261 }

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

   264         ucx_map_coder decoder, void* decdata) {

   266     int c; int r, n;

   268     char *key, *value;

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

   271         /* Discard leading spaces and comments */

   272         if (c < 33) continue;

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

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

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

   276             }

   277             continue;

   278         }

   280         /* read into key buffer */

   281         n = 16;

   282         key = malloc(n);

   283         r = 0;

   284         do {

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

   286             if (r > n - 2) {

   287                 n *= 2;

   288                 key = realloc(key, n);

   289             }

   290             key[r] = c;

   291             r++;

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

   293         if (c <= 0) {

   294             free(key);

   295             return 1;

   296         }

   297         key[r] = 0;

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

   300         /* skip whitespaces */

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

   302             if (c > 32) break;

   303         }

   304         if (c <= 0) {

   305             free(key);

   306             return 1;

   307         }

   309         /* read into value buffer */

   310         n = 64;

   311         value = malloc(n);

   312         r = 0;

   313         do {

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

   315             if (r > n - 2) {

   316                 n *= 2;

   317                 value = realloc(value, n);

   318             }

   319             value[r] = c;

   320             r++;

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

   322         value[r] = 0;

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

   325         if (decoder) {

   326             size_t decodedSize;

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

   328             free(value);

   329             value = decoded;

   330             r = decodedSize;

   331         } else {

   332             r += 2;

   333             value = realloc(value, r);

   334         }

   336         if (allocator.pool) {

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

   338             memcpy(pooledValue, value, r);

   339             free(value);

   340             value = pooledValue;

   341         }

   343         ucx_map_cstr_put(map, key, value);

   344         free(key);

   345     }

   347     return 0;

   348 }

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

   351         ucx_map_coder encoder, void *encdata) {

   352     UcxMapIterator iter = ucx_map_iterator(map);

   353     char *k, *v;

   354     sstr_t key, value;

   355     int written;

   357     UCX_MAP_FOREACH(v, iter) {

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

   359         key = sstr(k);

   360         if (encoder) {

   361             size_t encodedSize;

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

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

   364         } else {

   365             value = sstr(v);

   366         }

   368         written = 0;

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

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

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

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

   374         if (encoder) {

   375             free(value.ptr);

   376         }

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

   379     }

   381     return 0;

   382 }

Mercurial > hg > ucx / file revision

ucx/map.c@e533c170bfb8

ucx/map.c