Thread: How to bitset in C?

Sure. Say "bitPlace" is the bit you want to set, and "bits" is an array of unsigned ints, representing your enormous bitfield. Then:

Code:

bits[bitPlace / sizeof(unsigned)] |= 0x1 << (bitPlace % sizeof(unsigned));

it's really easy to expand on this for other operations too.

Originally Posted by Zacariaz

I find my self in a predicament, as I get a segmentation error trying to declare an array taking up that much memory.

You can try using malloc or declaring the array to have static storage location (by declaring it at file scope or declaring it static).

Originally Posted by Zacariaz

I actually had much the same problem while using std::bitset in c++, and had to allocate the memory manually.

std::bitset does not appear to have an allocator template parameter, but you could always wrap a dynamically allocated one using std::unique_ptr, or perhaps try Boost.DynamicBitset (but then the performance may be different).

Originally Posted by laserlight

declaring the array to have static storage location (by declaring it at file scope or declaring it static).

I note a typo error: "static storage location" should have been "static storage duration".

Originally Posted by Zacariaz

But of course it is almost always desirable to leave the memory management to the compiler / OS.

C++ has an advantage due to RAII, but that is a negligible advantage here given that such a huge array will almost certainly have special care given to its lifetime.

Originally Posted by Zacariaz

For instance, if I'm not much mistaken, the above code run alone and on a 64 bit system, with no call to free, will result in one heck of a memory leak of 512mb.

Yes, but surely you would call free, and if you don't, on a modern OS the memory leak will not last beyond the termination of the process.

Originally Posted by Zacariaz

when you basically know upfront how much you need, it does seem silly. Still, there's apparently no way around it.

Then take my suggestion of declaring the array to have static storage duration as that is indeed a "way around it".

Originally Posted by Zacariaz

Regarding the memory leak:
The program could crash before the call to free

As I noted, on a modern OS, the memory would be released anyway. Besides, such a crash would indicate that you have a serious bug that needs to be fixed, so this concern of a memory leak is secondary.

Originally Posted by Zacariaz

or mistakes could be made, not least in larger projects.

That is true, but if that is truly a concern to you, then you should use C++ instead of C so as to take advantage of RAII, not just in this scenario, but in more general cases that would otherwise require manual resource management.

Originally Posted by Zacariaz

Are you saying that if declared static, no manual intervention is required for deallocating memory?

Yes. The lifetime of an object with static storage duration is the entire execution of the program. The good part is that this means that you are guaranteed that at the termination of the program, storage that has been reserved for such an object will be released. The bad part is that the storage is reserved the whole time, which can be as bad as a memory leak for a long running process.

That is very good to know, only I must be doing something wrong, as it's the compiler complains when static is applied:

error: initializer element is not constant

Seems like I have figured out most of the issues. I didn't quite get the result I expected, referring to the reason I needed a bitset in the first place, but it worked just the same. Since then I've spend a little time a generic implementation. Haven't actually tested it, but it should work.

Code:

#include <stdlib.h>
#include "bitset.h"


static uint_fast8_t* bitset = NULL;
static uint_fast32_t limit = 0;
static uint_fast8_t typeWidth = sizeof(uint_fast8_t)*8;


void Init(uint_fast32_t n) {
    limit = (n%typeWidth) ? n*typeWidth : (n+1)*typeWidth;
    bitset = calloc(limit,typeWidth/8);
}


void Destroy() {
    free(bitset);
    bitset = NULL;
    limit = 0;
}


int_fast8_t SetBit(uint_fast32_t n) {
    return (n < limit) ? bitset[n/typeWidth] |= 1 << n%typeWidth & 1 : -1;
}


int_fast8_t ResetBit(uint_fast32_t n) {
    return (n < limit) ? bitset[n/typeWidth] &= ~(1 << n%typeWidth) & 1 : -1;
}


int_fast8_t GetBit(uint_fast32_t n) {
    return (n < limit) ? (bitset[n/typeWidth] >> (n%typeWidth)) & 1 : -1;
}

Code:

#ifndef BITSET_H
#define BITSET_H
#include <stdint.h>

