Bit Field Class

// A bit field is an important data structure in computer science, major uses include memory allocators and Bloom filters.
// The code is in the form of a header file and an implementation file.



// This class is a code snippet, it can be freely used and distributed.
// Author: irfan[dot]hamid[at]gmail[dot]com
//
// Bit fields are a widely used mechanism in computing applications.
// Typical applications include memory allocators and Bloom filters. This class
// provides a generic bit field implementation for an arbitrary number of bits.
//
// Implementation notes:
// The use of C++ allows the clean separation of the data structure from the
// interface. The bit field is implemented as a vector of unsigned int that is
// allocated at object creation.
//
// field: The vector that represents the bit field itself
// bit_count: The total number of bits in the bit field

#ifndef __BITFIELD_H__
#define __BITFIELD_H__
#include 
#define SZ_UINT sizeof(unsigned int)

class Bitfield
{
protected:
	unsigned int *field;
	unsigned int bit_count;

public:
	Bitfield (int bc);
	~Bitfield ();

	int set (int bit);
	int get (int bit);
	int reset (int bit);
};

#endif



#include 
#include "bitfield.h"

// The constructor takes an int param which gives the number of bits in this
// bit field.
Bitfield::Bitfield (int bc)
{
	bit_count = bc;

	// E.g, ceil(257/32*8) = 65, 64 ints fully used, last one partially used
	field = (unsigned int*) malloc(((int) ceil(bc/SZ_UINT*8)));
}

Bitfield::~Bitfield ()
{
	if (field)
		free(field);
}

// This function sets the corresponding bit in the field equal to 1.
//
// Returns: 0 on success, -1 on error.
int Bitfield::set (int bit)
{
	// Sanity check
	if (bit >= bit_count || !field)
		return -1;

	// The correct index into the vector will be given by bit/SZ_UNIT. The
	// index into the correct vector element is given by bit%SZ_UNIT, to
	// achieve this, simply left shift 0x01 the appropriate number of times.
	field[bit/SZ_UINT] |= (0x00000001 << (bit%(SZ_UINT*8)-1));
	return 0;
}

// This function sets the corresponding bit in the field equal to 0.
//
// Returns: 0 on success, -1 on error.
int Bitfield::reset (int bit)
{
	if (bit >= bit_count || !field)
		return -1;
	field[bit/SZ_UINT] &= ~(0x00000001 << (bit%(SZ_UINT*8)-1));
	return 0;
}

// This function returns the value of the corresponding bit.
//
// Returns: The value of the bit, if the field is initialized and bit index is
// within bounds, -1 otherwise.
int Bitfield::get (int bit)
{
	if (bit >= bit_count || !field)
		return -1;
	return (field[bit/SZ_UINT] & (0x00000001 << (bit%(SZ_UINT*8)-1)) ? 1 : 0);
}