ucx: src/hash_map.c@edb9f875b7f9

     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  */

    29 #include "cx/hash_map.h"

    30 #include "cx/utils.h"

    32 #include <string.h>

    33 #include <assert.h>

    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;

    39     /** The corresponding key. */

    40     CxHashKey key;

    42     /** The value data. */

    43     char data[];

    44 };

    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);

    63             // do not leave a dangling pointer

    64             hash_map->buckets[i] = NULL;

    65         }

    66     }

    67     map->size = 0;

    68 }

    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;

    73     // free the buckets

    74     cx_hash_map_clear(map);

    75     cxFree(map->allocator, hash_map->buckets);

    77     // free the map structure

    78     cxFree(map->allocator, map);

    79 }

    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;

    89     unsigned hash = key.hash;

    90     if (hash == 0) {

    91         cx_hash_murmur(&key);

    92         hash = key.hash;

    93     }

    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;

    99     while (elm != NULL && elm->key.hash < hash) {

   100         prev = elm;

   101         elm = elm->next;

   102     }

   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         }

   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         }

   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;

   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;

   147         // increase the size

   148         map->size++;

   149     }

   151     return 0;

   152 }

   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 }

   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;

   190     unsigned hash = key.hash;

   191     if (hash == 0) {

   192         cx_hash_murmur(&key);

   193         hash = key.hash;

   194     }

   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     }

   222     return NULL;

   223 }

   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 }

   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 }

   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 }

   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 }

   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 }

   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 }

   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;

   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;

   279         // clear the flag

   280         iter->base.remove = false;

   282         // determine the next element

   283         struct cx_hash_map_element_s *next = elm->next;

   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         }

   294         // destroy

   295         cx_invoke_destructor((struct cx_map_s *) map, elm->data);

   297         // unlink

   298         cx_hash_map_unlink(map, iter->slot, prev, elm);

   300         // advance

   301         elm = next;

   302     } else {

   303         // just advance

   304         elm = elm->next;

   305         iter->index++;

   306     }

   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     }

   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 }

   329 static CxIterator cx_hash_map_iterator(

   330         CxMap const *map,

   331         enum cx_map_iterator_type type

   332 ) {

   333     CxIterator iter;

   335     iter.src_handle = map;

   336     iter.base.valid = cx_hash_map_iter_valid;

   337     iter.base.next = cx_hash_map_iter_next;

   339     switch (type) {

   340         case CX_MAP_ITERATOR_PAIRS:

   341             iter.base.current = cx_hash_map_iter_current_entry;

   342             break;

   343         case CX_MAP_ITERATOR_KEYS:

   344             iter.base.current = cx_hash_map_iter_current_key;

   345             break;

   346         case CX_MAP_ITERATOR_VALUES:

   347             iter.base.current = cx_hash_map_iter_current_value;

   348             break;

   349         default:

   350             assert(false);

   351     }

   353     iter.base.remove = false;

   354     iter.base.mutating = false;

   356     iter.slot = 0;

   357     iter.index = 0;

   359     if (map->size > 0) {

   360         struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;

   361         struct cx_hash_map_element_s *elm = hash_map->buckets[0];

   362         while (elm == NULL) {

   363             elm = hash_map->buckets[++iter.slot];

   364         }

   365         iter.elem_handle = elm;

   366         iter.kv_data.key = &elm->key;

   367         if (map->store_pointer) {

   368             iter.kv_data.value = *(void **) elm->data;

   369         } else {

   370             iter.kv_data.value = elm->data;

   371         }

   372     } else {

   373         iter.elem_handle = NULL;

   374         iter.kv_data.key = NULL;

   375         iter.kv_data.value = NULL;

   376     }

   378     return iter;

   379 }

   381 static cx_map_class cx_hash_map_class = {

   382         cx_hash_map_destructor,

   383         cx_hash_map_clear,

   384         cx_hash_map_put,

   385         cx_hash_map_get,

   386         cx_hash_map_remove,

   387         cx_hash_map_iterator,

   388 };

   390 CxMap *cxHashMapCreate(

   391         CxAllocator const *allocator,

   392         size_t itemsize,

   393         size_t buckets

   394 ) {

   395     if (buckets == 0) {

   396         // implementation defined default

   397         buckets = 16;

   398     }

   400     struct cx_hash_map_s *map = cxCalloc(allocator, 1,

   401                                          sizeof(struct cx_hash_map_s));

   402     if (map == NULL) return NULL;

   404     // initialize hash map members

   405     map->bucket_count = buckets;

   406     map->buckets = cxCalloc(allocator, buckets,

   407                             sizeof(struct cx_hash_map_element_s *));

   408     if (map->buckets == NULL) {

   409         cxFree(allocator, map);

   410         return NULL;

   411     }

   413     // initialize base members

   414     map->base.cl = &cx_hash_map_class;

   415     map->base.allocator = allocator;

   417     if (itemsize > 0) {

   418         map->base.store_pointer = false;

   419         map->base.item_size = itemsize;

   420     } else {

   421         map->base.store_pointer = true;

   422         map->base.item_size = sizeof(void *);

   423     }

   425     return (CxMap *) map;

   426 }

   428 int cxMapRehash(CxMap *map) {

   429     struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;

   430     if (map->size > ((hash_map->bucket_count * 3) >> 2)) {

   432         size_t new_bucket_count = (map->size * 5) >> 1;

   433         struct cx_hash_map_element_s **new_buckets = cxCalloc(

   434                 map->allocator,

   435                 new_bucket_count, sizeof(struct cx_hash_map_element_s *)

   436         );

   438         if (new_buckets == NULL) {

   439             return 1;

   440         }

   442         // iterate through the elements and assign them to their new slots

   443         cx_for_n(slot, hash_map->bucket_count) {

   444             struct cx_hash_map_element_s *elm = hash_map->buckets[slot];

   445             while (elm != NULL) {

   446                 struct cx_hash_map_element_s *next = elm->next;

   447                 size_t new_slot = elm->key.hash % new_bucket_count;

   449                 // find position where to insert

   450                 struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot];

   451                 struct cx_hash_map_element_s *bucket_prev = NULL;

   452                 while (bucket_next != NULL &&

   453                        bucket_next->key.hash < elm->key.hash) {

   454                     bucket_prev = bucket_next;

   455                     bucket_next = bucket_next->next;

   456                 }

   458                 // insert

   459                 if (bucket_prev == NULL) {

   460                     elm->next = new_buckets[new_slot];

   461                     new_buckets[new_slot] = elm;

   462                 } else {

   463                     bucket_prev->next = elm;

   464                     elm->next = bucket_next;

   465                 }

   467                 // advance

   468                 elm = next;

   469             }

   470         }

   472         // assign result to the map

   473         hash_map->bucket_count = new_bucket_count;

   474         cxFree(map->allocator, hash_map->buckets);

   475         hash_map->buckets = new_buckets;

   476     }

   477     return 0;

   478 }

Mercurial > hg > ucx / file revision

src/hash_map.c@edb9f875b7f9

src/hash_map.c