ucx: ucx/map.c@db7d9860dbbd

     1 /*

     2  *

     3  */

     5 #include <stdlib.h>

     6 #include <string.h>

     8 #include "map.h"

    10 UcxMap *ucx_map_new(size_t size) {

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

    12     if(map == NULL) {

    13         return NULL;

    14     }

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

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

    18         free(map);

    19         return NULL;

    20     }

    21     map->size = size;

    23     return map;

    24 }

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

    27     if(key.hash == 0) {

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

    29     }

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

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

    32     key.data = kd;

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

    35     if(elm->next != NULL) {

    36         while(elm->next != NULL) {

    37             elm = elm->next;

    38         }

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

    40         if(e == NULL) {

    41             return -1;

    42         }

    43         elm->next = e;

    44         elm = e;

    45     }

    47     elm->key = key;

    48     elm->data = data;

    50     return 0;

    51 }

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

    54     if(key.hash == 0) {

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

    56     }

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

    59     while(elm != NULL) {

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

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

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

    63                 return elm->data;

    64             }

    65         }

    66         elm = elm->next;

    67     }

    69     return NULL;

    70 }

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

    73     UcxKey key;

    74     key.data = data;

    75     key.len = len;

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

    77     return key;

    78 }

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

    82     /* murmur hash 2 */

    84     int m = 0x5bd1e995;

    85     int r = 24;

    87     int h = 25 ^ len;

    89     int i = 0;

    90     while (len >= 4) {

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

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

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

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

    96         k *= m;

    97         k ^= k >> r;

    98         k *= m;

   100         h *= m;

   101         h ^= k;

   103         i += 4;

   104         len -= 4;

   105     }

   107     switch (len) {

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

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

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

   111     }

   113     h ^= h >> 13;

   114     h *= m;

   115     h ^= h >> 15;

   117     return h;

   118 }

Mercurial > hg > ucx / file revision