Mercurial > hg > ucx / file diff

     1.1 --- a/ucx/map.c	Sat Dec 31 22:48:28 2011 +0100
     1.2 +++ b/ucx/map.c	Thu Jan 05 14:53:54 2012 +0100
     1.3 @@ -1,1 +1,118 @@
     1.4 +/*
     1.5 + *
     1.6 + */
     1.7  
     1.8 +#include <stdlib.h>
     1.9 +#include <string.h>
    1.10 +
    1.11 +#include "map.h"
    1.12 +
    1.13 +UcxMap *ucx_map_new(size_t size) {
    1.14 +    UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap));
    1.15 +    if(map == NULL) {
    1.16 +        return NULL;
    1.17 +    }
    1.18 +
    1.19 +    map->map = (UcxMapElement*)calloc(size, sizeof(UcxMapElement));
    1.20 +    if(map->map == NULL) {
    1.21 +        free(map);
    1.22 +        return NULL;
    1.23 +    }
    1.24 +    map->size = size;
    1.25 +
    1.26 +    return map;
    1.27 +}
    1.28 +
    1.29 +int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
    1.30 +    if(key.hash == 0) {
    1.31 +        key.hash = ucx_hash((char*)key.data, key.len);
    1.32 +    }
    1.33 +    void *kd = malloc(key.len);
    1.34 +    memcpy(kd, key.data, key.len);
    1.35 +    key.data = kd;
    1.36 +
    1.37 +    UcxMapElement *elm = &map->map[key.hash%map->size];
    1.38 +    if(elm->next != NULL) {
    1.39 +        while(elm->next != NULL) {
    1.40 +            elm = elm->next;
    1.41 +        }
    1.42 +        UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement));
    1.43 +        if(e == NULL) {
    1.44 +            return -1;
    1.45 +        }
    1.46 +        elm->next = e;
    1.47 +        elm = e;
    1.48 +    }
    1.49 +
    1.50 +    elm->key = key;
    1.51 +    elm->data = data;
    1.52 +
    1.53 +    return 0;
    1.54 +}
    1.55 +
    1.56 +void* ucx_map_get(UcxMap *map, UcxKey key) {
    1.57 +    if(key.hash == 0) {
    1.58 +        key.hash = ucx_hash((char*)key.data, key.len);
    1.59 +    }
    1.60 +    
    1.61 +    UcxMapElement *elm = &map->map[key.hash%map->size];
    1.62 +    while(elm != NULL) {
    1.63 +        if(elm->key.hash == key.hash) {
    1.64 +            int n = (key.len > elm->key.len) ? elm->key.len : key.len;
    1.65 +            if(memcmp(elm->key.data, key.data, n) == 0) {
    1.66 +                return elm->data;
    1.67 +            }
    1.68 +        }
    1.69 +        elm = elm->next;
    1.70 +    }
    1.71 +
    1.72 +    return NULL;
    1.73 +}
    1.74 +
    1.75 +UcxKey ucx_key(void *data, size_t len) {
    1.76 +    UcxKey key;
    1.77 +    key.data = data;
    1.78 +    key.len = len;
    1.79 +    key.hash = ucx_hash(data, len);
    1.80 +    return key;
    1.81 +}
    1.82 +
    1.83 +
    1.84 +int ucx_hash(char *data, size_t len) {
    1.85 +    /* murmur hash 2 */
    1.86 +
    1.87 +    int m = 0x5bd1e995;
    1.88 +    int r = 24;
    1.89 +
    1.90 +    int h = 25 ^ len;
    1.91 +
    1.92 +    int i = 0;
    1.93 +    while (len >= 4) {
    1.94 +        int k = data[i + 0] & 0xFF;
    1.95 +        k |= (data[i + 1] & 0xFF) << 8;
    1.96 +        k |= (data[i + 2] & 0xFF) << 16;
    1.97 +        k |= (data[i + 3] & 0xFF) << 24;
    1.98 +
    1.99 +        k *= m;
   1.100 +        k ^= k >> r;
   1.101 +        k *= m;
   1.102 +
   1.103 +        h *= m;
   1.104 +        h ^= k;
   1.105 +
   1.106 +        i += 4;
   1.107 +        len -= 4;
   1.108 +    }
   1.109 +
   1.110 +    switch (len) {
   1.111 +        case 3: h ^= (data[i + 2] & 0xFF) << 16;
   1.112 +        case 2: h ^= (data[i + 1] & 0xFF) << 8;
   1.113 +        case 1: h ^= (data[i + 0] & 0xFF); h *= m;
   1.114 +    }
   1.115 +
   1.116 +    h ^= h >> 13;
   1.117 +    h *= m;
   1.118 +    h ^= h >> 15;
   1.119 +
   1.120 +    return h;
   1.121 +}