New version of source/lib/bitmap.c

[okuyamak at dd.iij4u.or.jp]

Dear all,

>>>>> "o" == okuyamak  <okuyamak at dd.iij4u.or.jp> writes:
o> I've created new version of ./source/lib/bitmap.c
o> Current bitmap.c did not have any bug, except for performance.

I seems to made bug in non-built in ffs().
My environment didn't even go into this.


Here's newer patch.

Index: bitmap.c
===================================================================
RCS file: /cvsroot/samba/source/lib/bitmap.c,v
retrieving revision 1.6
diff -u -b -B -r1.6 bitmap.c
--- bitmap.c	1999/12/13 13:27:13	1.6
+++ bitmap.c	2000/11/03 11:49:02
@@ -26,26 +26,83 @@
 /* these functions provide a simple way to allocate integers from a
    pool without repitition */
 
+#ifdef __GNUC__
+/* let's simply use built in ffs(), for it's usually equivalent, or
+   faster */
+#define HAVE_FFS
+#else
+#undef  HAVE_FFS
+#endif
+
+#define UINT32BITLEN	32
 
+
+
+#ifndef HAVE_FFS
+/*
+ * ffs() will return where lsb of val with 1 is.
+ * if val == 0, then 0 is returned.
+ * if 0x01 then 1, etc.
+ */
+
+static int ffs( unsigned long val )
+{
+    unsigned long       val_with_only_lsb;
+    int                 ret;
+
+    val_with_only_lsb	= val & (( ~val )+ 1 );
+
+    switch ( val_with_only_lsb ) {
+    case 0x00000000:
+        return 0;
+    case 0x00000002:
+    case 0x00000001:
+        return val_with_only_lsb;
+    default:
+        ret	= 0;
+    }
+
+    if ( val_with_only_lsb & 0xffff0000 ) {
+        ret	+= 16;
+        val_with_only_lsb	>>= 16;
+    }
+    if ( val_with_only_lsb & 0xff00 ) {
+        ret	+= 8;
+        val_with_only_lsb	>>= 8;
+    }
+    if ( val_with_only_lsb & 0xf0 ) {
+        ret	+= 4;
+        val_with_only_lsb	>>= 4;
+    }
+    if ( val_with_only_lsb & 0xc ) {
+        ret	+= 2;
+        val_with_only_lsb	>>= 2;
+    }
+    return ret + val_with_only_lsb;
+}
+#endif
+
+
 /****************************************************************************
 allocate a bitmap of the specified size
 ****************************************************************************/
 struct bitmap *bitmap_allocate(int n)
 {
 	struct bitmap *bm;
-
-	bm = (struct bitmap *)malloc(sizeof(*bm));
+    int	total_size;
 
-	if (!bm) return NULL;
+    total_size	= sizeof( struct bitmap )
+        + sizeof( uint32 ) * (( n + UINT32BITLEN - 1 ) / UINT32BITLEN );
 	
-	bm->n = n;
-	bm->b = (uint32 *)malloc(sizeof(bm->b[0])*(n+31)/32);
-	if (!bm->b) {
-		free(bm);
+    bm	= ( struct bitmap *)malloc( total_size );
+    if ( bm == NULL ) {
 		return NULL;
 	}
+
+    bm->b	= (uint32 *)( bm + 1 );
+    bm->n   = n;
 
-	memset(bm->b, 0, sizeof(bm->b[0])*(n+31)/32);
+    memset(bm->b, 0, sizeof(bm->b[0])*(n+UINT32BITLEN)/ UINT32BITLEN );
 
 	return bm;
 }
@@ -74,7 +131,7 @@
 		      i, bm->n));
 		return False;
 	}
-	bm->b[i/32] &= ~(1<<(i%32));
+	bm->b[i/UINT32BITLEN] &= ~(1<<(i%UINT32BITLEN));
 	return True;
 }
 
@@ -84,7 +141,7 @@
 BOOL bitmap_query(struct bitmap *bm, unsigned i)
 {
 	if (i >= bm->n) return False;
-	if (bm->b[i/32] & (1<<(i%32))) {
+	if (bm->b[i/UINT32BITLEN] & (1<<(i%UINT32BITLEN))) {
 		return True;
 	}
 	return False;
@@ -96,35 +153,40 @@
 ****************************************************************************/
 int bitmap_find(struct bitmap *bm, unsigned ofs)
 {
-	int i, j;
+    int		slide_word, maxwords, startword;
+    uint32	bf_first, bf_last, firstmask;
+    int		i, pos;
+
+    if (ofs > bm->n) {
+        ofs = 0;
+    }
+
+    maxwords	= ( bm->n + UINT32BITLEN - 1 ) / UINT32BITLEN;
+    startword	= ofs / UINT32BITLEN;
+    firstmask	= ( ~0  ) << ( ofs % UINT32BITLEN );
 
-	if (ofs > bm->n) ofs = 0;
+    bf_first	= bm->b[startword] & firstmask;
+    bf_last     = bm->b[startword] & ( ~firstmask );
 
-	i = ofs;
-	while (i < bm->n) {
-		if (~(bm->b[i/32])) {
-			j = i;
-			do {
-				if (!bitmap_query(bm, j)) return j;
-				j++;
-			} while (j & 31 && j < bm->n);
-		}
-		i += 32;
-		i &= ~31;
-	}
-
-	i = 0;
-	while (i < ofs) {
-		if (~(bm->b[i/32])) {
-			j = i;
-			do {
-				if (!bitmap_query(bm, j)) return j;
-				j++;
-			} while (j & 31 && j < bm->n);
+    if ( ~bf_first ) {
+        pos	= ffs( ~bf_first );
+        return pos + ( startword * UINT32BITLEN ) - 1;
 		}
-		i += 32;
-		i &= ~31;
+    for ( i = startword+1; i < maxwords; i++ ) {
+        if ( ~( bm->b[i] ) ) {
+            pos	= ffs( ~( bm->b[i] ));
+            return pos + ( i * UINT32BITLEN ) - 1;
 	}
-
+    }
+    for ( i = 0; i < startword; i++ ) {
+        if ( ~( bm->b[i] )) {
+            pos	= ffs( ~( bm->b[i] ));
+            return pos + ( i * UINT32BITLEN ) - 1;
+        }
+    }
+    if ( ~bf_last ) {
+        pos	= ffs( ~bf_last );
+        return pos + ( startword * UINT32BITLEN ) - 1;
+    }
 	return -1;
 }