olaf@20: /*
olaf@20:  *
olaf@20:  */
olaf@2: 
olaf@20: #include <stdlib.h>
olaf@20: #include <string.h>
olaf@20: 
olaf@20: #include "map.h"
olaf@20: 
olaf@20: UcxMap *ucx_map_new(size_t size) {
olaf@20:     UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap));
olaf@20:     if(map == NULL) {
olaf@20:         return NULL;
olaf@20:     }
olaf@20: 
universe@29:     map->map = (UcxMapElement**)calloc(size, sizeof(UcxMapElement*));
olaf@20:     if(map->map == NULL) {
olaf@20:         free(map);
olaf@20:         return NULL;
olaf@20:     }
olaf@20:     map->size = size;
olaf@20: 
olaf@20:     return map;
olaf@20: }
olaf@20: 
universe@29: void ucx_map_free(UcxMap *map) {
universe@29:     for (size_t n = 0 ; n < map->size ; n++) {
universe@29:         UcxMapElement *elem = map->map[n];
universe@29:         if (elem != NULL) {
universe@29:             do {
universe@29:                 UcxMapElement *next = elem->next;
olaf@30:                 free(elem->key.data);
universe@29:                 free(elem);
universe@29:                 elem = next;
universe@29:             } while (elem != NULL);
universe@29:         }
universe@29:     }
olaf@30:     free(map->map);
universe@29:     free(map);
universe@29: }
universe@29: 
olaf@20: int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
olaf@20:     if(key.hash == 0) {
olaf@20:         key.hash = ucx_hash((char*)key.data, key.len);
olaf@20:     }
olaf@20: 
universe@29:     size_t slot = key.hash%map->size;
universe@29:     UcxMapElement *elm = map->map[slot];
universe@29:     UcxMapElement *prev = NULL;
universe@29: 
universe@29:     while (elm != NULL && elm->key.hash < key.hash) {
universe@29:         prev = elm;
universe@29:         elm = elm->next;
universe@29:     }
universe@29:     
universe@29:     if (elm == NULL || elm->key.hash != key.hash) {
olaf@20:         UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement));
olaf@20:         if(e == NULL) {
olaf@20:             return -1;
olaf@20:         }
olaf@30:         e->key.data = NULL;
universe@29:         if (prev == NULL) {
universe@29:             map->map[slot] = e;
universe@29:         } else {
universe@29:             prev->next = e;
universe@29:         }
universe@29:         e->next = elm;
olaf@20:         elm = e;
olaf@20:     }
universe@29:     
olaf@30:     if(elm->key.data == NULL) {
olaf@30:         void *kd = malloc(key.len);
olaf@30:         if (kd == NULL) {
olaf@30:             return -1;
olaf@30:         }
olaf@30:         memcpy(kd, key.data, key.len);
olaf@30:         key.data = kd;
olaf@30:         elm->key = key;
olaf@30:     }
olaf@20:     elm->data = data;
olaf@20: 
olaf@20:     return 0;
olaf@20: }
olaf@20: 
olaf@20: void* ucx_map_get(UcxMap *map, UcxKey key) {
olaf@20:     if(key.hash == 0) {
olaf@20:         key.hash = ucx_hash((char*)key.data, key.len);
olaf@20:     }
olaf@20:     
universe@29:     UcxMapElement *elm = map->map[key.hash%map->size];
universe@29:     while (elm != NULL && elm->key.hash <= key.hash) {
olaf@20:         if(elm->key.hash == key.hash) {
olaf@20:             int n = (key.len > elm->key.len) ? elm->key.len : key.len;
universe@29:             if (memcmp(elm->key.data, key.data, n) == 0) {
olaf@20:                 return elm->data;
olaf@20:             }
olaf@20:         }
olaf@20:         elm = elm->next;
olaf@20:     }
olaf@20: 
olaf@20:     return NULL;
olaf@20: }
olaf@20: 
olaf@20: UcxKey ucx_key(void *data, size_t len) {
olaf@20:     UcxKey key;
olaf@20:     key.data = data;
olaf@20:     key.len = len;
olaf@20:     key.hash = ucx_hash(data, len);
olaf@20:     return key;
olaf@20: }
olaf@20: 
olaf@20: 
olaf@20: int ucx_hash(char *data, size_t len) {
olaf@20:     /* murmur hash 2 */
olaf@20: 
olaf@20:     int m = 0x5bd1e995;
olaf@20:     int r = 24;
olaf@20: 
olaf@20:     int h = 25 ^ len;
olaf@20: 
olaf@20:     int i = 0;
olaf@20:     while (len >= 4) {
olaf@20:         int k = data[i + 0] & 0xFF;
olaf@20:         k |= (data[i + 1] & 0xFF) << 8;
olaf@20:         k |= (data[i + 2] & 0xFF) << 16;
olaf@20:         k |= (data[i + 3] & 0xFF) << 24;
olaf@20: 
olaf@20:         k *= m;
olaf@20:         k ^= k >> r;
olaf@20:         k *= m;
olaf@20: 
olaf@20:         h *= m;
olaf@20:         h ^= k;
olaf@20: 
olaf@20:         i += 4;
olaf@20:         len -= 4;
olaf@20:     }
olaf@20: 
olaf@20:     switch (len) {
olaf@20:         case 3: h ^= (data[i + 2] & 0xFF) << 16;
universe@38:         /* no break */
olaf@20:         case 2: h ^= (data[i + 1] & 0xFF) << 8;
universe@38:         /* no break */
olaf@20:         case 1: h ^= (data[i + 0] & 0xFF); h *= m;
universe@38:         /* no break */
olaf@20:     }
olaf@20: 
olaf@20:     h ^= h >> 13;
olaf@20:     h *= m;
olaf@20:     h ^= h >> 15;
olaf@20: 
olaf@20:     return h;
olaf@20: }
olaf@31: 
olaf@31: UcxMapIterator ucx_map_iterator(UcxMap *map) {
olaf@31:     UcxMapIterator i;
olaf@31:     i.map = map;
olaf@31:     i.cur = NULL;
olaf@31:     i.index = 0;
olaf@31:     return i;
olaf@31: }
olaf@31: 
olaf@31: int ucx_map_iter_next(UcxMapIterator *i, void **elm) {
olaf@31:     UcxMapElement *e = i->cur;
olaf@31:     
olaf@31:     if(e == NULL) {
olaf@31:         e = i->map->map[0];
olaf@31:     } else {
olaf@31:         e = e->next;
olaf@31:     }
olaf@31:     
olaf@31:     while(i->index < i->map->size) {
olaf@31:         if(e != NULL) {
olaf@31:             if(e->data != NULL) {
olaf@31:                 i->cur = e;
olaf@31:                 *elm = e->data;
olaf@31:                 return 0;
olaf@31:             }
olaf@31: 
olaf@31:             e = e->next;
olaf@31:         } else {
olaf@31:             i->index++;
olaf@31:             
olaf@31:             if(i->index < i->map->size) {
olaf@31:                 e = i->map->map[i->index];
olaf@31:             }
olaf@31:         }
olaf@31:     }
olaf@31:     
olaf@31:     return 1;
olaf@31: }
universe@42: 
universe@42: int ucx_map_load(UcxMap *map, FILE *f) {
universe@42: 
universe@42:     char c; int r, n;
universe@42: 
universe@42:     char *key, *value;
universe@42: 
universe@42:     while ((c = (char) fgetc(f)) > 0) {
universe@42:         /* Discard leading spaces and comments */
universe@42:         if (c == ' ') continue;
universe@42:         if (c == '#' || c == '!') {
universe@42:             while ((c = (char) fgetc(f)) > 0) {
universe@42:                 if (c == '\n') break;
universe@42:             }
universe@42:             continue;
universe@42:         }
universe@42: 
universe@42:         /* read into key buffer */
universe@42:         n = 16;
universe@42:         key = malloc(n);
universe@42:         r = 0;
universe@42:         do {
universe@42:             if (c == '=') break;
universe@42:             if (r > n - 2) {
universe@42:                 n *= 2;
universe@42:                 key = realloc(key, n);
universe@42:             }
universe@42:             key[r] = c;
universe@42:             r++;
universe@42:         } while ((c = (char) fgetc(f)) > 0);
universe@42:         if (c == 0) {
universe@42:             free(key);
universe@42:             return 1;
universe@42:         }
universe@42:         key[r] = 0;
universe@42: 
universe@42:         /* read into value buffer */
universe@42:         n = 64;
universe@42:         value = malloc(n);
universe@42:         r = 0;
universe@42:         while ((c = (char) fgetc(f)) > 0) {
universe@42:             if (c == '\n') break;
universe@42:             if (r > n - 1) {
universe@42:                 n *= 2;
universe@42:                 value = realloc(value, n);
universe@42:             }
universe@42:             value[r] = c;
universe@42:             r++;
universe@42:         }
universe@42:         value = realloc(value, r+1);
universe@42:         value[r] = 0;
universe@42: 
universe@42:         ucx_map_cstr_put(map, key, value);
universe@42:         free(key);
universe@42:     }
universe@42: 
universe@42:     return 0;
universe@42: }
universe@42: 
universe@42: int ucx_map_store(UcxMap *map, FILE *f) {
universe@42:     UcxMapIterator iter = ucx_map_iterator(map);
universe@42:     char *k, *v;
universe@42:     sstr_t key, value;
universe@42:     int written;
universe@42: 
universe@42:     UCX_MAP_FOREACH(v, iter) {
universe@42:         k = (char*) iter.cur->key.data;
universe@42:         key = sstr(k); value = sstr(v);
universe@42: 
universe@42:         written = 0;
universe@42:         written += fwrite(key.ptr, 1, key.length, f);
universe@42:         written += fwrite(" = ", 1, 3, f);
universe@42:         written += fwrite(value.ptr, 1, value.length, f);
universe@42:         written += fwrite("\n", 1, 1, f);
universe@42: 
universe@42:         if (written != key.length + value.length + 4) return 1;
universe@42:     }
universe@42: 
universe@42:     return 0;
universe@42: }