BitSet

The BitSet datatype provides a low-level bit set. It provides the usual insert, delete, and membership functions. It has one special purpose function required for heap management that counts the zeros to the right starting at a position within the bit set.

This low-level implementation builds the set inside a pre-defined space that is passed into the initialization function for the datatype. The implementation does not dynamically allocate any data. All space for the implementation is determined before the datatype is instantiated.

An Example of Using the BitSet

Consider a BitSet of 1024 bits. The following code creates a BitSet, initializes it, and exercises a few of the functions.

Listing 53 A BitSet Example
 1size_t bitsetsize;
 2dragonBitSetErr_t brc;
 3bitsetsize = dragon_bitset_size(1024);
 4void* bsptr = malloc(bitsetsize);
 5dragonBitSet_t bset;
 6brc = dragon_bitset_init(bsptr,&bset,1024);
 7if (brc != DRAGON_SUCCESS)
 8    printf("Error Code was %u\n",brc);
 9brc = dragon_bitset_set(&bset, 0);
10if (brc != DRAGON_SUCCESS)
11    printf("Error Code was %u\n",brc);
12brc = dragon_bitset_set(&bset, 400);
13if (brc != DRAGON_SUCCESS)
14    printf("Error Code was %u\n",brc);
15brc = dragon_bitset_set(&bset, 916);
16if (brc != DRAGON_SUCCESS)
17    printf("Error Code was %u\n",brc);
18brc = dragon_bitset_set(&bset, 42);
19if (brc != DRAGON_SUCCESS)
20    printf("Error Code was %u\n",brc);
21unsigned char bit;
22brc = dragon_bitset_get(&bset, 42, &bit);
23if (brc != DRAGON_SUCCESS)
24    printf("Error Code was %u\n",brc);
25if (bit == 1)
26    printf("That was a one\n");
27brc = dragon_bitset_reset(&bset, 42);
28if (brc != DRAGON_SUCCESS)
29    printf("Error Code was %u\n",brc);
30brc = dragon_bitset_dump("A Bit Dump", &bset, "");
31if (brc != DRAGON_SUCCESS)
32    printf("Error Code was %u\n",brc);
33size_t val = 0;
34dragon_bitset_zeroes_to_right(&bset,0,&val);
35printf("The number is %lu\n",val);

The output from the example program in Listing 53 is given in Listing 54. The bits in the bitset display bit 0 on the left, not the right. In this way, the bits display lexicographically in a dump from left to right for easier reading. Bit 0 is the left-most bit in the dump while the last bit is lexicographically the last bit to be displayed.

Listing 54 BitSet Example Output
That was a one
A Bit Dump
Size of bitset is 125
BITS:
  0000000001123268 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  0000000001123278 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  ...
  0000000001123298 00 00 80 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  00000000011232A8 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
  ...
  00000000011232D8 00 00 08 00 00 00 00 00 00 00 00 00 00           .............
The number is 399

Meta-Data and Handles

The meta-data/data structures required to implement the BitSet includes the number of bits in the BitSet as the first 8 bytes, followed by enough bytes to hold the rest of the bits. Note that the BitSet is designed to always use a multiple of 8 bytes for easy alignment with other data.

When a BitSet is initialized, a handle to the BitSet is also initialized. The handle is now the user of this API accesses the BitSet. The handle structure is given in Listing 55.

Listing 55 BitSet Handle Definition
typedef struct dragonBitSet_st {
    size_t size;
    char* data;
} dragonBitSet_t;

Initialization copies the size field from the pre-defined memory into the handle. The data pointer points into the shared data.

NOTE: This implementation of BitSet is not locked and relies on some other locking mechanism for shared access between processes or threads.

Performance of Operations

The performance of all operations is O(1) in complexity except for the dragon_bitset_zeroes_to_right() function, which is O(n). However, this function is optimized so that is O(n) where n is the number of words to the right of the given bit. Whenever possible, entire words are examined rather than examining a bit at a time in the dragon_bitset_zeroes_to_right() function, resulting in a very efficient O(n) operation.

