XBitArray - a non-MFC C++ class to manipulate bits in a bit array.

Hans Dietrich

4.74/5 (22 votes)

Feb 11, 2004

CPOL

5 min read

72566

1052

XBitArray provides functions to set, test, and find bits in an array of bytes.

Download demo project - 53.4 Kb

Introduction

CXBitArray encapsulates a class for handling a bit array. Bit arrays are used most often to represent a collection of objects - for example, blocks of memory in a memory pool. Each bit in the array corresponds to an object, and is referenced by a "bit number", where bit number 0 is the first bit.

The underlying data structure of CXBitArray is assumed to be an array of bytes, which can either be allocated by CXBitArray or can be passed as an address to the CXBitArray constructor. For example, this code:

    CXBitArray bit(80, 0);

would construct a CXBitArray object, which would then allocate an array of 10 bytes (80 / 8) that are initialized to 0. Bit number 79 would be the last bit.

CXBitArray Features

Here are some of the methods provided by CXBitArray:

Constructor #1 - Construct un-initialized CXBitArray object. Before using the object, Init() or Attach() must be called.

///////////////////////////////////////////////////////////////////////////////
//
// CXBitArray() #1
//
// Purpose:     Construct uninitialized CXBitArray object
//
// Parameters:  None
//
// Returns:     None
//

Constructor #2 - Construct CXBitArray object from existing array. This constructor will initialize the bit array. To use an existing array without initializing it, use Attach().

///////////////////////////////////////////////////////////////////////////////
//
// CXBitArray() #2
//
// Purpose:     Construct CXBitArray object from existing array
//
// Parameters:  pBitArray      - address of bit array
//              nArraySizeBits - size of array in bits
//              bit_value      - bit array will be initialized to this value
//
// Returns:     None
//

Constructor #3 - Construct CXBitArray object with array allocation. The bit array will be allocated from the heap. To get the address of the bit array, use the LPBYTE() operator.

///////////////////////////////////////////////////////////////////////////////
//
// CXBitArray() #3
//
// Purpose:     Construct CXBitArray object with array allocation
//
// Parameters:  nArraySizeBits - size of array in bits
//              bit_value      - bit array will be initialized to this value
//
// Returns:     None
//

Constructor #4 - Construct CXBitArray object from file.

///////////////////////////////////////////////////////////////////////////////
//
// CXBitArray() #4
//
// Purpose:     Construct CXBitArray object from file
//
// Parameters:  lpszPersistFile - name of file to read bit array from
//              nArraySizeBits  - size of array in bits
//              bit_value       - bit array will be initialized to this value
//                                if it cannot be read from file
//
// Returns:     None
//
// Notes:       If the file specified by lpszPersistFile cannot be read,
//              the bit array will be allocated according to nArraySizeBits
//              and initialized to bit_value.  Regardless of whether the
//              file exists, the bit array will be saved to this file when
//              the destructor is called.
//
//              If the file specified by lpszPersistFile can be read, the
//              size of the bit array is determined by the size of the file.
//

Constructor #5 - Construct CXBitArray object from registry.

///////////////////////////////////////////////////////////////////////////////
//
// CXBitArray() #5
//
// Purpose:     Construct CXBitArray object from registry
//
// Parameters:  lpszKeyName    - key name (must not be NULL)
//              lpszValueName  - value name (may be NULL)
//              nArraySizeBits - size of array in bits
//              bit_value      - bit array will be initialized to this value
//                               if it cannot be read from registry
//
// Returns:     None
//
// Notes:       If the registry key specified by lpszKeyName cannot be read,
//              the bit array will be allocated according to nArraySizeBits
//              and initialized to bit_value.  Regardless of whether the
//              registry key exists, the bit array will be saved to this file
//              when the destructor is called.
//
//              If the registry key  specified by lpszKeyName can be read, the
//              size of the bit array is determined by the size of the registry 
//              value.
//
//              If lpszValueName is NULL, the key's unnamed or default value
//              will be used.
//

Attach() - Attach an existing bit array to a CXBitArray object.

///////////////////////////////////////////////////////////////////////////////
//
// Attach()
//
// Purpose:     Attach an existing bit array to a CXBitArray object
//
// Parameters:  pBitArray      - address of bit array (must not be NULL)
//              nArraySizeBits - size of array in bits
//
// Returns:     None
//
// Notes:       Attach will associate the bit array specified by pBitArray
//              with the CXBitArray object *without* initializing the bit 
//              array (unlike CXBitArray() #2, which always initializes 
//              the bit array).  If a heap-allocated bit array is already 
//              associated with the CXBitArray object, it will be deallocated.
//

Count() - Return counts of bits set to 0 and bits set to 1.

///////////////////////////////////////////////////////////////////////////////
//
// Count()
//
// Purpose:     Return counts of bits set to 0 and bits set to 1
//
// Parameters:  bits_set_to_zero - pointer to the variable where the count of
//                                 bits set to 0 is returned.
//              bits_set_to_one  - pointer to the variable where the count of
//                                 bits set to 1 is returned.
//
// Returns:     BOOL - TRUE = success
//

Find() - Find next bit that has the value specified by bit_value. This method can be used to manage any kind of circular list or buffer pool, where the items are continuously being allocated in front of the index and consumed behind the index. Find() will scan all bits in the bit array (wrapping the search to the beginning if necessary) until a bit with the specified value is found.

