ucx/map.c

   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  */
  28
  29 #include "ucx/map.h"
  30
  31 #include <stdlib.h>
  32 #include <string.h>
  33
  34 UcxMap *ucx_map_new(size_t size) {
  35     return ucx_map_new_a(NULL, size);
  36 }
  37
  38 UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size) {
  39     if(size == 0) {
  40         size = 16;
  41     }
  42
  43     if(!allocator) {
  44         allocator = ucx_default_allocator();
  45     }
  46
  47     UcxMap *map = (UcxMap*)almalloc(allocator, sizeof(UcxMap));
  48     if (!map) {
  49         return NULL;
  50     }
  51
  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;
  61
  62     return map;
  63 }
  64
  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 }
  78
  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 }
  84
  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 }
  96
  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 }
 105
 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 }
 116
 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 }
 120
 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 }
 131
 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;
 140
 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);
 150
 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 }
 157
 158 int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
 159     UcxAllocator *allocator = map->allocator;
 160
 161     if (key.hash == 0) {
 162         key.hash = ucx_hash((const char*)key.data, key.len);
 163     }
 164
 165     struct UcxMapKey mapkey;
 166     mapkey.hash = key.hash;
 167
 168     size_t slot = mapkey.hash%map->size;
 169     UcxMapElement *elm = map->map[slot];
 170     UcxMapElement *prev = NULL;
 171
 172     while (elm && elm->key.hash < mapkey.hash) {
 173         prev = elm;
 174         elm = elm->next;
 175     }
 176
 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     }
 192
 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;
 205
 206     return 0;
 207 }
 208
 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     }
 213
 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                 }
 232
 233                 return data;
 234             }
 235         }
 236         pelm = elm;
 237         elm = pelm->next;
 238     }
 239
 240     return NULL;
 241 }
 242
 243 void *ucx_map_get(UcxMap const *map, UcxKey key) {
 244     return ucx_map_get_and_remove((UcxMap *)map, key, 0);
 245 }
 246
 247 void *ucx_map_remove(UcxMap *map, UcxKey key) {
 248     return ucx_map_get_and_remove(map, key, 1);
 249 }
 250
 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 }
 258
 259
 260 int ucx_hash(const char *data, size_t len) {
 261     /* murmur hash 2 */
 262
 263     int m = 0x5bd1e995;
 264     int r = 24;
 265
 266     int h = 25 ^ len;
 267
 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;
 274
 275         k *= m;
 276         k ^= k >> r;
 277         k *= m;
 278
 279         h *= m;
 280         h ^= k;
 281
 282         i += 4;
 283         len -= 4;
 284     }
 285
 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     }
 294
 295     h ^= h >> 13;
 296     h *= m;
 297     h ^= h >> 15;
 298
 299     return h;
 300 }
 301
 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 }
 309
 310 int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm) {
 311     UcxMapElement *e = i->cur;
 312
 313     if (e) {
 314         e = e->next;
 315     } else {
 316         e = i->map->map[0];
 317     }
 318
 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             }
 329
 330             e = e->next;
 331         } else {
 332             i->index++;
 333
 334             if (i->index < i->map->size) {
 335                 e = i->map->map[i->index];
 336             }
 337         }
 338     }
 339
 340     return 0;
 341 }
 342
 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 }
 348
 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 }
 356
 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 }
 362
 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);
 368
 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     }
 376
 377     return result;
 378 }
 379
 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 }
 385
 386 UcxMap* ucx_map_difference_a(UcxAllocator *allocator,
 387                              const UcxMap *first, const UcxMap *second,
 388                              copy_func cpfnc, void* cpdata) {
 389
 390     UcxMap *result = ucx_map_new_a(allocator, first->size - second->count);
 391
 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     }
 399
 400     ucx_map_rehash(result);
 401     return result;
 402 }