New version of source/lib/bitmap.c
okuyamak at dd.iij4u.or.jp
okuyamak at dd.iij4u.or.jp
Sat Nov 4 06:44:03 GMT 2000
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;
}
More information about the samba-technical
mailing list