Bit map algorithms needed
Rich Salz
rsalz at bbn.com
Sat Jun 2 08:03:07 AEST 1990
Someone posted the following code:
>{
> unsigned char test_val;
> int index;
>
> index=bit_pos/8; /* element of array to test */
> switch(bit_pos%8) { /* bit in indexth element to get, set, or clear */
> case 0: test_val=0x01; break;
> case 1: test_val=0x02; break;
> case 2: test_val=0x04; break;
> case 3: test_val=0x08; break;
> case 4: test_val=0x10; break;
> case 5: test_val=0x20; break;
> case 6: test_val=0x40; break;
> case 7: test_val=0x80; break;
> }
> switch(action) {
> case GET:
> if((array[index]&test_val)==test_val)
> return(TRUE);
> return(FALSE);
> case SET:
> array[index]|=test_val;
> return(TRUE);
> case CLR:
> array[index]&=(0xff-test_val);
> return(FALSE);
> }
>}
I think this is better. Style aside, it avoids the gross unportability
used in the CLR case, and the switch used to set test_val.
index = bit_pos >> 3;
test_val = 1 << (bit_pos & 7);
switch (action) {
case GET:
return array[index] & test_val;
case SET:
array[index] |= test_value;
break;
case CLR:
array[index] &= ~test_val;
break;
}
return TRUE;
If you're doing general bitmap stuff, you're probably best off turning
the above routine into speciale-purpose macros, like the BSD fdset stuff,
or setbit/clrbit in <sys/param.h>:
#define setbit(a,i) ((a)[(i)/NBBY] |= 1<<((i)%NBBY))
#define clrbit(a,i) ((a)[(i)/NBBY] &= ~(1<<((i)%NBBY)))
#define isset(a,i) ((a)[(i)/NBBY] & (1<<((i)%NBBY)))
#define isclr(a,i) (((a)[(i)/NBBY] & (1<<((i)%NBBY))) == 0)
NBBY is the number of bits in a byte, and is typically 8, so
#define setbit(a,i) ((a)[(i) >> 3] |= 1<<((i) & 7))
#define clrbit(a,i) ((a)[(i) >> 3] &= ~(1<<((i) & 7)))
#define isset(a,i) ((a)[(i) >> 3] & (1<<((i) & 7)))
#define isclr(a,i) (((a)[(i) >> 3] & (1<<((i) & 7))) == 0)
--
Please send comp.sources.unix-related mail to rsalz at uunet.uu.net.
Use a domain-based address or give alternate paths, or you may lose out.
More information about the Comp.lang.c
mailing list