Category : C Source Code
Archive   : BITSET.ZIP
Filename : BITSET.C

 
Output of file : BITSET.C contained in archive : BITSET.ZIP


/* #define TESTING */

/* bitset.c bitset definition and manipulation routines
*
* version hx v1.0 : initial release to CIS : 09-07-87 : (jrh)
*
* author Richard Hargrove
* Texas Instruments, Inc.
* P.O. Box 869305, m/s 8473
* Plano, TX 75086
* 214/575-4128
*
* CIS 74756,664
*
* usenet ...{inhp4|cbosgd}!killer!richardh
* \!warble!richardh
*/

#if defined(TESTING)
#include
#define STATIC
#else
#define STATIC static
#endif TESTING

#include
#include "bitset.h"

#define FALSE 0
#define TRUE 1

/* private bitset type */

typedef struct {
unsigned size; /* bitset size */
unsigned char bits [1]; /* hook for the bitset */
} BITSET, *BITPTR;

/* binary operations with common algorithms */

#define UNION 0
#define INTERSECTION 1
#define EX_OR 2
#define DIFFERENCE 3

#define NUMCHARS(bitsize) (((bitsize) >> 3) + ((bitsize) & 0x07 ? 1 : 0))

/* Package work vars used to avoid casting operation parameters on every use
* and to get local bitset pointer refs off of the stack.
*/

STATIC BITPTR local1, local2;

/*****************************************************************************/

bitset makebitset (unsigned size)
{
/* Create a bitset containing size bits. Return a pointer to the
bitset if successful, NULL otherwise.
*/

#ifdef TESTING
printf ("Making a %d bit BITSET (%d bytes required)\n",
size, NUMCHARS(size));
#endif TESTING

/* packet size is adjusted for hook byte */
if ((local1 = (BITPTR) malloc (NUMCHARS(size) - 1 + sizeof(BITSET)))
!= (BITPTR) NULL) {
/* init the bitset */
local1->size = size;
clear_set ((bitset) local1);
}
return ((bitset) local1);
}

/*****************************************************************************/

BOOLEAN setbit (bitset set, unsigned bit, unsigned val)
{
/* Set bit# bit in set to the value of the least significant bit
* in val. Return TRUE if successful, FALSE otherwise.
*/

BOOLEAN ret_val = FALSE;

local1 = (BITPTR) set;
if (bit < local1->size) {
if ((val & 0x01) == 1) { /* set the bit */
local1->bits [bit >> 3] |= (1 << (bit & 0x07));
}
else { /* clear the bit */
local1->bits [bit >> 3] &= (~(1 << (bit & 0x07)));
}
ret_val = TRUE;
}
return (ret_val);
}

/*****************************************************************************/

BOOLEAN testbit (bitset set, unsigned bit)
{
/* If bit# bit in set is 1 return TRUE else return FALSE.
*/

local1 = (BITPTR) set;
return ((bit < local1->size) &&
(local1->bits [bit >> 3] & (1 << (bit & 0x07))));
}

/*****************************************************************************/

void clear_set (bitset set)
{
/* Clear the bitset pointed to by set.
*/

unsigned numchars;
char *localbits;

local1 = (BITPTR) set;
localbits = local1->bits;
numchars = NUMCHARS(local1->size);
while (numchars--) {
*localbits++ = '\0';
}
}

/*****************************************************************************/

void compl_set (bitset set)
{
/* Complement the bitset pointed to by set.
*/

unsigned numchars;
char *localbits;

local1 = (BITPTR) set;
localbits = local1->bits;
numchars = NUMCHARS(local1->size);
while (numchars--) {
*localbits++ ^= 0xff;
}
}

/*****************************************************************************/

STATIC void binsetop (int op)
{
char *localbits1 = local1->bits;
char *localbits2 = local2->bits;
unsigned numchars = (local1->size > local2->size)
? NUMCHARS(local2->size)
: NUMCHARS(local1->size);
while (numchars--) {
switch (op) {
case UNION: *localbits1++ |= *localbits2++;
continue;
case INTERSECTION: *localbits1++ &= *localbits2++;
continue;
case EX_OR: *localbits1++ ^= *localbits2++;
continue;
case DIFFERENCE: *localbits1 &= (~(*localbits1 & *localbits2++));
localbits1++;
}
}
}

/*****************************************************************************/

void union_set (bitset set1, bitset set2)
{
/* Transform the bitset pointed to by set1 into the union of
* the bitsets pointed to by set1 and set2.
*/

local1 = (BITPTR) set1;
local2 = (BITPTR) set2;
binsetop (UNION);
}

/*****************************************************************************/

void intrsct_set (bitset set1, bitset set2)
{
/* Transform the bitset pointed to by set1 into the intersection
* of the bitsets pointed to by set1 and set2.
*/

local1 = (BITPTR) set1;
local2 = (BITPTR) set2;
binsetop (INTERSECTION);

}

/*****************************************************************************/

void xor_set (bitset set1, bitset set2)
{
/* Transform the bitset pointed to by set1 into the exclusive-or
* of the bitsets pointed to by set1 and set2.
*/

local1 = (BITPTR) set1;
local2 = (BITPTR) set2;
binsetop (EX_OR);
}

/*****************************************************************************/

