patch for .samba-2.0.7/source/lib/bitmap.c

[Kenichi Okuyama]

Dear all,

I have made patch for
  samba-2.0.7/source/lib/bitmap.c

With this patch
1) constant '32' is now named.
2) make only one malloc on bitmap_allocate().
   ( This will make bitmap to fit within same page, which will cause
     lesser pagefault, I wish )
3) totally changed bitmap_find(). I guess this should work faster
   then testing each bits one-by-one.




--- ./source/lib/bitmap.c	2000/04/29 15:35:49	1.1
+++ ./source/lib/bitmap.c	2000/05/01 09:00:59
@@ -21,35 +21,42 @@
 
 #include "includes.h"
 
 extern int DEBUGLEVEL;
 
+#define	BITMAP_ALIGN	32
+#define	UINT32_BITS	32
+#define UINT32_ALLONE	(0xffffffffUL)
+
 /* these functions provide a simple way to allocate integers from a
    pool without repitition */
 
+static int     find_bitmap_one( uint32 bitmaps );
+
+
 
 /****************************************************************************
 allocate a bitmap of the specified size
 ****************************************************************************/
 struct bitmap *bitmap_allocate(int n)
 {
-	struct bitmap *bm;
+    size_t 	structsize, bitmapsize;
+    struct bitmap *bm;
 
-	bm = (struct bitmap *)malloc(sizeof(*bm));
+    structsize  = ( sizeof(*bm) + BITMAP_ALIGN - 1 )&( ~( BITMAP_ALIGN - 1));
+    bitmapsize  = ( sizeof( bm->b[0] ) * ( n + UINT32_BITS-1 )/ UINT32_BITS );
 
-	if (!bm) return NULL;
-	
-	bm->n = n;
-	bm->b = (uint32 *)malloc(sizeof(bm->b[0])*(n+31)/32);
-	if (!bm->b) {
-		free(bm);
-		return NULL;
-	}
+    bm  = (struct bitmap *)malloc( structsize + bitmapsize );
+    if (!bm) {
+        return NULL;
+    }
 
-	memset(bm->b, 0, sizeof(bm->b[0])*(n+31)/32);
+    bm->n       = n;
+    bm->b       = (uint32 *)((char *)bm + structsize);
 
-	return bm;
+    memset( bm->b, 0, bitmapsize );
+    return bm;
 }
 
 /****************************************************************************
 set a bit in a bitmap
 ****************************************************************************/
@@ -58,11 +65,11 @@
 	if (i >= bm->n) {
 		DEBUG(0,("Setting invalid bitmap entry %d (of %d)\n",
 		      i, bm->n));
 		return False;
 	}
-	bm->b[i/32] |= (1<<(i%32));
+	bm->b[i/UINT32_BITS] |= (1<<(i%UINT32_BITS));
 	return True;
 }
 
 /****************************************************************************
 clear a bit in a bitmap
@@ -72,21 +79,21 @@
 	if (i >= bm->n) {
 		DEBUG(0,("clearing invalid bitmap entry %d (of %d)\n",
 		      i, bm->n));
 		return False;
 	}
-	bm->b[i/32] &= ~(1<<(i%32));
+	bm->b[i/UINT32_BITS] &= ~(1<<(i%UINT32_BITS));
 	return True;
 }
 
 /****************************************************************************
 query a bit in a bitmap
 ****************************************************************************/
 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/UINT32_BITS] & (1<<(i%UINT32_BITS))) {
 		return True;
 	}
 	return False;
 }
 
@@ -94,37 +101,109 @@
 find a zero bit in a bitmap starting at the specified offset, with
 wraparound
 ****************************************************************************/
 int bitmap_find(struct bitmap *bm, unsigned ofs)
 {
-	int i, j;
+    uint32	ofs_negimage;
+    uint32	cur_negimage;
+    int         ofsseg, ofsoff;
+    int         iseg;
+    int		result;
+
+    if ( ofs >= bm->n ) {
+        ofs     = 0;
+    }
+
+    ofsseg      = ofs / UINT32_BITS;
+    ofsoff	= ofs % UINT32_BITS;
+
+    /* first, we have to treat first segment special */
+    ofs_negimage = ( ~( bm->b[ofsseg] ));
+
+    cur_negimage	= ofs_negimage & ( UINT32_ALLONE << ofsoff );
+    ofs_negimage	= ofs_negimage & ( ~( UINT32_ALLONE << ofsoff ));
+
+    result	= find_bitmap_one( cur_negimage );
+    if ( result >= 0 ) {
+        if ( result + ( ofsseg * UINT32_BITS ) < bm->n ) {
+            return result + ( ofsseg * UINT32_BITS );
+        }
+    }
+
+    for ( iseg = ofsseg+1;
+          iseg < (( bm->n + UINT32_BITS - 1) / UINT32_BITS ); iseg++ ) {
+        result  = find_bitmap_one( ~(bm->b[iseg]) );
+        if ( result >= 0 ) {
+
+            /* This is bit special case. you might be over-running */
+            if ( result + ( iseg * UINT32_BITS ) < bm->n ) {
+                return result + ( iseg * UINT32_BITS );
+            }
+        }
+    }
+
+    for ( iseg = 0; iseg < ofsseg; iseg++ ) {
+        result  = find_bitmap_one( ~(bm->b[iseg]) );
+        if ( result >= 0 ) {
+            return result + ( iseg * UINT32_BITS );
+        }
+    }
+
+    /* finally look at first segment again */
+    if ( ofs_negimage ) {
+        result  = find_bitmap_one( ofs_negimage );
+        if ( result >= 0 ) {
+            return result + ( ofsseg * UINT32_BITS );
+        }
+    }
+
+    return -1;
+}
 
-	if (ofs > bm->n) ofs = 0;
 
-	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;
-	}
+/*
+ * find bit with 1, from LSB.
+ *
+ * I first saw this hack at X11R3's source code. I don't know where it
+ * came from. --- Kenichi Okuyama.
+ */
+static int
+find_bitmap_one( uint32 bitmaps )
+{
+    uint32	only_lsb_is_one;
+    int         result;
 
-	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);
-		}
-		i += 32;
-		i &= ~31;
-	}
+    /* Somebody, tell me if you know. Who first found this ? */
+    only_lsb_is_one	= bitmaps & (( ~bitmaps )+ 1 );
+
+    if ( only_lsb_is_one ) {
+        result  = 0;
 
-	return -1;
+        if ( !( only_lsb_is_one & 0xffff )) {
+            result      += 16;
+            only_lsb_is_one	>>= 16;
+        }
+
+        if ( !( only_lsb_is_one & 0xff )) {
+            result      += 8;
+            only_lsb_is_one	>>= 8;
+        }
+
+        if ( !( only_lsb_is_one & 0xf )) {
+            result      += 4;
+            only_lsb_is_one	>>= 4;
+        }
+
+        if ( !( only_lsb_is_one & 0x3 )) {
+            result      += 2;
+            only_lsb_is_one	>>= 2;
+        }
+
+        if ( !( only_lsb_is_one & 0x1 )) {
+            result      += 1;
+            only_lsb_is_one	>>= 1;
+        }
+
+        return result;
+    }
+    return -1;
 }