LCOV - code coverage report
Current view: top level - gcc - hash-table.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 9 18 50.0 %
Date: 2020-03-28 11:57:23 Functions: 1 4 25.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* A type-safe hash table template.
       2                 :            :    Copyright (C) 2012-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Lawrence Crowl <crowl@google.com>
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify it under
       8                 :            : the terms of the GNU General Public License as published by the Free
       9                 :            : Software Foundation; either version 3, or (at your option) any later
      10                 :            : version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15                 :            : for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : 
      22                 :            : /* This file implements a typed hash table.
      23                 :            :    The implementation borrows from libiberty's hashtab.  */
      24                 :            : 
      25                 :            : #ifdef GENERATOR_FILE
      26                 :            : #include "bconfig.h"
      27                 :            : #else
      28                 :            : #include "config.h"
      29                 :            : #endif
      30                 :            : #include "system.h"
      31                 :            : #include "coretypes.h"
      32                 :            : #include "hash-table.h"
      33                 :            : 
      34                 :            : /* Table of primes and multiplicative inverses.
      35                 :            : 
      36                 :            :    Note that these are not minimally reduced inverses.  Unlike when generating
      37                 :            :    code to divide by a constant, we want to be able to use the same algorithm
      38                 :            :    all the time.  All of these inverses (are implied to) have bit 32 set.
      39                 :            : 
      40                 :            :    For the record, here's the function that computed the table; it's a 
      41                 :            :    vastly simplified version of the function of the same name from gcc.  */
      42                 :            : 
      43                 :            : struct prime_ent const prime_tab[] = {
      44                 :            :   {          7, 0x24924925, 0x9999999b, 2 },
      45                 :            :   {         13, 0x3b13b13c, 0x745d1747, 3 },
      46                 :            :   {         31, 0x08421085, 0x1a7b9612, 4 },
      47                 :            :   {         61, 0x0c9714fc, 0x15b1e5f8, 5 },
      48                 :            :   {        127, 0x02040811, 0x0624dd30, 6 },
      49                 :            :   {        251, 0x05197f7e, 0x073260a5, 7 },
      50                 :            :   {        509, 0x01824366, 0x02864fc8, 8 },
      51                 :            :   {       1021, 0x00c0906d, 0x014191f7, 9 },
      52                 :            :   {       2039, 0x0121456f, 0x0161e69e, 10 },
      53                 :            :   {       4093, 0x00300902, 0x00501908, 11 },
      54                 :            :   {       8191, 0x00080041, 0x00180241, 12 },
      55                 :            :   {      16381, 0x000c0091, 0x00140191, 13 },
      56                 :            :   {      32749, 0x002605a5, 0x002a06e6, 14 },
      57                 :            :   {      65521, 0x000f00e2, 0x00110122, 15 },
      58                 :            :   {     131071, 0x00008001, 0x00018003, 16 },
      59                 :            :   {     262139, 0x00014002, 0x0001c004, 17 },
      60                 :            :   {     524287, 0x00002001, 0x00006001, 18 },
      61                 :            :   {    1048573, 0x00003001, 0x00005001, 19 },
      62                 :            :   {    2097143, 0x00004801, 0x00005801, 20 },
      63                 :            :   {    4194301, 0x00000c01, 0x00001401, 21 },
      64                 :            :   {    8388593, 0x00001e01, 0x00002201, 22 },
      65                 :            :   {   16777213, 0x00000301, 0x00000501, 23 },
      66                 :            :   {   33554393, 0x00001381, 0x00001481, 24 },
      67                 :            :   {   67108859, 0x00000141, 0x000001c1, 25 },
      68                 :            :   {  134217689, 0x000004e1, 0x00000521, 26 },
      69                 :            :   {  268435399, 0x00000391, 0x000003b1, 27 },
      70                 :            :   {  536870909, 0x00000019, 0x00000029, 28 },
      71                 :            :   { 1073741789, 0x0000008d, 0x00000095, 29 },
      72                 :            :   { 2147483647, 0x00000003, 0x00000007, 30 },
      73                 :            :   /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
      74                 :            :   { 0xfffffffb, 0x00000006, 0x00000008, 31 }
      75                 :            : };
      76                 :            : 
      77                 :            : /* Limit number of comparisons when calling hash_table<>::verify.  */
      78                 :            : unsigned int hash_table_sanitize_eq_limit;
      79                 :            : 
      80                 :            : /* The following function returns an index into the above table of the
      81                 :            :    nearest prime number which is at least N, and near a power of two. */
      82                 :            : 
      83                 :            : unsigned int
      84                 : 2215500000 : hash_table_higher_prime_index (unsigned long n)
      85                 :            : {
      86                 : 2215500000 :   unsigned int low = 0;
      87                 : 2215500000 :   unsigned int high = sizeof (prime_tab) / sizeof (prime_tab[0]);
      88                 :            : 
      89                 :13293000000 :   while (low != high)
      90                 :            :     {
      91                 :11077500000 :       unsigned int mid = low + (high - low) / 2;
      92                 :11077500000 :       if (n > prime_tab[mid].prime)
      93                 : 2304080000 :         low = mid + 1;
      94                 :            :       else
      95                 :            :         high = mid;
      96                 :            :     }
      97                 :            : 
      98                 :            :   /* If we've run out of primes, abort.  */
      99                 : 2215500000 :   gcc_assert (n <= prime_tab[low].prime);
     100                 :            : 
     101                 : 2215500000 :   return low;
     102                 :            : }
     103                 :            : 
     104                 :            : /* Return a reference to the lazily initialized hash-table usage description.
     105                 :            :    This needs to be a function rather than a simple global variable so that it
     106                 :            :    is reliably initialized before hash table variables in other files such as
     107                 :            :    sem_item::m_type_hash_cache.  */
     108                 :            : mem_alloc_description<mem_usage>&
     109                 :          0 : hash_table_usage ()
     110                 :            : {
     111                 :          0 :   static mem_alloc_description<mem_usage> usage;
     112                 :          0 :   return usage;
     113                 :            : }
     114                 :            : 
     115                 :            : /* Support function for statistics.  */
     116                 :          0 : void dump_hash_table_loc_statistics (void)
     117                 :            : {
     118                 :          0 :   if (!GATHER_STATISTICS)
     119                 :          0 :     return;
     120                 :            : 
     121                 :            :   for (unsigned i = HASH_TABLE_ORIGIN; i <= HASH_SET_ORIGIN; i++)
     122                 :            :     {
     123                 :            :       mem_alloc_origin origin = (mem_alloc_origin) i;
     124                 :            :       hash_table_usage ().dump (origin);
     125                 :            :     }
     126                 :            : }
     127                 :            : 
     128                 :            : /* Report a hash table checking error.  */
     129                 :            : 
     130                 :            : ATTRIBUTE_NORETURN ATTRIBUTE_COLD
     131                 :            : void
     132                 :          0 : hashtab_chk_error ()
     133                 :            : {
     134                 :          0 :   fprintf (stderr, "hash table checking failed: "
     135                 :            :            "equal operator returns true for a pair "
     136                 :            :            "of values with a different hash value\n");
     137                 :          0 :   gcc_unreachable ();
     138                 :            : }

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.