Re: Bitset statistics

[Akim Demaille]

| Akim Demaille writes:
|  > I have finished (at home), spreading bitset into Bison.  I have a few
|  > wishes: 
|  > 
|  > - int bitset_count: number of bits set.
|  > - int bitset_disjoint_p (bitset, bitset): whether they have common
|  >   bits.  (If different size, then die I guess).
| 
| OK, these are trivial to implement and are included in my new patch.

Thanks!

| I've also changed the API for the bitset vectors so that the
| number of vectors do not have to passed to every call.

Yeah!  I missed the existence of these!  Excellent, that cleans up
Bison even further.  Then I have another suggestion, which, I believe,
is general enough for submission to bitset:

----------------------------------------
/* Generate transitive closure of a matrix,
   Copyright 1984, 1989, 2000, 2001, 2002 Free Software Foundation,
Inc.

   This file is part of Bison, the GNU Compiler Compiler.

   Bison is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published
by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   Bison is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with Bison; see the file COPYING.  If not, write to
   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.  */


#include "system.h"
#include "getargs.h"
#include "bitsetv.h"
#include "warshall.h"

/*--------------------------------------------------------.
| Display the MATRIX array of SIZE bitsets of size SIZE.  |
`--------------------------------------------------------*/

static void
bitmatrix_print (const char *title, bitsetv matrix)
{
  size_t i, j;
  size_t size = bitset_size (matrix[0]);

  /* Title. */
  fprintf (stderr, "%s BEGIN\n", title);

  /* Column numbers. */
  fputs ("   ", stderr);
  for (i = 0; i < size; ++i)
    putc (i / 10 ? '0' + i / 10 : ' ', stderr);
  putc ('\n', stderr);
  fputs ("   ", stderr);
  for (i = 0; i < size; ++i)
    fprintf (stderr, "%d", i % 10);
  putc ('\n', stderr);

  /* Bar. */
  fputs ("  .", stderr);
  for (i = 0; i < size; ++i)
    putc ('-', stderr);
  fputs (".\n", stderr);

  /* Contents. */
  for (i = 0; i < size; ++i)
    {
      fprintf (stderr, "%2d|", i);
      for (j = 0; j < size; ++j)
        fputs (bitset_test (matrix[i], j) ? "1" : " ", stderr);
      fputs ("|\n", stderr);
    }

  /* Bar. */
  fputs ("  `", stderr);
  for (i = 0; i < size; ++i)
    putc ('-', stderr);
  fputs ("'\n", stderr);

  /* End title. */
  fprintf (stderr, "%s END\n\n", title);
}

/*-------------------------------------------------------------------.
| Given the MATRIX array of N bitsets of size N, modify its contents |
| to be the transive closure of what was given.                      |
`-------------------------------------------------------------------*/

static void
TC (bitsetv matrix)
{
  int i, j;

  if (trace_flag)
    bitmatrix_print ("TC: Input", matrix);

  /* R (J, I) && R (I, K) => R (J, K).
     I *must* be the outter loop. */

  for (i = 0; matrix[i]; ++i)
    for (j = 0; matrix[j]; ++j)
      if (bitset_test (matrix[j], i))
        bitset_or (matrix[j], matrix[j], matrix[i]);

  if (trace_flag)
    bitmatrix_print ("TC: Output", matrix);
}


/*---------------------------------------------------------------.
| Reflexive Transitive Closure.  Same as TC and then set all the |
| bits on the diagonal of MATRIX.                                |
`---------------------------------------------------------------*/

void
RTC (bitsetv matrix)
{
  int i;

  TC (matrix);
  for (i = 0; matrix[i]; ++i)
    bitset_set (matrix[i], i);
}
----------------------------------------

| I suppose the next thing to do is to write up the docs.  I've been
| waiting for a response on the gcc mailing list but the "cone of
| silence" seems to have descended...

:(

AFAIAC, I am still waiting for the FSF's approval :(

Also, as yet another wish from a painful user ;) I have many
warnings.  If I was not aware GCC was also looking for 0 warnings, I
wouldn't report these, but you might want to fix them.  Some are due
to missing protos, but most are related to id clashes.

