LCOV - code coverage report
Current view: top level - gcc - sparseset.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 51 88 58.0 %
Date: 2020-04-04 11:58:09 Functions: 5 7 71.4 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* SparseSet implementation.
       2                 :            :    Copyright (C) 2007-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Peter Bergner <bergner@vnet.ibm.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                 :            : #include "config.h"
      22                 :            : #include "system.h"
      23                 :            : #include "sparseset.h"
      24                 :            : 
      25                 :            : /* Allocate and clear a n_elms SparseSet.  */
      26                 :            : 
      27                 :            : sparseset
      28                 :   13948100 : sparseset_alloc (SPARSESET_ELT_TYPE n_elms)
      29                 :            : {
      30                 :   13948100 :   unsigned int n_bytes = sizeof (struct sparseset_def)
      31                 :   13948100 :                          + ((n_elms - 1) * 2 * sizeof (SPARSESET_ELT_TYPE));
      32                 :            : 
      33                 :   13948100 :   sparseset set = XNEWVAR (struct sparseset_def, n_bytes);
      34                 :            : 
      35                 :            :   /* Mark the sparseset as defined to silence some valgrind uninitialized
      36                 :            :      read errors when accessing set->sparse[n] when "n" is not, and never has
      37                 :            :      been, in the set.  These uninitialized reads are expected, by design and
      38                 :            :      harmless.  */
      39                 :   13948100 :   VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (set, n_bytes));
      40                 :            : 
      41                 :   13948100 :   set->dense = &(set->elms[0]);
      42                 :   13948100 :   set->sparse = &(set->elms[n_elms]);
      43                 :   13948100 :   set->size = n_elms;
      44                 :   13948100 :   sparseset_clear (set);
      45                 :   13948100 :   return set;
      46                 :            : }
      47                 :            : 
      48                 :            : /* Low level routine not meant for use outside of sparseset.[ch].
      49                 :            :    Assumes idx1 < s->members and idx2 < s->members.  */
      50                 :            : 
      51                 :            : static inline void
      52                 :     406416 : sparseset_swap (sparseset s, SPARSESET_ELT_TYPE idx1, SPARSESET_ELT_TYPE idx2)
      53                 :            : {
      54                 :     406416 :   SPARSESET_ELT_TYPE tmp = s->dense[idx2];
      55                 :     406416 :   sparseset_insert_bit (s, s->dense[idx1], idx2);
      56                 :     406416 :   sparseset_insert_bit (s, tmp, idx1);
      57                 :            : }
      58                 :            : 
      59                 :            : /* Operation: S = S - {e}
      60                 :            :    Delete e from the set S if it is a member of S.  */
      61                 :            : 
      62                 :            : void
      63                 :  518323000 : sparseset_clear_bit (sparseset s, SPARSESET_ELT_TYPE e)
      64                 :            : {
      65                 :  518323000 :   if (sparseset_bit_p (s, e))
      66                 :            :     {
      67                 :  512876000 :       SPARSESET_ELT_TYPE idx = s->sparse[e];
      68                 :  512876000 :       SPARSESET_ELT_TYPE iter = s->iter;
      69                 :  512876000 :       SPARSESET_ELT_TYPE mem = s->members - 1;
      70                 :            : 
      71                 :            :       /* If we are iterating over this set and we want to delete a
      72                 :            :          member we've already visited, then we swap the element we
      73                 :            :          want to delete with the element at the current iteration
      74                 :            :          index so that it plays well together with the code below
      75                 :            :          that actually removes the element.  */
      76                 :  512876000 :       if (s->iterating && idx <= iter)
      77                 :            :         {
      78                 :  312286000 :           if (idx < iter)
      79                 :            :             {
      80                 :     406416 :               sparseset_swap (s, idx, iter);
      81                 :     406416 :               idx = iter;
      82                 :            :             }
      83                 :  312286000 :           s->iter_inc = 0;
      84                 :            :         }
      85                 :            : 
      86                 :            :       /* Replace the element we want to delete with the last element
      87                 :            :          in the dense array and then decrement s->members, effectively
      88                 :            :          removing the element we want to delete.  */
      89                 :  512876000 :       sparseset_insert_bit (s, s->dense[mem], idx);
      90                 :  512876000 :       s->members = mem;
      91                 :            :     }
      92                 :  518323000 : }
      93                 :            : 
      94                 :            : /* Operation: D = S
      95                 :            :    Restrictions: none.  */
      96                 :            : 
      97                 :            : void
      98                 :  139236000 : sparseset_copy (sparseset d, sparseset s)
      99                 :            : {
     100                 :  139236000 :   SPARSESET_ELT_TYPE i;
     101                 :            : 
     102                 :  139236000 :   if (d == s)
     103                 :            :     return;
     104                 :            : 
     105                 :  139236000 :   sparseset_clear (d);
     106                 :  156326000 :   for (i = 0; i < s->members; i++)
     107                 :   17090100 :     sparseset_insert_bit (d, s->dense[i], i);
     108                 :  139236000 :   d->members = s->members;
     109                 :            : }
     110                 :            : 
     111                 :            : /* Operation: D = A & B.
     112                 :            :    Restrictions: none.  */
     113                 :            : 
     114                 :            : void
     115                 :          0 : sparseset_and (sparseset d, sparseset a, sparseset b)
     116                 :            : {
     117                 :          0 :   SPARSESET_ELT_TYPE e;
     118                 :            : 
     119                 :          0 :   if (a == b)
     120                 :            :     {
     121                 :          0 :       if (d != a)
     122                 :          0 :         sparseset_copy (d, a);
     123                 :          0 :       return;
     124                 :            :     }
     125                 :            : 
     126                 :          0 :   if (d == a || d == b)
     127                 :            :     {
     128                 :          0 :       sparseset s = (d == a) ? b : a;
     129                 :            : 
     130                 :          0 :       EXECUTE_IF_SET_IN_SPARSESET (d, e)
     131                 :          0 :         if (!sparseset_bit_p (s, e))
     132                 :          0 :           sparseset_clear_bit (d, e);
     133                 :            :     }
     134                 :            :   else
     135                 :            :     {
     136                 :          0 :       sparseset sml, lrg;
     137                 :            : 
     138                 :          0 :       if (sparseset_cardinality (a) < sparseset_cardinality (b))
     139                 :            :         {
     140                 :            :           sml = a;
     141                 :            :           lrg = b;
     142                 :            :         }
     143                 :            :       else
     144                 :            :         {
     145                 :          0 :           sml = b;
     146                 :          0 :           lrg = a;
     147                 :            :         }
     148                 :            : 
     149                 :          0 :       sparseset_clear (d);
     150                 :          0 :       EXECUTE_IF_SET_IN_SPARSESET (sml, e)
     151                 :          0 :         if (sparseset_bit_p (lrg, e))
     152                 :          0 :           sparseset_set_bit (d, e);
     153                 :            :     }
     154                 :            : }
     155                 :            : 
     156                 :            : /* Operation: D = A & ~B.
     157                 :            :    Restrictions: D != B, unless D == A == B.  */
     158                 :            : 
     159                 :            : void
     160                 :  139236000 : sparseset_and_compl (sparseset d, sparseset a, sparseset b)
     161                 :            : {
     162                 :  139236000 :   SPARSESET_ELT_TYPE e;
     163                 :            : 
     164                 :  139236000 :   if (a == b)
     165                 :            :     {
     166                 :          0 :       sparseset_clear (d);
     167                 :          0 :       return;
     168                 :            :     }
     169                 :            : 
     170                 :  139236000 :   gcc_assert (d != b);
     171                 :            : 
     172                 :  139236000 :   if (d == a)
     173                 :            :     {
     174                 :          0 :       if (sparseset_cardinality (d) < sparseset_cardinality (b))
     175                 :            :         {
     176                 :          0 :           EXECUTE_IF_SET_IN_SPARSESET (d, e)
     177                 :          0 :             if (sparseset_bit_p (b, e))
     178                 :          0 :               sparseset_clear_bit (d, e);
     179                 :            :         }
     180                 :            :       else
     181                 :            :         {
     182                 :          0 :           EXECUTE_IF_SET_IN_SPARSESET (b, e)
     183                 :          0 :             sparseset_clear_bit (d, e);
     184                 :            :         }
     185                 :            :     }
     186                 :            :   else
     187                 :            :     {
     188                 :  139236000 :       sparseset_clear (d);
     189                 :  478363000 :       EXECUTE_IF_SET_IN_SPARSESET (a, e)
     190                 :   99945100 :         if (!sparseset_bit_p (b, e))
     191                 :   84059500 :           sparseset_set_bit (d, e);
     192                 :            :     }
     193                 :            : }
     194                 :            : 
     195                 :            : /* Operation: D = A | B.
     196                 :            :    Restrictions: none.  */
     197                 :            : 
     198                 :            : void
     199                 :    8004240 : sparseset_ior (sparseset d, sparseset a, sparseset b)
     200                 :            : {
     201                 :    8004240 :   SPARSESET_ELT_TYPE e;
     202                 :            : 
     203                 :    8004240 :   if (a == b)
     204                 :          0 :     sparseset_copy (d, a);
     205                 :    8004240 :   else if (d == b)
     206                 :            :     {
     207                 :          0 :       EXECUTE_IF_SET_IN_SPARSESET (a, e)
     208                 :          0 :         sparseset_set_bit (d, e);
     209                 :            :     }
     210                 :            :   else
     211                 :            :     {
     212                 :    8004240 :       if (d != a)
     213                 :          0 :         sparseset_copy (d, a);
     214                 :   88291400 :       EXECUTE_IF_SET_IN_SPARSESET (b, e)
     215                 :   72282900 :         sparseset_set_bit (d, e);
     216                 :            :     }
     217                 :    8004240 : }
     218                 :            : 
     219                 :            : /* Operation: A == B
     220                 :            :    Restrictions: none.  */
     221                 :            : 
     222                 :            : bool
     223                 :          0 : sparseset_equal_p (sparseset a, sparseset b)
     224                 :            : {
     225                 :          0 :   SPARSESET_ELT_TYPE e;
     226                 :            : 
     227                 :          0 :   if (a == b)
     228                 :            :     return true;
     229                 :            : 
     230                 :          0 :   if (sparseset_cardinality (a) != sparseset_cardinality (b))
     231                 :            :     return false;
     232                 :            : 
     233                 :          0 :   EXECUTE_IF_SET_IN_SPARSESET (a, e)
     234                 :          0 :     if (!sparseset_bit_p (b, e))
     235                 :            :       return false;
     236                 :            : 
     237                 :            :   return true;
     238                 :            : }
     239                 :            : 

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.