Bitmap implementation

Question

I recently started cleaning up my projects and decided that I want to create a personal repository of useful bits of code. I found this bitmap code between them and heavily edited it and I'd appreciate if someone could review it, because I'm not that used to bitwise operations and such. Is the code portable enough, or there should be changes?

bitmap.h

#ifndef BITMAP__
#define BITMAP__

#define BIT (8*sizeof(byte))
#define BITMAP_NOTFOUND -1

typedef enum{false=0, true} bool;
typedef unsigned char byte;

bool bitmapGet   (byte *, int);
void bitmapSet   (byte *, int);
void bitmapReset (byte *, int);
int  bitmapSearch(byte *, bool, int, int);

#endif

bitmap.c

#include "bitmap.h"

static bool get  (byte,   byte);
static void set  (byte *, byte);
static void reset(byte *, byte);

/* CAREFUL WITH pos AND BITMAP SIZE! */

bool bitmapGet(byte *bitmap, int pos) {
/* gets the value of the bit at pos */
    return get(bitmap[pos/BIT], pos%BIT);
}

void bitmapSet(byte *bitmap, int pos) {
/* sets bit at pos to 1 */
    set(&bitmap[pos/BIT], pos%BIT);
}

void bitmapReset(byte *bitmap, int pos) {
/* sets bit at pos to 0 */
    reset(&bitmap[pos/BIT], pos%BIT);
}

int bitmapSearch(byte *bitmap, bool n, int size, int start) {
/* Finds the first n value in bitmap after start */
/* size is the Bitmap size in bytes */
    int i;
    /* size is now the Bitmap size in bits */
    for(i = start+1, size *= BIT; i < size; i++)
        if(bitmapGet(bitmap,i) == n)
            return i;
    return BITMAP_NOTFOUND;
}

static bool get(byte a, byte pos) {
/* pos is something from 0 to 7*/
    return (a >> pos) & 1;
}

static void set(byte *a, byte pos) {
/* pos is something from 0 to 7*/
/* sets bit to 1 */
    *a |= 1 << pos;
}

static void reset(byte *a, byte pos) {
/* pos is something from 0 to 7*/
/* sets bit to 0 */
    *a &= ~(1 << pos);
}

Answer 1

If you expect your code will ever be used from C++ (which a lot of C code is) then you should not use any identifiers with a double underscore.

#ifndef BITMAP__
    //        ^^   May cause problems in C++

As this is reserved for the implementation in C++. Also the term BITMAP is very generic and you are very likely to clash with other libraries try and make it more unique to your project.

You are assuming that a char is 8 bits.

#define BIT (8*sizeof(byte))

The standard does not say this (it is at least 8 bits) but it is actually defined via the macro CHAR_BITS so you should use:

#define BIT (CHAR_BITS*sizeof(byte))

Your header file is how most people will first see your code and try and understand how to use it. Thus putting the parameter names into the header file is probably a good idea as it helps document their usage.

bool bitmapGet   (byte *, int);
void bitmapSet   (byte *, int);
void bitmapReset (byte *, int);
int  bitmapSearch(byte *, bool, int, int);

Additional the action of bitmapSearch is not obvious thus a comment on its usage in the header would probably be a good idea. Actually a small blurb about how the first parameter can be an array would probably be a good idea (as it is not obvious without reading the code).

Be careful with comments:

/* pos is something from 0 to 7*/

This is only true if you make assumptions (A: that sizeof(byte) == 1 B: you multiply this by 8). The comment should have been:

/* pos is a value between [0, BIT) */

Note the use of '[' on the left and ')' on the right. It is mathematical notation indicating that 0 is inclusive and BIT is not included in the range (it is common in both C/C++ documentation).

Answer 2

1. Your types are unnecessary - just use unsigned char and int as the standard library would.

2. On the same topic, your enum bool is unnecessary because in C non-zero indicates the true state. You confirm that yourself because get() assumes that the value 1 is true. Everyone assumes this and so the type is redundant. Moreover it is also wrong because if I change your enum to

   typedef enum{true=0, false} bool;
   

   your function fails, even though it is logically a reasonable thing to do.

   If you want to use a bool like that your should return one of its values explicitly:

   return ((a >> pos) & 1) ? true : false;
   

   but there is really no point in this. Just return an int as the standard library would.

3. bitmapGet() returning a bool seems mis-named to me. The bitmap bits have values 1 and 0, not true and false (even though these are currently the same). Calling it bitmapIsSet() would be more logical.

4. sizeof(char) is 1 by definition, so BIT can be replaced with CHAR_BIT

5. Opening brackets for functions are normally at column 0

6. The order of parameters for bitmapSearch would be more logical is the size followed the thing it refers to (bitmap).

7. The start parameter for bitmapSearch is wrong. To specify a search starting from bit 0 (surely the most common) the caller must pass -1 !!

8. Why pass the 'pos' parameter as a 'byte' ? You have defined 'byte' to represent the bitmap bytes and 'pos' is certainly not one of those. You will get compiler warnings if they are enabled (they should be) about passing arguments with different widths due to prototypes. And restricting 'pos' to a byte may add an extra machine instruction (look at the assembler) while and achieving nothing. If you could define a type pos_t with the range 0..7 that you seem to want then you might argue that it was in some way correct, but as you cannot do that in C and clearly the byte value has the range 0..255, it is no better than using an int.

Answer 3

Do didn't ask about performance, but you can speed up bitmapSearch for sparse bitmaps by first looking at a byte at a time. If looking for a 1, you can skip bytes that are 0x00, and if looking for a 0, you can skip bytes that are 0xFF. After that, you can scan the bits on the next byte or use a look-up table on it.

As far as the API goes, you might add

byte * bitmapAlloc(int sizeInBits);
void   bitmapFree(byte * bitmap);

so the client doesn't have to worry about how many bytes to allocate.

And/or provide a macro to help with allocations. A macro instead of a function if you want it to appear in array allocations.

#define BITMAP_BYTE_COUNT_FOR(n) ((n)+BIT-1)/BIT)

I'd also have bitmapSearch take its size as a bit count instead of a byte count. Then if the client only cares about, say, 26 bits for letters, they don't have to worry about a search returning 27 because the bitmap really have 32 bits in it.