LCOV - code coverage report
Current view: top level - lib - dynamicsizehash_concurrent.c (source / functions) Hit Total Coverage
Test: elfutils-0.191 Lines: 129 176 73.3 %
Date: 2024-03-01 16:42:08 Functions: 12 13 92.3 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 48 94 51.1 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2000-2019 Red Hat, Inc.
       2                 :            :    This file is part of elfutils.
       3                 :            :    Written by Srdan Milakovic <sm108@rice.edu>, 2019.
       4                 :            :    Derived from Ulrich Drepper <drepper@redhat.com>, 2000.
       5                 :            : 
       6                 :            :    This file is free software; you can redistribute it and/or modify
       7                 :            :    it under the terms of either
       8                 :            : 
       9                 :            :      * the GNU Lesser General Public License as published by the Free
      10                 :            :        Software Foundation; either version 3 of the License, or (at
      11                 :            :        your option) any later version
      12                 :            : 
      13                 :            :    or
      14                 :            : 
      15                 :            :      * the GNU General Public License as published by the Free
      16                 :            :        Software Foundation; either version 2 of the License, or (at
      17                 :            :        your option) any later version
      18                 :            : 
      19                 :            :    or both in parallel, as here.
      20                 :            : 
      21                 :            :    elfutils is distributed in the hope that it will be useful, but
      22                 :            :    WITHOUT ANY WARRANTY; without even the implied warranty of
      23                 :            :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      24                 :            :    General Public License for more details.
      25                 :            : 
      26                 :            :    You should have received copies of the GNU General Public License and
      27                 :            :    the GNU Lesser General Public License along with this program.  If
      28                 :            :    not, see <http://www.gnu.org/licenses/>.  */
      29                 :            : 
      30                 :            : #include <assert.h>
      31                 :            : #include <stdlib.h>
      32                 :            : #include <system.h>
      33                 :            : #include <pthread.h>
      34                 :            : 
      35                 :            : /* Before including this file the following macros must be defined:
      36                 :            : 
      37                 :            :    NAME      name of the hash table structure.
      38                 :            :    TYPE      data type of the hash table entries
      39                 :            :  */
      40                 :            : 
      41                 :            : 
      42                 :            : static size_t
      43                 :   11785854 : lookup (NAME *htab, HASHTYPE hval)
      44                 :            : {
      45                 :            :   /* First hash function: simply take the modulus but prevent zero.  Small values
      46                 :            :       can skip the division, which helps performance when this is common.  */
      47         [ +  + ]:   11785854 :   size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
      48                 :            : 
      49                 :            :   HASHTYPE hash;
      50                 :            : 
      51                 :   11785854 :   hash = atomic_load_explicit(&htab->table[idx].hashval,
      52                 :            :                               memory_order_acquire);
      53         [ +  + ]:   11785854 :   if (hash == hval)
      54                 :    9690410 :     return idx;
      55         [ +  + ]:    2095444 :   else if (hash == 0)
      56                 :    2094980 :     return 0;
      57                 :            : 
      58                 :            :   /* Second hash function as suggested in [Knuth].  */
      59                 :        464 :   HASHTYPE second_hash = 1 + hval % (htab->size - 2);
      60                 :            : 
      61                 :            :   for(;;)
      62                 :            :     {
      63         [ +  - ]:        464 :       if (idx <= second_hash)
      64                 :        464 :           idx = htab->size + idx - second_hash;
      65                 :            :       else
      66                 :          0 :           idx -= second_hash;
      67                 :            : 
      68                 :        464 :       hash = atomic_load_explicit(&htab->table[idx].hashval,
      69                 :            :                                   memory_order_acquire);
      70         [ -  + ]:        464 :       if (hash == hval)
      71                 :          0 :         return idx;
      72         [ +  - ]:        464 :       else if (hash == 0)
      73                 :        464 :         return 0;
      74                 :            :     }
      75                 :            : }
      76                 :            : 
      77                 :            : static int
      78                 :    2369272 : insert_helper (NAME *htab, HASHTYPE hval, TYPE val)
      79                 :            : {
      80                 :            :   /* First hash function: simply take the modulus but prevent zero.  Small values
      81                 :            :       can skip the division, which helps performance when this is common.  */
      82         [ +  + ]:    2369272 :   size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
      83                 :            : 
      84                 :            :   TYPE val_ptr;
      85                 :            :   HASHTYPE hash;
      86                 :            : 
      87                 :    2369272 :   hash = atomic_load_explicit(&htab->table[idx].hashval,
      88                 :            :                               memory_order_acquire);
      89         [ -  + ]:    2369272 :   if (hash == hval)
      90                 :          0 :     return -1;
      91         [ +  - ]:    2369272 :   else if (hash == 0)
      92                 :            :     {
      93                 :    2369272 :       val_ptr = NULL;
      94                 :    2369272 :       atomic_compare_exchange_strong_explicit(&htab->table[idx].val_ptr,
      95                 :            :                                               (uintptr_t *) &val_ptr,
      96                 :            :                                               (uintptr_t) val,
      97                 :            :                                               memory_order_acquire,
      98                 :            :                                               memory_order_acquire);
      99                 :            : 
     100         [ +  - ]:    2369272 :       if (val_ptr == NULL)
     101                 :            :         {
     102                 :    2369272 :           atomic_store_explicit(&htab->table[idx].hashval, hval,
     103                 :            :                                 memory_order_release);
     104                 :    2369272 :           return 0;
     105                 :            :         }
     106                 :            :       else
     107                 :            :         {
     108                 :            :           do
     109                 :            :             {
     110                 :          0 :               hash = atomic_load_explicit(&htab->table[idx].hashval,
     111                 :            :                                           memory_order_acquire);
     112                 :            :             }
     113         [ #  # ]:          0 :           while (hash == 0);
     114         [ #  # ]:          0 :           if (hash == hval)
     115                 :          0 :             return -1;
     116                 :            :         }
     117                 :            :     }
     118                 :            : 
     119                 :            :   /* Second hash function as suggested in [Knuth].  */
     120                 :          0 :   HASHTYPE second_hash = 1 + hval % (htab->size - 2);
     121                 :            : 
     122                 :            :   for(;;)
     123                 :            :     {
     124         [ #  # ]:          0 :       if (idx <= second_hash)
     125                 :          0 :           idx = htab->size + idx - second_hash;
     126                 :            :       else
     127                 :          0 :           idx -= second_hash;
     128                 :            : 
     129                 :          0 :       hash = atomic_load_explicit(&htab->table[idx].hashval,
     130                 :            :                                   memory_order_acquire);
     131         [ #  # ]:          0 :       if (hash == hval)
     132                 :          0 :         return -1;
     133         [ #  # ]:          0 :       else if (hash == 0)
     134                 :            :         {
     135                 :          0 :           val_ptr = NULL;
     136                 :          0 :           atomic_compare_exchange_strong_explicit(&htab->table[idx].val_ptr,
     137                 :            :                                                   (uintptr_t *) &val_ptr,
     138                 :            :                                                   (uintptr_t) val,
     139                 :            :                                                   memory_order_acquire,
     140                 :            :                                                   memory_order_acquire);
     141                 :            : 
     142         [ #  # ]:          0 :           if (val_ptr == NULL)
     143                 :            :             {
     144                 :          0 :               atomic_store_explicit(&htab->table[idx].hashval, hval,
     145                 :            :                                     memory_order_release);
     146                 :          0 :               return 0;
     147                 :            :             }
     148                 :            :           else
     149                 :            :             {
     150                 :            :               do
     151                 :            :                 {
     152                 :          0 :                   hash = atomic_load_explicit(&htab->table[idx].hashval,
     153                 :            :                                               memory_order_acquire);
     154                 :            :                 }
     155         [ #  # ]:          0 :               while (hash == 0);
     156         [ #  # ]:          0 :               if (hash == hval)
     157                 :          0 :                 return -1;
     158                 :            :             }
     159                 :            :         }
     160                 :            :     }
     161                 :            : }
     162                 :            : 
     163                 :            : #define NO_RESIZING 0u
     164                 :            : #define ALLOCATING_MEMORY 1u
     165                 :            : #define MOVING_DATA 3u
     166                 :            : #define CLEANING 2u
     167                 :            : 
     168                 :            : #define STATE_BITS 2u
     169                 :            : #define STATE_INCREMENT (1u << STATE_BITS)
     170                 :            : #define STATE_MASK (STATE_INCREMENT - 1)
     171                 :            : #define GET_STATE(A) ((A) & STATE_MASK)
     172                 :            : 
     173                 :            : #define IS_NO_RESIZE_OR_CLEANING(A) (((A) & 0x1u) == 0)
     174                 :            : 
     175                 :            : #define GET_ACTIVE_WORKERS(A) ((A) >> STATE_BITS)
     176                 :            : 
     177                 :            : #define INITIALIZATION_BLOCK_SIZE 256
     178                 :            : #define MOVE_BLOCK_SIZE 256
     179                 :            : #define CEIL(A, B) (((A) + (B) - 1) / (B))
     180                 :            : 
     181                 :            : /* Initializes records and copies the data from the old table.
     182                 :            :    It can share work with other threads.  Only the coordinator
     183                 :            :    will pass blocking as 1, other worker threads pass 0.  */
     184                 :      15304 : static void resize_helper(NAME *htab, int blocking)
     185                 :            : {
     186                 :      15304 :   size_t num_old_blocks = CEIL(htab->old_size, MOVE_BLOCK_SIZE);
     187                 :      15304 :   size_t num_new_blocks = CEIL(htab->size, INITIALIZATION_BLOCK_SIZE);
     188                 :            : 
     189                 :            :   size_t my_block;
     190                 :      15304 :   size_t num_finished_blocks = 0;
     191                 :            : 
     192                 :      15304 :   while ((my_block = atomic_fetch_add_explicit(&htab->next_init_block, 1,
     193                 :            :                                                 memory_order_acquire))
     194         [ +  + ]:      30638 :                                                     < num_new_blocks)
     195                 :            :     {
     196                 :      15334 :       size_t record_it = my_block * INITIALIZATION_BLOCK_SIZE;
     197                 :      15334 :       size_t record_end = (my_block + 1) * INITIALIZATION_BLOCK_SIZE;
     198         [ +  + ]:      15334 :       if (record_end > htab->size)
     199                 :      15304 :           record_end = htab->size;
     200                 :            : 
     201         [ +  + ]:    1390626 :       while (record_it++ != record_end)
     202                 :            :         {
     203                 :    1375292 :           atomic_init(&htab->table[record_it].hashval, (uintptr_t) NULL);
     204                 :    1375292 :           atomic_init(&htab->table[record_it].val_ptr, (uintptr_t) NULL);
     205                 :            :         }
     206                 :            : 
     207                 :      15334 :       num_finished_blocks++;
     208                 :            :     }
     209                 :            : 
     210                 :      15304 :   atomic_fetch_add_explicit(&htab->num_initialized_blocks,
     211                 :            :                             num_finished_blocks, memory_order_release);
     212                 :      15304 :   while (atomic_load_explicit(&htab->num_initialized_blocks,
     213         [ -  + ]:      15304 :                               memory_order_acquire) != num_new_blocks);
     214                 :            : 
     215                 :            :   /* All block are initialized, start moving */
     216                 :      15304 :   num_finished_blocks = 0;
     217                 :      15304 :   while ((my_block = atomic_fetch_add_explicit(&htab->next_move_block, 1,
     218                 :            :                                                 memory_order_acquire))
     219         [ +  + ]:      30608 :                                                     < num_old_blocks)
     220                 :            :     {
     221                 :      15304 :       size_t record_it = my_block * MOVE_BLOCK_SIZE;
     222                 :      15304 :       size_t record_end = (my_block + 1) * MOVE_BLOCK_SIZE;
     223         [ +  - ]:      15304 :       if (record_end > htab->old_size)
     224                 :      15304 :           record_end = htab->old_size;
     225                 :            : 
     226         [ +  + ]:     695268 :       while (record_it++ != record_end)
     227                 :            :         {
     228                 :     679964 :           TYPE val_ptr = (TYPE) atomic_load_explicit(
     229                 :            :               &htab->old_table[record_it].val_ptr,
     230                 :            :               memory_order_acquire);
     231         [ +  + ]:     679964 :           if (val_ptr == NULL)
     232                 :      66216 :               continue;
     233                 :            : 
     234                 :     613748 :           HASHTYPE hashval = atomic_load_explicit(
     235                 :            :               &htab->old_table[record_it].hashval,
     236                 :            :               memory_order_acquire);
     237         [ -  + ]:     613748 :           assert(hashval);
     238                 :            : 
     239                 :     613748 :           insert_helper(htab, hashval, val_ptr);
     240                 :            :         }
     241                 :            : 
     242                 :      15304 :       num_finished_blocks++;
     243                 :            :     }
     244                 :            : 
     245                 :      15304 :   atomic_fetch_add_explicit(&htab->num_moved_blocks, num_finished_blocks,
     246                 :            :                             memory_order_release);
     247                 :            : 
     248                 :            :   /* The coordinating thread will block here waiting for all blocks to
     249                 :            :      be moved.  */
     250         [ +  - ]:      15304 :   if (blocking)
     251                 :      15304 :       while (atomic_load_explicit(&htab->num_moved_blocks,
     252         [ -  + ]:      15304 :                                   memory_order_acquire) != num_old_blocks);
     253                 :      15304 : }
     254                 :            : 
     255                 :            : /* Called by the main thread holding the htab->resize_rwl lock to
     256                 :            :    coordinate the moving of hash table data. Allocates the new hash
     257                 :            :    table and frees the old one when moving all data is done.  */
     258                 :            : static void
     259                 :      15304 : resize_coordinator(NAME *htab)
     260                 :            : {
     261                 :      15304 :   htab->old_size = htab->size;
     262                 :      15304 :   htab->old_table = htab->table;
     263                 :            : 
     264                 :      15304 :   htab->size = next_prime(htab->size * 2);
     265                 :      15304 :   htab->table = malloc((1 + htab->size) * sizeof(htab->table[0]));
     266         [ -  + ]:      15304 :   assert(htab->table);
     267                 :            : 
     268                 :            :   /* Change state from ALLOCATING_MEMORY to MOVING_DATA */
     269                 :      15304 :   atomic_fetch_xor_explicit(&htab->resizing_state,
     270                 :            :                             ALLOCATING_MEMORY ^ MOVING_DATA,
     271                 :            :                             memory_order_release);
     272                 :            : 
     273                 :      15304 :   resize_helper(htab, 1);
     274                 :            : 
     275                 :            :   /* Change state from MOVING_DATA to CLEANING */
     276                 :      15304 :   size_t resize_state = atomic_fetch_xor_explicit(&htab->resizing_state,
     277                 :            :                                                   MOVING_DATA ^ CLEANING,
     278                 :            :                                                   memory_order_acq_rel);
     279         [ -  + ]:      15304 :   while (GET_ACTIVE_WORKERS(resize_state) != 0)
     280                 :          0 :       resize_state = atomic_load_explicit(&htab->resizing_state,
     281                 :            :                                           memory_order_acquire);
     282                 :            : 
     283                 :            :   /* There are no more active workers */
     284                 :      15304 :   atomic_store_explicit(&htab->next_init_block, 0, memory_order_relaxed);
     285                 :      15304 :   atomic_store_explicit(&htab->num_initialized_blocks, 0,
     286                 :            :                         memory_order_relaxed);
     287                 :            : 
     288                 :      15304 :   atomic_store_explicit(&htab->next_move_block, 0, memory_order_relaxed);
     289                 :      15304 :   atomic_store_explicit(&htab->num_moved_blocks, 0, memory_order_relaxed);
     290                 :            : 
     291                 :      15304 :   free(htab->old_table);
     292                 :            : 
     293                 :            :   /* Change state to NO_RESIZING */
     294                 :      15304 :   atomic_fetch_xor_explicit(&htab->resizing_state, CLEANING ^ NO_RESIZING,
     295                 :            :                             memory_order_relaxed);
     296                 :            : 
     297                 :      15304 : }
     298                 :            : 
     299                 :            : /* Called by any thread that wants to do an insert or find operation
     300                 :            :    but notices it cannot get the htab->resize_rwl lock because another
     301                 :            :    thread is resizing the hash table.  Try to help out by moving table
     302                 :            :    data if still necessary.  */
     303                 :            : static void
     304                 :          0 : resize_worker(NAME *htab)
     305                 :            : {
     306                 :          0 :   size_t resize_state = atomic_load_explicit(&htab->resizing_state,
     307                 :            :                                               memory_order_acquire);
     308                 :            : 
     309                 :            :   /* If the resize has finished */
     310         [ #  # ]:          0 :   if (IS_NO_RESIZE_OR_CLEANING(resize_state))
     311                 :          0 :       return;
     312                 :            : 
     313                 :            :   /* Register as worker and check if the resize has finished in the meantime*/
     314                 :          0 :   resize_state = atomic_fetch_add_explicit(&htab->resizing_state,
     315                 :            :                                             STATE_INCREMENT,
     316                 :            :                                             memory_order_acquire);
     317         [ #  # ]:          0 :   if (IS_NO_RESIZE_OR_CLEANING(resize_state))
     318                 :            :     {
     319                 :          0 :       atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
     320                 :            :                                 memory_order_relaxed);
     321                 :          0 :       return;
     322                 :            :     }
     323                 :            : 
     324                 :            :   /* Wait while the new table is being allocated. */
     325         [ #  # ]:          0 :   while (GET_STATE(resize_state) == ALLOCATING_MEMORY)
     326                 :          0 :       resize_state = atomic_load_explicit(&htab->resizing_state,
     327                 :            :                                           memory_order_acquire);
     328                 :            : 
     329                 :            :   /* Check if the resize is done */
     330         [ #  # ]:          0 :   assert(GET_STATE(resize_state) != NO_RESIZING);
     331         [ #  # ]:          0 :   if (GET_STATE(resize_state) == CLEANING)
     332                 :            :     {
     333                 :          0 :       atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
     334                 :            :                                 memory_order_relaxed);
     335                 :          0 :       return;
     336                 :            :     }
     337                 :            : 
     338                 :          0 :   resize_helper(htab, 0);
     339                 :            : 
     340                 :            :   /* Deregister worker */
     341                 :          0 :   atomic_fetch_sub_explicit(&htab->resizing_state, STATE_INCREMENT,
     342                 :            :                             memory_order_release);
     343                 :            : }
     344                 :            : 
     345                 :            : 
     346                 :            : int
     347                 :            : #define INIT(name) _INIT (name)
     348                 :            : #define _INIT(name) \
     349                 :            :   name##_init
     350                 :      69858 : INIT(NAME) (NAME *htab, size_t init_size)
     351                 :            : {
     352                 :            :   /* We need the size to be a prime.  */
     353                 :      69858 :   init_size = next_prime (init_size);
     354                 :            : 
     355                 :            :   /* Initialize the data structure.  */
     356                 :      69858 :   htab->size = init_size;
     357                 :      69858 :   atomic_init(&htab->filled, 0);
     358                 :      69858 :   atomic_init(&htab->resizing_state, 0);
     359                 :            : 
     360                 :      69858 :   atomic_init(&htab->next_init_block, 0);
     361                 :      69858 :   atomic_init(&htab->num_initialized_blocks, 0);
     362                 :            : 
     363                 :      69858 :   atomic_init(&htab->next_move_block, 0);
     364                 :      69858 :   atomic_init(&htab->num_moved_blocks, 0);
     365                 :            : 
     366                 :      69858 :   pthread_rwlock_init(&htab->resize_rwl, NULL);
     367                 :            : 
     368                 :      69858 :   htab->table = malloc ((init_size + 1) * sizeof (htab->table[0]));
     369         [ -  + ]:      69858 :   if (htab->table == NULL)
     370                 :          0 :       return -1;
     371                 :            : 
     372         [ +  + ]:    2642454 :   for (size_t i = 0; i <= init_size; i++)
     373                 :            :     {
     374                 :    2572596 :       atomic_init(&htab->table[i].hashval, (uintptr_t) NULL);
     375                 :    2572596 :       atomic_init(&htab->table[i].val_ptr, (uintptr_t) NULL);
     376                 :            :     }
     377                 :            : 
     378                 :      69858 :   return 0;
     379                 :            : }
     380                 :            : 
     381                 :            : 
     382                 :            : int
     383                 :            : #define FREE(name) _FREE (name)
     384                 :            : #define _FREE(name) \
     385                 :            : name##_free
     386                 :      69858 : FREE(NAME) (NAME *htab)
     387                 :            : {
     388                 :      69858 :   pthread_rwlock_destroy(&htab->resize_rwl);
     389                 :      69858 :   free (htab->table);
     390                 :      69858 :   return 0;
     391                 :            : }
     392                 :            : 
     393                 :            : 
     394                 :            : int
     395                 :            : #define INSERT(name) _INSERT (name)
     396                 :            : #define _INSERT(name) \
     397                 :            : name##_insert
     398                 :    1755524 : INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
     399                 :            : {
     400                 :    1755524 :   int incremented = 0;
     401                 :            : 
     402                 :            :   for(;;)
     403                 :      15304 :     {
     404                 :            :       /* If we cannot get the resize_rwl lock someone is resizing
     405                 :            :          hash table, try to help out by moving table data.  */
     406         [ -  + ]:    1770828 :       while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
     407                 :          0 :           resize_worker(htab);
     408                 :            : 
     409                 :            :       size_t filled;
     410         [ +  + ]:    1770828 :       if (!incremented)
     411                 :            :         {
     412                 :    1755524 :           filled = atomic_fetch_add_explicit(&htab->filled, 1,
     413                 :            :                                               memory_order_acquire);
     414                 :    1755524 :           incremented = 1;
     415                 :            :         }
     416                 :            :       else
     417                 :            :         {
     418                 :      15304 :           filled = atomic_load_explicit(&htab->filled,
     419                 :            :                                         memory_order_acquire);
     420                 :            :         }
     421                 :            : 
     422                 :            : 
     423         [ +  + ]:    1770828 :       if (100 * filled > 90 * htab->size)
     424                 :            :         {
     425                 :            :           /* Table is filled more than 90%.  Resize the table.  */
     426                 :            : 
     427                 :      15304 :           size_t resizing_state = atomic_load_explicit(&htab->resizing_state,
     428                 :            :                                                         memory_order_acquire);
     429         [ +  - ]:      15304 :           if (resizing_state == 0 &&
     430         [ +  - ]:      15304 :               atomic_compare_exchange_strong_explicit(&htab->resizing_state,
     431                 :            :                                                       &resizing_state,
     432                 :            :                                                       ALLOCATING_MEMORY,
     433                 :            :                                                       memory_order_acquire,
     434                 :            :                                                       memory_order_acquire))
     435                 :            :             {
     436                 :            :               /* Main resizing thread, will coordinate moving data.  */
     437                 :      15304 :               pthread_rwlock_unlock(&htab->resize_rwl);
     438                 :            : 
     439                 :      15304 :               pthread_rwlock_wrlock(&htab->resize_rwl);
     440                 :      15304 :               resize_coordinator(htab);
     441                 :      15304 :               pthread_rwlock_unlock(&htab->resize_rwl);
     442                 :            : 
     443                 :            :             }
     444                 :            :           else
     445                 :            :             {
     446                 :            :               /* Worker thread, will help moving data.  */
     447                 :          0 :               pthread_rwlock_unlock(&htab->resize_rwl);
     448                 :          0 :               resize_worker(htab);
     449                 :            :             }
     450                 :            :         }
     451                 :            :       else
     452                 :            :         {
     453                 :            :           /* Lock acquired, no need for resize*/
     454                 :    1755524 :           break;
     455                 :            :         }
     456                 :            :     }
     457                 :            : 
     458                 :    1755524 :   int ret_val = insert_helper(htab, hval, data);
     459         [ -  + ]:    1755524 :   if (ret_val == -1)
     460                 :          0 :       atomic_fetch_sub_explicit(&htab->filled, 1, memory_order_relaxed);
     461                 :    1755524 :   pthread_rwlock_unlock(&htab->resize_rwl);
     462                 :    1755524 :   return ret_val;
     463                 :            : }
     464                 :            : 
     465                 :            : 
     466                 :            : 
     467                 :            : TYPE
     468                 :            : #define FIND(name) _FIND (name)
     469                 :            : #define _FIND(name) \
     470                 :            :   name##_find
     471                 :   11785854 : FIND(NAME) (NAME *htab, HASHTYPE hval)
     472                 :            : {
     473                 :            :   /* If we cannot get the resize_rwl lock someone is resizing
     474                 :            :      the hash table, try to help out by moving table data.  */
     475         [ -  + ]:   11785854 :   while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
     476                 :          0 :     resize_worker(htab);
     477                 :            : 
     478                 :            :   size_t idx;
     479                 :            : 
     480                 :            :   /* Make the hash data nonzero.  */
     481         [ +  - ]:   11785854 :   hval = hval ?: 1;
     482                 :   11785854 :   idx = lookup(htab, hval);
     483                 :            : 
     484         [ +  + ]:   11785854 :   if (idx == 0)
     485                 :            :     {
     486                 :    2095444 :       pthread_rwlock_unlock(&htab->resize_rwl);
     487                 :    2095444 :       return NULL;
     488                 :            :     }
     489                 :            : 
     490                 :            :   /* get a copy before unlocking the lock */
     491                 :    9690410 :   TYPE ret_val = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
     492                 :            :                                              memory_order_relaxed);
     493                 :            : 
     494                 :    9690410 :   pthread_rwlock_unlock(&htab->resize_rwl);
     495                 :    9690410 :   return ret_val;
     496                 :            : }

Generated by: LCOV version 1.14