This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH gcc/ebitmap] fix for ebitmap_and_compl_into()


This patch fixes the removal of an empty element after applying the
and_compl operation.

Indeed, the current implementation does remove the element from the
wordmask, but not from the elements array. This results to a corruption.

The fix shifts next elements over the old one. Just like in
ebitmap_clear_bit().
As dsteltindex is incremented earlier, the destination address for the
memmove() is based on a decremented value of it.

The attached testcase is a function which is intended to be called
from any GCC function (maybe arch dependent, tested on x86_64).
Defining EBITMAP_DEBUGGING and performing the test would also result in
an assertion failure. But it is currently unavailable as the debugging
code uses an undefined function verify_popcount(), which should actually
be sbitmap_verify_popcount() (available only when SBITMAP_DEBUGGING is
defined).


2009-09-14 Nicolas Benoit <nbenoit@tuxfamily.org>


* ebitmap.c (ebitmap_and_compl_into): Fixed empty element removal.


Index: ebitmap.c =================================================================== --- ebitmap.c (revision 151685) +++ ebitmap.c (working copy) @@ -824,7 +824,11 @@ *dstplace = tmpword; } else - RESET_BIT (dst->wordmask, i); + { + RESET_BIT (dst->wordmask, i); + memmove (&dst->elts[dsteltindex-1], &dst->elts[dsteltindex], + sizeof (EBITMAP_ELT_TYPE) * (dst->numwords - dsteltindex)); + } } else {


void
test_ebitmap_and_compl_into ( void )
{
  ebitmap m1;
  ebitmap m2;

  m1 = ebitmap_alloc ( 1 );
  m2 = ebitmap_alloc ( 1 );

  ebitmap_set_bit ( m1, 1208 );
  ebitmap_set_bit ( m1, 1209 );
  ebitmap_set_bit ( m1, 1210 );
  ebitmap_set_bit ( m1, 1211 );
  ebitmap_set_bit ( m1, 1236 );
  ebitmap_set_bit ( m1, 1237 );
  ebitmap_set_bit ( m1, 1238 );
  ebitmap_set_bit ( m1, 1239 );

  ebitmap_set_bit ( m2, 1208 );
  ebitmap_set_bit ( m2, 1209 );
  ebitmap_set_bit ( m2, 1210 );
  ebitmap_set_bit ( m2, 1211 );

  gcc_assert ( ebitmap_bit_p(m1,1236) );

  ebitmap_and_compl_into ( m1, m2 );

  gcc_assert ( ebitmap_bit_p(m1,1236) );

  fprintf ( stderr, "ebitmap_and_compl_into() test passed\n" );
}

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]