LCOV - code coverage report
Current view: top level - lib - fixedsizehash.h (source / functions) Hit Total Coverage
Test: elfutils-0.189 Lines: 42 45 93.3 %
Date: 2023-11-01 00:28:02 Functions: 4 4 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 18 22 81.8 %

           Branch data     Line data    Source code
       1                 :            : /* Fixed size hash table with internal linking.
       2                 :            :    Copyright (C) 2000, 2001, 2002, 2004, 2005 Red Hat, Inc.
       3                 :            :    This file is part of elfutils.
       4                 :            :    Written by 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 <errno.h>
      31                 :            : #include <stdlib.h>
      32                 :            : #include <string.h>
      33                 :            : 
      34                 :            : #include <system.h>
      35                 :            : 
      36                 :            : #define CONCAT_EXPANDED(t1,t2) t1 ## t2
      37                 :            : #define CONCAT(t1,t2) CONCAT_EXPANDED(t1,t2)
      38                 :            : 
      39                 :            : /* Before including this file the following macros must be defined:
      40                 :            : 
      41                 :            :    TYPE           data type of the hash table entries
      42                 :            :    HASHFCT        name of the hashing function to use
      43                 :            :    HASHTYPE       type used for the hashing value
      44                 :            :    COMPARE        comparison function taking two pointers to TYPE objects
      45                 :            :    CLASS          can be defined to `static' to avoid exporting the functions
      46                 :            :    PREFIX         prefix to be used for function and data type names
      47                 :            :    STORE_POINTER  if defined the table stores a pointer and not an element
      48                 :            :                   of type TYPE
      49                 :            :    INSERT_HASH    if defined alternate insert function which takes a hash
      50                 :            :                   value is defined
      51                 :            :    NO_FINI_FCT    if defined the fini function is not defined
      52                 :            : */
      53                 :            : 
      54                 :            : 
      55                 :            : /* Defined separately.  */
      56                 :            : extern size_t next_prime (size_t seed);
      57                 :            : 
      58                 :            : 
      59                 :            : /* Set default values.  */
      60                 :            : #ifndef HASHTYPE
      61                 :            : # define HASHTYPE size_t
      62                 :            : #endif
      63                 :            : 
      64                 :            : #ifndef CLASS
      65                 :            : # define CLASS
      66                 :            : #endif
      67                 :            : 
      68                 :            : #ifndef PREFIX
      69                 :            : # define PREFIX
      70                 :            : #endif
      71                 :            : 
      72                 :            : 
      73                 :            : /* The data structure.  */
      74                 :            : struct CONCAT(PREFIX,fshash)
      75                 :            : {
      76                 :            :   size_t nslots;
      77                 :            :   struct CONCAT(PREFIX,fshashent)
      78                 :            :   {
      79                 :            :     HASHTYPE hval;
      80                 :            : #ifdef STORE_POINTER
      81                 :            : # define ENTRYP(el) (el).entry
      82                 :            :     TYPE *entry;
      83                 :            : #else
      84                 :            : # define ENTRYP(el) &(el).entry
      85                 :            :     TYPE entry;
      86                 :            : #endif
      87                 :            :   } table[0];
      88                 :            : };
      89                 :            : 
      90                 :            : 
      91                 :            : /* Constructor for the hashing table.  */
      92                 :            : CLASS struct CONCAT(PREFIX,fshash) *
      93                 :          2 : CONCAT(PREFIX,fshash_init) (size_t nelems)
      94                 :            : {
      95                 :          2 :   struct CONCAT(PREFIX,fshash) *result;
      96                 :            :   /* We choose a size for the hashing table 150% over the number of
      97                 :            :      entries.  This will guarantee short medium search lengths.  */
      98                 :          2 :   const size_t max_size_t = ~((size_t) 0);
      99                 :            : 
     100         [ -  + ]:          2 :   if (nelems >= (max_size_t / 3) * 2)
     101                 :            :     {
     102                 :          0 :       errno = EINVAL;
     103                 :          0 :       return NULL;
     104                 :            :     }
     105                 :            : 
     106                 :            :   /* Adjust the size to be used for the hashing table.  */
     107         [ +  - ]:          2 :   nelems = next_prime (MAX ((nelems * 3) / 2, 10));
     108                 :            : 
     109                 :            :   /* Allocate the data structure for the result.  */
     110                 :          2 :   result = (struct CONCAT(PREFIX,fshash) *)
     111                 :          2 :     xcalloc (sizeof (struct CONCAT(PREFIX,fshash))
     112                 :            :              + (nelems + 1) * sizeof (struct CONCAT(PREFIX,fshashent)), 1);
     113         [ -  + ]:          2 :   if (result == NULL)
     114                 :            :     return NULL;
     115                 :            : 
     116                 :          2 :   result->nslots = nelems;
     117                 :            : 
     118                 :          2 :   return result;
     119                 :            : }
     120                 :            : 
     121                 :            : 
     122                 :            : #ifndef NO_FINI_FCT
     123                 :            : CLASS void
     124                 :          2 : CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab)
     125                 :            : {
     126                 :          2 :   free (htab);
     127                 :          0 : }
     128                 :            : #endif
     129                 :            : 
     130                 :            : 
     131                 :            : static struct CONCAT(PREFIX,fshashent) *
     132                 :       1184 : CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab,
     133                 :            :                               HASHTYPE hval, TYPE *data)
     134                 :            : {
     135                 :       1184 :   size_t idx = 1 + hval % htab->nslots;
     136                 :            : 
     137         [ +  + ]:       1184 :   if (htab->table[idx].hval != 0)
     138                 :            :     {
     139                 :        462 :       HASHTYPE hash;
     140                 :            : 
     141                 :            :       /* See whether this is the same entry.  */
     142         [ +  + ]:        462 :       if (htab->table[idx].hval == hval
     143         [ +  + ]:        142 :           && COMPARE (data, ENTRYP (htab->table[idx])) == 0)
     144                 :        138 :         return &htab->table[idx];
     145                 :            : 
     146                 :            :       /* Second hash function as suggested in [Knuth].  */
     147                 :        324 :       hash = 1 + hval % (htab->nslots - 2);
     148                 :            : 
     149                 :        538 :       do
     150                 :            :         {
     151         [ +  + ]:        538 :           if (idx <= hash)
     152                 :        274 :             idx = htab->nslots + idx - hash;
     153                 :            :           else
     154                 :        264 :             idx -= hash;
     155                 :            : 
     156         [ +  + ]:        538 :           if (htab->table[idx].hval == hval
     157         [ +  - ]:          4 :               && COMPARE (data, ENTRYP(htab->table[idx])) == 0)
     158                 :          4 :             return &htab->table[idx];
     159                 :            :         }
     160         [ +  + ]:        534 :       while (htab->table[idx].hval != 0);
     161                 :            :     }
     162                 :            : 
     163                 :       1042 :   return &htab->table[idx];
     164                 :            : }
     165                 :            : 
     166                 :            : 
     167                 :            : CLASS int
     168                 :            : __attribute__ ((unused))
     169                 :            : CONCAT(PREFIX,fshash_insert) (struct CONCAT(PREFIX,fshash) *htab,
     170                 :            :                               const char *str,
     171                 :            :                               size_t len __attribute__ ((unused)), TYPE *data)
     172                 :            : {
     173                 :            :   HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
     174                 :            :   struct CONCAT(PREFIX,fshashent) *slot;
     175                 :            : 
     176                 :            :   slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
     177                 :            :  if (slot->hval != 0)
     178                 :            :     /* We don't want to overwrite the old value.  */
     179                 :            :     return -1;
     180                 :            : 
     181                 :            :   slot->hval = hval;
     182                 :            : #ifdef STORE_POINTER
     183                 :            :   slot->entry = data;
     184                 :            : #else
     185                 :            :   slot->entry = *data;
     186                 :            : #endif
     187                 :            : 
     188                 :            :   return 0;
     189                 :            : }
     190                 :            : 
     191                 :            : 
     192                 :            : #ifdef INSERT_HASH
     193                 :            : CLASS int
     194                 :            : __attribute__ ((unused))
     195                 :            : CONCAT(PREFIX,fshash_insert_hash) (struct CONCAT(PREFIX,fshash) *htab,
     196                 :            :                                    HASHTYPE hval, TYPE *data)
     197                 :            : {
     198                 :            :   struct CONCAT(PREFIX,fshashent) *slot;
     199                 :            : 
     200                 :            :   slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
     201                 :            :   if (slot->hval != 0)
     202                 :            :     /* We don't want to overwrite the old value.  */
     203                 :            :     return -1;
     204                 :            : 
     205                 :            :   slot->hval = hval;
     206                 :            : #ifdef STORE_POINTER
     207                 :            :   slot->entry = data;
     208                 :            : #else
     209                 :            :   slot->entry = *data;
     210                 :            : #endif
     211                 :            : 
     212                 :            :   return 0;
     213                 :            : }
     214                 :            : #endif
     215                 :            : 
     216                 :            : 
     217                 :            : CLASS int
     218                 :            : __attribute__ ((unused))
     219                 :       1174 : CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab,
     220                 :            :                                  const char *str,
     221                 :            :                                  size_t len __attribute__ ((unused)),
     222                 :            :                                  TYPE *data)
     223                 :            : {
     224                 :       1174 :   HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
     225                 :       1174 :   struct CONCAT(PREFIX,fshashent) *slot;
     226                 :            : 
     227                 :       1174 :   slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
     228                 :       1174 :   slot->hval = hval;
     229                 :            : #ifdef STORE_POINTER
     230                 :            :   slot->entry = data;
     231                 :            : #else
     232                 :       1174 :   slot->entry = *data;
     233                 :            : #endif
     234                 :            : 
     235                 :       1174 :   return 0;
     236                 :            : }
     237                 :            : 
     238                 :            : 
     239                 :            : CLASS const TYPE *
     240                 :         10 : CONCAT(PREFIX,fshash_find) (const struct CONCAT(PREFIX,fshash) *htab,
     241                 :            :                             const char *str,
     242                 :            :                             size_t len __attribute__ ((unused)), TYPE *data)
     243                 :            : {
     244                 :         10 :   HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
     245                 :         10 :   struct CONCAT(PREFIX,fshashent) *slot;
     246                 :            : 
     247                 :         10 :   slot = CONCAT(PREFIX,fshash_lookup) ((struct CONCAT(PREFIX,fshash) *) htab,
     248                 :            :                                        hval, data);
     249         [ +  + ]:         10 :   if (slot->hval == 0)
     250                 :            :     /* Not found.  */
     251                 :            :     return NULL;
     252                 :            : 
     253                 :          8 :   return ENTRYP(*slot);
     254                 :            : }
     255                 :            : 
     256                 :            : 
     257                 :            : /* Unset the macros we expect.  */
     258                 :            : #undef TYPE
     259                 :            : #undef HASHFCT
     260                 :            : #undef HASHTYPE
     261                 :            : #undef COMPARE
     262                 :            : #undef CLASS
     263                 :            : #undef PREFIX
     264                 :            : #undef INSERT_HASH
     265                 :            : #undef STORE_POINTER
     266                 :            : #undef NO_FINI_FCT

Generated by: LCOV version 1.16