Line data    Source code

       1             : // SPDX-License-Identifier: BSD-2-Clause
       2             : // Copyright (C) 2010 Andrea Mazzoleni
       3             : 
       4             : #include "tommyhashdyn.h"
       5             : #include "tommylist.h"
       6             : 
       7             : /******************************************************************************/
       8             : /* hashdyn */
       9             : 
      10       10682 : TOMMY_API void tommy_hashdyn_init(tommy_hashdyn* hashdyn)
      11             : {
      12             :         /* fixed initial size */
      13       10682 :         hashdyn->bucket_bit = TOMMY_HASHDYN_BIT;
      14       10682 :         hashdyn->bucket_max = (tommy_size_t)1 << hashdyn->bucket_bit;
      15       10682 :         hashdyn->bucket_mask = hashdyn->bucket_max - 1;
      16       10682 :         hashdyn->bucket = tommy_cast(tommy_hashdyn_node**, tommy_calloc(hashdyn->bucket_max, sizeof(tommy_hashdyn_node*)));
      17             : 
      18       10682 :         hashdyn->count = 0;
      19       10682 : }
      20             : 
      21        9946 : TOMMY_API void tommy_hashdyn_done(tommy_hashdyn* hashdyn)
      22             : {
      23        9946 :         tommy_free(hashdyn->bucket);
      24        9946 : }
      25             : 
      26             : /**
      27             :  * Resize the bucket vector.
      28             :  */
      29       46471 : static void tommy_hashdyn_resize(tommy_hashdyn* hashdyn, tommy_uint_t new_bucket_bit)
      30             : {
      31             :         tommy_size_t bucket_bit;
      32             :         tommy_size_t bucket_max;
      33             :         tommy_size_t new_bucket_max;
      34             :         tommy_size_t new_bucket_mask;
      35             :         tommy_hashdyn_node** new_bucket;
      36             : 
      37       46471 :         bucket_bit = hashdyn->bucket_bit;
      38       46471 :         bucket_max = hashdyn->bucket_max;
      39             : 
      40       46471 :         new_bucket_max = (tommy_size_t)1 << new_bucket_bit;
      41       46471 :         new_bucket_mask = new_bucket_max - 1;
      42             : 
      43             :         /* allocate the new vector using malloc() and not calloc() */
      44             :         /* because data is fully initialized in the update process */
      45       46471 :         new_bucket = tommy_cast(tommy_hashdyn_node**, tommy_malloc(new_bucket_max * sizeof(tommy_hashdyn_node*)));
      46             : 
      47             :         /* reinsert all the elements */
      48       46471 :         if (new_bucket_bit > bucket_bit) {
      49             :                 tommy_size_t i;
      50             : 
      51             :                 /* grow */
      52    34713920 :                 for (i = 0; i < bucket_max; ++i) {
      53             :                         tommy_hashdyn_node* j;
      54             : 
      55             :                         /* setup the new two buckets */
      56    34667504 :                         new_bucket[i] = 0;
      57    34667504 :                         new_bucket[i + bucket_max] = 0;
      58             : 
      59             :                         /* reinsert the bucket */
      60    34667504 :                         j = hashdyn->bucket[i];
      61    52001256 :                         while (j) {
      62    17333752 :                                 tommy_hashdyn_node* j_next = j->next;
      63    17333752 :                                 tommy_size_t pos = j->index & new_bucket_mask;
      64    17333752 :                                 if (new_bucket[pos])
      65     2068301 :                                         tommy_list_insert_tail_not_empty(new_bucket[pos], j);
      66             :                                 else
      67    15265451 :                                         tommy_list_insert_first(&new_bucket[pos], j);
      68    17333752 :                                 j = j_next;
      69             :                         }
      70             :                 }
      71             :         } else {
      72             :                 tommy_size_t i;
      73             : 
      74             :                 /* shrink */
      75       79335 :                 for (i = 0; i < new_bucket_max; ++i) {
      76             :                         /* setup the new bucket with the lower bucket*/
      77       79280 :                         new_bucket[i] = hashdyn->bucket[i];
      78             : 
      79             :                         /* concat the upper bucket */
      80       79280 :                         tommy_list_concat(&new_bucket[i], &hashdyn->bucket[i + new_bucket_max]);
      81             :                 }
      82             :         }
      83             : 
      84       46471 :         tommy_free(hashdyn->bucket);
      85             : 
      86             :         /* setup */
      87       46471 :         hashdyn->bucket_bit = new_bucket_bit;
      88       46471 :         hashdyn->bucket_max = new_bucket_max;
      89       46471 :         hashdyn->bucket_mask = new_bucket_mask;
      90       46471 :         hashdyn->bucket = new_bucket;
      91       46471 : }
      92             : 
      93             : /**
      94             :  * Grow.
      95             :  */
      96    14223566 : tommy_inline void hashdyn_grow_step(tommy_hashdyn* hashdyn)
      97             : {
      98             :         /* grow if more than 50% full */
      99    14223566 :         if (hashdyn->count >= hashdyn->bucket_max / 2)
     100       46416 :                 tommy_hashdyn_resize(hashdyn, hashdyn->bucket_bit + 1);
     101    14223566 : }
     102             : 
     103             : /**
     104             :  * Shrink.
     105             :  */
     106      305148 : tommy_inline void hashdyn_shrink_step(tommy_hashdyn* hashdyn)
     107             : {
     108             :         /* shrink if less than 12.5% full */
     109      305148 :         if (hashdyn->count <= hashdyn->bucket_max / 8 && hashdyn->bucket_bit > TOMMY_HASHDYN_BIT)
     110          55 :                 tommy_hashdyn_resize(hashdyn, hashdyn->bucket_bit - 1);
     111      305148 : }
     112             : 
     113    14223566 : TOMMY_API void tommy_hashdyn_insert(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node, void* data, tommy_hash_t hash)
     114             : {
     115    14223566 :         tommy_size_t pos = hash & hashdyn->bucket_mask;
     116             : 
     117    14223566 :         tommy_list_insert_tail(&hashdyn->bucket[pos], node, data);
     118             : 
     119    14223566 :         node->index = hash;
     120             : 
     121    14223566 :         ++hashdyn->count;
     122             : 
     123    14223566 :         hashdyn_grow_step(hashdyn);
     124    14223566 : }
     125             : 
     126      305020 : TOMMY_API void* tommy_hashdyn_remove_existing(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node)
     127             : {
     128      305020 :         tommy_size_t pos = node->index & hashdyn->bucket_mask;
     129             : 
     130      305020 :         tommy_list_remove_existing(&hashdyn->bucket[pos], node);
     131             : 
     132      305020 :         --hashdyn->count;
     133             : 
     134      305020 :         hashdyn_shrink_step(hashdyn);
     135             : 
     136      305020 :         return node->data;
     137             : }
     138             : 
     139         256 : TOMMY_API void* tommy_hashdyn_remove(tommy_hashdyn* hashdyn, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
     140             : {
     141         256 :         tommy_size_t pos = hash & hashdyn->bucket_mask;
     142         256 :         tommy_hashdyn_node* node = hashdyn->bucket[pos];
     143             : 
     144         512 :         while (node) {
     145             :                 /* we first check if the hash matches, as in the same bucket we may have multiples hash values */
     146         384 :                 if (node->index == hash && cmp(cmp_arg, node->data) == 0) {
     147         128 :                         tommy_list_remove_existing(&hashdyn->bucket[pos], node);
     148             : 
     149         128 :                         --hashdyn->count;
     150             : 
     151         128 :                         hashdyn_shrink_step(hashdyn);
     152             : 
     153         128 :                         return node->data;
     154             :                 }
     155         256 :                 node = node->next;
     156             :         }
     157             : 
     158         128 :         return 0;
     159             : }
     160             : 
     161         299 : TOMMY_API void tommy_hashdyn_foreach(tommy_hashdyn* hashdyn, tommy_foreach_func* func)
     162             : {
     163         299 :         tommy_size_t bucket_max = hashdyn->bucket_max;
     164         299 :         tommy_hashdyn_node** bucket = hashdyn->bucket;
     165             :         tommy_size_t pos;
     166             : 
     167     6080699 :         for (pos = 0; pos < bucket_max; ++pos) {
     168     6080400 :                 tommy_hashdyn_node* node = bucket[pos];
     169             : 
     170     8011372 :                 while (node) {
     171     1930972 :                         void* data = node->data;
     172     1930972 :                         node = node->next;
     173     1930972 :                         func(data);
     174             :                 }
     175             :         }
     176         299 : }
     177             : 
     178           4 : TOMMY_API void tommy_hashdyn_foreach_arg(tommy_hashdyn* hashdyn, tommy_foreach_arg_func* func, void* arg)
     179             : {
     180           4 :         tommy_size_t bucket_max = hashdyn->bucket_max;
     181           4 :         tommy_hashdyn_node** bucket = hashdyn->bucket;
     182             :         tommy_size_t pos;
     183             : 
     184        1316 :         for (pos = 0; pos < bucket_max; ++pos) {
     185        1312 :                 tommy_hashdyn_node* node = bucket[pos];
     186             : 
     187        1629 :                 while (node) {
     188         317 :                         void* data = node->data;
     189         317 :                         node = node->next;
     190         317 :                         func(arg, data);
     191             :                 }
     192             :         }
     193           4 : }
     194             : 
     195           1 : TOMMY_API tommy_size_t tommy_hashdyn_memory_usage(tommy_hashdyn* hashdyn)
     196             : {
     197           1 :         return hashdyn->bucket_max * (tommy_size_t)sizeof(hashdyn->bucket[0])
     198           1 :                + tommy_hashdyn_count(hashdyn) * (tommy_size_t)sizeof(tommy_hashdyn_node);
     199             : }
     200             : 
     201             : /**
     202             :  * \brief Transfers all elements from the dynamic hashtable into a tommy_list.
     203             :  *
     204             :  * Removes every element from the \p hashdyn hashtable and inserts them
     205             :  * into the provided \p list (at the tail), preserving the per-bucket order
     206             :  * but not guaranteeing any particular global order.
     207             :  *
     208             :  * After the call:
     209             :  * - the hashtable is left completely empty (\c count = 0, all buckets = NULL)
     210             :  * - the target list contains all the elements that were previously in the hashtable
     211             :  *
     212             :  * This function is useful when you need to:
     213             :  * - extract all elements to process/sort them outside the hash table
     214             :  * - convert the hashtable into a list for sequential iteration
     215             :  * - prepare for a full clear + re-insertion with different hash/ordering
     216             :  * - move ownership of the nodes to a list-based container
     217             :  *
     218             :  * \note The operation is O(n) where n is the number of elements.
     219             :  * \note No memory allocation is performed.
     220             :  * \note The relative order of elements that were in the same bucket is preserved,
     221             :  *       but the order among different buckets is bucket-order dependent.
     222             :  *
     223             :  * Typical usage pattern:
     224             :  * \code
     225             :  * tommy_list all_elements;
     226             :  * tommy_list_init(&all_elements);
     227             :  *
     228             :  * // move everything out of the hashtable into the list
     229             :  * tommy_hashdyn_to_list(&hashdyn, &all_elements);
     230             :  *
     231             :  * // now you can sort, filter, process sequentially, etc.
     232             :  * tommy_list_sort(&all_elements, compare_by_value);
     233             :  * \endcode
     234             :  *
     235             :  * \param hashdyn The dynamic hashtable to drain
     236             :  * \param list    The list that will receive all the elements
     237             :  */
     238         473 : TOMMY_API void tommy_hashdyn_to_list(tommy_hashdyn* hashdyn, tommy_list* list)
     239             : {
     240         473 :         tommy_size_t bucket_max = hashdyn->bucket_max;
     241         473 :         tommy_hashdyn_node** bucket = hashdyn->bucket;
     242             :         tommy_size_t pos;
     243             : 
     244             :         /* move everything to the list */
     245        8041 :         for (pos = 0; pos < bucket_max; ++pos) {
     246        7568 :                 tommy_hashdyn_node* node = bucket[pos];
     247             : 
     248        8465 :                 while (node) {
     249         897 :                         tommy_node* node_next = node->next;
     250         897 :                         tommy_list_insert_tail(list, node, node->data);
     251         897 :                         node = node_next;
     252             :                 }
     253             :         }
     254             : 
     255             :         /* clear all */
     256         473 :         memset(hashdyn->bucket, 0, hashdyn->bucket_max * sizeof(tommy_hashdyn_node*));
     257         473 :         hashdyn->count = 0;
     258         473 : }