BitSet Client API

The API for using BitSets defines a shared datatype and a similar per-process handle definition.

Structures

The enumeration of error codes and the handle definition are the two structures that are defined for the BitSet datatype.

Error Codes

enum dragonBitSetErr_t

This is the BitSet error code enumeration. Most API calls return an error code as a result of calling them. The possible error codes for specific API calls are given with their function definitions, given below.

enumerator DRAGON_SUCCESS

Operation completed successfully.

enumerator DRAGON_BOUNDS_ERROR

The requested bit was out of the bounds of the set.

enumerator DRAGON_BITSET_NULL_POINTER

A null pointer was provided for the BitSet handle.

The Handle

struct dragonBitSet_t

A bitset handle.

This structure should not be used directly. All manipulation of the bitset occurs via its API functions. This structure is meant to meant to be used internally within some larger structure and will be self-contained completely within the larger structure. The bitset implementation does no dynamic memory allocation.

Public Members

size_t size

For internal use only

char *data

For internal use only

API

These are the user-facing API calls for bit sets.

Life-Cycle

size_t dragon_bitset_size(size_t num_bits)

Compute the number of bytes needed to hold this bitset.

This API provides a bitset implementation that resides in a pre-allocated blob of memory. This datatype does not do any dynamic allocation of memory on its own. The bitset is a set of integers ranging from to to num_bits-1.

Parameters:

  • num_bits – The number of integers that may be in the set. Potential members of the set range from 0 to num_bits-1.

  • size – The returned size required for this bitset. The user allocates a blob of this size and then passes a pointer to it in on the init function call before using any other functions in this API.

Returns:

  • DRAGON_SUCCESS It did its job.

  • DRAGON_BITSET_NULL_POINTER The set was a null-pointer.

Example Usage

size_t bitsetsize = dragon_bitset_size(1024);
dragonError_t dragon_bitset_get_num_bits(const dragonBitSet_t *set, size_t *num_bits)

Return the number of bits contained in this set.

Returns the number of bits (i.e. One more than maximum integer that can be contained in the set) in the set.

Parameters:

  • set – A pointer to a bitset handle.

  • num_bits – A pointer to the size_t variable that will hold the number of bits this set contains.

Returns:

  • DRAGON_SUCCESS It did its job.

  • DRAGON_BITSET_NULL_POINTER The set or num_bits was a null-pointer.

Example Usage

dragonError_t brc;
dragonBitSet_t bset;
size_t num_bits;
brc = dragon_bitset_init(bsptr,&bset,1024);
if (brc != DRAGON_SUCCESS) {
    printf("Error Code was %u\n",brc);
}
brc = dragon_bitset_get_num_bits(bset, &num_bits);
if (brc != DRAGON_SUCCESS) {
    printf("Error Code was %u\n",brc);
}
printf("Number of bits was %u\n", num_bits);
dragonError_t dragon_bitset_init(void *ptr, dragonBitSet_t *set, const size_t num_bits)

Initialize a bitset from a blob of memory.

This API provides a bitset implementation that resides in a pre-allocated blob of memory. This datatype does not do any dynamic allocation of memory on its own. The bitset is a set of integers ranging from to to num_bits-1.

A bitset must be initialized by calling init before any other API calls can be made except the size function which should be called first to determine required size of the blob to hold this bitset.

Parameters:

  • ptr – A pointer to the blob of memory where the bitset will reside.

  • set – A pointer to a handle to be initialized to use this bitset. The handle is used on subsequent calls to the API.

  • num_bits – The number of bits for this bitset. This must be the same number of bits that was provided on the previous call to the size function in this API.

Returns:

  • DRAGON_SUCCESS It did its job.

  • DRAGON_BITSET_NULL_POINTER The set or ptr was a null-pointer.

Example Usage

