ucx: src/hash_map.c@3390b58ad15a

     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 <string.h>

    30 #include "cx/hash_map.h"

    31 #include "cx/utils.h"

    33 struct cx_hash_map_element_s {

    34     /** A pointer to the next element in the current bucket. */

    35     struct cx_hash_map_element_s *next;

    37     /** The corresponding key. */

    38     CxHashKey key;

    40     /** The value data. */

    41     char data[];

    42 };

    44 static void cx_hash_map_clear(struct cx_map_s *map) {

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

    46     cx_for_n(i, hash_map->bucket_count) {

    47         struct cx_hash_map_element_s *elem = hash_map->buckets[i];

    48         if (elem != NULL) {

    49             do {

    50                 struct cx_hash_map_element_s *next = elem->next;

    51                 // invoke the destructor

    52                 cx_invoke_destructor(map, elem->data);

    53                 // free the key data

    54                 cxFree(map->allocator, (void *) elem->key.data);

    55                 // free the node

    56                 cxFree(map->allocator, elem);

    57                 // proceed

    58                 elem = next;

    59             } while (elem != NULL);

    61             // do not leave a dangling pointer

    62             hash_map->buckets[i] = NULL;

    63         }

    64     }

    65     map->size = 0;

    66 }

    68 static void cx_hash_map_destructor(struct cx_map_s *map) {

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

    71     // free the buckets

    72     cx_hash_map_clear(map);

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

    75     // free the map structure

    76     cxFree(map->allocator, map);

    77 }

    79 static int cx_hash_map_put(

    80         CxMap *map,

    81         CxHashKey key,

    82         void *value

    83 ) {

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

    85     CxAllocator const *allocator = map->allocator;

    87     unsigned hash = key.hash;

    88     if (hash == 0) {

    89         cx_hash_murmur(&key);

    90         hash = key.hash;

    91     }

    93     size_t slot = hash % hash_map->bucket_count;

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

    95     struct cx_hash_map_element_s *prev = NULL;

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

    98         prev = elm;

    99         elm = elm->next;

   100     }

   102     if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len &&

   103         memcmp(elm->key.data, key.data, key.len) == 0) {

   104         // overwrite existing element

   105         if (map->store_pointer) {

   106             memcpy(elm->data, &value, sizeof(void *));

   107         } else {

   108             memcpy(elm->data, value, map->item_size);

   109         }

   110     } else {

   111         // allocate new element

   112         struct cx_hash_map_element_s *e = cxMalloc(

   113                 allocator,

   114                 sizeof(struct cx_hash_map_element_s) + map->item_size

   115         );

   116         if (e == NULL) {

   117             return -1;

   118         }

   120         // write the value

   121         if (map->store_pointer) {

   122             memcpy(e->data, &value, sizeof(void *));

   123         } else {

   124             memcpy(e->data, value, map->item_size);

   125         }

   127         // copy the key

   128         void *kd = cxMalloc(allocator, key.len);

   129         if (kd == NULL) {

   130             return -1;

   131         }

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

   133         e->key.data = kd;

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

   135         e->key.hash = hash;

   137         // insert the element into the linked list

   138         if (prev == NULL) {

   139             hash_map->buckets[slot] = e;

   140         } else {

   141             prev->next = e;

   142         }

   143         e->next = elm;

   145         // increase the size

   146         map->size++;

   147     }

   149     return 0;

   150 }

   152 static void cx_hash_map_unlink(

   153         struct cx_hash_map_s *hash_map,

   154         size_t slot,

   155         struct cx_hash_map_element_s *prev,

   156         struct cx_hash_map_element_s *elm

   157 ) {

   158     // unlink

   159     if (prev == NULL) {

   160         hash_map->buckets[slot] = elm->next;

   161     } else {

   162         prev->next = elm->next;

   163     }

   164     // free element

   165     cxFree(hash_map->base.allocator, (void *) elm->key.data);

   166     cxFree(hash_map->base.allocator, elm);

   167     // decrease size

   168     hash_map->base.size--;

   169 }

   171 /**

   172  * Helper function to avoid code duplication.

   173  *

   174  * @param map the map

   175  * @param key the key to look up

   176  * @param remove flag indicating whether the looked up entry shall be removed

   177  * @param destroy flag indicating whether the destructor shall be invoked

   178  * @return a pointer to the value corresponding to the key or \c NULL

   179  */

   180 static void *cx_hash_map_get_remove(

   181         CxMap *map,

   182         CxHashKey key,

   183         bool remove,

   184         bool destroy

   185 ) {

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

   188     unsigned hash = key.hash;

   189     if (hash == 0) {

   190         cx_hash_murmur(&key);

   191         hash = key.hash;

   192     }

   194     size_t slot = hash % hash_map->bucket_count;

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

   196     struct cx_hash_map_element_s *prev = NULL;

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

   198         if (elm->key.hash == hash && elm->key.len == key.len) {

   199             if (memcmp(elm->key.data, key.data, key.len) == 0) {

   200                 void *data = NULL;

   201                 if (destroy) {

   202                     cx_invoke_destructor(map, elm->data);

   203                 } else {

   204                     if (map->store_pointer) {

   205                         data = *(void **) elm->data;

   206                     } else {

   207                         data = elm->data;

   208                     }

   209                 }

   210                 if (remove) {

   211                     cx_hash_map_unlink(hash_map, slot, prev, elm);

   212                 }

   213                 return data;

   214             }

   215         }

   216         prev = elm;

   217         elm = prev->next;

   218     }

   220     return NULL;

   221 }

   223 static void *cx_hash_map_get(

   224         CxMap const *map,

   225         CxHashKey key

   226 ) {

   227     // we can safely cast, because we know the map stays untouched

   228     return cx_hash_map_get_remove((CxMap *) map, key, false, false);

   229 }

   231 static void *cx_hash_map_remove(

   232         CxMap *map,

   233         CxHashKey key,

   234         bool destroy

   235 ) {

   236     return cx_hash_map_get_remove(map, key, true, destroy);

   237 }

   239 static void *cx_hash_map_iter_current_entry(void const *it) {

   240     struct cx_iterator_s const *iter = it;

   241     // struct has to have a compatible signature

   242     return (struct cx_map_entry_s *) &(iter->kv_data);

   243 }

   245 static void *cx_hash_map_iter_current_key(void const *it) {

   246     struct cx_iterator_s const *iter = it;

   247     struct cx_hash_map_element_s *elm = iter->elem_handle;

   248     return &elm->key;

   249 }

   251 static void *cx_hash_map_iter_current_value(void const *it) {

   252     struct cx_iterator_s const *iter = it;

   253     struct cx_hash_map_s const *map = iter->src_handle;

   254     struct cx_hash_map_element_s *elm = iter->elem_handle;

   255     if (map->base.store_pointer) {

   256         return *(void **) elm->data;

   257     } else {

   258         return elm->data;

   259     }

   260 }

   262 static bool cx_hash_map_iter_valid(void const *it) {

   263     struct cx_iterator_s const *iter = it;

   264     return iter->elem_handle != NULL;

   265 }

   267 static void cx_hash_map_iter_next(void *it) {

   268     struct cx_iterator_s *iter = it;

   269     struct cx_hash_map_element_s *elm = iter->elem_handle;

   271     // remove current element, if asked

   272     if (iter->base.remove) {

   273         // obtain mutable pointer to the map

   274         struct cx_mut_iterator_s *miter = it;

   275         struct cx_hash_map_s *map = miter->src_handle;

   277         // clear the flag

   278         iter->base.remove = false;

   280         // determine the next element

   281         struct cx_hash_map_element_s *next = elm->next;

   283         // search the previous element

   284         struct cx_hash_map_element_s *prev = NULL;

   285         if (map->buckets[iter->slot] != elm) {

   286             prev = map->buckets[iter->slot];

   287             while (prev->next != elm) {

   288                 prev = prev->next;

   289             }

   290         }

   292         // destroy

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

   295         // unlink

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

   298         // advance

   299         elm = next;

   300     } else {

   301         // just advance

   302         elm = elm->next;

   303         iter->index++;

   304     }

   306     // search the next bucket, if required

   307     struct cx_hash_map_s const *map = iter->src_handle;

   308     while (elm == NULL && ++iter->slot < map->bucket_count) {

   309         elm = map->buckets[iter->slot];

   310     }

   312     // fill the struct with the next element

   313     iter->elem_handle = elm;

   314     if (elm == NULL) {

   315         iter->kv_data.key = NULL;

   316         iter->kv_data.value = NULL;

   317     } else {

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

   319         if (map->base.store_pointer) {

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

   321         } else {

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

   323         }

   324     }

   325 }

   327 static bool cx_hash_map_iter_flag_rm(void *it) {

   328     struct cx_iterator_base_s *iter = it;

   329     if (iter->mutating) {

   330         iter->remove = true;

   331         return true;

   332     } else {

   333         return false;

   334     }

   335 }

   337 static CxIterator cx_hash_map_iterator(CxMap const *map) {

   338     CxIterator iter;

   340     iter.src_handle = map;

   341     iter.base.valid = cx_hash_map_iter_valid;

   342     iter.base.next = cx_hash_map_iter_next;

   343     iter.base.current = cx_hash_map_iter_current_entry;

   344     iter.base.flag_removal = cx_hash_map_iter_flag_rm;

   345     iter.base.remove = false;

   346     iter.base.mutating = false;

   348     iter.slot = 0;

   349     iter.index = 0;

   351     if (map->size > 0) {

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

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

   354         while (elm == NULL) {

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

   356         }

   357         iter.elem_handle = elm;

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

   359         if (map->store_pointer) {

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

   361         } else {

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

   363         }

   364     } else {

   365         iter.elem_handle = NULL;

   366         iter.kv_data.key = NULL;

   367         iter.kv_data.value = NULL;

   368     }

   370     return iter;

   371 }

   373 static CxIterator cx_hash_map_iterator_keys(CxMap const *map) {

   374     CxIterator iter = cx_hash_map_iterator(map);

   375     iter.base.current = cx_hash_map_iter_current_key;

   376     return iter;

   377 }

   379 static CxIterator cx_hash_map_iterator_values(CxMap const *map) {

   380     CxIterator iter = cx_hash_map_iterator(map);

   381     iter.base.current = cx_hash_map_iter_current_value;

   382     return iter;

   383 }

   385 static CxMutIterator cx_hash_map_mut_iterator(CxMap *map) {

   386     CxIterator it = cx_hash_map_iterator(map);

   387     it.base.mutating = true;

   389     // we know the iterators share the same memory layout

   390     CxMutIterator iter;

   391     memcpy(&iter, &it, sizeof(CxMutIterator));

   392     return iter;

   393 }

   395 static CxMutIterator cx_hash_map_mut_iterator_keys(CxMap *map) {

   396     CxMutIterator iter = cx_hash_map_mut_iterator(map);

   397     iter.base.current = cx_hash_map_iter_current_key;

   398     return iter;

   399 }

   401 static CxMutIterator cx_hash_map_mut_iterator_values(CxMap *map) {

   402     CxMutIterator iter = cx_hash_map_mut_iterator(map);

   403     iter.base.current = cx_hash_map_iter_current_value;

   404     return iter;

   405 }

   407 static cx_map_class cx_hash_map_class = {

   408         cx_hash_map_destructor,

   409         cx_hash_map_clear,

   410         cx_hash_map_put,

   411         cx_hash_map_get,

   412         cx_hash_map_remove,

   413         cx_hash_map_iterator,

   414         cx_hash_map_iterator_keys,

   415         cx_hash_map_iterator_values,

   416         cx_hash_map_mut_iterator,

   417         cx_hash_map_mut_iterator_keys,

   418         cx_hash_map_mut_iterator_values,

   419 };

   421 CxMap *cxHashMapCreate(

   422         CxAllocator const *allocator,

   423         size_t itemsize,

   424         size_t buckets

   425 ) {

   426     if (buckets == 0) {

   427         // implementation defined default

   428         buckets = 16;

   429     }

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

   432                                          sizeof(struct cx_hash_map_s));

   433     if (map == NULL) return NULL;

   435     // initialize hash map members

   436     map->bucket_count = buckets;

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

   438                             sizeof(struct cx_hash_map_element_s *));

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

   440         cxFree(allocator, map);

   441         return NULL;

   442     }

   444     // initialize base members

   445     map->base.cl = &cx_hash_map_class;

   446     map->base.allocator = allocator;

   448     if (itemsize > 0) {

   449         map->base.store_pointer = false;

   450         map->base.item_size = itemsize;

   451     } else {

   452         map->base.store_pointer = true;

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

   454     }

   456     return (CxMap *) map;

   457 }

   459 int cxMapRehash(CxMap *map) {

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

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

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

   464         struct cx_hash_map_element_s **new_buckets = cxCalloc(

   465                 map->allocator,

   466                 new_bucket_count, sizeof(struct cx_hash_map_element_s *)

   467         );

   469         if (new_buckets == NULL) {

   470             return 1;

   471         }

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

   474         cx_for_n(slot, hash_map->bucket_count) {

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

   476             while (elm != NULL) {

   477                 struct cx_hash_map_element_s *next = elm->next;

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

   480                 // find position where to insert

   481                 struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot];

   482                 struct cx_hash_map_element_s *bucket_prev = NULL;

   483                 while (bucket_next != NULL &&

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

   485                     bucket_prev = bucket_next;

   486                     bucket_next = bucket_next->next;

   487                 }

   489                 // insert

   490                 if (bucket_prev == NULL) {

   491                     elm->next = new_buckets[new_slot];

   492                     new_buckets[new_slot] = elm;

   493                 } else {

   494                     bucket_prev->next = elm;

   495                     elm->next = bucket_next;

   496                 }

   498                 // advance

   499                 elm = next;

   500             }

   501         }

   503         // assign result to the map

   504         hash_map->bucket_count = new_bucket_count;

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

   506         hash_map->buckets = new_buckets;

   507     }

   508     return 0;

   509 }

Mercurial > hg > ucx / file revision

src/hash_map.c@3390b58ad15a

src/hash_map.c