ucx: ucx/map.c@bce0d7f2912b (annotated)

ucx/map.c@bce0d7f2912b (annotated)

ucx/map.c

Tue, 21 Feb 2012 01:13:17 +0100

author: Mike Becker <universe@uap-core.de>
date: Tue, 21 Feb 2012 01:13:17 +0100
changeset 29: bce0d7f2912b
parent 20: db7d9860dbbd
child 30: 23bb65cbf7a4
permissions: -rw-r--r--

fixed map with the help of new tests

 /*
  *
  */
 #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;
 }
 void ucx_map_free(UcxMap *map) {
     for (size_t n = 0 ; n < map->size ; n++) {
         UcxMapElement *elem = map->map[n];
         if (elem != NULL) {
             do {
                 UcxMapElement *next = elem->next;
                 free(elem);
                 elem = next;
             } while (elem != NULL);
         }
     }
     free(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 = malloc(key.len);
     if (kd == NULL) {
         return -1;
     }
     memcpy(kd, key.data, key.len);
     key.data = kd;
     size_t slot = key.hash%map->size;
     UcxMapElement *elm = map->map[slot];
     UcxMapElement *prev = NULL;
     while (elm != NULL && elm->key.hash < key.hash) {
         prev = elm;
         elm = elm->next;
     }
     if (elm == NULL || elm->key.hash != key.hash) {
         UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement));
         if(e == NULL) {
             return -1;
         }
         if (prev == NULL) {
             map->map[slot] = e;
         } else {
             prev->next = e;
         }
         e->next = elm;
         elm = e;
     }
     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 && elm->key.hash <= key.hash) {
         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;
 }

Mercurial > hg > ucx / annotate

ucx/map.c@bce0d7f2912b (annotated)

ucx/map.c