dragonBitSet_t bset;
brc = dragon_bitset_init(bsptr,&bset,1024);
if (brc != DRAGON_SUCCESS) {
    printf("Error Code was %u\n",brc);
}
dragonError_t dragon_bitset_destroy(dragonBitSet_t *set)

Destroy a bitset.

Once done with a bitset, destroy should be called to free resources use by the bitset.

Parameters:

set – A pointer to a bitset handle.

Returns:

  • DRAGON_SUCCESS It did its job.

  • DRAGON_BITSET_NULL_POINTER The set was a null-pointer.

Example Usage

dragonBitSet_t set;
// initialize and use the bitset. Then finally destroy it.
dragon_bitset_destroy(&set);
dragonError_t dragon_bitset_attach(void *ptr, dragonBitSet_t *set)

Attach to a previously initialized bitset.

Once initialized, a previously initialized heap may be attached. However, bitsets are not multi-threaded/multi-processing safe. Sychronization of API calls must be done separately.

Parameters:

  • ptr – The pointer to the blob of previously initialized bitset.

  • set – A pointer to a handle that will be initialized by this call.

Returns:

  • DRAGON_SUCCESS It did its job.

  • DRAGON_BITSET_NULL_POINTER The set or ptr was a null-pointer.

Example Usage

dragonBitSet_t bset;
//bsptr points at the previously initialized BitSet space.
brc = dragon_bitset_attach(bsptr,&bset);
if (brc != DRAGON_SUCCESS) {
    // handle it
}
dragonError_t dragon_bitset_detach(dragonBitSet_t *set)

Detach from an attached bitset.

If attached was called to attach a bitset, then detach should be called when access to the bitset is no longer required.

Parameters:

set – A pointer to a bitset handle.

Returns:

  • DRAGON_SUCCESS It did its job.

  • DRAGON_BITSET_NULL_POINTER The set was a null-pointer.

Example Usage

dragonBitSet_t set2; // attach this space to a BitSet.
// Then later...
brc = dragon_bitset_detach(&set2);

if (brc != DRAGON_SUCCESS) {
    // handle it
}

Services

dragonError_t dragon_bitset_set(dragonBitSet_t *set, const size_t val_index)

Set a bit to 1 in the bitset.

Turn on a bit in the bitset regardless of its previous value. This makes the integer given by val_index a member of the set.

Parameters:

  • set – A pointer to a bitset handle.

  • val_index – The integer to add to the set. The val_index value must be between 0 and the number of bits in the bitset minus one.

Returns:

  • DRAGON_SUCCESS It did its job.

  • DRAGON_BITSET_NULL_POINTER The set was a null-pointer.

  • DRAGON_BITSET_BOUNDS_ERROR The val_index was too big for the given set.

Example Usage

brc = dragon_bitset_set(&bset, 0);
if (brc != DRAGON_SUCCESS)
    printf("Error Code was %u\n",brc);
dragonError_t dragon_bitset_reset(dragonBitSet_t *set, const size_t val_index)

Reset a bit to 0 in the bitset.

Turn off a bit in the bitset regardless of its previous value. This means the integer given by val_index is no longer a member of the bitset.

Parameters:

  • set – A pointer to a bitset handle.

  • val_index – The integer to remove from the set. The val_index value must be between 0 and the number of bits in the bitset minus one.

Returns:

  • DRAGON_SUCCESS It did its job.

  • DRAGON_BITSET_NULL_POINTER The set was a null-pointer.

  • DRAGON_BITSET_BOUNDS_ERROR The val_index was too big for the given set.

Example Usage

brc = dragon_bitset_reset(&bset, 0);
if (brc != DRAGON_SUCCESS)
    printf("Error Code was %u\n",brc);
dragonError_t dragon_bitset_get(const dragonBitSet_t *set, const size_t val_index, unsigned char *val)

Get a bit from the bitset.

Retrieve a bit from the bitset. This is a membership test for the set.

