views:

161

answers:

5

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

+10  A: 
  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.

Carl Norum
Thank you for pointing out the weak spots in my code. But if I don't specify any type if I use unsigned, I thought it would be an int automatically? Isn't that true?
Ief2
@Ief2: `unsigned`, `unsigned int` (and even `int unsigned`) are ways of writing the same type. Most people write `unsigned`.
Gilles
@Carl: in point 7, did you mean to recommend to always use braces, e.g., `if (flag == 0) { flag = 0; } else { flag = 1; }` (I don't see a place where I'd add parentheses)? @Ief2: using braces is a good idea because otherwise it's tempting to add a second indented statement and you won't realize it's not part of the conditionally executed block.
Gilles
@Gilles, I meant parentheses. For instance in `(orignalStatus == 0 in my experience it's the opposite. Even better would be to use the fully specified types available in C99.
Carl Norum
+3  A: 

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);
ysap
You'll also have to handle cases where your array is greater than 13 in size.
Merlyn Morgan-Graham
Thanks for pointing out that the value of bit #n in the binary can be set using C without math functions.
Ief2
@Ief2: don't use a floating-point function to perform integer computations. For large numbers you'll get wrong results because of rounding. For small numbers it may work but you have the burden of ensuring that your input is small enough and it'll usually be slower.
Gilles
+4  A: 

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:


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:


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.

Luther Blissett
`return !result` does the oposite.
Maciej Piechotka
@Maciej, thanks, corrected. It's late here already :-)
Luther Blissett
Thank you for pointing that out. I always was a little scared about using the !-operator, I never did know what it was going to return if I use the operator on 0, I'll get 1. For all the other values I get 0. Am I right?
Ief2
Oh, and thanks for the links!! I will definitely study them!
Ief2
`!x` is equivalent to `(x?0:1)`, `!!x` means `(x?1:0)`
Luther Blissett
+1  A: 

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.

asveikau
Thank you || But if I promote my char to an int, isn't it impossible to know the amount of bits in an int then? I thought a char was always 1 byte, and so 8 bits, but an int is machine dependent?
Ief2
@Ief2: in C terms a byte is a `char` and at least 8 bits (and almost always, but not absolutely always, exactly 8 bits). An `int` is at least 16 bits, usually 32, but can be 16 or other sizes. `sizeof(char)` is always 1; whether to write it as `sizeof(char)` or `1` is a matter of religious debates, however it's better to write `newReference = malloc(sizeof(*newReference))` so that the size will automatically be correct if you ever decide to change the type of `newReference`.
Gilles
+1  A: 

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?

Maciej Piechotka
About the copyright thing sorry: Xcode's way of making files. About the lost thing: I was thinking about something you can retain and release. A pointer to some data you can safely return, nevertheless it's out of is scope:char *f() { char f[] = "Hello World"; return f;}isn't safechar *f() { char *f = malloc(strlen("Hello World") + 1); strcpy(f, "Hello World"); return f; }is safe, but you have to free() it.
Ief2
char are much faster to just pass by value - you don't need to pass them by reference.
Maciej Piechotka