LCOV - code coverage report
Current view: top level - gcc - sbitmap.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 410 491 83.5 %
Date: 2020-04-04 11:58:09 Functions: 29 39 74.4 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Simple bitmaps.
       2                 :            :    Copyright (C) 1999-2020 Free Software Foundation, Inc.
       3                 :            : 
       4                 :            : This file is part of GCC.
       5                 :            : 
       6                 :            : GCC is free software; you can redistribute it and/or modify it under
       7                 :            : the terms of the GNU General Public License as published by the Free
       8                 :            : Software Foundation; either version 3, or (at your option) any later
       9                 :            : version.
      10                 :            : 
      11                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :            : for more details.
      15                 :            : 
      16                 :            : You should have received a copy of the GNU General Public License
      17                 :            : along with GCC; see the file COPYING3.  If not see
      18                 :            : <http://www.gnu.org/licenses/>.  */
      19                 :            : 
      20                 :            : #include "config.h"
      21                 :            : #include "system.h"
      22                 :            : #include "coretypes.h"
      23                 :            : #include "sbitmap.h"
      24                 :            : #include "selftest.h"
      25                 :            : 
      26                 :            : typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
      27                 :            : typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr;
      28                 :            : 
      29                 :            : /* Return the size in bytes of a bitmap MAP.  */
      30                 :            : 
      31                 :  812041000 : static inline unsigned int sbitmap_size_bytes (const_sbitmap map)
      32                 :            : {
      33                 :  812041000 :    return map->size * sizeof (SBITMAP_ELT_TYPE);
      34                 :            : }
      35                 :            : 
      36                 :            : 
      37                 :            : /* Bitmap manipulation routines.  */
      38                 :            : 
      39                 :            : /* Allocate a simple bitmap of N_ELMS bits.  */
      40                 :            : 
      41                 :            : sbitmap
      42                 :  592297000 : sbitmap_alloc (unsigned int n_elms)
      43                 :            : {
      44                 :  592297000 :   unsigned int bytes, size, amt;
      45                 :  592297000 :   sbitmap bmap;
      46                 :            : 
      47                 :  592297000 :   size = SBITMAP_SET_SIZE (n_elms);
      48                 :  592297000 :   bytes = size * sizeof (SBITMAP_ELT_TYPE);
      49                 :  592297000 :   amt = (sizeof (struct simple_bitmap_def)
      50                 :            :          + bytes - sizeof (SBITMAP_ELT_TYPE));
      51                 :  592297000 :   bmap = (sbitmap) xmalloc (amt);
      52                 :  592297000 :   bmap->n_bits = n_elms;
      53                 :  592297000 :   bmap->size = size;
      54                 :  592297000 :   return bmap;
      55                 :            : }
      56                 :            : 
      57                 :            : /* Resize a simple bitmap BMAP to N_ELMS bits.  If increasing the
      58                 :            :    size of BMAP, clear the new bits to zero if the DEF argument
      59                 :            :    is zero, and set them to one otherwise.  */
      60                 :            : 
      61                 :            : sbitmap
      62                 :    1208700 : sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
      63                 :            : {
      64                 :    1208700 :   unsigned int bytes, size, amt;
      65                 :    1208700 :   unsigned int last_bit;
      66                 :            : 
      67                 :    1208700 :   size = SBITMAP_SET_SIZE (n_elms);
      68                 :    1208700 :   bytes = size * sizeof (SBITMAP_ELT_TYPE);
      69                 :    1208700 :   if (bytes > sbitmap_size_bytes (bmap))
      70                 :            :     {
      71                 :     246998 :       amt = (sizeof (struct simple_bitmap_def)
      72                 :            :             + bytes - sizeof (SBITMAP_ELT_TYPE));
      73                 :     246998 :       bmap = (sbitmap) xrealloc (bmap, amt);
      74                 :            :     }
      75                 :            : 
      76                 :    1208700 :   if (n_elms > bmap->n_bits)
      77                 :            :     {
      78                 :    1208700 :       if (def)
      79                 :            :         {
      80                 :          0 :           memset (bmap->elms + bmap->size, -1,
      81                 :          0 :                   bytes - sbitmap_size_bytes (bmap));
      82                 :            : 
      83                 :            :           /* Set the new bits if the original last element.  */
      84                 :          0 :           last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
      85                 :          0 :           if (last_bit)
      86                 :          0 :             bmap->elms[bmap->size - 1]
      87                 :          0 :               |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
      88                 :            : 
      89                 :            :           /* Clear the unused bit in the new last element.  */
      90                 :          0 :           last_bit = n_elms % SBITMAP_ELT_BITS;
      91                 :          0 :           if (last_bit)
      92                 :          0 :             bmap->elms[size - 1]
      93                 :          0 :               &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
      94                 :            :         }
      95                 :            :       else
      96                 :    1208700 :         memset (bmap->elms + bmap->size, 0, bytes - sbitmap_size_bytes (bmap));
      97                 :            :     }
      98                 :          0 :   else if (n_elms < bmap->n_bits)
      99                 :            :     {
     100                 :            :       /* Clear the surplus bits in the last word.  */
     101                 :          0 :       last_bit = n_elms % SBITMAP_ELT_BITS;
     102                 :          0 :       if (last_bit)
     103                 :          0 :         bmap->elms[size - 1]
     104                 :          0 :           &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
     105                 :            :     }
     106                 :            : 
     107                 :    1208700 :   bmap->n_bits = n_elms;
     108                 :    1208700 :   bmap->size = size;
     109                 :    1208700 :   return bmap;
     110                 :            : }
     111                 :            : 
     112                 :            : /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized.  */
     113                 :            : 
     114                 :            : sbitmap
     115                 :          0 : sbitmap_realloc (sbitmap src, unsigned int n_elms)
     116                 :            : {
     117                 :          0 :   unsigned int bytes, size, amt;
     118                 :          0 :   sbitmap bmap;
     119                 :            : 
     120                 :          0 :   size = SBITMAP_SET_SIZE (n_elms);
     121                 :          0 :   bytes = size * sizeof (SBITMAP_ELT_TYPE);
     122                 :          0 :   amt = (sizeof (struct simple_bitmap_def)
     123                 :            :          + bytes - sizeof (SBITMAP_ELT_TYPE));
     124                 :            : 
     125                 :          0 :   if (sbitmap_size_bytes (src)  >= bytes)
     126                 :            :     {
     127                 :          0 :       src->n_bits = n_elms;
     128                 :          0 :       return src;
     129                 :            :     }
     130                 :            : 
     131                 :          0 :   bmap = (sbitmap) xrealloc (src, amt);
     132                 :          0 :   bmap->n_bits = n_elms;
     133                 :          0 :   bmap->size = size;
     134                 :          0 :   return bmap;
     135                 :            : }
     136                 :            : 
     137                 :            : /* Allocate a vector of N_VECS bitmaps of N_ELMS bits.  */
     138                 :            : 
     139                 :            : sbitmap *
     140                 :    8888210 : sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
     141                 :            : {
     142                 :    8888210 :   unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
     143                 :    8888210 :   sbitmap *bitmap_vector;
     144                 :            : 
     145                 :    8888210 :   size = SBITMAP_SET_SIZE (n_elms);
     146                 :    8888210 :   bytes = size * sizeof (SBITMAP_ELT_TYPE);
     147                 :    8888210 :   elm_bytes = (sizeof (struct simple_bitmap_def)
     148                 :            :                + bytes - sizeof (SBITMAP_ELT_TYPE));
     149                 :    8888210 :   vector_bytes = n_vecs * sizeof (sbitmap *);
     150                 :            : 
     151                 :            :   /* Round up `vector_bytes' to account for the alignment requirements
     152                 :            :      of an sbitmap.  One could allocate the vector-table and set of sbitmaps
     153                 :            :      separately, but that requires maintaining two pointers or creating
     154                 :            :      a cover struct to hold both pointers (so our result is still just
     155                 :            :      one pointer).  Neither is a bad idea, but this is simpler for now.  */
     156                 :    8888210 :   {
     157                 :            :     /* Based on DEFAULT_ALIGNMENT computation in obstack.c.  */
     158                 :    8888210 :     struct { char x; SBITMAP_ELT_TYPE y; } align;
     159                 :    8888210 :     int alignment = (char *) & align.y - & align.x;
     160                 :    8888210 :     vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
     161                 :            :   }
     162                 :            : 
     163                 :    8888210 :   amt = vector_bytes + (n_vecs * elm_bytes);
     164                 :    8888210 :   bitmap_vector = (sbitmap *) xmalloc (amt);
     165                 :            : 
     166                 :  212893000 :   for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
     167                 :            :     {
     168                 :  204005000 :       sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
     169                 :            : 
     170                 :  204005000 :       bitmap_vector[i] = b;
     171                 :  204005000 :       b->n_bits = n_elms;
     172                 :  204005000 :       b->size = size;
     173                 :            :     }
     174                 :            : 
     175                 :    8888210 :   return bitmap_vector;
     176                 :            : }
     177                 :            : 
     178                 :            : /* Copy sbitmap SRC to DST.  */
     179                 :            : 
     180                 :            : void
     181                 :   42184400 : bitmap_copy (sbitmap dst, const_sbitmap src)
     182                 :            : {
     183                 :   42184400 :   gcc_checking_assert (src->size <= dst->size);
     184                 :            : 
     185                 :   42184400 :   memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
     186                 :   42184400 : }
     187                 :            : 
     188                 :            : /* Determine if a == b.  */
     189                 :            : int
     190                 :          0 : bitmap_equal_p (const_sbitmap a, const_sbitmap b)
     191                 :            : {
     192                 :          0 :   bitmap_check_sizes (a, b);
     193                 :            : 
     194                 :          0 :   return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
     195                 :            : }
     196                 :            : 
     197                 :            : /* Return true if the bitmap is empty.  */
     198                 :            : 
     199                 :            : bool
     200                 :  150374000 : bitmap_empty_p (const_sbitmap bmap)
     201                 :            : {
     202                 :  150374000 :   unsigned int i;
     203                 :  190129000 :   for (i=0; i<bmap->size; i++)
     204                 :  186029000 :     if (bmap->elms[i])
     205                 :            :       return false;
     206                 :            : 
     207                 :            :   return true;
     208                 :            : }
     209                 :            : 
     210                 :            : /* Clear COUNT bits from START in BMAP.  */
     211                 :            : 
     212                 :            : void
     213                 :    1645980 : bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count)
     214                 :            : {
     215                 :    1645980 :   if (count == 0)
     216                 :            :     return;
     217                 :            : 
     218                 :    1645980 :   bitmap_check_index (bmap, start + count - 1);
     219                 :            : 
     220                 :    1645980 :   unsigned int start_word = start / SBITMAP_ELT_BITS;
     221                 :    1645980 :   unsigned int start_bitno = start % SBITMAP_ELT_BITS;
     222                 :            : 
     223                 :            :   /* Clearing less than a full word, starting at the beginning of a word.  */
     224                 :    1645980 :   if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
     225                 :            :     {
     226                 :     556129 :       SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
     227                 :     556129 :       bmap->elms[start_word] &= ~mask;
     228                 :     556129 :       return;
     229                 :            :     }
     230                 :            : 
     231                 :    1089850 :   unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
     232                 :    1089850 :   unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
     233                 :            : 
     234                 :            :   /* Clearing starts somewhere in the middle of the first word.  Clear up to
     235                 :            :      the end of the first word or the end of the requested region, whichever
     236                 :            :      comes first.  */
     237                 :    1089850 :   if (start_bitno != 0)
     238                 :            :     {
     239                 :    2168310 :       unsigned int nbits = ((start_word == end_word)
     240                 :    1084160 :                             ? end_bitno - start_bitno
     241                 :            :                             : SBITMAP_ELT_BITS - start_bitno);
     242                 :    1084160 :       SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
     243                 :    1084160 :       mask <<= start_bitno;
     244                 :    1084160 :       bmap->elms[start_word] &= ~mask;
     245                 :    1084160 :       start_word++;
     246                 :    1084160 :       count -= nbits;
     247                 :            :     }
     248                 :            : 
     249                 :    1089850 :   if (count == 0)
     250                 :            :     return;
     251                 :            : 
     252                 :            :   /* Now clear words at a time until we hit a partial word.  */
     253                 :      13162 :   unsigned int nwords = (end_word - start_word);
     254                 :      13162 :   if (nwords)
     255                 :            :     {
     256                 :       5754 :       memset (&bmap->elms[start_word], 0, nwords * sizeof (SBITMAP_ELT_TYPE));
     257                 :       5754 :       count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
     258                 :       5754 :       start_word += nwords;
     259                 :            :     }
     260                 :            : 
     261                 :      13162 :   if (count == 0)
     262                 :            :     return;
     263                 :            : 
     264                 :            :   /* Now handle residuals in the last word.  */
     265                 :       9220 :   SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
     266                 :       9220 :   bmap->elms[start_word] &= ~mask;
     267                 :            : }
     268                 :            : 
     269                 :            : /* Set COUNT bits from START in BMAP.  */
     270                 :            : void
     271                 :   15241100 : bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count)
     272                 :            : {
     273                 :   15241100 :   if (count == 0)
     274                 :            :     return;
     275                 :            : 
     276                 :   15241100 :   bitmap_check_index (bmap, start + count - 1);
     277                 :            : 
     278                 :   15241100 :   unsigned int start_word = start / SBITMAP_ELT_BITS;
     279                 :   15241100 :   unsigned int start_bitno = start % SBITMAP_ELT_BITS;
     280                 :            : 
     281                 :            :   /* Setting less than a full word, starting at the beginning of a word.  */
     282                 :   15241100 :   if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
     283                 :            :     {
     284                 :   15057300 :       SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
     285                 :   15057300 :       bmap->elms[start_word] |= mask;
     286                 :   15057300 :       return;
     287                 :            :     }
     288                 :            : 
     289                 :     183732 :   unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
     290                 :     183732 :   unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
     291                 :            : 
     292                 :            :   /* Setting starts somewhere in the middle of the first word.  Set up to
     293                 :            :      the end of the first word or the end of the requested region, whichever
     294                 :            :      comes first.  */
     295                 :     183732 :   if (start_bitno != 0)
     296                 :            :     {
     297                 :          4 :       unsigned int nbits = ((start_word == end_word)
     298                 :          2 :                             ? end_bitno - start_bitno
     299                 :            :                             : SBITMAP_ELT_BITS - start_bitno);
     300                 :          2 :       SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
     301                 :          2 :       mask <<= start_bitno;
     302                 :          2 :       bmap->elms[start_word] |= mask;
     303                 :          2 :       start_word++;
     304                 :          2 :       count -= nbits;
     305                 :            :     }
     306                 :            : 
     307                 :     183732 :   if (count == 0)
     308                 :            :     return;
     309                 :            : 
     310                 :            :   /* Now set words at a time until we hit a partial word.  */
     311                 :     183730 :   unsigned int nwords = (end_word - start_word);
     312                 :     183730 :   if (nwords)
     313                 :            :     {
     314                 :     183730 :       memset (&bmap->elms[start_word], 0xff,
     315                 :     183730 :               nwords * sizeof (SBITMAP_ELT_TYPE));
     316                 :     183730 :       count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
     317                 :     183730 :       start_word += nwords;
     318                 :            :     }
     319                 :            : 
     320                 :     183730 :   if (count == 0)
     321                 :            :     return;
     322                 :            : 
     323                 :            :   /* Now handle residuals in the last word.  */
     324                 :     119376 :   SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
     325                 :     119376 :   bmap->elms[start_word] |= mask;
     326                 :            : }
     327                 :            : 
     328                 :            : /* Return TRUE if any bit between START and END inclusive is set within
     329                 :            :    the simple bitmap BMAP.  Return FALSE otherwise.  */
     330                 :            : 
     331                 :            : bool
     332                 :     277763 : bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end)
     333                 :            : {
     334                 :     277763 :   gcc_checking_assert (start <= end);
     335                 :     277763 :   bitmap_check_index (bmap, end);
     336                 :            : 
     337                 :     277763 :   unsigned int start_word = start / SBITMAP_ELT_BITS;
     338                 :     277763 :   unsigned int start_bitno = start % SBITMAP_ELT_BITS;
     339                 :            : 
     340                 :     277763 :   unsigned int end_word = end / SBITMAP_ELT_BITS;
     341                 :     277763 :   unsigned int end_bitno = end % SBITMAP_ELT_BITS;
     342                 :            : 
     343                 :            :   /* Check beginning of first word if different from zero.  */
     344                 :     277763 :   if (start_bitno != 0)
     345                 :            :     {
     346                 :     257979 :       SBITMAP_ELT_TYPE high_mask = ~(SBITMAP_ELT_TYPE)0;
     347                 :     257979 :       if (start_word == end_word && end_bitno + 1 < SBITMAP_ELT_BITS)
     348                 :     257156 :         high_mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
     349                 :            : 
     350                 :     257979 :       SBITMAP_ELT_TYPE low_mask = ((SBITMAP_ELT_TYPE)1 << start_bitno) - 1;
     351                 :     257979 :       SBITMAP_ELT_TYPE mask = high_mask - low_mask;
     352                 :     257979 :       if (bmap->elms[start_word] & mask)
     353                 :            :         return true;
     354                 :        401 :       start_word++;
     355                 :            :     }
     356                 :            : 
     357                 :      20185 :   if (start_word > end_word)
     358                 :            :     return false;
     359                 :            : 
     360                 :            :   /* Now test words at a time until we hit a partial word.  */
     361                 :      19801 :   unsigned int nwords = (end_word - start_word);
     362                 :      19975 :   while (nwords)
     363                 :            :     {
     364                 :        208 :       if (bmap->elms[start_word])
     365                 :            :         return true;
     366                 :        174 :       start_word++;
     367                 :        174 :       nwords--;
     368                 :            :     }
     369                 :            : 
     370                 :            :   /* Now handle residuals in the last word.  */
     371                 :      19767 :   SBITMAP_ELT_TYPE mask = ~(SBITMAP_ELT_TYPE)0;
     372                 :      19767 :   if (end_bitno + 1 < SBITMAP_ELT_BITS)
     373                 :      19610 :     mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1;
     374                 :      19767 :   return (bmap->elms[start_word] & mask) != 0;
     375                 :            : }
     376                 :            : 
     377                 :            : #if GCC_VERSION < 3400
     378                 :            : /* Table of number of set bits in a character, indexed by value of char.  */
     379                 :            : static const unsigned char popcount_table[] =
     380                 :            : {
     381                 :            :     0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
     382                 :            :     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
     383                 :            :     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
     384                 :            :     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
     385                 :            :     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
     386                 :            :     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
     387                 :            :     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
     388                 :            :     3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
     389                 :            : };
     390                 :            : 
     391                 :            : static unsigned long
     392                 :            : sbitmap_popcount (SBITMAP_ELT_TYPE a)
     393                 :            : {
     394                 :            :   unsigned long ret = 0;
     395                 :            :   unsigned i;
     396                 :            : 
     397                 :            :   /* Just do this the table way for now  */
     398                 :            :   for (i = 0; i < HOST_BITS_PER_WIDEST_FAST_INT; i += 8)
     399                 :            :     ret += popcount_table[(a >> i) & 0xff];
     400                 :            :   return ret;
     401                 :            : }
     402                 :            : #endif
     403                 :            : 
     404                 :            : /* Count and return the number of bits set in the bitmap BMAP.  */
     405                 :            : 
     406                 :            : unsigned int
     407                 :          2 : bitmap_count_bits (const_sbitmap bmap)
     408                 :            : {
     409                 :          2 :   unsigned int count = 0;
     410                 :          4 :   for (unsigned int i = 0; i < bmap->size; i++)
     411                 :          2 :     if (bmap->elms[i])
     412                 :            :       {
     413                 :            : #if GCC_VERSION < 3400
     414                 :            :         count += sbitmap_popcount (bmap->elms[i]);
     415                 :            : #else
     416                 :            : # if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
     417                 :          2 :         count += __builtin_popcountl (bmap->elms[i]);
     418                 :            : # elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG
     419                 :            :         count += __builtin_popcountll (bmap->elms[i]);
     420                 :            : # else
     421                 :            :         count += __builtin_popcount (bmap->elms[i]);
     422                 :            : # endif
     423                 :            : #endif
     424                 :            :       }
     425                 :          2 :   return count;
     426                 :            : }
     427                 :            : 
     428                 :            : /* Zero all elements in a bitmap.  */
     429                 :            : 
     430                 :            : void
     431                 :  745130000 : bitmap_clear (sbitmap bmap)
     432                 :            : {
     433                 :  745130000 :   memset (bmap->elms, 0, sbitmap_size_bytes (bmap));
     434                 :  745130000 : }
     435                 :            : 
     436                 :            : /* Set all elements in a bitmap to ones.  */
     437                 :            : 
     438                 :            : void
     439                 :   64493800 : bitmap_ones (sbitmap bmap)
     440                 :            : {
     441                 :   64493800 :   unsigned int last_bit;
     442                 :            : 
     443                 :   64493800 :   memset (bmap->elms, -1, sbitmap_size_bytes (bmap));
     444                 :            : 
     445                 :   64493800 :   last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
     446                 :   64493800 :   if (last_bit)
     447                 :   63948500 :     bmap->elms[bmap->size - 1]
     448                 :   63948500 :       = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
     449                 :   64493800 : }
     450                 :            : 
     451                 :            : /* Zero a vector of N_VECS bitmaps.  */
     452                 :            : 
     453                 :            : void
     454                 :    4033550 : bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs)
     455                 :            : {
     456                 :    4033550 :   unsigned int i;
     457                 :            : 
     458                 :   97797100 :   for (i = 0; i < n_vecs; i++)
     459                 :   93763500 :     bitmap_clear (bmap[i]);
     460                 :    4033550 : }
     461                 :            : 
     462                 :            : /* Set a vector of N_VECS bitmaps to ones.  */
     463                 :            : 
     464                 :            : void
     465                 :    2421690 : bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
     466                 :            : {
     467                 :    2421690 :   unsigned int i;
     468                 :            : 
     469                 :   57555800 :   for (i = 0; i < n_vecs; i++)
     470                 :   55134200 :     bitmap_ones (bmap[i]);
     471                 :    2421690 : }
     472                 :            : 
     473                 :            : /* Set DST to be A union (B - C).
     474                 :            :    DST = A | (B & ~C).
     475                 :            :    Returns true if any change is made.  */
     476                 :            : 
     477                 :            : bool
     478                 :   46622500 : bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
     479                 :            : {
     480                 :   46622500 :   bitmap_check_sizes (a, b);
     481                 :   46622500 :   bitmap_check_sizes (b, c);
     482                 :            : 
     483                 :   46622500 :   unsigned int i, n = dst->size;
     484                 :   46622500 :   sbitmap_ptr dstp = dst->elms;
     485                 :   46622500 :   const_sbitmap_ptr ap = a->elms;
     486                 :   46622500 :   const_sbitmap_ptr bp = b->elms;
     487                 :   46622500 :   const_sbitmap_ptr cp = c->elms;
     488                 :   46622500 :   SBITMAP_ELT_TYPE changed = 0;
     489                 :            : 
     490                 :  164210000 :   for (i = 0; i < n; i++)
     491                 :            :     {
     492                 :  117587000 :       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
     493                 :  117587000 :       changed |= *dstp ^ tmp;
     494                 :  117587000 :       *dstp++ = tmp;
     495                 :            :     }
     496                 :            : 
     497                 :   46622500 :   return changed != 0;
     498                 :            : }
     499                 :            : 
     500                 :            : /* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
     501                 :            : 
     502                 :            : void
     503                 :   14885600 : bitmap_not (sbitmap dst, const_sbitmap src)
     504                 :            : {
     505                 :   14885600 :   bitmap_check_sizes (src, dst);
     506                 :            : 
     507                 :   14885600 :   unsigned int i, n = dst->size;
     508                 :   14885600 :   sbitmap_ptr dstp = dst->elms;
     509                 :   14885600 :   const_sbitmap_ptr srcp = src->elms;
     510                 :   14885600 :   unsigned int last_bit;
     511                 :            : 
     512                 :   52659000 :   for (i = 0; i < n; i++)
     513                 :   37773400 :     *dstp++ = ~*srcp++;
     514                 :            : 
     515                 :            :   /* Zero all bits past n_bits, by ANDing dst with bitmap_ones.  */
     516                 :   14885600 :   last_bit = src->n_bits % SBITMAP_ELT_BITS;
     517                 :   14885600 :   if (last_bit)
     518                 :   14697600 :     dst->elms[n-1] = dst->elms[n-1]
     519                 :   14697600 :       & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
     520                 :   14885600 : }
     521                 :            : 
     522                 :            : /* Set the bits in DST to be the difference between the bits
     523                 :            :    in A and the bits in B. i.e. dst = a & (~b).  */
     524                 :            : 
     525                 :            : void
     526                 :   24861400 : bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
     527                 :            : {
     528                 :   24861400 :   bitmap_check_sizes (a, b);
     529                 :   24861400 :   bitmap_check_sizes (b, dst);
     530                 :            : 
     531                 :   24861400 :   unsigned int i, dst_size = dst->size;
     532                 :   24861400 :   unsigned int min_size = dst->size;
     533                 :   24861400 :   sbitmap_ptr dstp = dst->elms;
     534                 :   24861400 :   const_sbitmap_ptr ap = a->elms;
     535                 :   24861400 :   const_sbitmap_ptr bp = b->elms;
     536                 :            : 
     537                 :            :   /* A should be at least as large as DEST, to have a defined source.  */
     538                 :   24861400 :   gcc_assert (a->size >= dst_size);
     539                 :            :   /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
     540                 :            :      only copy the subtrahend into dest.  */
     541                 :   24861400 :   if (b->size < min_size)
     542                 :            :     min_size = b->size;
     543                 :   86904900 :   for (i = 0; i < min_size; i++)
     544                 :   62043500 :     *dstp++ = *ap++ & (~*bp++);
     545                 :            :   /* Now fill the rest of dest from A, if B was too short.
     546                 :            :      This makes sense only when destination and A differ.  */
     547                 :   24861400 :   if (dst != a && i != dst_size)
     548                 :          0 :     for (; i < dst_size; i++)
     549                 :          0 :       *dstp++ = *ap++;
     550                 :   24861400 : }
     551                 :            : 
     552                 :            : /* Return true if there are any bits set in A are also set in B.
     553                 :            :    Return false otherwise.  */
     554                 :            : 
     555                 :            : bool
     556                 :          0 : bitmap_intersect_p (const_sbitmap a, const_sbitmap b)
     557                 :            : {
     558                 :          0 :   bitmap_check_sizes (a, b);
     559                 :            : 
     560                 :          0 :   const_sbitmap_ptr ap = a->elms;
     561                 :          0 :   const_sbitmap_ptr bp = b->elms;
     562                 :          0 :   unsigned int i, n;
     563                 :            : 
     564                 :          0 :   n = MIN (a->size, b->size);
     565                 :          0 :   for (i = 0; i < n; i++)
     566                 :          0 :     if ((*ap++ & *bp++) != 0)
     567                 :            :       return true;
     568                 :            : 
     569                 :            :   return false;
     570                 :            : }
     571                 :            : 
     572                 :            : /* Set DST to be (A and B).
     573                 :            :    Return nonzero if any change is made.  */
     574                 :            : 
     575                 :            : bool
     576                 :   14005100 : bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b)
     577                 :            : {
     578                 :   14005100 :   bitmap_check_sizes (a, b);
     579                 :   14005100 :   bitmap_check_sizes (b, dst);
     580                 :            : 
     581                 :   14005100 :   unsigned int i, n = dst->size;
     582                 :   14005100 :   sbitmap_ptr dstp = dst->elms;
     583                 :   14005100 :   const_sbitmap_ptr ap = a->elms;
     584                 :   14005100 :   const_sbitmap_ptr bp = b->elms;
     585                 :   14005100 :   SBITMAP_ELT_TYPE changed = 0;
     586                 :            : 
     587                 :   49010000 :   for (i = 0; i < n; i++)
     588                 :            :     {
     589                 :   35004900 :       const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
     590                 :   35004900 :       SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
     591                 :   35004900 :       *dstp++ = tmp;
     592                 :   35004900 :       changed |= wordchanged;
     593                 :            :     }
     594                 :   14005100 :   return changed != 0;
     595                 :            : }
     596                 :            : 
     597                 :            : /* Set DST to be (A xor B)).
     598                 :            :    Return nonzero if any change is made.  */
     599                 :            : 
     600                 :            : bool
     601                 :          0 : bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b)
     602                 :            : {
     603                 :          0 :   bitmap_check_sizes (a, b);
     604                 :          0 :   bitmap_check_sizes (b, dst);
     605                 :            : 
     606                 :          0 :   unsigned int i, n = dst->size;
     607                 :          0 :   sbitmap_ptr dstp = dst->elms;
     608                 :          0 :   const_sbitmap_ptr ap = a->elms;
     609                 :          0 :   const_sbitmap_ptr bp = b->elms;
     610                 :          0 :   SBITMAP_ELT_TYPE changed = 0;
     611                 :            : 
     612                 :          0 :   for (i = 0; i < n; i++)
     613                 :            :     {
     614                 :          0 :       const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
     615                 :          0 :       SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
     616                 :          0 :       *dstp++ = tmp;
     617                 :          0 :       changed |= wordchanged;
     618                 :            :     }
     619                 :          0 :   return changed != 0;
     620                 :            : }
     621                 :            : 
     622                 :            : /* Set DST to be (A or B)).
     623                 :            :    Return nonzero if any change is made.  */
     624                 :            : 
     625                 :            : bool
     626                 :   20449900 : bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b)
     627                 :            : {
     628                 :   20449900 :   bitmap_check_sizes (a, b);
     629                 :   20449900 :   bitmap_check_sizes (b, dst);
     630                 :            : 
     631                 :   20449900 :   unsigned int i, n = dst->size;
     632                 :   20449900 :   sbitmap_ptr dstp = dst->elms;
     633                 :   20449900 :   const_sbitmap_ptr ap = a->elms;
     634                 :   20449900 :   const_sbitmap_ptr bp = b->elms;
     635                 :   20449900 :   SBITMAP_ELT_TYPE changed = 0;
     636                 :            : 
     637                 :  171358000 :   for (i = 0; i < n; i++)
     638                 :            :     {
     639                 :  150908000 :       const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
     640                 :  150908000 :       SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
     641                 :  150908000 :       *dstp++ = tmp;
     642                 :  150908000 :       changed |= wordchanged;
     643                 :            :     }
     644                 :   20449900 :   return changed != 0;
     645                 :            : }
     646                 :            : 
     647                 :            : /* Return nonzero if A is a subset of B.  */
     648                 :            : 
     649                 :            : bool
     650                 :          0 : bitmap_subset_p (const_sbitmap a, const_sbitmap b)
     651                 :            : {
     652                 :          0 :   bitmap_check_sizes (a, b);
     653                 :            : 
     654                 :          0 :   unsigned int i, n = a->size;
     655                 :          0 :   const_sbitmap_ptr ap, bp;
     656                 :            : 
     657                 :          0 :   for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
     658                 :          0 :     if ((*ap | *bp) != *bp)
     659                 :            :       return false;
     660                 :            : 
     661                 :            :   return true;
     662                 :            : }
     663                 :            : 
     664                 :            : /* Set DST to be (A or (B and C)).
     665                 :            :    Return nonzero if any change is made.  */
     666                 :            : 
     667                 :            : bool
     668                 :    7488310 : bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
     669                 :            : {
     670                 :    7488310 :   bitmap_check_sizes (a, b);
     671                 :    7488310 :   bitmap_check_sizes (b, c);
     672                 :    7488310 :   bitmap_check_sizes (c, dst);
     673                 :            : 
     674                 :    7488310 :   unsigned int i, n = dst->size;
     675                 :    7488310 :   sbitmap_ptr dstp = dst->elms;
     676                 :    7488310 :   const_sbitmap_ptr ap = a->elms;
     677                 :    7488310 :   const_sbitmap_ptr bp = b->elms;
     678                 :    7488310 :   const_sbitmap_ptr cp = c->elms;
     679                 :    7488310 :   SBITMAP_ELT_TYPE changed = 0;
     680                 :            : 
     681                 :   26617600 :   for (i = 0; i < n; i++)
     682                 :            :     {
     683                 :   19129300 :       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
     684                 :   19129300 :       changed |= *dstp ^ tmp;
     685                 :   19129300 :       *dstp++ = tmp;
     686                 :            :     }
     687                 :            : 
     688                 :    7488310 :   return changed != 0;
     689                 :            : }
     690                 :            : 
     691                 :            : /* Set DST to be (A and (B or C)).
     692                 :            :    Return nonzero if any change is made.  */
     693                 :            : 
     694                 :            : bool
     695                 :    8720990 : bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
     696                 :            : {
     697                 :    8720990 :   bitmap_check_sizes (a, b);
     698                 :    8720990 :   bitmap_check_sizes (b, c);
     699                 :    8720990 :   bitmap_check_sizes (c, dst);
     700                 :            : 
     701                 :    8720990 :   unsigned int i, n = dst->size;
     702                 :    8720990 :   sbitmap_ptr dstp = dst->elms;
     703                 :    8720990 :   const_sbitmap_ptr ap = a->elms;
     704                 :    8720990 :   const_sbitmap_ptr bp = b->elms;
     705                 :    8720990 :   const_sbitmap_ptr cp = c->elms;
     706                 :    8720990 :   SBITMAP_ELT_TYPE changed = 0;
     707                 :            : 
     708                 :   31270600 :   for (i = 0; i < n; i++)
     709                 :            :     {
     710                 :   22549600 :       const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
     711                 :   22549600 :       changed |= *dstp ^ tmp;
     712                 :   22549600 :       *dstp++ = tmp;
     713                 :            :     }
     714                 :            : 
     715                 :    8720990 :   return changed != 0;
     716                 :            : }
     717                 :            : 
     718                 :            : /* Return number of first bit set in the bitmap, -1 if none.  */
     719                 :            : 
     720                 :            : int
     721                 :    6298530 : bitmap_first_set_bit (const_sbitmap bmap)
     722                 :            : {
     723                 :    6298530 :   unsigned int n = 0;
     724                 :    6298530 :   sbitmap_iterator sbi;
     725                 :            : 
     726                 :   12597100 :   EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi)
     727                 :    3228260 :     return n;
     728                 :            :   return -1;
     729                 :            : }
     730                 :            : 
     731                 :            : /* Return number of last bit set in the bitmap, -1 if none.  */
     732                 :            : 
     733                 :            : int
     734                 :   31268700 : bitmap_last_set_bit (const_sbitmap bmap)
     735                 :            : {
     736                 :   31268700 :   int i;
     737                 :   31268700 :   const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
     738                 :            : 
     739                 :   43308500 :   for (i = bmap->size - 1; i >= 0; i--)
     740                 :            :     {
     741                 :   32039700 :       const SBITMAP_ELT_TYPE word = ptr[i];
     742                 :            : 
     743                 :   32039700 :       if (word != 0)
     744                 :            :         {
     745                 :   19999900 :           unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
     746                 :   19999900 :           SBITMAP_ELT_TYPE mask
     747                 :            :             = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
     748                 :            : 
     749                 : 2364850000 :           while (1)
     750                 :            :             {
     751                 : 1192430000 :               if ((word & mask) != 0)
     752                 :   19999900 :                 return index;
     753                 :            : 
     754                 : 1172430000 :               mask >>= 1;
     755                 : 1172430000 :               index--;
     756                 :            :             }
     757                 :            :         }
     758                 :            :     }
     759                 :            : 
     760                 :            :   return -1;
     761                 :            : }
     762                 :            : 
     763                 :            : void
     764                 :         28 : dump_bitmap (FILE *file, const_sbitmap bmap)
     765                 :            : {
     766                 :         28 :   unsigned int i, n, j;
     767                 :         28 :   unsigned int set_size = bmap->size;
     768                 :         28 :   unsigned int total_bits = bmap->n_bits;
     769                 :            : 
     770                 :         28 :   fprintf (file, "  ");
     771                 :         56 :   for (i = n = 0; i < set_size && n < total_bits; i++)
     772                 :         56 :     for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
     773                 :            :       {
     774                 :         28 :         if (n != 0 && n % 10 == 0)
     775                 :          0 :           fprintf (file, " ");
     776                 :            : 
     777                 :         28 :         fprintf (file, "%d",
     778                 :         28 :                  (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
     779                 :            :       }
     780                 :            : 
     781                 :         28 :   fprintf (file, "\n");
     782                 :         28 : }
     783                 :            : 
     784                 :            : DEBUG_FUNCTION void
     785                 :          0 : debug_raw (simple_bitmap_def &ref)
     786                 :            : {
     787                 :          0 :   dump_bitmap (stderr, &ref);
     788                 :          0 : }
     789                 :            : 
     790                 :            : DEBUG_FUNCTION void
     791                 :          0 : debug_raw (simple_bitmap_def *ptr)
     792                 :            : {
     793                 :          0 :   if (ptr)
     794                 :          0 :     debug_raw (*ptr);
     795                 :            :   else
     796                 :          0 :     fprintf (stderr, "<nil>\n");
     797                 :          0 : }
     798                 :            : 
     799                 :            : void
     800                 :         64 : dump_bitmap_file (FILE *file, const_sbitmap bmap)
     801                 :            : {
     802                 :         64 :   unsigned int i, pos;
     803                 :            : 
     804                 :         64 :   fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
     805                 :            : 
     806                 :        864 :   for (pos = 30, i = 0; i < bmap->n_bits; i++)
     807                 :        800 :     if (bitmap_bit_p (bmap, i))
     808                 :            :       {
     809                 :        122 :         if (pos > 70)
     810                 :            :           {
     811                 :          1 :             fprintf (file, "\n  ");
     812                 :          1 :             pos = 0;
     813                 :            :           }
     814                 :            : 
     815                 :        122 :         fprintf (file, "%d ", i);
     816                 :        189 :         pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
     817                 :            :       }
     818                 :            : 
     819                 :         64 :   fprintf (file, "}\n");
     820                 :         64 : }
     821                 :            : 
     822                 :            : DEBUG_FUNCTION void
     823                 :          0 : debug_bitmap (const_sbitmap bmap)
     824                 :            : {
     825                 :          0 :   dump_bitmap_file (stderr, bmap);
     826                 :          0 : }
     827                 :            : 
     828                 :            : DEBUG_FUNCTION void
     829                 :          0 : debug (simple_bitmap_def &ref)
     830                 :            : {
     831                 :          0 :   dump_bitmap_file (stderr, &ref);
     832                 :          0 : }
     833                 :            : 
     834                 :            : DEBUG_FUNCTION void
     835                 :          0 : debug (simple_bitmap_def *ptr)
     836                 :            : {
     837                 :          0 :   if (ptr)
     838                 :          0 :     debug (*ptr);
     839                 :            :   else
     840                 :          0 :     fprintf (stderr, "<nil>\n");
     841                 :          0 : }
     842                 :            : 
     843                 :            : void
     844                 :          4 : dump_bitmap_vector (FILE *file, const char *title, const char *subtitle,
     845                 :            :                      sbitmap *bmaps, int n_maps)
     846                 :            : {
     847                 :          4 :   int i;
     848                 :            : 
     849                 :          4 :   fprintf (file, "%s\n", title);
     850                 :         32 :   for (i = 0; i < n_maps; i++)
     851                 :            :     {
     852                 :         28 :       fprintf (file, "%s %d\n", subtitle, i);
     853                 :         28 :       dump_bitmap (file, bmaps[i]);
     854                 :            :     }
     855                 :            : 
     856                 :          4 :   fprintf (file, "\n");
     857                 :          4 : }
     858                 :            : 
     859                 :            : #if CHECKING_P
     860                 :            : 
     861                 :            : namespace selftest {
     862                 :            : 
     863                 :            : /* Selftests for sbitmaps.  */
     864                 :            : 
     865                 :            : /* Checking function that uses both bitmap_bit_in_range_p and
     866                 :            :    loop of bitmap_bit_p and verifies consistent results.  */
     867                 :            : 
     868                 :            : static bool
     869                 :         28 : bitmap_bit_in_range_p_checking (sbitmap s, unsigned int start,
     870                 :            :                                 unsigned end)
     871                 :            : {
     872                 :         28 :   bool r1 = bitmap_bit_in_range_p (s, start, end);
     873                 :         28 :   bool r2 = false;
     874                 :            : 
     875                 :       4076 :   for (unsigned int i = start; i <= end; i++)
     876                 :       4062 :     if (bitmap_bit_p (s, i))
     877                 :            :       {
     878                 :            :         r2 = true;
     879                 :            :         break;
     880                 :            :       }
     881                 :            : 
     882                 :         28 :   ASSERT_EQ (r1, r2);
     883                 :         28 :   return r1;
     884                 :            : }
     885                 :            : 
     886                 :            : /* Verify bitmap_set_range functions for sbitmap.  */
     887                 :            : 
     888                 :            : static void
     889                 :          2 : test_set_range ()
     890                 :            : {
     891                 :          2 :   sbitmap s = sbitmap_alloc (16);
     892                 :          2 :   bitmap_clear (s);
     893                 :            : 
     894                 :          2 :   bitmap_set_range (s, 0, 1);
     895                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 0, 0));
     896                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 15));
     897                 :          2 :   bitmap_set_range (s, 15, 1);
     898                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 14));
     899                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 15, 15));
     900                 :          2 :   sbitmap_free (s);
     901                 :            : 
     902                 :          2 :   s = sbitmap_alloc (1024);
     903                 :          2 :   bitmap_clear (s);
     904                 :          2 :   bitmap_set_range (s, 512, 1);
     905                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511));
     906                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 513, 1023));
     907                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512));
     908                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 512));
     909                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 513));
     910                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 508, 511));
     911                 :            : 
     912                 :          2 :   bitmap_clear (s);
     913                 :          2 :   bitmap_set_range (s, 512, 64);
     914                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511));
     915                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 512 + 64, 1023));
     916                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512));
     917                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512 + 63, 512 + 63));
     918                 :          2 :   sbitmap_free (s);
     919                 :          2 : }
     920                 :            : 
     921                 :            : /* Verify bitmap_bit_in_range_p functions for sbitmap.  */
     922                 :            : 
     923                 :            : static void
     924                 :          2 : test_bit_in_range ()
     925                 :            : {
     926                 :          2 :   sbitmap s = sbitmap_alloc (1024);
     927                 :          2 :   bitmap_clear (s);
     928                 :            : 
     929                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023));
     930                 :          2 :   bitmap_set_bit (s, 100);
     931                 :            : 
     932                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023));
     933                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 99));
     934                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 101, 1023));
     935                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 100));
     936                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 100));
     937                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 100, 100));
     938                 :          2 :   ASSERT_TRUE (bitmap_bit_p (s, 100));
     939                 :            : 
     940                 :          2 :   sbitmap_free (s);
     941                 :            : 
     942                 :          2 :   s = sbitmap_alloc (64);
     943                 :          2 :   bitmap_clear (s);
     944                 :          2 :   bitmap_set_bit (s, 63);
     945                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63));
     946                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 63));
     947                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 63, 63));
     948                 :          2 :   ASSERT_TRUE (bitmap_bit_p (s, 63));
     949                 :          2 :   sbitmap_free (s);
     950                 :            : 
     951                 :          2 :   s = sbitmap_alloc (1024);
     952                 :          2 :   bitmap_clear (s);
     953                 :          2 :   bitmap_set_bit (s, 128);
     954                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 127));
     955                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 129, 1023));
     956                 :            : 
     957                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 128));
     958                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 128));
     959                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 255));
     960                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 254));
     961                 :          2 :   ASSERT_TRUE (bitmap_bit_p (s, 128));
     962                 :            : 
     963                 :          2 :   bitmap_clear (s);
     964                 :          2 :   bitmap_set_bit (s, 8);
     965                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 8));
     966                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 12));
     967                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63));
     968                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 127));
     969                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 512));
     970                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 8, 8));
     971                 :          2 :   ASSERT_TRUE (bitmap_bit_p (s, 8));
     972                 :            : 
     973                 :          2 :   bitmap_clear (s);
     974                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 0));
     975                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 8));
     976                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 63));
     977                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 63));
     978                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 256));
     979                 :            : 
     980                 :          2 :   bitmap_set_bit (s, 0);
     981                 :          2 :   bitmap_set_bit (s, 16);
     982                 :          2 :   bitmap_set_bit (s, 32);
     983                 :          2 :   bitmap_set_bit (s, 48);
     984                 :          2 :   bitmap_set_bit (s, 64);
     985                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 0));
     986                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 16));
     987                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 48, 63));
     988                 :          2 :   ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 64));
     989                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 15));
     990                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 17, 31));
     991                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 49, 63));
     992                 :          2 :   ASSERT_FALSE (bitmap_bit_in_range_p (s, 65, 1023));
     993                 :          2 :   sbitmap_free (s);
     994                 :          2 : }
     995                 :            : 
     996                 :            : /* Run all of the selftests within this file.  */
     997                 :            : 
     998                 :            : void
     999                 :          2 : sbitmap_c_tests ()
    1000                 :            : {
    1001                 :          2 :   test_set_range ();
    1002                 :          2 :   test_bit_in_range ();
    1003                 :          2 : }
    1004                 :            : 
    1005                 :            : } // namespace selftest
    1006                 :            : #endif /* CHECKING_P */

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.