Parameters:

  • set – A pointer to a bitset handle.

  • val_index – The integer to test for membership. The integer must be between 0 and the number of bits in the bitset minus one.

  • val – A pointer to an unsigned byte that will hold the result. It will be 0 or 1.

Returns:

  • DRAGON_SUCCESS It did its job.

  • DRAGON_BITSET_NULL_POINTER Either the set or the val was a null-pointer.

  • DRAGON_BITSET_BOUNDS_ERROR The val_index was too big for the given set.

Example Usage

unsigned char bit;
brc = dragon_bitset_get(&bset, 42, &bit);
if (brc != DRAGON_SUCCESS)
    printf("Error Code was %u\n",brc);
dragonError_t dragon_bitset_zeroes_to_right(const dragonBitSet_t *set, const size_t val_index, size_t *val)

Compute the number of zero bits to the right of a member of the bitset.

This is a special purpose function (primarily for the heap manager) that counts the zeroes to the right of a member of the set.

Parameters:

  • set – A pointer to a bitset handle.

  • val_index – The integer member of the set. Whether this integer is a member of the set or not is irrelevant to this function call. It will count the zeroes to the right of any integer in the acceptable range of integers for the bitset.

  • val – A pointer to an unsigned integer that will hold the number of zeroes to the right of val_index.

Returns:

  • DRAGON_SUCCESS It did its job.

  • DRAGON_BITSET_NULL_POINTER If either the set or the val pointer were passed in as NULL.

  • DRAGON_BITSET_BOUNDS_ERROR If val_index was too large for the given set.

Example Usage

size_t val = 0;
brc = dragon_bitset_zeroes_to_right(&bset,0,&val);
if (brc != DRAGON_SUCCESS)
    printf("Error Code was %u\n",brc);
else
    printf("The number is %lu\n",val);

Status/Debug

dragonError_t dragon_bitset_dump(const char *title, const dragonBitSet_t *set, const char *indent)

Dump a bitset to standard output for debug purposes.

This prints the contents of a bitset as a hex dump to standard output.

Parameters:

  • title – A null-terminated string to identify the dump in the output.

  • set – A pointer to a bitset handle.

  • indent – A null-terminated string (usually spaces) that prefixes each line of output in the dump.

Returns:

  • DRAGON_SUCCESS It did its job.

  • DRAGON_BITSET_NULL_POINTER

Example Usage

dragon_bitset_dump("Block Set", &set, "  ");
dragonError_t dragon_bitset_dump_to_fd(FILE *fd, const char *title, const dragonBitSet_t *set, const char *indent)

Dump a bitset to a file descriptor for debug purposes.

Print a dump to the file fd. Exactly the same of :c:func:dragon_bitset_dump except you can specify an open, writable file.

Parameters:

  • fd – An open, writable file descriptor.

  • title – A null-terminated string to identify the dump in the output.

  • set – A pointer to a bitset handle.

  • indent – A null-terminated string (usually spaces) that prefixes each line of output in the dump.

Returns:

  • DRAGON_SUCCESS It did its job.

  • DRAGON_BITSET_NULL_POINTER Indicates an incorrect call. The fd, title, set, and indent must all be non-null. A bad, non-null, pointer would result in a segfault.

Example Usage

Print a dump of the BitSet structure with the given title to standard output. The output looks similar to this.

*   Block Set
*    Size of bitset is 131072
*    BITS:
*    00007F5218663068 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
*    00007F5218663078 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
*    ...
*    00007F5218683058 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

dragon_bitset_dump_to_fd(logfile, "Block Set", &set, "  ");

Python Interface

This provides the Python interface to BitSet.

init

init(const size_t num_bits, unsigned char [:] space)

Initialize the space with a BitSet of size num_bits.

Parameters:

  • num_bits – The size of the BitSet.

  • space – The space big enough to hold the BitSet.

Returns:

The BitSet object

Example Usage

# example using BitSet.init