Mercurial > hg > webserver / file revision

/*
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "map.h"

UcxMap *ucx_map_new(size_t size) {
    UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap));
    if(map == NULL) {
        return NULL;
    }

    map->map = (UcxMapElement*)calloc(size, sizeof(UcxMapElement));
    if(map->map == NULL) {
        free(map);
        return NULL;
    }
    map->size = size;

    return map;
}

int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
    if(key.hash == 0) {
        key.hash = ucx_hash((char*)key.data, key.len);
    }
    void *kd = calloc(1, key.len);
    memcpy(kd, key.data, key.len);
    key.data = kd;

    UcxMapElement *elm = &map->map[key.hash%map->size];
    if(elm->key.hash != 0) {
        UcxMapElement *e = elm;
        for(;;) {
            /* check if the key is already in use */
            if(key.hash == e->key.hash) {
                int n = (key.len > elm->key.len) ? elm->key.len : key.len;
                if(memcmp(elm->key.data, key.data, n) == 0) {
                    /* use elm as storage place */
                    elm = e;
                    break;
                }
            }

            /* check if this is the last element */
            if(e->next == NULL) {
                /* create new element */
                UcxMapElement *en = (UcxMapElement*)malloc(sizeof(UcxMapElement));
                if(en == NULL) {
                    return -1;
                }
                e->next = en;
                elm = en;
                break;
            }

            e = e->next;
        }
    }

    elm->key = key;
    elm->data = data;

    return 0;
}

void* ucx_map_get(UcxMap *map, UcxKey key) {
    if(key.hash == 0) {
        key.hash = ucx_hash((char*)key.data, key.len);
    }

    UcxMapElement *elm = &map->map[key.hash%map->size];
    while(elm != NULL) {
        if(elm->key.hash == key.hash) {
            int n = (key.len > elm->key.len) ? elm->key.len : key.len;
            if(memcmp(elm->key.data, key.data, n) == 0) {
                return elm->data;
            }
        }
        elm = elm->next;
    }

    return NULL;
}

UcxKey ucx_key(void *data, size_t len) {
    UcxKey key;
    key.data = data;
    key.len = len;
    key.hash = ucx_hash(data, len);
    return key;
}


int ucx_hash(char *data, size_t len) {
    /* murmur hash 2 */

    int m = 0x5bd1e995;
    int r = 24;

    int h = 25 ^ len;

    int i = 0;
    while (len >= 4) {
        int k = data[i + 0] & 0xFF;
        k |= (data[i + 1] & 0xFF) << 8;
        k |= (data[i + 2] & 0xFF) << 16;
        k |= (data[i + 3] & 0xFF) << 24;

        k *= m;
        k ^= k >> r;
        k *= m;

        h *= m;
        h ^= k;

        i += 4;
        len -= 4;
    }

    switch (len) {
        case 3: h ^= (data[i + 2] & 0xFF) << 16;
        case 2: h ^= (data[i + 1] & 0xFF) << 8;
        case 1: h ^= (data[i + 0] & 0xFF); h *= m;
    }

    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return h;
}