Line data    Source code

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