void diff_set (bitset set1, bitset set2)
{
/* Transform the bitset pointed to by set1 into the set
* difference of the bitsets pointed to by set1 and set2.
*/

local1 = (BITPTR) set1;
local2 = (BITPTR) set2;
binsetop (DIFFERENCE);
}

/*****************************************************************************/

BOOLEAN equal_sets (bitset set1, bitset set2)
{
/* If the bitsets pointed to by set1 and set2 are the same
* size and contain the same bit pattern then return TRUE
* else return FALSE
*/

BOOLEAN areequal;

local1 = (BITPTR) set1;
local2 = (BITPTR) set2;

if ((areequal = (local1->size == local2->size)) != FALSE) {
char *localbits1 = local1->bits;
char *localbits2 = local2->bits;
unsigned numchars = NUMCHARS(local1->size);

while (areequal && numchars--) {
areequal = (*localbits1++ == *localbits2++);
}
}
return (areequal);
}

/*****************************************************************************/

BOOLEAN in_set (bitset set1, bitset set2)
{
/* If the bitset pointed to by set1 is a subset of the bitset
* pointed to by set2 then return TRUE else return FALSE.
*
* This rotuine requires that the size of *set1 be less than
* or equal to the size of *set2 in order to return TRUE.
*/

BOOLEAN isinset;

local1 = (BITPTR) set1;
local2 = (BITPTR) set2;

if ((isinset = (local1->size <= local2->size)) != FALSE) {
char *localbits1 = local1->bits;
char *localbits2 = local2->bits;
unsigned numchars = NUMCHARS(local1->size);

while (isinset && numchars--) {
isinset = ((*localbits1 & *localbits2++) == *localbits1);
localbits1++;
}
}
return (isinset);
}
#if defined(TESTING)

/*****************************************************************************/

#define NUMBITS 21 /* vary these for different tests */

put_set (msg, set)
char *msg;
bitset set;
{
int i;

printf ("%s", msg);
for (i = 0; i < NUMBITS; i++) {
if (i % 4 == 0) putchar (' ');
fputc (testbit (set, i) ? '1' : '0', stdout);
}
}

/*****************************************************************************/

main (void)
{
/* Test the bitset package
*/

bitset set, x, y, z;
unsigned bitnum, val, i;
char buf [16];

puts ("Making a 32 bit wide bitset");
if ((set = makebitset (32)) == (bitset) NULL) {
puts ("Can't make the bitset");
exit (1);
}

/* test setbit and testbit */
do {
/* Output the bitset */
for (i = 0; i <= 31; i++) {
fputc (testbit (set, i) ? '1' : '0', stdout);
}
fputc ('\n', stdout);

fputs ("Which bit? ", stderr);
bitnum = atoi (fgets (buf, 16, stdin));
fputs ("val ([^0-1] quits)? ", stderr);
val = atoi (fgets (buf, 16, stdin));

printf ("bitnum == %d val == %d\n", bitnum, val);

if (!setbit (set, bitnum, val)) {
printf ("Bit out of range\n");
}
} while ((val >= 0) && (val <= 1));

/* test the set operations */
x = makebitset (NUMBITS);
z = makebitset (NUMBITS);
y = makebitset (NUMBITS);
if ((x == (bitset) NULL) || (y == (bitset) NULL) ||
(z == (bitset) NULL)) {
printf ("Can't make the bitsets\n");
exit (1);
}

setbit (x, 3, 1); setbit (x, 6, 1); /* vary these for */
setbit (x, 10, 1); setbit (x, 11, 1); /* different tests */
setbit (x, 13, 1); setbit (x, 17, 1);
setbit (x, 19, 1);

setbit (y, 0, 1); setbit (y, 4, 1); /* vary these for */
setbit (y, 7, 1); setbit (y, 8, 1); /* different tests */
setbit (y, 10, 1); setbit (y, 12, 1);
setbit (y, 14, 1); setbit (y, 15, 1);
setbit (y, 16, 1); setbit (y, 17, 1);
setbit (y, 20, 1);

put_set ("\nbitset x:", x);
put_set ("\nbitset y:", y);
put_set ("\nbitset z:", z);

union_set (z, x);
put_set ("\n\nz union x:", z);

if (equal_sets (z, x))
printf ("\nz is equal to x");
else
printf ("\nz is not equal to x");

if (equal_sets (y, x))
printf ("\ny is equal to x");
else
printf ("\ny is not equal to x");

intrsct_set (z, y);
put_set ("\nz intersection y:", z);

clear_set (z);
put_set ("\n\nz cleared:", z);

compl_set (z);
put_set ("\nz complement:", z);

xor_set (z, x);
put_set ("\nz xor x:", z);

clear_set (z);
setbit (z, 0, 1);
setbit (z, 7, 1);
setbit (z, 8, 1);
setbit (z, 14, 1);
setbit (z, 17, 1);
put_set ("\n\nz is", z);
if (in_set (z, y))
printf (" and is a subset of y");
else
printf (" and is not a subset of y");

if (in_set (x, y))
printf ("\nx is a subset of y");
else
printf ("\nx is not a subset of y");

if (in_set (y, y))
printf ("\ny is a subset of y");
else
printf ("\ny is not a subset of y");

compl_set (z);
put_set ("\n\nz is", z);
put_set ("\ny is", y);
diff_set (z, y);
put_set ("\nz diff y:", z);

putchar ('\n');
exit (0);
}
#endif TESTING