ucx/hash_map.c

   1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
   3  *
   4  * Copyright 2021 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 "cx/hash_map.h"
  30 #include "cx/utils.h"
  31
  32 #include <string.h>
  33 #include <assert.h>
  34
  35 struct cx_hash_map_element_s {
  36     /** A pointer to the next element in the current bucket. */
  37     struct cx_hash_map_element_s *next;
  38
  39     /** The corresponding key. */
  40     CxHashKey key;
  41
  42     /** The value data. */
  43     char data[];
  44 };
  45
  46 static void cx_hash_map_clear(struct cx_map_s *map) {
  47     struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
  48     cx_for_n(i, hash_map->bucket_count) {
  49         struct cx_hash_map_element_s *elem = hash_map->buckets[i];
  50         if (elem != NULL) {
  51             do {
  52                 struct cx_hash_map_element_s *next = elem->next;
  53                 // invoke the destructor
  54                 cx_invoke_destructor(map, elem->data);
  55                 // free the key data
  56                 cxFree(map->allocator, (void *) elem->key.data);
  57                 // free the node
  58                 cxFree(map->allocator, elem);
  59                 // proceed
  60                 elem = next;
  61             } while (elem != NULL);
  62
  63             // do not leave a dangling pointer
  64             hash_map->buckets[i] = NULL;
  65         }
  66     }
  67     map->size = 0;
  68 }
  69
  70 static void cx_hash_map_destructor(struct cx_map_s *map) {
  71     struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
  72
  73     // free the buckets
  74     cx_hash_map_clear(map);
  75     cxFree(map->allocator, hash_map->buckets);
  76
  77     // free the map structure
  78     cxFree(map->allocator, map);
  79 }
  80
  81 static int cx_hash_map_put(
  82         CxMap *map,
  83         CxHashKey key,
  84         void *value
  85 ) {
  86     struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
  87     CxAllocator const *allocator = map->allocator;
  88
  89     unsigned hash = key.hash;
  90     if (hash == 0) {
  91         cx_hash_murmur(&key);
  92         hash = key.hash;
  93     }
  94
  95     size_t slot = hash % hash_map->bucket_count;
  96     struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
  97     struct cx_hash_map_element_s *prev = NULL;
  98
  99     while (elm != NULL && elm->key.hash < hash) {
 100         prev = elm;
 101         elm = elm->next;
 102     }
 103
 104     if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len &&
 105         memcmp(elm->key.data, key.data, key.len) == 0) {
 106         // overwrite existing element
 107         if (map->store_pointer) {
 108             memcpy(elm->data, &value, sizeof(void *));
 109         } else {
 110             memcpy(elm->data, value, map->item_size);
 111         }
 112     } else {
 113         // allocate new element
 114         struct cx_hash_map_element_s *e = cxMalloc(
 115                 allocator,
 116                 sizeof(struct cx_hash_map_element_s) + map->item_size
 117         );
 118         if (e == NULL) {
 119             return -1;
 120         }
 121
 122         // write the value
 123         if (map->store_pointer) {
 124             memcpy(e->data, &value, sizeof(void *));
 125         } else {
 126             memcpy(e->data, value, map->item_size);
 127         }
 128
 129         // copy the key
 130         void *kd = cxMalloc(allocator, key.len);
 131         if (kd == NULL) {
 132             return -1;
 133         }
 134         memcpy(kd, key.data, key.len);
 135         e->key.data = kd;
 136         e->key.len = key.len;
 137         e->key.hash = hash;
 138
 139         // insert the element into the linked list
 140         if (prev == NULL) {
 141             hash_map->buckets[slot] = e;
 142         } else {
 143             prev->next = e;
 144         }
 145         e->next = elm;
 146
 147         // increase the size
 148         map->size++;
 149     }
 150
 151     return 0;
 152 }
 153
 154 static void cx_hash_map_unlink(
 155         struct cx_hash_map_s *hash_map,
 156         size_t slot,
 157         struct cx_hash_map_element_s *prev,
 158         struct cx_hash_map_element_s *elm
 159 ) {
 160     // unlink
 161     if (prev == NULL) {
 162         hash_map->buckets[slot] = elm->next;
 163     } else {
 164         prev->next = elm->next;
 165     }
 166     // free element
 167     cxFree(hash_map->base.allocator, (void *) elm->key.data);
 168     cxFree(hash_map->base.allocator, elm);
 169     // decrease size
 170     hash_map->base.size--;
 171 }
 172
 173 /**
 174  * Helper function to avoid code duplication.
 175  *
 176  * @param map the map
 177  * @param key the key to look up
 178  * @param remove flag indicating whether the looked up entry shall be removed
 179  * @param destroy flag indicating whether the destructor shall be invoked
 180  * @return a pointer to the value corresponding to the key or \c NULL
 181  */
 182 static void *cx_hash_map_get_remove(
 183         CxMap *map,
 184         CxHashKey key,
 185         bool remove,
 186         bool destroy
 187 ) {
 188     struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
 189
 190     unsigned hash = key.hash;
 191     if (hash == 0) {
 192         cx_hash_murmur(&key);
 193         hash = key.hash;
 194     }
 195
 196     size_t slot = hash % hash_map->bucket_count;
 197     struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
 198     struct cx_hash_map_element_s *prev = NULL;
 199     while (elm && elm->key.hash <= hash) {
 200         if (elm->key.hash == hash && elm->key.len == key.len) {
 201             if (memcmp(elm->key.data, key.data, key.len) == 0) {
 202                 void *data = NULL;
 203                 if (destroy) {
 204                     cx_invoke_destructor(map, elm->data);
 205                 } else {
 206                     if (map->store_pointer) {
 207                         data = *(void **) elm->data;
 208                     } else {
 209                         data = elm->data;
 210                     }
 211                 }
 212                 if (remove) {
 213                     cx_hash_map_unlink(hash_map, slot, prev, elm);
 214                 }
 215                 return data;
 216             }
 217         }
 218         prev = elm;
 219         elm = prev->next;
 220     }
 221
 222     return NULL;
 223 }
 224
 225 static void *cx_hash_map_get(
 226         CxMap const *map,
 227         CxHashKey key
 228 ) {
 229     // we can safely cast, because we know the map stays untouched
 230     return cx_hash_map_get_remove((CxMap *) map, key, false, false);
 231 }
 232
 233 static void *cx_hash_map_remove(
 234         CxMap *map,
 235         CxHashKey key,
 236         bool destroy
 237 ) {
 238     return cx_hash_map_get_remove(map, key, true, destroy);
 239 }
 240
 241 static void *cx_hash_map_iter_current_entry(void const *it) {
 242     struct cx_iterator_s const *iter = it;
 243     // struct has to have a compatible signature
 244     return (struct cx_map_entry_s *) &(iter->kv_data);
 245 }
 246
 247 static void *cx_hash_map_iter_current_key(void const *it) {
 248     struct cx_iterator_s const *iter = it;
 249     struct cx_hash_map_element_s *elm = iter->elem_handle;
 250     return &elm->key;
 251 }
 252
 253 static void *cx_hash_map_iter_current_value(void const *it) {
 254     struct cx_iterator_s const *iter = it;
 255     struct cx_hash_map_s const *map = iter->src_handle;
 256     struct cx_hash_map_element_s *elm = iter->elem_handle;
 257     if (map->base.store_pointer) {
 258         return *(void **) elm->data;
 259     } else {
 260         return elm->data;
 261     }
 262 }
 263
 264 static bool cx_hash_map_iter_valid(void const *it) {
 265     struct cx_iterator_s const *iter = it;
 266     return iter->elem_handle != NULL;
 267 }
 268
 269 static void cx_hash_map_iter_next(void *it) {
 270     struct cx_iterator_s *iter = it;
 271     struct cx_hash_map_element_s *elm = iter->elem_handle;
 272
 273     // remove current element, if asked
 274     if (iter->base.remove) {
 275         // obtain mutable pointer to the map
 276         struct cx_mut_iterator_s *miter = it;
 277         struct cx_hash_map_s *map = miter->src_handle;
 278
 279         // clear the flag
 280         iter->base.remove = false;
 281
 282         // determine the next element
 283         struct cx_hash_map_element_s *next = elm->next;
 284
 285         // search the previous element
 286         struct cx_hash_map_element_s *prev = NULL;
 287         if (map->buckets[iter->slot] != elm) {
 288             prev = map->buckets[iter->slot];
 289             while (prev->next != elm) {
 290                 prev = prev->next;
 291             }
 292         }
 293
 294         // destroy
 295         cx_invoke_destructor((struct cx_map_s *) map, elm->data);
 296
 297         // unlink
 298         cx_hash_map_unlink(map, iter->slot, prev, elm);
 299
 300         // advance
 301         elm = next;
 302     } else {
 303         // just advance
 304         elm = elm->next;
 305         iter->index++;
 306     }
 307
 308     // search the next bucket, if required
 309     struct cx_hash_map_s const *map = iter->src_handle;
 310     while (elm == NULL && ++iter->slot < map->bucket_count) {
 311         elm = map->buckets[iter->slot];
 312     }
 313
 314     // fill the struct with the next element
 315     iter->elem_handle = elm;
 316     if (elm == NULL) {
 317         iter->kv_data.key = NULL;
 318         iter->kv_data.value = NULL;
 319     } else {
 320         iter->kv_data.key = &elm->key;
 321         if (map->base.store_pointer) {
 322             iter->kv_data.value = *(void **) elm->data;
 323         } else {
 324             iter->kv_data.value = elm->data;
 325         }
 326     }
 327 }
 328
 329 static bool cx_hash_map_iter_flag_rm(void *it) {
 330     struct cx_iterator_base_s *iter = it;
 331     if (iter->mutating) {
 332         iter->remove = true;
 333         return true;
 334     } else {
 335         return false;
 336     }
 337 }
 338
 339 static CxIterator cx_hash_map_iterator(
 340         CxMap const *map,
 341         enum cx_map_iterator_type type
 342 ) {
 343     CxIterator iter;
 344
 345     iter.src_handle = map;
 346     iter.base.valid = cx_hash_map_iter_valid;
 347     iter.base.next = cx_hash_map_iter_next;
 348
 349     switch (type) {
 350         case CX_MAP_ITERATOR_PAIRS:
 351             iter.base.current = cx_hash_map_iter_current_entry;
 352             break;
 353         case CX_MAP_ITERATOR_KEYS:
 354             iter.base.current = cx_hash_map_iter_current_key;
 355             break;
 356         case CX_MAP_ITERATOR_VALUES:
 357             iter.base.current = cx_hash_map_iter_current_value;
 358             break;
 359         default:
 360             assert(false);
 361     }
 362
 363     iter.base.flag_removal = cx_hash_map_iter_flag_rm;
 364     iter.base.remove = false;
 365     iter.base.mutating = false;
 366
 367     iter.slot = 0;
 368     iter.index = 0;
 369
 370     if (map->size > 0) {
 371         struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
 372         struct cx_hash_map_element_s *elm = hash_map->buckets[0];
 373         while (elm == NULL) {
 374             elm = hash_map->buckets[++iter.slot];
 375         }
 376         iter.elem_handle = elm;
 377         iter.kv_data.key = &elm->key;
 378         if (map->store_pointer) {
 379             iter.kv_data.value = *(void **) elm->data;
 380         } else {
 381             iter.kv_data.value = elm->data;
 382         }
 383     } else {
 384         iter.elem_handle = NULL;
 385         iter.kv_data.key = NULL;
 386         iter.kv_data.value = NULL;
 387     }
 388
 389     return iter;
 390 }
 391
 392 static cx_map_class cx_hash_map_class = {
 393         cx_hash_map_destructor,
 394         cx_hash_map_clear,
 395         cx_hash_map_put,
 396         cx_hash_map_get,
 397         cx_hash_map_remove,
 398         cx_hash_map_iterator,
 399 };
 400
 401 CxMap *cxHashMapCreate(
 402         CxAllocator const *allocator,
 403         size_t itemsize,
 404         size_t buckets
 405 ) {
 406     if (buckets == 0) {
 407         // implementation defined default
 408         buckets = 16;
 409     }
 410
 411     struct cx_hash_map_s *map = cxCalloc(allocator, 1,
 412                                          sizeof(struct cx_hash_map_s));
 413     if (map == NULL) return NULL;
 414
 415     // initialize hash map members
 416     map->bucket_count = buckets;
 417     map->buckets = cxCalloc(allocator, buckets,
 418                             sizeof(struct cx_hash_map_element_s *));
 419     if (map->buckets == NULL) {
 420         cxFree(allocator, map);
 421         return NULL;
 422     }
 423
 424     // initialize base members
 425     map->base.cl = &cx_hash_map_class;
 426     map->base.allocator = allocator;
 427
 428     if (itemsize > 0) {
 429         map->base.store_pointer = false;
 430         map->base.item_size = itemsize;
 431     } else {
 432         map->base.store_pointer = true;
 433         map->base.item_size = sizeof(void *);
 434     }
 435
 436     return (CxMap *) map;
 437 }
 438
 439 int cxMapRehash(CxMap *map) {
 440     struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
 441     if (map->size > ((hash_map->bucket_count * 3) >> 2)) {
 442
 443         size_t new_bucket_count = (map->size * 5) >> 1;
 444         struct cx_hash_map_element_s **new_buckets = cxCalloc(
 445                 map->allocator,
 446                 new_bucket_count, sizeof(struct cx_hash_map_element_s *)
 447         );
 448
 449         if (new_buckets == NULL) {
 450             return 1;
 451         }
 452
 453         // iterate through the elements and assign them to their new slots
 454         cx_for_n(slot, hash_map->bucket_count) {
 455             struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
 456             while (elm != NULL) {
 457                 struct cx_hash_map_element_s *next = elm->next;
 458                 size_t new_slot = elm->key.hash % new_bucket_count;
 459
 460                 // find position where to insert
 461                 struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot];
 462                 struct cx_hash_map_element_s *bucket_prev = NULL;
 463                 while (bucket_next != NULL &&
 464                        bucket_next->key.hash < elm->key.hash) {
 465                     bucket_prev = bucket_next;
 466                     bucket_next = bucket_next->next;
 467                 }
 468
 469                 // insert
 470                 if (bucket_prev == NULL) {
 471                     elm->next = new_buckets[new_slot];
 472                     new_buckets[new_slot] = elm;
 473                 } else {
 474                     bucket_prev->next = elm;
 475                     elm->next = bucket_next;
 476                 }
 477
 478                 // advance
 479                 elm = next;
 480             }
 481         }
 482
 483         // assign result to the map
 484         hash_map->bucket_count = new_bucket_count;
 485         cxFree(map->allocator, hash_map->buckets);
 486         hash_map->buckets = new_buckets;
 487     }
 488     return 0;
 489 }