LCOV - code coverage report
Current view: top level - gcc - sparseset.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 33 33 100.0 %
Date: 2020-05-30 12:51:24 Functions: 2 2 100.0 %
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                 :            : #ifndef GCC_SPARSESET_H
      22                 :            : #define GCC_SPARSESET_H
      23                 :            : 
      24                 :            : /* Implementation of the Briggs and Torczon sparse set representation.
      25                 :            :    The sparse set representation was first published in:
      26                 :            : 
      27                 :            :    "An Efficient Representation for Sparse Sets",
      28                 :            :    ACM LOPLAS, Vol. 2, Nos. 1-4, March-December 1993, Pages 59-69.
      29                 :            : 
      30                 :            :    The sparse set representation is suitable for integer sets with a
      31                 :            :    fixed-size universe.  Two vectors are used to store the members of
      32                 :            :    the set.  If an element I is in the set, then sparse[I] is the
      33                 :            :    index of I in the dense vector, and dense[sparse[I]] == I.  The dense
      34                 :            :    vector works like a stack.  The size of the stack is the cardinality
      35                 :            :    of the set.
      36                 :            : 
      37                 :            :    The following operations can be performed in O(1) time:
      38                 :            : 
      39                 :            :      * clear                    : sparseset_clear
      40                 :            :      * cardinality              : sparseset_cardinality
      41                 :            :      * set_size                 : sparseset_size
      42                 :            :      * member_p                 : sparseset_bit_p
      43                 :            :      * add_member               : sparseset_set_bit
      44                 :            :      * remove_member            : sparseset_clear_bit
      45                 :            :      * choose_one               : sparseset_pop
      46                 :            : 
      47                 :            :    Additionally, the sparse set representation supports enumeration of
      48                 :            :    the members in O(N) time, where n is the number of members in the set.
      49                 :            :    The members of the set are stored cache-friendly in the dense vector.
      50                 :            :    This makes it a competitive choice for iterating over relatively sparse
      51                 :            :    sets requiring operations:
      52                 :            : 
      53                 :            :      * forall                   : EXECUTE_IF_SET_IN_SPARSESET
      54                 :            :      * set_copy                 : sparseset_copy
      55                 :            :      * set_intersection         : sparseset_and
      56                 :            :      * set_union                : sparseset_ior
      57                 :            :      * set_difference           : sparseset_and_compl
      58                 :            :      * set_disjuction           : (not implemented)
      59                 :            :      * set_compare              : sparseset_equal_p
      60                 :            : 
      61                 :            :    NB: It is OK to use remove_member during EXECUTE_IF_SET_IN_SPARSESET.
      62                 :            :    The iterator is updated for it.
      63                 :            : 
      64                 :            :    Based on the efficiency of these operations, this representation of
      65                 :            :    sparse sets will often be superior to alternatives such as simple
      66                 :            :    bitmaps, linked-list bitmaps, array bitmaps, balanced binary trees,
      67                 :            :    hash tables, linked lists, etc., if the set is sufficiently sparse.
      68                 :            :    In the LOPLAS paper the cut-off point where sparse sets became faster
      69                 :            :    than simple bitmaps (see sbitmap.h) when N / U < 64 (where U is the
      70                 :            :    size of the universe of the set).
      71                 :            : 
      72                 :            :    Because the set universe is fixed, the set cannot be resized.  For
      73                 :            :    sparse sets with initially unknown size, linked-list bitmaps are a
      74                 :            :    better choice, see bitmap.h.
      75                 :            : 
      76                 :            :    Sparse sets storage requirements are relatively large: O(U) with a
      77                 :            :    larger constant than sbitmaps (if the storage requirement for an
      78                 :            :    sbitmap with universe U is S, then the storage required for a sparse
      79                 :            :    set for the same universe are 2*HOST_BITS_PER_WIDEST_FAST_INT * S).
      80                 :            :    Accessing the sparse vector is not very cache-friendly, but iterating
      81                 :            :    over the members in the set is cache-friendly because only the dense
      82                 :            :    vector is used.  */
      83                 :            : 
      84                 :            : /* Data Structure used for the SparseSet representation.  */
      85                 :            : 
      86                 :            : #define SPARSESET_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
      87                 :            : #define SPARSESET_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
      88                 :            : 
      89                 :            : typedef struct sparseset_def
      90                 :            : {
      91                 :            :   SPARSESET_ELT_TYPE *dense;    /* Dense array.  */
      92                 :            :   SPARSESET_ELT_TYPE *sparse;   /* Sparse array.  */
      93                 :            :   SPARSESET_ELT_TYPE members;   /* Number of elements.  */
      94                 :            :   SPARSESET_ELT_TYPE size;      /* Maximum number of elements.  */
      95                 :            :   SPARSESET_ELT_TYPE iter;      /* Iterator index.  */
      96                 :            :   unsigned char iter_inc;       /* Iteration increment amount.  */
      97                 :            :   bool iterating;
      98                 :            :   SPARSESET_ELT_TYPE elms[2];   /* Combined dense and sparse arrays.  */
      99                 :            : } *sparseset;
     100                 :            : 
     101                 :            : #define sparseset_free(MAP)  free(MAP)
     102                 :            : extern sparseset sparseset_alloc (SPARSESET_ELT_TYPE n_elms);
     103                 :            : extern void sparseset_clear_bit (sparseset, SPARSESET_ELT_TYPE);
     104                 :            : extern void sparseset_copy (sparseset, sparseset);
     105                 :            : extern void sparseset_and (sparseset, sparseset, sparseset);
     106                 :            : extern void sparseset_and_compl (sparseset, sparseset, sparseset);
     107                 :            : extern void sparseset_ior (sparseset, sparseset, sparseset);
     108                 :            : extern bool sparseset_equal_p (sparseset, sparseset);
     109                 :            : 
     110                 :            : /* Operation: S = {}
     111                 :            :    Clear the set of all elements.  */
     112                 :            : 
     113                 :            : static inline void
     114                 :  930589520 : sparseset_clear (sparseset s)
     115                 :            : {
     116                 :  930589520 :   s->members = 0;
     117                 :  906914560 :   s->iterating = false;
     118                 :   33144890 : }
     119                 :            : 
     120                 :            : /* Return the number of elements currently in the set.  */
     121                 :            : 
     122                 :            : static inline SPARSESET_ELT_TYPE
     123                 :   89340405 : sparseset_cardinality (sparseset s)
     124                 :            : {
     125                 :   68736305 :   return s->members;
     126                 :            : }
     127                 :            : 
     128                 :            : /* Return the maximum number of elements this set can hold.  */
     129                 :            : 
     130                 :            : static inline SPARSESET_ELT_TYPE
     131                 :            : sparseset_size (sparseset s)
     132                 :            : {
     133                 :            :   return s->size;
     134                 :            : }
     135                 :            : 
     136                 :            : /* Return true if e is a member of the set S, otherwise return false.  */
     137                 :            : 
     138                 :            : static inline bool
     139                 : 5592909700 : sparseset_bit_p (sparseset s, SPARSESET_ELT_TYPE e)
     140                 :            : {
     141                 : 5592909700 :   SPARSESET_ELT_TYPE idx;
     142                 :            : 
     143                 : 5592909700 :   gcc_checking_assert (e < s->size);
     144                 :            : 
     145                 : 5592909700 :   idx = s->sparse[e];
     146                 :            : 
     147                 : 5592909700 :   return idx < s->members && s->dense[idx] == e;
     148                 :            : }
     149                 :            : 
     150                 :            : /* Low level insertion routine not meant for use outside of sparseset.[ch].
     151                 :            :    Assumes E is valid and not already a member of the set S.  */
     152                 :            : 
     153                 :            : static inline void
     154                 : 3198995700 : sparseset_insert_bit (sparseset s, SPARSESET_ELT_TYPE e, SPARSESET_ELT_TYPE idx)
     155                 :            : {
     156                 : 3198995700 :   s->sparse[e] = idx;
     157                 : 3076053700 :   s->dense[idx] = e;
     158                 : 2661762700 : }
     159                 :            : 
     160                 :            : /* Operation: S = S + {e}
     161                 :            :    Insert E into the set S, if it isn't already a member.  */
     162                 :            : 
     163                 :            : static inline void
     164                 : 2751500480 : sparseset_set_bit (sparseset s, SPARSESET_ELT_TYPE e)
     165                 :            : {
     166                 : 2751500480 :   if (!sparseset_bit_p (s, e))
     167                 : 2661762700 :     sparseset_insert_bit (s, e, s->members++);
     168                 : 2751500480 : }
     169                 :            : 
     170                 :            : /* Return and remove the last member added to the set S.  */
     171                 :            : 
     172                 :            : static inline SPARSESET_ELT_TYPE
     173                 :            : sparseset_pop (sparseset s)
     174                 :            : {
     175                 :            :   SPARSESET_ELT_TYPE mem = s->members;
     176                 :            : 
     177                 :            :   gcc_checking_assert (mem != 0);
     178                 :            : 
     179                 :            :   s->members = mem - 1;
     180                 :            :   return s->dense[s->members];
     181                 :            : }
     182                 :            : 
     183                 :            : static inline void
     184                 : 1122808500 : sparseset_iter_init (sparseset s)
     185                 :            : {
     186                 : 1122808500 :   s->iter = 0;
     187                 : 1122808500 :   s->iter_inc = 1;
     188                 : 1122808500 :   s->iterating = true;
     189                 : 1122808500 : }
     190                 :            : 
     191                 :            : static inline bool
     192                 : 3171236000 : sparseset_iter_p (sparseset s)
     193                 :            : {
     194                 : 3171236000 :   if (s->iterating && s->iter < s->members)
     195                 :            :     return true;
     196                 :            :   else
     197                 :  996027000 :     return s->iterating = false;
     198                 :            : }
     199                 :            : 
     200                 :            : static inline SPARSESET_ELT_TYPE
     201                 : 2175205000 : sparseset_iter_elm (sparseset s)
     202                 :            : {
     203                 : 2175205000 :   return s->dense[s->iter];
     204                 :            : }
     205                 :            : 
     206                 :            : static inline void
     207                 : 2048429000 : sparseset_iter_next (sparseset s)
     208                 :            : {
     209                 : 2048429000 :   s->iter += s->iter_inc;
     210                 : 2048429000 :   s->iter_inc = 1;
     211                 : 1880273000 : }
     212                 :            : 
     213                 :            : #define EXECUTE_IF_SET_IN_SPARSESET(SPARSESET, ITER)                    \
     214                 :            :   for (sparseset_iter_init (SPARSESET);                                 \
     215                 :            :        sparseset_iter_p (SPARSESET)                                     \
     216                 :            :        && (((ITER) = sparseset_iter_elm (SPARSESET)) || 1);             \
     217                 :            :        sparseset_iter_next (SPARSESET))
     218                 :            : 
     219                 :            : #endif /* GCC_SPARSESET_H */

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.