///////////////////////////////////////////////////////////////////////////////
//
// Find()
//
// Purpose:     Find next bit that has the value specified by bit_value
//
// Parameters:  start_pos - bit number (0 - N);  the search for a bit will
//                          start at this bit number.  If necessary, the search
//                          will wrap to the beginning of the bit array.
//              bit_value - value to look for (0 or 1)
//              bit_pos   - pointer to variable where bit number will be 
//                          returned
//
// Returns:     BOOL - TRUE = success
//

Get() - Get bit value.

///////////////////////////////////////////////////////////////////////////////
//
// Get()
//
// Purpose:     Get bit value
//
// Parameters:  pos  - bit number (0 - N)
//
// Returns:     BOOL - TRUE = bit is 1;  FALSE = bit is 0
//

Set() - Set bit value.

///////////////////////////////////////////////////////////////////////////////
//
// Set()
//
// Purpose:     Set bit value
//
// Parameters:  pos       - bit number (0 - N)
//              bit_value - 0 or 1
//
// Returns:     None
//

SetAll() - Set all bits to a value.

///////////////////////////////////////////////////////////////////////////////
//
// SetAll()
//
// Purpose:     Set all bits to a value
//
// Parameters:  bit_value - 0 or 1
//
// Returns:     None
//

ToString() - Returns a pointer to a string that represents the bit array. The string must be deallocated by the caller.

///////////////////////////////////////////////////////////////////////////////
//
// ToString()
//
// Purpose:     Returns a string that represents the bit array
//
// Parameters:  None
//
// Returns:     LPTSTR - pointer to a string that has been allocated on the 
//                       heap and must be freed by caller.  The string
//                       contains one TCHAR for each bit in the array, plus
//                       a trailing nul.  Returns NULL if failure.
//

CXBitArray Class Reference

METHOD	DESCRIPTION
`CXBitArray()` #1	Construct un-initialized `CXBitArray` object
`CXBitArray()` #2	Construct `CXBitArray` object from existing array
`CXBitArray()` #3	Construct `CXBitArray` object with array allocation
`CXBitArray()` #4	Construct `CXBitArray` object from file
`CXBitArray()` #5	Construct `CXBitArray` object from registry
`~CXBitArray()`	Save bit array to file and/or registry and deallocate bit array
`Attach()`	Attach an existing bit array to a `CXBitArray` object
`Count()`	Return counts of bits set to 0 and bits set to 1
`Find()`	Find next bit that has the value specified by `bit_value`
`Get()`	Get bit value
`GetArraySizeBits()`	Get size of bit array in bits
`GetArraySizeBytes()`	Get size of bit array in bytes
`GetBitNo()`	Convert bit mask to bit number
`GetBitPos()`	Convert bit number to byte and bit indexes and bit mask
`GetPersistFileName()`	Get persist file name
`GetRegistryKeyName()`	Get registry key name
`GetRegistryValueName()`	Get registry value name
`Init()`	Initialize `CXBitArray` object
operator `[]`	Get bit value at a bit index
operator `LPBYTE`	Get address of bit array
`ReadPersistFile()`	Read bit array from file
`ReadRegistry()`	Read bit array from registry
`Set()`	Set bit value
`SetAll()`	Set all bits to a value
`SetPersistFileName()`	Set persist file name
`SetRegistryNames()`	Set registry key and value names
`ToString()`	Returns a string that represents the bit array
`WritePersistFile()`	Write bit array to file
`WriteRegistry()`	Write bit array to registry

Free and Used Bits

In CXBitArray, there is no built-in assumption about what constitutes a "free" or a "used" bit. The concepts of "free" and "used" are determined by the application. For example, a backup utility might consider a "used" bit to mean "archived", and a "free" bit to mean "not archived". Or an appointment application might consider a "used" bit to mean "not available", and a "free" bit to mean "available". It does not matter to CXBitArray whether a "free" bit is defined to have a value of 0 or 1. CXBitArray has methods to set, test, and find bits with values of 0 or 1.

How To Use

To integrate CXBitArray class into your app, you first need to add the following file to your project:

XBitArray.h

For details on how to use CXBitArray object, refer to the code in XBitArrayTestDlg.cpp.

Here are some examples of how to construct a CXBitArray object:

Construct uninitialized CXBitArray object - Init() or Attach() must be called prior to using the object.
```
    CXBitArray();
```
Construct CXBitArray object from existing array - the address specified by bitarray will be used to access the 80-bit bit array, which will be initialized to 0.
```
    CXBitArray(bitarray, 80, 0);
```
Construct CXBitArray object with array allocation - an 80-bit bit array will be allocated from the heap and initialized to 0.
```
    CXBitArray(80, 0);
```
Construct CXBitArray object from file - the bit array (allocated from the heap, according to the size of the file) will be read from the file bitarray.dat. If the bit array cannot be read from the file, an 80-bit bit array will be allocated from the heap and initialized to 1.
```
    CXBitArray("bitarray.dat", 80, 1);
```
Construct CXBitArray object from registry - the bit array (allocated from the heap, according to the size of the registry value) will be read from the registry value at Software\CodeProject\XBitArrayTest\BitArray. If the bit array cannot be read from the registry, an 80-bit bit array will be allocated from the heap and initialized to 1.
```
    CXBitArray("Software\\CodeProject\\XBitArrayTest", "BitArray", 80, 1);
```

Demo App

The XBitArrayTest.exe demo tests the methods in CXBitArray:

Revision History

Version 1.2 - 2004 February 10

Initial public release

Usage

This software is released into the public domain. You are free to use it in any way you like, except that you may not sell this source code. If you modify it or extend it, please to consider posting new code here for everyone to share. This software is provided "as is" with no expressed or implied warranty. I accept no liability for any damage or loss of business that this software may cause.