ucx: ucx/map.c@dddb9348ea42

     1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

     3  *

     4  * Copyright 2013 Olaf Wintermann. All rights reserved.

     5  *

     6  * Redistribution and use in source and binary forms, with or without

     7  * modification, are permitted provided that the following conditions are met:

     8  *

     9  *   1. Redistributions of source code must retain the above copyright

    10  *      notice, this list of conditions and the following disclaimer.

    11  *

    12  *   2. Redistributions in binary form must reproduce the above copyright

    13  *      notice, this list of conditions and the following disclaimer in the

    14  *      documentation and/or other materials provided with the distribution.

    15  *

    16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

    20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    26  * POSSIBILITY OF SUCH DAMAGE.

    27  */

    29 #include <stdlib.h>

    30 #include <string.h>

    32 #include "map.h"

    34 UcxMap *ucx_map_new(size_t size) {

    35     return ucx_map_new_a(NULL, size);

    36 }

    38 UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size) {

    39     if(size == 0) {

    40         size = 16;

    41     }

    43     if(!allocator) {

    44         allocator = ucx_default_allocator();

    45     }

    47     UcxMap *map = (UcxMap*)allocator->malloc(allocator->pool, sizeof(UcxMap));

    48     if (!map) {

    49         return NULL;

    50     }

    52     map->allocator = allocator;

    53     map->map = (UcxMapElement**)allocator->calloc(

    54             allocator->pool,

    55             size,

    56             sizeof(UcxMapElement*));

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

    58         allocator->free(allocator->pool, map);

    59         return NULL;

    60     }

    61     map->size = size;

    62     map->count = 0;

    64     return map;

    65 }

    67 static void ucx_map_free_elmlist(UcxMap *map) {

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

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

    70         if (elem != NULL) {

    71             do {

    72                 UcxMapElement *next = elem->next;

    73                 map->allocator->free(map->allocator->pool, elem->key.data);

    74                 map->allocator->free(map->allocator->pool, elem);

    75                 elem = next;

    76             } while (elem != NULL);

    77         }

    78     }

    79     map->allocator->free(map->allocator->pool, map->map);

    80 }

    82 void ucx_map_free(UcxMap *map) {

    83     ucx_map_free_elmlist(map);

    84     map->allocator->free(map->allocator->pool, map);

    85 }

    87 int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to,

    88         copy_func fnc, void *data) {

    89     UcxMapIterator i = ucx_map_iterator(from);

    90     void *value;

    91     UCX_MAP_FOREACH(key, value, i) {

    92         if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) {

    93             return 1;

    94         }

    95     }

    96     return 0;

    97 }

    99 UcxMap *ucx_map_clone(UcxMap *map, copy_func fnc, void *data) {

   100     size_t bs = (map->count * 5) >> 1;

   101     UcxMap *newmap = ucx_map_new(bs > map->size ? bs : map->size);

   102     if (!newmap) {

   103         return NULL;

   104     }

   105     ucx_map_copy(map, newmap, fnc, data);

   106     return newmap;

   107 }

   109 int ucx_map_rehash(UcxMap *map) {

   110     size_t load = (map->size * 3) >> 2;

   111     if (map->count > load) {

   112         UcxMap oldmap;

   113         oldmap.map = map->map;

   114         oldmap.size = map->size;

   115         oldmap.count = map->count;

   116         oldmap.allocator = map->allocator;

   118         map->size = (map->count * 5) >> 1;

   119         map->map = (UcxMapElement**)map->allocator->calloc(

   120                 map->allocator->pool,

   121                 map->size,

   122                 sizeof(UcxMapElement*));

   123         if (!map->map) {

   124             *map = oldmap;

   125             return 1;

   126         }

   127         map->count = 0;

   128         ucx_map_copy(&oldmap, map, NULL, NULL);

   130         /* free the UcxMapElement list of oldmap */

   131         ucx_map_free_elmlist(&oldmap);

   132     }

   133     return 0;

   134 }

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

   137     UcxAllocator *allocator = map->allocator;

   139     if (key.hash == 0) {

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

   141     }

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

   144     UcxMapElement *restrict elm = map->map[slot];

   145     UcxMapElement *restrict prev = NULL;

   147     while (elm && elm->key.hash < key.hash) {

   148         prev = elm;

   149         elm = elm->next;

   150     }

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

   153         UcxMapElement *e = (UcxMapElement*)allocator->malloc(

   154                 allocator->pool,

   155                 sizeof(UcxMapElement));

   156         if (!e) {

   157             return -1;

   158         }

   159         e->key.data = NULL;

   160         if (prev) {

   161             prev->next = e;

   162         } else {

   163             map->map[slot] = e;

   164         }

   165         e->next = elm;

   166         elm = e;

   167     }

   169     if (!elm->key.data) {

   170         void *kd = allocator->malloc(allocator->pool, key.len);

   171         if (!kd) {

   172             return -1;

   173         }

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

   175         key.data = kd;

   176         elm->key = key;

   177         map->count++;

   178     }

   179     elm->data = data;

   181     return 0;

   182 }

   184 void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) {

   185     if(key.hash == 0) {

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

   187     }

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

   190     UcxMapElement *restrict elm = map->map[slot];

   191     UcxMapElement *restrict pelm = NULL;

   192     while (elm && elm->key.hash <= key.hash) {

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

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

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

   196                 void *data = elm->data;

   197                 if (remove) {

   198                     if (pelm) {

   199                         pelm->next = elm->next;

   200                     } else {

   201                         map->map[slot] = elm->next;

   202                     }

   203                     map->allocator->free(map->allocator->pool, elm);

   204                     map->count--;

   205                 }

   207                 return data;

   208             }

   209         }

   210         pelm = elm;

   211         elm = pelm->next;

   212     }

   214     return NULL;

   215 }

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

   218     return ucx_map_get_and_remove(map, key, 0);

   219 }

   221 void *ucx_map_remove(UcxMap *map, UcxKey key) {

   222     return ucx_map_get_and_remove(map, key, 1);

   223 }

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

   226     UcxKey key;

   227     key.data = data;

   228     key.len = len;

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

   230     return key;

   231 }

   234 int ucx_hash(const char *data, size_t len) {

   235     /* murmur hash 2 */

   237     int m = 0x5bd1e995;

   238     int r = 24;

   240     int h = 25 ^ len;

   242     int i = 0;

   243     while (len >= 4) {

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

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

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

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

   249         k *= m;

   250         k ^= k >> r;

   251         k *= m;

   253         h *= m;

   254         h ^= k;

   256         i += 4;

   257         len -= 4;

   258     }

   260     switch (len) {

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

   262         /* no break */

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

   264         /* no break */

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

   266         /* no break */

   267     }

   269     h ^= h >> 13;

   270     h *= m;

   271     h ^= h >> 15;

   273     return h;

   274 }

   276 UcxMapIterator ucx_map_iterator(UcxMap *map) {

   277     UcxMapIterator i;

   278     i.map = map;

   279     i.cur = NULL;

   280     i.index = 0;

   281     return i;

   282 }

   284 int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm) {

   285     UcxMapElement *e = i->cur;

   287     if (e) {

   288         e = e->next;

   289     } else {

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

   291     }

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

   294         if (e) {

   295             if (e->data) {

   296                 i->cur = e;

   297                 *elm = e->data;

   298                 *key = e->key;

   299                 return 1;

   300             }

   302             e = e->next;

   303         } else {

   304             i->index++;

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

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

   308             }

   309         }

   310     }

   312     return 0;

   313 }

Mercurial > hg > ucx / file revision

ucx/map.c@dddb9348ea42

ucx/map.c