ucx: ucx/map.c@02f38adea013

     1 /*

     2  *

     3  */

     5 #include <stdlib.h>

     6 #include <string.h>

     7 #ifndef _WIN32

     8 #include <unistd.h>

     9 #endif /* not _WIN32 */

    11 #include "map.h"

    13 UcxMap *ucx_map_new(size_t size) {

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

    15     if(map == NULL) {

    16         return NULL;

    17     }

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

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

    21         free(map);

    22         return NULL;

    23     }

    24     map->size = size;

    26     return map;

    27 }

    29 void ucx_map_free(UcxMap *map) {

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

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

    32         if (elem != NULL) {

    33             do {

    34                 UcxMapElement *next = elem->next;

    35                 free(elem->key.data);

    36                 free(elem);

    37                 elem = next;

    38             } while (elem != NULL);

    39         }

    40     }

    41     free(map->map);

    42     free(map);

    43 }

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

    46     if(key.hash == 0) {

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

    48     }

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

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

    52     UcxMapElement *prev = NULL;

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

    55         prev = elm;

    56         elm = elm->next;

    57     }

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

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

    61         if(e == NULL) {

    62             return -1;

    63         }

    64         e->key.data = NULL;

    65         if (prev == NULL) {

    66             map->map[slot] = e;

    67         } else {

    68             prev->next = e;

    69         }

    70         e->next = elm;

    71         elm = e;

    72     }

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

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

    76         if (kd == NULL) {

    77             return -1;

    78         }

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

    80         key.data = kd;

    81         elm->key = key;

    82     }

    83     elm->data = data;

    85     return 0;

    86 }

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

    89     if(key.hash == 0) {

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

    91     }

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

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

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

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

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

    98                 return elm->data;

    99             }

   100         }

   101         elm = elm->next;

   102     }

   104     return NULL;

   105 }

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

   108     UcxKey key;

   109     key.data = data;

   110     key.len = len;

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

   112     return key;

   113 }

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

   117     /* murmur hash 2 */

   119     int m = 0x5bd1e995;

   120     int r = 24;

   122     int h = 25 ^ len;

   124     int i = 0;

   125     while (len >= 4) {

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

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

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

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

   131         k *= m;

   132         k ^= k >> r;

   133         k *= m;

   135         h *= m;

   136         h ^= k;

   138         i += 4;

   139         len -= 4;

   140     }

   142     switch (len) {

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

   144         /* no break */

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

   146         /* no break */

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

   148         /* no break */

   149     }

   151     h ^= h >> 13;

   152     h *= m;

   153     h ^= h >> 15;

   155     return h;

   156 }

   158 UcxMapIterator ucx_map_iterator(UcxMap *map) {

   159     UcxMapIterator i;

   160     i.map = map;

   161     i.cur = NULL;

   162     i.index = 0;

   163     return i;

   164 }

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

   167     UcxMapElement *e = i->cur;

   169     if(e == NULL) {

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

   171     } else {

   172         e = e->next;

   173     }

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

   176         if(e != NULL) {

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

   178                 i->cur = e;

   179                 *elm = e->data;

   180                 return 0;

   181             }

   183             e = e->next;

   184         } else {

   185             i->index++;

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

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

   189             }

   190         }

   191     }

   193     return 1;

   194 }

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

   198     int c; int r, n;

   200     char *key, *value;

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

   203         /* Discard leading spaces and comments */

   204         if (c < 33) continue;

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

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

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

   208             }

   209             continue;

   210         }

   212         /* read into key buffer */

   213         n = 16;

   214         key = malloc(n);

   215         r = 0;

   216         do {

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

   218             if (r > n - 2) {

   219                 n *= 2;

   220                 key = realloc(key, n);

   221             }

   222             key[r] = c;

   223             r++;

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

   225         if (c <= 0) {

   226             free(key);

   227             return 1;

   228         }

   229         key[r] = 0;

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

   232         /* skip whitespaces */

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

   234             if (c > 32) break;

   235         }

   236         if (c <= 0) {

   237             free(key);

   238             return 1;

   239         }

   241         /* read into value buffer */

   242         n = 64;

   243         value = malloc(n);

   244         r = 0;

   245         do {

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

   247             if (r > n - 2) {

   248                 n *= 2;

   249                 value = realloc(value, n);

   250             }

   251             value[r] = c;

   252             r++;

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

   254         value[r] = 0;

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

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

   258         ucx_map_cstr_put(map, key, value);

   259         free(key);

   260     }

   262     return 0;

   263 }

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

   266     UcxMapIterator iter = ucx_map_iterator(map);

   267     char *k, *v;

   268     sstr_t key, value;

   269     int written;

   271     UCX_MAP_FOREACH(v, iter) {

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

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

   275         written = 0;

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

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

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

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

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

   282     }

   284     return 0;

   285 }

Mercurial > hg > ucx / file revision