ucx: ucx/map.c@bce0d7f2912b

     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 void ucx_map_free(UcxMap *map) {

    27     for (size_t n = 0 ; n < map->size ; n++) {

    28         UcxMapElement *elem = map->map[n];

    29         if (elem != NULL) {

    30             do {

    31                 UcxMapElement *next = elem->next;

    32                 free(elem);

    33                 elem = next;

    34             } while (elem != NULL);

    35         }

    36     }

    37     free(map);

    38 }

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

    41     if(key.hash == 0) {

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

    43     }

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

    45     if (kd == NULL) {

    46         return -1;

    47     }

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

    49     key.data = kd;

    51     size_t slot = key.hash%map->size;

    52     UcxMapElement *elm = map->map[slot];

    53     UcxMapElement *prev = NULL;

    55     while (elm != NULL && elm->key.hash < key.hash) {

    56         prev = elm;

    57         elm = elm->next;

    58     }

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

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

    62         if(e == NULL) {

    63             return -1;

    64         }

    65         if (prev == NULL) {

    66             map->map[slot] = e;

    67         } else {

    68             prev->next = e;

    69         }

    70         e->next = elm;

    71         elm = e;

    72     }

    74     elm->key = key;

    75     elm->data = data;

    77     return 0;

    78 }

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

    81     if(key.hash == 0) {

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

    83     }

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

    86     while (elm != NULL && elm->key.hash <= key.hash) {

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

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

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

    90                 return elm->data;

    91             }

    92         }

    93         elm = elm->next;

    94     }

    96     return NULL;

    97 }

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

   100     UcxKey key;

   101     key.data = data;

   102     key.len = len;

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

   104     return key;

   105 }

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

   109     /* murmur hash 2 */

   111     int m = 0x5bd1e995;

   112     int r = 24;

   114     int h = 25 ^ len;

   116     int i = 0;

   117     while (len >= 4) {

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

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

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

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

   123         k *= m;

   124         k ^= k >> r;

   125         k *= m;

   127         h *= m;

   128         h ^= k;

   130         i += 4;

   131         len -= 4;

   132     }

   134     switch (len) {

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

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

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

   138     }

   140     h ^= h >> 13;

   141     h *= m;

   142     h ^= h >> 15;

   144     return h;

   145 }

Mercurial > hg > ucx / file revision