Mercurial > hg > webserver / file revision

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2011 Olaf Wintermann. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

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

#include "map.h"

hashmap_t* hashmap_new(size_t size) {
    hashmap_t *map = malloc(sizeof(hashmap_t));
    map->map = calloc(size, sizeof(sdlist_t));
    map->len = size;

    return map;
}

void hashmap_free(hashmap_t *map) {
    for(int i=0;i<map->len;i++) {
        sdlist_t *list = map->map[0];
        while(list != NULL) {
            hashmap_elm_t *elm = (hashmap_elm_t*)list->data;
            free(elm->key.ptr);
            sdlist_t *l = list;
            list = list->next;
            free(elm);
            free(l);
        }
    }
    free(map->map);
    free(map);
}


void hashmap_put(hashmap_t *map, sstr_t key, void *value) {
    int hash = hashmap_hash(key.ptr, key.length);

    sdlist_t *list = map->map[hash%map->len];

    sstr_t k = sstrdub(key);

    hashmap_elm_t *elm = malloc(sizeof(hashmap_elm_t));
    elm->data = value;
    elm->hash = hash;
    elm->key = k;

    map->map[hash%map->len] = sdlist_add(list, elm);
}

void* hashmap_get(hashmap_t *map, sstr_t key) {
    int hash = hashmap_hash(key.ptr, key.length);
    sdlist_t *list = map->map[hash%map->len];
    void *value = NULL;

    while (list != NULL) {
        hashmap_elm_t *elm = list->data;
        if (elm->hash == hash &&
                strncmp(key.ptr, elm->key.ptr, key.length) == 0) {
            value = elm->data;
            break;
        }
        list = list->next;
    }

    return value;
}




/* hash function */
int hashmap_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;
}