ucx: src/map.c@fbc33813265b

UcxMap now separates internal non-const keys from public const keys

This simplifies function calls with constant keys like scstr_t or const char*.

     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 *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 *map, copy_func fnc, void *data) {

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

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

   120     if (!newmap) {

   121         return NULL;

   122     }

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

   124     return newmap;

   125 }

   127 int ucx_map_rehash(UcxMap *map) {

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

   129     if (map->count > load) {

   130         UcxMap oldmap;

   131         oldmap.map = map->map;

   132         oldmap.size = map->size;

   133         oldmap.count = map->count;

   134         oldmap.allocator = map->allocator;

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

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

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

   139         if (!map->map) {

   140             *map = oldmap;

   141             return 1;

   142         }

   143         map->count = 0;

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

   146         /* free the UcxMapElement list of oldmap */

   147         ucx_map_free_elmlist_contents(&oldmap);

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

   149     }

   150     return 0;

   151 }

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

   154     UcxAllocator *allocator = map->allocator;

   156     if (key.hash == 0) {

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

   158     }

   160     struct UcxMapKey mapkey;

   161     mapkey.hash = key.hash;

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

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

   165     UcxMapElement *prev = NULL;

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

   168         prev = elm;

   169         elm = elm->next;

   170     }

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

   173         UcxMapElement *e = (UcxMapElement*)almalloc(

   174                 allocator, sizeof(UcxMapElement));

   175         if (!e) {

   176             return -1;

   177         }

   178         e->key.data = NULL;

   179         if (prev) {

   180             prev->next = e;

   181         } else {

   182             map->map[slot] = e;

   183         }

   184         e->next = elm;

   185         elm = e;

   186     }

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

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

   190         if (!kd) {

   191             return -1;

   192         }

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

   194         mapkey.data = kd;

   195         mapkey.len = key.len;

   196         elm->key = mapkey;

   197         map->count++;

   198     }

   199     elm->data = data;

   201     return 0;

   202 }

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

   205     if(key.hash == 0) {

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

   207     }

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

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

   211     UcxMapElement *pelm = NULL;

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

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

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

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

   216                 void *data = elm->data;

   217                 if (remove) {

   218                     if (pelm) {

   219                         pelm->next = elm->next;

   220                     } else {

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

   222                     }

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

   224                     alfree(map->allocator, elm);

   225                     map->count--;

   226                 }

   228                 return data;

   229             }

   230         }

   231         pelm = elm;

   232         elm = pelm->next;

   233     }

   235     return NULL;

   236 }

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

   239     return ucx_map_get_and_remove(map, key, 0);

   240 }

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

   243     return ucx_map_get_and_remove(map, key, 1);

   244 }

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

   247     UcxKey key;

   248     key.data = data;

   249     key.len = len;

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

   251     return key;

   252 }

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

   256     /* murmur hash 2 */

   258     int m = 0x5bd1e995;

   259     int r = 24;

   261     int h = 25 ^ len;

   263     int i = 0;

   264     while (len >= 4) {

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

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

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

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

   270         k *= m;

   271         k ^= k >> r;

   272         k *= m;

   274         h *= m;

   275         h ^= k;

   277         i += 4;

   278         len -= 4;

   279     }

   281     switch (len) {

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

   283         /* no break */

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

   285         /* no break */

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

   287         /* no break */

   288     }

   290     h ^= h >> 13;

   291     h *= m;

   292     h ^= h >> 15;

   294     return h;

   295 }

   297 UcxMapIterator ucx_map_iterator(UcxMap *map) {

   298     UcxMapIterator i;

   299     i.map = map;

   300     i.cur = NULL;

   301     i.index = 0;

   302     return i;

   303 }

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

   306     UcxMapElement *e = i->cur;

   308     if (e) {

   309         e = e->next;

   310     } else {

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

   312     }

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

   315         if (e) {

   316             if (e->data) {

   317                 i->cur = e;

   318                 *elm = e->data;

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

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

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

   322                 return 1;

   323             }

   325             e = e->next;

   326         } else {

   327             i->index++;

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

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

   331             }

   332         }

   333     }

   335     return 0;

   336 }

Mercurial > hg > ucx / file revision

src/map.c@fbc33813265b

src/map.c