I'm implementing a bitset data structure in C, which is constructed as a Bit vector, which in turn is implemented as an array of the data type char. After set_empty creates an empty set, set_insert inserts a value in that set and set_remove is supposed to remove the value inserted in that parameter from the set in that parameter but I keep running into an error. I know there's something wrong with that free() operation but not sure how else to do it.

struct set {
    int capacity;
    int size;
    char *array;
};
set *set_empty()
{

struct set *ptr = malloc(sizeof(struct set));

ptr->size = 0;

ptr->array = malloc(sizeof(char));

ptr->capacity = 1;

return ptr;
}
void set_insert(const int value, set *s)
{
    if (!set_member_of(value, s)) {
        int bit_in_array = value; 


    // Increase the capacity if necessary
    if (bit_in_array >= s->capacity) {
        int no_of_bytes = bit_in_array / 8   1;
        s->array = realloc(s->array, no_of_bytes);
        for (int i = s->capacity / 8 ; i < no_of_bytes ; i  ) {
            s->array[i] = 0;
        }
        s->capacity = no_of_bytes * 8;
    }

    // Set the bit
    int byte_no = bit_in_array / 8;
    int bit = 7 - bit_in_array % 8;
    s->array[byte_no] = s->array[byte_no] | 1 << bit;
    s->size  ;
}
}
void set_remove(const int value, set *const s)
{
  for (int i = 0; i < s->size; i  )
  {
    if (value == s->array[i])
    {
      free(s->array[i]);
    }
    else
    {
      printf("Value does not exist in set");
    }
  }
}

CodePudding user response：

Some bugs ...

You can not do free(s->array[i]) for a few reasons:

1. You're not passing an address/pointer. You're passing the value, so this won't even compile cleanly
2. You can only free an address that you got from malloc/realloc/calloc so you can't free the middle of an array. (i.e.) You can't do: free(&s->array[i])
3. If you're clearing a bit, you want to use the same index/mask technique you used when setting the bit.

Also, capacity is set to 1 initially. It should be a multiple of 8. Both size and capacity are bit oriented.

Also, you need the bit indexing/masking code in several places. That would require some replication of code. Better to use some macros.

Probably better to use unsigned char as a base array type.

Here's a refactoring of the code with some cleanup. I've compiled it but not tested it:

#include <stdio.h>
#include <stdlib.h>

typedef unsigned char u8;

typedef struct {
    int capacity;
    int size;
    u8 *array;
} set;

#define IDXOF(_bitno) \
    ((_bitno) / 8)

#define BITOF(_bitno) \
    (7 - ((_bitno) % 8))

#define MSKOF(_bitno) \
    (1u << BITOF(_bitno))

#define INRANGE(_bitno) \
    (((_bitno) >= 0) && ((_bitno) < s->capacity))

set *
set_empty()
{

    set *ptr = malloc(sizeof(*ptr));

    ptr->size = 0;
    ptr->array = NULL;
    ptr->capacity = 0;

    return ptr;
}

u8
set_member_of(int bitno,set *s)
{
    u8 ret = 0;

    if (INRANGE(bitno)) {
        int idx = IDXOF(bitno);
        u8 mask = MSKOF(bitno);
        ret = s->array[idx] & mask;
    }

    return ret;
}

void
set_insert(int bitno, set *s)
{
    int idx = IDXOF(bitno);
    u8 mask = MSKOF(bitno);

    if (INRANGE(bitno)) {
        if (s->array[idx] & mask)
            return;
    }

    // Increase the capacity if necessary
    if (bitno >= s->capacity) {
        int no_of_bytes = (bitno / 8)   1;

        s->array = realloc(s->array, no_of_bytes);
        for (int i = s->capacity / 8; i < no_of_bytes; i  )
            s->array[i] = 0;

        s->capacity = no_of_bytes * 8;
    }

    // Set the bit
    s->array[idx] |= mask;
    s->size  ;
}

u8
set_remove(int bitno, set *s)
{
    u8 ret = 0;

    if (INRANGE(bitno)) {
        int idx = IDXOF(bitno);
        u8 mask = MSKOF(bitno);

        // get old bit value
        ret = s->array[idx] & mask;

        if (ret) {
            // clear the bit
            s->array[idx] &= ~mask;

            // reduce the active count
            s->size--;
        }
    }

    return ret;
}

CodePudding user response：

To remove an element from the set, you want to clear the bit corresponding to that element.

void set_remove(const int value, set *const s)
{
    if (value >= set->capacity * 8) {
        // too big for the set, so not present
        return; }
    // clear the bit
    int byte_no = value / 8;
    int bit = 7 - value % 8;
    if (s->array[byte_no] & (1 << bit)) {
        s->array[byte_no] &= ~(1 << bit);
        s->size--;
    }
}

Note that this is assuming capacity is in bytes (what you set it to in your set_empty function that creates a set) rather than bits (which you use in other places). You should make it consistent.