LCOV - code coverage report
Current view: top level - src/container - hashmap.c (source / functions) Hit Total Coverage
Test: passgen-test.info Lines: 147 157 93.6 %
Date: 2024-06-14 06:05:32 Functions: 20 20 100.0 %

          Line data    Source code
       1             : #include "passgen/container/hashmap.h"
       2             : #include "passgen/config.h"
       3             : #include "passgen/util/siphash.h"
       4             : #include <stdlib.h>
       5             : #define UNUSED(x) (void) x
       6             : 
       7             : static const size_t hashmap_sizes[] = {
       8             :     3,
       9             :     7,
      10             :     17,
      11             :     37,
      12             :     79,
      13             :     163,
      14             :     331,
      15             :     673,
      16             :     1361,
      17             :     2729,
      18             :     5471,
      19             :     10949,
      20             :     21911,
      21             :     43853,
      22             :     87719,
      23             :     175447,
      24             :     350899,
      25             :     701819,
      26             :     0};
      27             : 
      28             : struct siphash_keys {
      29             :     const char *first;
      30             :     const char *second;
      31             : };
      32             : 
      33             : static const struct siphash_keys utf8_keys = {
      34             :     .first = "someverylongpass",
      35             :     .second = "myotherverylongk",
      36             : };
      37             : 
      38             : static const struct siphash_keys utf32_keys = {
      39             :     .first = "someverylongpass",
      40             :     .second = "myotherverylongk",
      41             : };
      42             : 
      43          95 : void passgen_hashmap_init(
      44             :     passgen_hashmap *map,
      45             :     const passgen_hashmap_context *context) {
      46             :     // zero-out hashmap
      47          95 :     memset(map, 0, sizeof(*map));
      48             : 
      49             :     // set context or default to UTF-8 context
      50          95 :     if(context) {
      51          89 :         map->context = context;
      52             :     } else {
      53           6 :         map->context = &passgen_hashmap_context_utf8;
      54             :     }
      55             : 
      56             :     // initialize hashmap context
      57          95 :     map->context->init(map);
      58          95 : }
      59             : 
      60          19 : void passgen_hashmap_free(passgen_hashmap *map) {
      61             :     // deinitialize context
      62          19 :     map->context->fini(map);
      63             : 
      64             :     // deallocate data
      65          19 :     free(map->data);
      66             : 
      67             :     // set everything to zero
      68          19 :     PASSGEN_CLEAR(map);
      69          19 : }
      70             : 
      71          20 : void passgen_hashmap_realloc(passgen_hashmap *map, size_t capacity) {
      72             :     // save previous hashmap
      73          20 :     passgen_hashmap old = *map;
      74             : 
      75          20 :     map->data = calloc(capacity, sizeof(passgen_hashmap_entry));
      76          20 :     map->capacity = capacity;
      77          20 :     map->len = 0;
      78             : 
      79             :     // copy data over
      80       87607 :     for(size_t i = 0; i < old.capacity; i++) {
      81       87587 :         if(old.data[i].key) {
      82       13997 :             passgen_hashmap_insert(map, old.data[i].key, old.data[i].value);
      83             :         }
      84             :     }
      85             : 
      86          20 :     free(old.data);
      87          20 : }
      88             : 
      89       38651 : static inline size_t passgen_hashmap_position(
      90             :     const passgen_hashmap *map,
      91             :     const void *key,
      92             :     bool first) {
      93       38651 :     return map->context->hash(map, key, first) % map->capacity;
      94             : }
      95             : 
      96        1859 : static inline bool passgen_hashmap_move(passgen_hashmap *map, size_t pos) {
      97        1859 :     const void *key = map->data[pos].key;
      98        1859 :     bool first = passgen_hashmap_position(map, key, true) == pos;
      99        1859 :     size_t other_pos = passgen_hashmap_position(map, key, !first);
     100        1859 :     if(!map->data[other_pos].key) {
     101        1568 :         map->data[other_pos].key = map->data[pos].key;
     102        1568 :         map->data[other_pos].value = map->data[pos].value;
     103        1568 :         return true;
     104             :     }
     105         291 :     return false;
     106             : }
     107             : 
     108          15 : static inline size_t next_capacity(passgen_hashmap *map) {
     109             :     size_t i;
     110         106 :     for(i = 0; hashmap_sizes[i]; i++) {
     111         106 :         if(hashmap_sizes[i] >= map->capacity) {
     112          15 :             break;
     113             :         }
     114             :     }
     115          15 :     if(hashmap_sizes[i] && hashmap_sizes[i + 1]) {
     116          15 :         return hashmap_sizes[i + 1];
     117             :     } else {
     118           0 :         return 2 * map->capacity - 1;
     119             :     }
     120             : }
     121             : 
     122             : passgen_hashmap_entry
     123       24023 : passgen_hashmap_insert(passgen_hashmap *map, const void *key, void *value) {
     124       24023 :     if(map->capacity == 0) {
     125           5 :         passgen_hashmap_realloc(map, hashmap_sizes[0]);
     126             :     }
     127             : 
     128             :     size_t hash;
     129             : 
     130       24023 :     hash = passgen_hashmap_position(map, key, true);
     131       24023 :     if(!map->data[hash].key) {
     132       22211 :         map->data[hash].key = key;
     133       22211 :         map->data[hash].value = value;
     134       22211 :         map->len += 1;
     135       22211 :         return (passgen_hashmap_entry){NULL, NULL};
     136             :     } else {
     137        1812 :         if(map->context->equal(map, map->data[hash].key, key)) {
     138           0 :             passgen_hashmap_entry entry = map->data[hash];
     139           0 :             map->data[hash].key = key;
     140           0 :             map->data[hash].value = value;
     141           0 :             return entry;
     142        1812 :         } else if(passgen_hashmap_move(map, hash)) {
     143        1536 :             map->data[hash].key = key;
     144        1536 :             map->data[hash].value = value;
     145        1536 :             map->len += 1;
     146        1536 :             return (passgen_hashmap_entry){NULL, NULL};
     147             :         }
     148             :     }
     149             : 
     150         276 :     hash = passgen_hashmap_position(map, key, false);
     151         276 :     if(!map->data[hash].key) {
     152         229 :         map->data[hash].key = key;
     153         229 :         map->data[hash].value = value;
     154         229 :         map->len += 1;
     155         229 :         return (passgen_hashmap_entry){NULL, NULL};
     156             :     } else {
     157          47 :         if(map->context->equal(map, map->data[hash].key, key)) {
     158           0 :             passgen_hashmap_entry entry = map->data[hash];
     159           0 :             map->data[hash].key = key;
     160           0 :             map->data[hash].value = value;
     161           0 :             return entry;
     162          47 :         } else if(passgen_hashmap_move(map, hash)) {
     163          32 :             map->data[hash].key = key;
     164          32 :             map->data[hash].value = value;
     165          32 :             map->len += 1;
     166          32 :             return (passgen_hashmap_entry){NULL, NULL};
     167             :         }
     168             :     }
     169             : 
     170          15 :     passgen_hashmap_realloc(map, next_capacity(map));
     171          15 :     return passgen_hashmap_insert(map, key, value);
     172             : }
     173             : 
     174             : passgen_hashmap_entry
     175           2 : passgen_hashmap_remove(passgen_hashmap *map, const void *key) {
     176             :     size_t hash;
     177             : 
     178             :     // if this key exists
     179           2 :     hash = passgen_hashmap_position(map, key, true);
     180           2 :     if(map->data[hash].key) {
     181             :         // and it matches
     182           2 :         if(map->context->equal(map, map->data[hash].key, key)) {
     183           1 :             passgen_hashmap_entry entry = map->data[hash];
     184           1 :             map->data[hash].key = NULL;
     185           1 :             map->data[hash].value = NULL;
     186           1 :             map->len -= 1;
     187           1 :             return entry;
     188             :         }
     189             :     }
     190             : 
     191             :     // if this key exists
     192           1 :     hash = passgen_hashmap_position(map, key, false);
     193           1 :     if(map->data[hash].key) {
     194             :         // and it matches
     195           1 :         if(map->context->equal(map, map->data[hash].key, key)) {
     196           1 :             passgen_hashmap_entry entry = map->data[hash];
     197           1 :             map->data[hash].key = NULL;
     198           1 :             map->data[hash].value = NULL;
     199           1 :             map->len -= 1;
     200           1 :             return entry;
     201             :         }
     202             :     }
     203             : 
     204           0 :     return (passgen_hashmap_entry){NULL, NULL};
     205             : }
     206             : 
     207             : passgen_hashmap_entry *
     208       10016 : passgen_hashmap_lookup(const passgen_hashmap *map, const void *key) {
     209             :     // make sure the hashmap is not empty
     210       10016 :     if(!map->data) {
     211           1 :         return NULL;
     212             :     }
     213             : 
     214             :     size_t hash;
     215             : 
     216             :     // lookup first possible location
     217       10015 :     hash = passgen_hashmap_position(map, key, true);
     218       20026 :     if(map->data[hash].key &&
     219       10011 :        map->context->equal(map, map->data[hash].key, key)) {
     220        9399 :         return &map->data[hash];
     221             :     }
     222             : 
     223             :     // lookup second possible location
     224         616 :     hash = passgen_hashmap_position(map, key, false);
     225        1225 :     if(map->data[hash].key &&
     226         609 :        map->context->equal(map, map->data[hash].key, key)) {
     227         609 :         return &map->data[hash];
     228             :     }
     229             : 
     230           7 :     return NULL;
     231             : }
     232             : 
     233           8 : int passgen_hashmap_foreach(
     234             :     const passgen_hashmap *map,
     235             :     void *user,
     236             :     int (*func)(void *user, passgen_hashmap_entry *entry)) {
     237           8 :     if(map->len) {
     238       87730 :         for(size_t i = 0; i < map->capacity; i++) {
     239       87728 :             if(map->data[i].key) {
     240       10006 :                 int ret = func(user, &map->data[i]);
     241       10006 :                 if(ret != 0) {
     242           1 :                     return ret;
     243             :                 }
     244             :             }
     245             :         }
     246             :     }
     247             : 
     248           7 :     return 0;
     249             : }
     250             : 
     251          93 : static void utf8_init(passgen_hashmap *map) {
     252          93 :     map->context_data = (void *) &utf8_keys;
     253          93 : }
     254             : 
     255          17 : static void utf8_fini(passgen_hashmap *map) {
     256          17 :     map->context_data = NULL;
     257          17 : }
     258             : 
     259             : static uint64_t
     260       38650 : utf8_hash(const passgen_hashmap *map, const void *key, bool first) {
     261             :     UNUSED(map);
     262             :     uint64_t output;
     263       38650 :     const struct siphash_keys *keys = map->context_data;
     264       38650 :     const char *siphash_key = first ? keys->first : keys->second;
     265       38650 :     passgen_siphash(
     266             :         key,
     267             :         strlen(key),
     268             :         siphash_key,
     269             :         (uint8_t *) &output,
     270             :         sizeof(output));
     271       38650 :     return output;
     272             : }
     273             : 
     274             : static bool
     275       12482 : utf8_equal(const passgen_hashmap *map, const void *lhs, const void *rhs) {
     276             :     UNUSED(map);
     277       12482 :     return strcmp(lhs, rhs) == 0;
     278             : }
     279             : 
     280             : const passgen_hashmap_context passgen_hashmap_context_utf8 = {
     281             :     .hash = utf8_hash,
     282             :     .equal = utf8_equal,
     283             :     .init = utf8_init,
     284             :     .fini = utf8_fini,
     285             : };
     286             : 
     287          21 : static size_t utf32_len(const void *data) {
     288             :     // cast void pointer to array of UTF-32 codepoints
     289          21 :     const int32_t *utf32 = data;
     290             : 
     291             :     // iterate over until we hit zero codepoint
     292          21 :     size_t len = 0;
     293         117 :     while(utf32[len]) {
     294          96 :         len++;
     295             :     }
     296             : 
     297          21 :     return len;
     298             : }
     299             : 
     300             : static uint64_t
     301           9 : utf32_hash(const passgen_hashmap *map, const void *key, bool first) {
     302             :     UNUSED(map);
     303             :     uint64_t output;
     304           9 :     const struct siphash_keys *keys = map->context_data;
     305           9 :     const char *siphash_key = first ? keys->first : keys->second;
     306           9 :     passgen_siphash(
     307             :         key,
     308             :         utf32_len(key),
     309             :         siphash_key,
     310             :         (uint8_t *) &output,
     311             :         sizeof(output));
     312           9 :     return output;
     313             : }
     314             : 
     315             : static bool
     316           6 : utf32_equal(const passgen_hashmap *map, const void *lhs, const void *rhs) {
     317             :     UNUSED(map);
     318             :     // compute lengths of lhs and rhs
     319           6 :     size_t rhs_len = utf32_len(rhs);
     320           6 :     size_t lhs_len = utf32_len(lhs);
     321             : 
     322             :     // if lengths are not the same, the keys cannot be equal
     323           6 :     if(rhs_len != lhs_len) {
     324           1 :         return false;
     325             :     }
     326             : 
     327             :     // compare lhs and rhs
     328           5 :     int ret = memcmp(lhs, rhs, rhs_len * sizeof(uint32_t));
     329             : 
     330             :     // return true if comparison was equal
     331           5 :     return ret == 0;
     332             : }
     333             : 
     334           2 : static void utf32_init(passgen_hashmap *map) {
     335           2 :     map->context_data = (void *) &utf32_keys;
     336           2 : }
     337             : 
     338           2 : static void utf32_fini(passgen_hashmap *map) {
     339           2 :     map->context_data = NULL;
     340           2 : }
     341             : 
     342             : const passgen_hashmap_context passgen_hashmap_context_utf32 = {
     343             :     .hash = utf32_hash,
     344             :     .equal = utf32_equal,
     345             :     .init = utf32_init,
     346             :     .fini = utf32_fini,
     347             : };
     348             : 
     349       10000 : int passgen_hashmap_entry_free(void *user, passgen_hashmap_entry *entry) {
     350             :     (void) user;
     351       10000 :     free((void *) entry->key);
     352       10000 :     free(entry->value);
     353       10000 :     PASSGEN_CLEAR(entry);
     354       10000 :     return 0;
     355             : }

Generated by: LCOV version 1.14