memory efficient flag array in C

Question

I need to store in memory a very long array.Each array item will be just a flag TRUE/FALSE (0/1). I need it to be very memory efficient so I have thought of implementing it as a masked-bit on top of an unsigned char region. Every char in memory should give me at least 8 flags. I have implemented the following functions:

static SIZE = 8; /* 8 bits = 1 byte = 1 char */

/* creates and initializes the array for N elements */
unsigned char *new_bit_array(long n) {
    int extra = (n % SIZE) ? 1 : 0;
    size_t ms = ((n / SIZE)+extra) * sizeof(unsigned char);
    unsigned char *p = malloc(ms);
    memset(p,0xFF,ms);
    return p;
}

/* mask setter for nth bit of a char, call by function bit_array_set*/
char bit_mask_set(short nbit,short value) {    
    if (value)
        return  0xFF;
    if (nbit == 0) 
        return 0x7F;
    else if (nbit == 1)
        return 0xBF;
    else if (nbit == 2) 
        return 0xDF;
    else if (nbit == 3) 
        return 0xEF;
    else if (nbit == 4) 
        return 0xF7;
    else if (nbit == 5) 
        return 0xFB;
    else if (nbit == 6) 
        return 0xFD;
    else if (nbit == 7) 
        return 0xFE;
    return 0xFF;
}

/* mask setter for nth element of the array */
void bit_array_set(unsigned char *p,long i,int value) {
    p[i/] &= bit_mask_set(i % SIZE,value);
}

/* mask getter for nth bit of a char, call by function bit_array_get */
char bit_mask_get(short nbit) {
    if (nbit == 0) 
        return 0x80;
    else if (nbit == 1)
        return 0x40;
    else if (nbit == 2) 
        return 0x20;
    else if (nbit == 3) 
        return 0x10;
    else if (nbit == 4) 
        return 0x08;
    else if (nbit == 5) 
        return 0x04;
    else if (nbit == 6) 
        return 0x02;
    else if (nbit == 7) 
        return 0x01;
    return 0x00;
}

/* mask getter for nth element of the array */
short bit_array_get(unsigned char *p,long i) {
    return p[i/SIZE] & bit_mask_get(i % SIZE) ? 1 : 0;
}

This code works fine but my question is if there are any built-in features in C or in any widely used library (i.e glib) that would provide the same functionality ?

... and also if there are any better ways of implementing bit_mask_get and bit_mask_set, the 7-branch IFs look ugly. Any other comments on this code are also very welcome.

I had a switch statement before and, to be honest, it doesn't change the code the a lot. It's basically the same thing. — Manuel Salvadores
– Manuel Salvadores, Commented Jul 27, 2011 at 17:35
0xff ^ (1 << (7-nbit)) should get rid of the if-else stuff in bit_mask_set. — user786653
– user786653, Commented Jul 27, 2011 at 17:36

MByD · Accepted Answer · 2011-07-27 17:32:18Z

8

You can do it simpler:

unsigned char flag_bitmask[MAX_FLAGS];

void setFlag( int flag) {
    flag_bitmask[flag / 8] |= (1 << (flag % 8) );
}

char isFlagSet(int flag) {
    return flag_bitmask[flag / 8] & (1 << (flag % 8) );
}

void unSetFlag(int flag) {
    flag_bitmask[flag / 8] &= ~(1 << (flag % 8) );
}

I'm using it a lot, and you can pass the flag_bitmask array instead of using it as global.

answered Jul 27, 2011 at 17:32

MByD

138k30 gold badges269 silver badges278 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Manuel Salvadores Over a year ago

I knew there was a clean way to do this. Nice answer (+1)

rph Over a year ago

Does the performance change if you choose unsigned int instead of char?

MByD Over a year ago

@rkioji - not really in most cases, there might be differences in some platforms, but it can go both ways. I use unsigned char as it is the smallest available unit and it has no endianess confusions.

user25148 · Accepted Answer · 2011-07-27 17:31:14Z

3

You can replace your SIZE constant with the macro CHAR_BIT from <limits.h>, which does the same thing.

In the new_bit_array function, you can replace 0xFF with (unsigned char) ~0, which is indepdendent of the number of bits in a char. Although it would be easier to initialize the memory to zero bits, perhaps by using calloc instead of malloc.

In bit_masK_get, you can replace the body with this:

return 1 << nbit;

Then similarly replace bit_mask_set with:

return (!!value) << nbit;

These put the bits in a different order from yours, but that doesn't matter, as long as they are consistent between each other.

answered Jul 27, 2011 at 17:31

user25148

Comments

Vinicius Kamakura · Accepted Answer · 2011-07-27 17:36:06Z

2

You can use bitfields in structs. You could have an array of the following struct:

struct bitflags {
    unsigned char f0:1;
    unsigned char f1:1;
    unsigned char f2:1;
    unsigned char f3:1;
    unsigned char f4:1;
    unsigned char f5:1;
    unsigned char f6:1;
    unsigned char f7:1;
};

struct bitflags many_flags[9001];
many_flags[0].f0 = 1;

answered Jul 27, 2011 at 17:36

Vinicius Kamakura

7,8121 gold badge31 silver badges44 bronze badges

3 Comments

Manuel Salvadores Over a year ago

This wouldn't be memory efficient. If I need like ... 1000e6 elements then I need malloc 1000e6/8 pointers to the structure bitflags. Pointers are memory expensive.

Vinicius Kamakura Over a year ago

that structure has the size of 1 byte. One up side from this approach is that you let the compiler figure out how to read and write the specific bits. It can use the machine's assembly if it is better and it can probably optimize better than you.

Manuel Salvadores Over a year ago

That is actually true. If you have it in a continuous memory space then no need of pointers, casting would work just fine. I take it back, it is actually memory efficient. Good answer, cheers (+1)

Collectives™ on Stack Overflow

memory efficient flag array in C

3 Answers 3

3 Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related