ucx: src/map.c@871a8ffe6c9d

     1 /*

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

     3  *

     4  * Copyright 2017 Mike Becker, 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 "ucx/map.h"

    31 #include <stdlib.h>

    32 #include <string.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*)almalloc(allocator, sizeof(UcxMap));

    48     if (!map) {

    49         return NULL;

    50     }

    52     map->allocator = allocator;

    53     map->map = (UcxMapElement**)alcalloc(

    54             allocator, size, sizeof(UcxMapElement*));

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

    56         alfree(allocator, map);

    57         return NULL;

    58     }

    59     map->size = size;

    60     map->count = 0;

    62     return map;

    63 }

    65 static void ucx_map_free_elmlist_contents(UcxMap *map) {

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

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

    68         if (elem != NULL) {

    69             do {

    70                 UcxMapElement *next = elem->next;

    71                 alfree(map->allocator, elem->key.data);

    72                 alfree(map->allocator, elem);

    73                 elem = next;

    74             } while (elem != NULL);

    75         }

    76     }

    77 }

    79 void ucx_map_free(UcxMap *map) {

    80     ucx_map_free_elmlist_contents(map);

    81     alfree(map->allocator, map->map);

    82     alfree(map->allocator, map);

    83 }

    85 void ucx_map_free_content(UcxMap *map, ucx_destructor destr) {

    86     UcxMapIterator iter = ucx_map_iterator(map);

    87     void *val;

    88     UCX_MAP_FOREACH(key, val, iter) {

    89         if (destr) {

    90             destr(val);

    91         } else {

    92             alfree(map->allocator, val);

    93         }

    94     }

    95 }

    97 void ucx_map_clear(UcxMap *map) {

    98     if (map->count == 0) {

    99         return; // nothing to do

   100     }

   101     ucx_map_free_elmlist_contents(map);

   102     memset(map->map, 0, map->size*sizeof(UcxMapElement*));

   103     map->count = 0;

   104 }

   106 int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data) {

   107     UcxMapIterator i = ucx_map_iterator(from);

   108     void *value;

   109     UCX_MAP_FOREACH(key, value, i) {

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

   111             return 1;

   112         }

   113     }

   114     return 0;

   115 }

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

   118     return ucx_map_clone_a(ucx_default_allocator(), map, fnc, data);

   119 }

   121 UcxMap *ucx_map_clone_a(UcxAllocator *allocator,

   122         UcxMap const *map, copy_func fnc, void *data) {

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

   124     UcxMap *newmap = ucx_map_new_a(allocator, bs > map->size ? bs : map->size);

   125     if (!newmap) {

   126         return NULL;

   127     }

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

   129     return newmap;

   130 }

   132 int ucx_map_rehash(UcxMap *map) {

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

   134     if (map->count > load) {

   135         UcxMap oldmap;

   136         oldmap.map = map->map;

   137         oldmap.size = map->size;

   138         oldmap.count = map->count;

   139         oldmap.allocator = map->allocator;

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

   142         map->map = (UcxMapElement**)alcalloc(

   143                 map->allocator, map->size, sizeof(UcxMapElement*));

   144         if (!map->map) {

   145             *map = oldmap;

   146             return 1;

   147         }

   148         map->count = 0;

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

   151         /* free the UcxMapElement list of oldmap */

   152         ucx_map_free_elmlist_contents(&oldmap);

   153         alfree(map->allocator, oldmap.map);

   154     }

   155     return 0;

   156 }

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

   159     UcxAllocator *allocator = map->allocator;

   161     if (key.hash == 0) {

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

   163     }

   165     struct UcxMapKey mapkey;

   166     mapkey.hash = key.hash;

   168     size_t slot = mapkey.hash%map->size;

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

   170     UcxMapElement *prev = NULL;

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

   173         prev = elm;

   174         elm = elm->next;

   175     }

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

   178         UcxMapElement *e = (UcxMapElement*)almalloc(

   179                 allocator, sizeof(UcxMapElement));

   180         if (!e) {

   181             return -1;

   182         }

   183         e->key.data = NULL;

   184         if (prev) {

   185             prev->next = e;

   186         } else {

   187             map->map[slot] = e;

   188         }

   189         e->next = elm;

   190         elm = e;

   191     }

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

   194         void *kd = almalloc(allocator, key.len);

   195         if (!kd) {

   196             return -1;

   197         }

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

   199         mapkey.data = kd;

   200         mapkey.len = key.len;

   201         elm->key = mapkey;

   202         map->count++;

   203     }

   204     elm->data = data;

   206     return 0;

   207 }

   209 static void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, int remove) {

   210     if(key.hash == 0) {

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

   212     }

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

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

   216     UcxMapElement *pelm = NULL;

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

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

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

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

   221                 void *data = elm->data;

   222                 if (remove) {

   223                     if (pelm) {

   224                         pelm->next = elm->next;

   225                     } else {

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

   227                     }

   228                     alfree(map->allocator, elm->key.data);

   229                     alfree(map->allocator, elm);

   230                     map->count--;

   231                 }

   233                 return data;

   234             }

   235         }

   236         pelm = elm;

   237         elm = pelm->next;

   238     }

   240     return NULL;

   241 }

   243 void *ucx_map_get(UcxMap const *map, UcxKey key) {

   244     return ucx_map_get_and_remove((UcxMap *)map, key, 0);

   245 }

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

   248     return ucx_map_get_and_remove(map, key, 1);

   249 }

   251 UcxKey ucx_key(const void *data, size_t len) {

   252     UcxKey key;

   253     key.data = data;

   254     key.len = len;

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

   256     return key;

   257 }

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

   261     /* murmur hash 2 */

   263     int m = 0x5bd1e995;

   264     int r = 24;

   266     int h = 25 ^ len;

   268     int i = 0;

   269     while (len >= 4) {

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

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

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

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

   275         k *= m;

   276         k ^= k >> r;

   277         k *= m;

   279         h *= m;

   280         h ^= k;

   282         i += 4;

   283         len -= 4;

   284     }

   286     switch (len) {

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

   288         /* no break */

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

   290         /* no break */

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

   292         /* no break */

   293     }

   295     h ^= h >> 13;

   296     h *= m;

   297     h ^= h >> 15;

   299     return h;

   300 }

   302 UcxMapIterator ucx_map_iterator(UcxMap const *map) {

   303     UcxMapIterator i;

   304     i.map = map;

   305     i.cur = NULL;

   306     i.index = 0;

   307     return i;

   308 }

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

   311     UcxMapElement *e = i->cur;

   313     if (e) {

   314         e = e->next;

   315     } else {

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

   317     }

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

   320         if (e) {

   321             if (e->data) {

   322                 i->cur = e;

   323                 *elm = e->data;

   324                 key->data = e->key.data;

   325                 key->hash = e->key.hash;

   326                 key->len = e->key.len;

   327                 return 1;

   328             }

   330             e = e->next;

   331         } else {

   332             i->index++;

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

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

   336             }

   337         }

   338     }

   340     return 0;

   341 }

   343 UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second,

   344                       copy_func cpfnc, void* cpdata) {

   345     return ucx_map_union_a(ucx_default_allocator(),

   346             first, second, cpfnc, cpdata);

   347 }

   349 UcxMap* ucx_map_union_a(UcxAllocator *allocator,

   350                         const UcxMap *first, const UcxMap *second,

   351                         copy_func cpfnc, void* cpdata) {

   352     UcxMap* result = ucx_map_clone_a(allocator, first, cpfnc, cpdata);

   353     ucx_map_copy(second, result, cpfnc, cpdata);

   354     return result;

   355 }

   357 UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second,

   358                              copy_func cpfnc, void* cpdata) {

   359     return ucx_map_intersection_a(ucx_default_allocator(),

   360             first, second, cpfnc, cpdata);

   361 }

   363 UcxMap* ucx_map_intersection_a(UcxAllocator *allocator,

   364                                const UcxMap *first, const UcxMap *second,

   365                                copy_func cpfnc, void* cpdata) {

   366     UcxMap *result = ucx_map_new_a(allocator, first->size < second->size ?

   367             first->size : second->size);

   369     UcxMapIterator iter = ucx_map_iterator(first);

   370     void* value;

   371     UCX_MAP_FOREACH(key, value, iter) {

   372         if (ucx_map_get(second, key)) {

   373             ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value);

   374         }

   375     }

   377     return result;

   378 }

   380 UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second,

   381                            copy_func cpfnc, void* cpdata) {

   382     return ucx_map_difference_a(ucx_default_allocator(),

   383             first, second, cpfnc, cpdata);

   384 }

   386 UcxMap* ucx_map_difference_a(UcxAllocator *allocator,

   387                              const UcxMap *first, const UcxMap *second,

   388                              copy_func cpfnc, void* cpdata) {

   390     UcxMap *result = ucx_map_new_a(allocator, first->size - second->count);

   392     UcxMapIterator iter = ucx_map_iterator(first);

   393     void* value;

   394     UCX_MAP_FOREACH(key, value, iter) {

   395         if (!ucx_map_get(second, key)) {

   396             ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value);

   397         }

   398     }

   400     ucx_map_rehash(result);

   401     return result;

   402 }

Mercurial > hg > ucx / file revision

src/map.c@871a8ffe6c9d

src/map.c