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;
}
