Re: PING: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Nicolas BENOIT <nbenoit at tuxfamily dot org>]

Nicolas BENOIT wrote:
> This patch was posted on Fri, 28 August 2009.
>
> http://gcc.gnu.org/ml/gcc-patches/2009-08/msg01536.html
>
> Discussed and reviewed with Diego Novillo on the IRC channel.
>

The patch above fixed cache reset in ebitmap_clear_bit() operation.
I discovered another issue with the cache reset, this patch fixes both.

Issue 1 : The map->cacheindex compared against eltwordindex, which is
irrelevant; discussed in the message mentioned above.

Issue 2 : When the cache points to an element which is after the element
being removed, it is not updated, although all the elements are going to
be shifted in the array. Then, the cache points to the succeeding
element it should point to.

This patch fixes both issues :
1/ it uses the correct wordindex to compare cacheindex with.
2/ it makes the cache points one element backwards if the cached
element is about to be shifted.

I attached to this message two testcases for each issue.
The first one is taken from issue 1 initial patch.

By the way, patches

http://gcc.gnu.org/ml/gcc-patches/2009-09/msg00956.html and
http://gcc.gnu.org/ml/gcc-patches/2009-09/msg00959.html

are still pending. I hope someone will have a look at them.

Greetings,
Nicolas BENOIT.


Index: ebitmap.c
===================================================================
--- ebitmap.c	(revision 151856)
+++ ebitmap.c	(working copy)
@@ -254,8 +254,13 @@
       if (!have_eltwordindex)
 	eltwordindex = sbitmap_popcount (map->wordmask, wordindex);

-      if (map->cache != NULL && map->cacheindex == eltwordindex)
-	map->cache = NULL;
+      if (map->cache != NULL)
+        {
+          if (map->cacheindex == wordindex)
+            map->cache = NULL;
+          else if (map->cacheindex > wordindex)
+            map->cache = map->cache - 1;
+        }

       RESET_BIT (map->wordmask, wordindex);


static void
test_ebitmap_clear_bit_cache_update_1 ( void )
{
  ebitmap map1, map2;
  map1 = ebitmap_alloc ( 1 );
  map2 = ebitmap_alloc ( 1 );

  ebitmap_set_bit ( map1, 1247 );
  ebitmap_set_bit ( map1, 1248 );
  ebitmap_set_bit ( map1, 1249 );
  ebitmap_set_bit ( map1, 1250 );
  ebitmap_set_bit ( map1, 1251 );
  ebitmap_set_bit ( map1, 1252 );
  ebitmap_set_bit ( map1, 1293 );
  ebitmap_set_bit ( map1, 1294 );
  ebitmap_set_bit ( map1, 1295 );
  ebitmap_set_bit ( map1, 1296 );
  ebitmap_set_bit ( map1, 1301 );
  ebitmap_set_bit ( map1, 1302 );
  ebitmap_set_bit ( map1, 1303 );
  ebitmap_set_bit ( map1, 1304 );
  ebitmap_set_bit ( map1, 1313 );
  ebitmap_set_bit ( map1, 1314 );
  ebitmap_set_bit ( map1, 1315 );
  ebitmap_set_bit ( map1, 1316 );
  ebitmap_set_bit ( map1, 1317 );
  ebitmap_set_bit ( map1, 1318 );
  ebitmap_set_bit ( map1, 1319 );
  ebitmap_set_bit ( map1, 1320 );
  ebitmap_set_bit ( map2, 1285 );
  ebitmap_clear_bit ( map1, 1285 );
  ebitmap_set_bit ( map2, 1286 );
  ebitmap_clear_bit ( map1, 1286 );
  ebitmap_set_bit ( map2, 1287 );
  ebitmap_clear_bit ( map1, 1287 );
  ebitmap_set_bit ( map2, 1288 );
  ebitmap_clear_bit ( map1, 1288 );
  ebitmap_clear_bit ( map1, 1233 );
  ebitmap_set_bit ( map2, 1234 );
  ebitmap_clear_bit ( map1, 1234 );
  ebitmap_set_bit ( map2, 1235 );
  ebitmap_clear_bit ( map1, 1235 );
  ebitmap_set_bit ( map2, 1236 );
  ebitmap_clear_bit ( map1, 1236 );
  ebitmap_set_bit ( map2, 1237 );
  ebitmap_clear_bit ( map1, 1237 );
  ebitmap_set_bit ( map2, 1238 );
  ebitmap_clear_bit ( map1, 1238 );
  ebitmap_set_bit ( map2, 1239 );
  ebitmap_clear_bit ( map1, 1239 );
  ebitmap_set_bit ( map2, 1240 );
  ebitmap_clear_bit ( map1, 1240 );
  ebitmap_set_bit ( map2, 1245 );
  ebitmap_clear_bit ( map1, 1245 );
  ebitmap_set_bit ( map2, 1246 );
  ebitmap_clear_bit ( map1, 1246 );
  ebitmap_set_bit ( map2, 1247 );
  ebitmap_clear_bit ( map1, 1247 );
  ebitmap_set_bit ( map2, 1248 );
  ebitmap_clear_bit ( map1, 1248 );
  ebitmap_set_bit ( map2, 1249 );
  ebitmap_clear_bit ( map1, 1249 );
  ebitmap_set_bit ( map2, 1250 );
  ebitmap_clear_bit ( map1, 1250 );
  ebitmap_set_bit ( map2, 1251 );
  ebitmap_clear_bit ( map1, 1251 );

  if ( !ebitmap_bit_p(map2,1252) )
    {
      if ( ebitmap_bit_p(map1,1252) )
        {
          ebitmap_set_bit ( map2, 1252 );
          ebitmap_clear_bit ( map1, 1252 );
        }
    }

  gcc_assert ( !ebitmap_bit_p(map1,1253) );

  fprintf ( stderr, "ebitmap_clear_bit() cache update test 1 passed\n" );

  ebitmap_free ( map1 );
  ebitmap_free ( map2 );
}

static void
test_ebitmap_clear_bit_cache_update_2 ( void )
{
  ebitmap map;

  map = ebitmap_alloc ( 1 );
  ebitmap_set_bit ( map, 148 );
  ebitmap_set_bit ( map, 147 );
  ebitmap_set_bit ( map, 146 );
  ebitmap_set_bit ( map, 4026 );
  ebitmap_clear_bit ( map, 146 );
  ebitmap_set_bit ( map, 4040 );
  ebitmap_clear_bit ( map, 147 );
  ebitmap_set_bit ( map, 4054 );
  ebitmap_clear_bit ( map, 148 );
  gcc_assert ( !ebitmap_bit_p(map,4032) );

  fprintf ( stderr, "ebitmap_clear_bit() cache update test 2 passed\n" );

  ebitmap_free ( map );
}

static void
test_ebitmap_clear_bit_cache_update ( void )
{
  test_ebitmap_clear_bit_cache_update_1 ( );
  test_ebitmap_clear_bit_cache_update_2 ( );
}