----------------------------------------
source='bitset.c' object='bitset.o' libtool=no \
depfile='.deps/bitset.Po' tmpdepfile='.deps/bitset.TPo' \
depmode=gcc /bin/sh ../config/depcomp \
gcc -DHAVE_CONFIG_H -I. -I. -I.. -I../intl -I.. -I../src -I../intl
-I../lib    -g -O2 -Wall -W -Wbad-function-cast -Wcast-align
-Wcast-qual -Wformat -Wmissing-declarations -Wmissing-prototypes
-Wnested-externs -Wshadow -Wstrict-prototypes -Wwrite-strings -c `test
-f bitset.c || echo './'`bitset.c
source='bitsetv.c' object='bitsetv.o' libtool=no \
depfile='.deps/bitsetv.Po' tmpdepfile='.deps/bitsetv.TPo' \
depmode=gcc /bin/sh ../config/depcomp \
gcc -DHAVE_CONFIG_H -I. -I. -I.. -I../intl -I.. -I../src -I../intl
-I../lib    -g -O2 -Wall -W -Wbad-function-cast -Wcast-align
-Wcast-qual -Wformat -Wmissing-declarations -Wmissing-prototypes
-Wnested-externs -Wshadow -Wstrict-prototypes -Wwrite-strings -c `test
-f bitsetv.c || echo './'`bitsetv.c
bitsetv.c:137: warning: function declaration isn't a prototype
source='ebitset.c' object='ebitset.o' libtool=no \
depfile='.deps/ebitset.Po' tmpdepfile='.deps/ebitset.TPo' \
depmode=gcc /bin/sh ../config/depcomp \
gcc -DHAVE_CONFIG_H -I. -I. -I.. -I../intl -I.. -I../src -I../intl
-I../lib    -g -O2 -Wall -W -Wbad-function-cast -Wcast-align
-Wcast-qual -Wformat -Wmissing-declarations -Wmissing-prototypes
-Wnested-externs -Wshadow -Wstrict-prototypes -Wwrite-strings -c `test
-f ebitset.c || echo './'`ebitset.c
ebitset.c: In function `ebitset_elt_find':
ebitset.c:316: warning: declaration of `index' shadows global declaration
ebitset.c:331: warning: declaration of `elt' shadows previous local
ebitset.c: In function `ebitset_set':
ebitset.c:584: warning: declaration of `index' shadows global declaration
ebitset.c: In function `ebitset_reset':
ebitset.c:598: warning: declaration of `index' shadows global declaration
ebitset.c: In function `ebitset_test':
ebitset.c:617: warning: declaration of `index' shadows global declaration
ebitset.c: In function `ebitset_reverse_list':
ebitset.c:651: warning: declaration of `index' shadows global declaration
ebitset.c: In function `ebitset_list':
ebitset.c:734: warning: declaration of `index' shadows global declaration
ebitset.c:796: warning: declaration of `elt' shadows previous local
ebitset.c: In function `ebitset_op2':
ebitset.c:956: warning: declaration of `selt' shadows previous local
ebitset.c:957: warning: declaration of `delt' shadows previous local
ebitset.c:995: warning: declaration of `selt' shadows previous local
ebitset.c:996: warning: declaration of `delt' shadows previous local
ebitset.c: At top level:
ebitset.c:1243: warning: function declaration isn't a prototype
ebitset.c:1253: warning: function declaration isn't a prototype
ebitset.c:1277: warning: function declaration isn't a prototype
source='lbitset.c' object='lbitset.o' libtool=no \
depfile='.deps/lbitset.Po' tmpdepfile='.deps/lbitset.TPo' \
depmode=gcc /bin/sh ../config/depcomp \
gcc -DHAVE_CONFIG_H -I. -I. -I.. -I../intl -I.. -I../src -I../intl
-I../lib    -g -O2 -Wall -W -Wbad-function-cast -Wcast-align
-Wcast-qual -Wformat -Wmissing-declarations -Wmissing-prototypes
-Wnested-externs -Wshadow -Wstrict-prototypes -Wwrite-strings -c `test
-f lbitset.c || echo './'`lbitset.c
lbitset.c: In function `lbitset_elt_link':
lbitset.c:309: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_elt_find':
lbitset.c:371: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_set':
lbitset.c:588: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_reset':
lbitset.c:602: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_test':
lbitset.c:619: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_reverse_list':
lbitset.c:651: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_list':
lbitset.c:735: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_op1':
lbitset.c:936: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_op2':
lbitset.c:987: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_op3':
lbitset.c:1096: warning: declaration of `index' shadows global declaration
lbitset.c: At top level:
lbitset.c:1310: warning: function declaration isn't a prototype
lbitset.c:1320: warning: function declaration isn't a prototype
lbitset.c:1330: warning: function declaration isn't a prototype
source='sbitset.c' object='sbitset.o' libtool=no \
depfile='.deps/sbitset.Po' tmpdepfile='.deps/sbitset.TPo' \
depmode=gcc /bin/sh ../config/depcomp \
gcc -DHAVE_CONFIG_H -I. -I. -I.. -I../intl -I.. -I../src -I../intl
-I../lib    -g -O2 -Wall -W -Wbad-function-cast -Wcast-align
-Wcast-qual -Wformat -Wmissing-declarations -Wmissing-prototypes
-Wnested-externs -Wshadow -Wstrict-prototypes -Wwrite-strings -c `test
-f sbitset.c || echo './'`sbitset.c
sbitset.c: In function `sbitset_reverse_list':
sbitset.c:187: warning: declaration of `index' shadows global declaration
sbitset.c: In function `sbitset_list':
sbitset.c:246: warning: declaration of `index' shadows global declaration