Line data    Source code

       1             : /*
       2             :  *  hashmap.c
       3             :  *  Patater GUI Kit
       4             :  *
       5             :  *  Created by Jaeden Amero on 2019-05-04.
       6             :  *  Copyright 2019. SPDX-License-Identifier: AGPL-3.0-or-later
       7             :  */
       8             : 
       9             : #include "guikit/hashmap.h"
      10             : #include "guikit/pmemory.h"
      11             : 
      12             : static const size_t MIN_CAPACITY = 8;
      13             : 
      14             : struct hashmap
      15             : {
      16             :     size_t length;
      17             :     size_t num_collisions;
      18             :     size_t capacity;
      19             :     u32 (*keys)[2];
      20             :     ptrdiff_t *values;
      21             : };
      22             : 
      23          29 : struct hashmap *hashmap_alloc_cap(size_t capacity)
      24             : {
      25             :     struct hashmap *hashmap;
      26             : 
      27          29 :     hashmap = pmalloc(sizeof(*hashmap));
      28          29 :     hashmap->length = 0;
      29          29 :     hashmap->num_collisions = 0;
      30          29 :     hashmap->capacity = capacity;
      31          29 :     hashmap->keys = pcalloc(hashmap->capacity, sizeof(*hashmap->keys));
      32          29 :     hashmap->values = pcalloc(hashmap->capacity, sizeof(*hashmap->values));
      33             : 
      34          29 :     return hashmap;
      35             : }
      36             : 
      37          29 : struct hashmap *hashmap_alloc(void)
      38             : {
      39          29 :     return hashmap_alloc_cap(MIN_CAPACITY);
      40             : }
      41             : 
      42           3 : static void hashmap_grow(struct hashmap *hashmap, size_t capacity)
      43             : {
      44             :     size_t i;
      45             :     u32 (*old_keys)[2];
      46             :     ptrdiff_t *old_values;
      47             :     size_t old_capacity;
      48             : 
      49           3 :     old_capacity = hashmap->capacity;
      50           3 :     old_keys = hashmap->keys;
      51           3 :     old_values = hashmap->values;
      52             : 
      53             :     /* Allocate memory for the new keys and values. */
      54           3 :     hashmap->length = 0;
      55           3 :     hashmap->capacity = capacity;
      56           3 :     hashmap->keys = pcalloc(hashmap->capacity, sizeof(*hashmap->keys));
      57           3 :     hashmap->values = pcalloc(hashmap->capacity, sizeof(*hashmap->values));
      58             : 
      59          35 :     for (i = 0; i < old_capacity; ++i)
      60             :     {
      61             :         /* Add each previously occupied slot to the new map. */
      62          32 :         if (old_keys[i][0] != 0 ||
      63          19 :             old_keys[i][1] != 0)
      64             :         {
      65          16 :             hashmap_put(hashmap, old_keys[i], old_values[i]);
      66             :         }
      67             :     }
      68             : 
      69             :     /* Free the old hashmap memory. */
      70           3 :     pfree(old_keys);
      71           3 :     pfree(old_values);
      72           3 : }
      73             : 
      74          29 : void hashmap_free(struct hashmap *hashmap)
      75             : {
      76          29 :     if (hashmap)
      77             :     {
      78          29 :         pfree(hashmap->keys);
      79          29 :         pfree(hashmap->values);
      80             :     }
      81          29 :     pfree(hashmap);
      82          29 : }
      83             : 
      84          43 : ptrdiff_t hashmap_get(const struct hashmap *hashmap, const u32 hash[])
      85             : {
      86             :     size_t i;
      87             : 
      88          43 :     if (hashmap->length == 0)
      89             :     {
      90             :         /* Nothing inside. */
      91           6 :         return 0;
      92             :     }
      93             : 
      94             :     /* We are ignoring the upper 32-bits of hash for indexing purposes, as
      95             :      * they'd get masked off anyway when converting the hash to an index. */
      96          37 :     i = hash[0];
      97             : 
      98             :     for (;;)
      99             :     {
     100             :         /* Convert hash or out-of-bounds index to a valid index. */
     101          49 :         i &= hashmap->capacity - 1;
     102             : 
     103          49 :         if (hashmap->keys[i][0] == hash[0] &&
     104          41 :             hashmap->keys[i][1] == hash[1])
     105             :         {
     106             :             /* Found the key! */
     107          31 :             return hashmap->values[i];
     108             :         }
     109          18 :         else if (hashmap->keys[i][0] == 0 &&
     110           6 :                  hashmap->keys[i][1] == 0)
     111             :         {
     112             :             /* Found first empty slot. We can stop searching. */
     113           6 :             break;
     114             :         }
     115             :         /* Try the next slot. */
     116          12 :         ++i;
     117             :     }
     118             : 
     119             :     /* We've ended our scan and didn't find the key. */
     120           6 :     return 0;
     121             : }
     122             : 
     123          73 : void hashmap_put(struct hashmap *hashmap, const u32 hash[], ptrdiff_t value)
     124             : {
     125             :     size_t i;
     126             :     size_t initial_i;
     127             : 
     128          73 :     if (hashmap->length >= hashmap->capacity / 2)
     129             :     {
     130             :         /* Double the size of the map. Keep it to a power of 2 in size, so that
     131             :          * we can efficiently convert from a hash to an index with a mask
     132             :          * (bitwise anding with one less than the capacity). */
     133             :         /* Note that growing here will avoid infinite loops in hashmap_get() as
     134             :          * we'll always be guaranteed a bunch of empty space in the map. */
     135           3 :         hashmap_grow(hashmap, 2 * hashmap->capacity);
     136             :     }
     137             : 
     138          73 :     i = hash[0];
     139          73 :     initial_i = i & (hashmap->capacity - 1);
     140             : 
     141             :     for (;;)
     142             :     {
     143             :         /* Convert hash or out-of-bounds index to a valid index. */
     144          89 :         i &= hashmap->capacity - 1;
     145             : 
     146          89 :         if (hashmap->keys[i][0] == 0 && hashmap->keys[i][1] == 0)
     147             :         {
     148             :             break;
     149             :         }
     150          20 :         else if (hashmap->keys[i][0] == hash[0]
     151          19 :                  && hashmap->keys[i][1] == hash[1])
     152             :         {
     153             :             /* Found an existing index with same hash. As we use a decent
     154             :              * 64-bit hash, this is very likely to be the key we are looking
     155             :              * for. So, go ahead and update the value. */
     156           4 :             hashmap->values[i] = value;
     157           4 :             return;
     158             :         }
     159             :         /* Try the next slot. Take a note that we had to go to the next slot as
     160             :          * we encountered another value with similar hash (enough to want to go
     161             :          * into the same index). */
     162          16 :         ++i;
     163             :     }
     164             : 
     165             :     /* Found an empty slot. We can stop looking for one. Go ahead and
     166             :      * set the key and value. */
     167          69 :     hashmap->keys[i][0] =  hash[0];
     168          69 :     hashmap->keys[i][1] =  hash[1];
     169          69 :     hashmap->values[i] = value;
     170          69 :     ++hashmap->length;
     171          69 :     if (i != initial_i)
     172             :     {
     173          13 :         ++hashmap->num_collisions;
     174             :     }
     175             : }
     176             : 
     177           6 : void hashmap_del(struct hashmap *hashmap, const u32 hash[])
     178             : {
     179             :     size_t i;
     180             : 
     181           6 :     i = hash[0];
     182             : 
     183             :     for (;;)
     184             :     {
     185             :         /* Convert hash or out-of-bounds index to a valid index. */
     186           7 :         i &= hashmap->capacity - 1;
     187             : 
     188           7 :         if (hashmap->keys[i][0] == 0 && hashmap->keys[i][1] == 0)
     189             :         {
     190             :             /* Key not present, so nothing to do. */
     191           3 :             return;
     192             :         }
     193           4 :         else if (hashmap->keys[i][0] == hash[0]
     194           4 :                  && hashmap->keys[i][1] == hash[1])
     195             :         {
     196             :             /* Found an existing index with same hash. As we use a decent
     197             :              * 64-bit hash, this is very likely to be the key we are looking
     198             :              * for. */
     199           3 :              break;
     200             :         }
     201             :         /* Try the next slot. */
     202           1 :         ++i;
     203             :     }
     204             : 
     205           3 :     hashmap->keys[i][0] = 0;
     206           3 :     hashmap->keys[i][1] = 0;
     207           3 :     --hashmap->length;
     208             : 
     209             :     /* Re-add all subsequent occupied keys in the same probe range, as leaving
     210             :      * a gap where we removed the key will cause these subsequent entries to
     211             :      * never be found (as probing stops at first 0 hash and we just make the
     212             :      * removed entry have a zero hash). */
     213           3 :     ++i;
     214             :     for (;;)
     215           1 :     {
     216           4 :         u32 key[2];
     217             :         ptrdiff_t value;
     218             : 
     219             :         /* Convert hash or out-of-bounds index to a valid index. */
     220           4 :         i &= hashmap->capacity - 1;
     221             : 
     222           4 :         if (hashmap->keys[i][0] == 0 && hashmap->keys[i][1] == 0)
     223             :         {
     224             :             /* End of the probe range. We are done. */
     225           3 :             break;
     226             :         }
     227             : 
     228           1 :         key[0] = hashmap->keys[i][0];
     229           1 :         key[1] = hashmap->keys[i][1];
     230           1 :         value = hashmap->values[i];
     231           1 :         hashmap->keys[i][0] = 0;
     232           1 :         hashmap->keys[i][1] = 0;
     233           1 :         --hashmap->length;
     234           1 :         hashmap_put(hashmap, key, value);
     235             : 
     236             :         /* Keep going within the probe range. */
     237           1 :         ++i;
     238             :     }
     239             : 
     240             :     /* We've now re-added any entries within the same probe range. */
     241             : }
     242             : 
     243           8 : size_t hashmap_capacity(const struct hashmap *hashmap)
     244             : {
     245           8 :     return hashmap->capacity;
     246             : }
     247             : 
     248          21 : size_t hashmap_length(const struct hashmap *hashmap)
     249             : {
     250          21 :     return hashmap->length;
     251             : }
     252             : 
     253          11 : size_t hashmap_num_collisions(const struct hashmap *hashmap)
     254             : {
     255          11 :     return hashmap->num_collisions;
     256             : }