void Init(uint_fast32_t);
void Destroy();
void SetBit(uint_fast32_t);
void ResetBit(uint_fast32_t);
int_fast8_t GetBit(uint_fast32_t);

#endif

It looks right to me, except to say that set/reset bit should probably have some sort of return value.

Anyway it's past my bedtime, so any testing will have to wait.


Best regards

If you want to go the calloc/free route, then it would be better to write a reusable library, e.g.,

Code:

#ifndef ZACARIAZ_BITSET_H
#define ZACARIAZ_BITSET_H

/* bitset.h */

#include <stdint.h>

typedef struct Bitset_ Bitset;

void BitsetInit(Bitset *bitset, uint_fast32_t n);
void BitsetDestroy(Bitset *bitset);
int_fast8_t BitsetSetBit(Bitset *bitset, uint_fast32_t n);
int_fast8_t BitsetResetBit(Bitset *bitset, uint_fast32_t n);
int_fast8_t BitsetGetBit(Bitset *bitset, uint_fast32_t n);

#endif

Code:

#include <stdlib.h>
#include "bitset.h"


struct Bitset_ {
    uint_fast8_t *data;
    uint_fast32_t limit;
};

static const uint_fast8_t BitsetTypeWidth = sizeof(uint_fast8_t) * CHAR_BIT;


void BitsetInit(Bitset *bitset, uint_fast32_t n) {
    bitset->limit = ((n % BitsetTypeWidth) ? n : (n + 1)) * BitsetTypeWidth;
    bitset->data = calloc(bitset->limit, sizeof(bitset->data[0]));
}


void BitsetDestroy(Bitset *bitset) {
    free(bitset->data);
    bitset->data = NULL;
    bitset->limit = 0;
}

/* ... */

Originally Posted by Zacariaz

At any rate, Except for the keyword 'typedef', which for some odd reason has always confused me, though I'm uncertain how exactly to use it.

In this case, typedef is used for convenience: unlike C++, the tag name by itself cannot be used to refer to a struct type, i.e., by declaring struct Bitset_, we cannot just use the name Bitset_, but rather have to use struct Bitset_. This can be useful at times for the reader to be explicitly aware that a struct type is in use, but here it is just verbose, hence I made Bitset an alias for struct Bitset_, thus from the point of the typedef onwards Bitset can be used instead of struct Bitset_.

Originally Posted by Zacariaz

You obviously have declare a type Bitset on your own, in order to be able to pass it to the various functions, but that seems rather unsafe and convoluted.

That is not true. The Bitset type has already been declared. What the user of the library must do is to create a Bitset object in order to be able to pass a pointer to it to the various function. There is nothing unsafe or convoluted about that.

That said, I noticed that there is a flaw in my example code: I would like the implementation of struct Bitset_ to be hidden in the source file, but if so, the user cannot declare a Bitset object, i.e., this will be invalid:

Code:

Bitset bitset;
BitsetInit(&bitset, 20);

A solution is to change BitsetInit to take a pointer to a pointer instead:

Code:

void BitsetInit(Bitset **bitset, uint_fast32_t n) {
    Bitset *result = malloc(sizeof(*result));
    if (result) {
        result->limit = ((n % BitsetTypeWidth) ? n : (n + 1)) * BitsetTypeWidth;
        result->data = calloc(result->limit, sizeof(result->data[0]));
    }
    *bitset = result;
}

Now the user can create a pointer to Bitset instead:

Code:

Bitset *bitset = NULL;
BitsetInit(&bitset, 20);

Of course, BitsetDestroy would have to be changed accordingly.

Originally Posted by Zacariaz

Furthermore is was never my intention to go the free() route, but as only one bitset could exist, I thought Destroy might come in handy. Now however, looking at your code, it would seem that you can't do without free, as 'data' is not static.

Even if data was static, you cannot do without free. If you want an array with static storage duration so as to do without calloc/free, then it must really be an array, not a pointer:

Code:

uint_fast8_t bitset[1234];

Note that you do not have to actually use the static keyword: just defining at file scope in a source file would suffice. In the header file, you would declare it extern. If you do use the static keyword, then the array becomes local to the source file (or rather the translation unit), in which case declaring it in the header usually does not make sense.