Trying to remove a value from a set which is constructed using bitvector

Question

Im trying to remove value from a set but can't get it to work this is the struct

struct set {
int capacity;
int size;
char *array;
};

This is how i insert the values in to the set

void set_insert(const int value, set *s)
{
  if (!set_member_of(value, s))
  {
    int bit_in_array = value; // To make the code easier to read

    // 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++;
}

}

This is how i've tried to remove the values. I don't know why but it completely ruins the set and assigns different values to the entire array

void set_remove(const int value, set *const s)
{
   int byte_no = value / 8;

   if(set_member_of(value, s))
   {
      s->array[byte_no] = 0;
      s->size--;
   }
}

Answer 1

You didn't post set_member_of, so I had to synthesize it.

The main issue with set_remove is that it is zeroing out all bits in the given byte. You want to and against the complement of the bit mask. So, change this:

s->array[byte_no] = 0;

Into:

s->array[byte_no] &= ~mask;

When I do bit masks, I like to use macros instead of shifts/divides/etc in multiple places.

In set_insert, I think it's easier to make capacity be number of bytes rather than number of bits.

Although char for the array type works, using unsigned char is probably better.

Note that as you define set, under C, it is not a type.

Anyway, here is the refactored code. I've compiled it but not tested it:

#include <stdlib.h>

typedef unsigned char atom;

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

#define INDEX(_bitno)       ((_bitno) / 8)
#define MASK(_bitno)        (7 - ((_bitno) % 8))

int
set_member_of(int bitno,set *s)
{
    int byte_no = INDEX(bitno);
    atom mask = MASK(bitno);
    atom match = 0;

    if (byte_no < s->capacity)
        match = s->array[byte_no] & mask;

    return match;
}

void
set_insert(int bitno, set *s)
{

    if (! set_member_of(bitno, s)) {
        int newcap = INDEX(bitno + 8);

        // Increase the capacity if necessary
        if (newcap > s->capacity) {
            s->array = realloc(s->array, newcap);

            // zero out any new cells
            for (int i = s->capacity;  i < newcap;  ++i)
                s->array[i] = 0;

            s->capacity = newcap;
        }

        atom mask = MASK(bitno);
        int byte_no = INDEX(bitno);
        s->array[byte_no] |= mask;
        s->size++;
    }

}

void
set_remove(int bitno, set *s)
{

    if (set_member_of(bitno, s)) {
        int byte_no = INDEX(bitno);
        atom mask = MASK(bitno);

        s->array[byte_no] &= ~mask;
        s->size--;
    }
}