ucx: ucx/map.c@91ac86557290

     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->key.data);

    33                 free(elem);

    34                 elem = next;

    35             } while (elem != NULL);

    36         }

    37     }

    38     free(map->map);

    39     free(map);

    40 }

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

    43     if(key.hash == 0) {

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

    45     }

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

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

    49     UcxMapElement *prev = NULL;

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

    52         prev = elm;

    53         elm = elm->next;

    54     }

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

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

    58         if(e == NULL) {

    59             return -1;

    60         }

    61         e->key.data = NULL;

    62         if (prev == NULL) {

    63             map->map[slot] = e;

    64         } else {

    65             prev->next = e;

    66         }

    67         e->next = elm;

    68         elm = e;

    69     }

    71     if(elm->key.data == NULL) {

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

    73         if (kd == NULL) {

    74             return -1;

    75         }

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

    77         key.data = kd;

    78         elm->key = key;

    79     }

    80     elm->data = data;

    82     return 0;

    83 }

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

    86     if(key.hash == 0) {

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

    88     }

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

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

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

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

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

    95                 return elm->data;

    96             }

    97         }

    98         elm = elm->next;

    99     }

   101     return NULL;

   102 }

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

   105     UcxKey key;

   106     key.data = data;

   107     key.len = len;

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

   109     return key;

   110 }

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

   114     /* murmur hash 2 */

   116     int m = 0x5bd1e995;

   117     int r = 24;

   119     int h = 25 ^ len;

   121     int i = 0;

   122     while (len >= 4) {

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

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

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

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

   128         k *= m;

   129         k ^= k >> r;

   130         k *= m;

   132         h *= m;

   133         h ^= k;

   135         i += 4;

   136         len -= 4;

   137     }

   139     switch (len) {

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

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

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

   143     }

   145     h ^= h >> 13;

   146     h *= m;

   147     h ^= h >> 15;

   149     return h;

   150 }

   152 UcxMapIterator ucx_map_iterator(UcxMap *map) {

   153     UcxMapIterator i;

   154     i.map = map;

   155     i.cur = NULL;

   156     i.index = 0;

   157     return i;

   158 }

   160 int ucx_map_iter_next(UcxMapIterator *i, void **elm) {

   161     UcxMapElement *e = i->cur;

   163     if(e == NULL) {

   164         e = i->map->map[0];

   165     } else {

   166         e = e->next;

   167     }

   169     while(i->index < i->map->size) {

   170         if(e != NULL) {

   171             if(e->data != NULL) {

   172                 i->cur = e;

   173                 *elm = e->data;

   174                 return 0;

   175             }

   177             e = e->next;

   178         } else {

   179             i->index++;

   181             if(i->index < i->map->size) {

   182                 e = i->map->map[i->index];

   183             }

   184         }

   185     }

   187     return 1;

   188 }

Mercurial > hg > ucx / file revision