Boolean array using "char"

Question

Hi, I made an object that actually represents an array of 8 booleans stored in a char. I made it to learn something more about bitwise operators and about creating your own objects in C. So I've got two questions:

1. Can I be certain if the below code always works?
2. Is this a good implementation to make an object that can't get lost in C, unless you release it yourself.

The Code:

/*
 *  IEFBooleanArray.h
 *  IEFBooleanArray
 *
 *  Created by ief2 on 8/08/10.
 *  Copyright 2010 ief2. All rights reserved.
 *
 */

#ifndef IEFBOOLEANARRAY_H
#define IEFBOOLEANARRAY_H

#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef char * IEFBooleanArrayRef;

void IEFBooleanArrayCreate(IEFBooleanArrayRef *ref);
void IEFBooleanArrayRelease(IEFBooleanArrayRef ref);
int IEFBooleanArraySetBitAtIndex(IEFBooleanArrayRef ref, 
                                 unsigned index, 
                                 int flag);
int IEFBooleanArrayGetBitAtIndex(IEFBooleanArrayRef ref, 
                                 unsigned index);

#endif

---

/*
 *  IEFBooleanArray.c
 *  IEFBooleanArray
 *
 *  Created by ief2 on 8/08/10.
 *  Copyright 2010 ief2. All rights reserved.
 *
 */

#include "IEFBooleanArray.h"

void IEFBooleanArrayCreate(IEFBooleanArrayRef *ref) {
    IEFBooleanArrayRef newReference;

    newReference = malloc(sizeof(char));
    memset(newReference, 0, sizeof(char));
    *ref = newReference;
}

void IEFBooleanArrayRelease(IEFBooleanArrayRef ref) {
    free(ref);
}

int IEFBooleanArraySetBitAtIndex(IEFBooleanArrayRef ref, unsigned index, int flag) {
    int orignalStatus;

    if(index < 0 || index > 7)
        return -1;

    if(flag == 0)
        flag = 0;
    else
        flag = 1;

    orignalStatus = IEFBooleanArrayGetBitAtIndex(ref, index);
    if(orignalStatus == 0 && flag == 1)
        *ref = *ref + (int)pow(2, index);
    else if(orignalStatus == 1 && flag == 0)
        *ref = *ref - (int)pow(2, index);

    return 0;
}

int IEFBooleanArrayGetBitAtIndex(IEFBooleanArrayRef ref, unsigned index) {
    int result;
    int value;

    value = (int)pow(2, index);
    result = value & *ref;

    if(result == 0)
        return 0;
    else
        return 1;
}

I'm more of an Objective-C guy, but I really want to learn C more. Can anyone request some more "homework" which I can improve myself with?

Thank you, ief2

Answer 1

1. Don't check unsigned types with < 0, it's meaningless and causes warnings on some compilers.
2. Don't use unsigned types without specifying their size (unsigned int, unsigned char, etc).
3. If flag == 0 why are you setting it to 0?
4. I don't like abstracting the * away in a typedef, but it's not wrong by any means.
5. You don't need to call memset() to set a single byte to 0.
6. Using pow to calculate a bit offset is crazy. Check out the << and >> operators and use those instead
7. Fully parenthesize your if statement conditions or be prepared for debugging pain in your future.
8. If you use the bitwise operators & and | instead of arithmetic + and - in your SetBitAtIndex function, you won't need all those complicated if statements anyway.
9. Your GetBitAtIndex routine doesn't bounds check index.

From that list, #9 is the only one that means your program won't work in all cases, I think. I didn't exhaustively test it - that's just a first glance check.

Answer 2

As for accessing bit #n in your char object, instead of using pow() function, you can use shifting and masking:

Set bit #n:

a = a | (1 << n);

Clear bit #n:

a = a & (~(1 << n));

Get bit #n:

return ((a >> n) & 1);

Answer 3

---

pow(2,index) is among the more inefficient ways to produce a bit mask. I can imagine that using the Ackermann function could be worse, but pow() is pretty much on the slow side. You should use (1<<index) instead. Also, the C'ish way to set/clear a bit in a value looks different. Here's a recent question about this:

• http://stackoverflow.com/questions/3423788/simple-way-to-set-unset-an-individual-bit/

---

If you want to munge bits in C in an efficient and portable way, then you really should have a look at the bit twiddling page, that everyone here will suggest to you if you mention "bits" somehow:

• http://graphics.stanford.edu/~seander/bithacks.html

---

The following code sequence:

if(result == 0)
        return 0;
    else
        return 1;

can be written as return (result != 0);, return resultor return !!result (if result should be forced to 0 or 1) . Though it's always a good idea to make an intent clear, most C programmer will prefer 'result result;' because in C this the way to make your intent clear. The if looks iffy, like a warning sticker saying "Original developer is a Java guy and knows not much about bits" or something.

---

newReference = malloc(sizeof(char));
memset(newReference, 0, sizeof(char));

malloc + memset(x,0,z) == calloc();

---

You have a way to report an error (invalid index) for IEFBooleanArraySetBitAtIndex but not for IEFBooleanArrayGetBitAtIndex. This is inconsistent. Make error reporting uniform, or the users of your library will botch error checking.

Answer 4

Nobody seems to be mentioning this (I am surprised), but... You can't tell me you're seriously doing malloc(sizeof(char))? That is a very small allocation. It doesn't make sense to make this a heap allocated object. Just declare it as char.

If you want to have some degree of encapsulation, you can do: typedef char IEFBoolArray; and make accessor functions to manipulate an IEFBoolArray. Or even do typedef struct { char value; } IEFBoolArray; But given the size of the data it would be sheer madness to allocate these one at a time on the heap. Have consumers of the type just declare it inline and use the accessors.

Further... Are you sure you want it to be char? You might get slightly better code generated if you promote that to something larger, like int.

Answer 5

In addition to Carl Norum points:

1. Don't save space in char such way unless you have to (i.e. you store a lot of bit values). It is much slower as you have to perform bitwise operations etc.
2. On most architectures you waste memory by mallocing char. One pointer takes 4 to 8 times more then char on most modern architectures and additionally you have data about the malloced chunk as it.
3. Probably static size is not the best approach as it inflexible. I wouldn't see any benefit of using speciall functions for it.

As of 3rd point something like:

typedef struct {
    uint64_t size;
    uint64_t *array;
}bitarray;

bitarray bitarray_new(uint64_t size) {
    bitarray arr;
    arr.size = size;
    arr.array = calloc(size/8);
    return arr;
}

void bitarray_free(bitarray arr) {
    free(arr.array);
}

void bitarray_set(bitarray arr, uint64_t index, int bit) {
  assert (index <= arr.size)
  if (bit)
    array[index/8] |= 1 << (index % 8);
  else
    array[index/8] ^= ~(1 << (index % 8));
}

void bitarray_get(bitarray arr, uint64_t index, int bit) {
  assert (index <= arr.size)
  return array[index/8] & 1 << (index % 8);
}

Copyright 2010 ief2. All rights reserved.

Actually they are not. You volontarly published them under cc-by-sa licence and only some right are reserved. Additionally you want us to read and modify the code so reserving all right is pointless.

(PS. I would advice against publishing trivial work under restrictive licences anyway - it does not look professionaly - unless you have legal issues to do so)

Is this a good implementation to make an object that can't get lost in C, unless you release it yourself.

Sorry?