parallel_primes.c

/* Because bitset comprises 3 operations:
 *  1. Read array[bitset_index] into 'temp'
 *  2. Set bit (bit_index) on 'temp'
 *  3. Write 'temp' into array[bitset_index]
 * A thread running bitset can be preempted before it can write 'temp', during
 * which time another thread has written 'array[bitset_index]', and 'temp' does
 * not include the changes made by that thread. Thus, the preempted thread
 * overwrites the changes made by the other thread when it executes step 3.
 *
 * To avoid this, I use the GCC extension '__sync_bool_compare_and_swap' which
 * does an atomic compare and swap with 'oldval' (the initial value of
 * array[bitset_index]) and 'newval' ('oldval' with the relevant bit set on it)
 * and returns true if the operation succeeded and false if it doesn't.
 *
 * Thus, I just use it in a do while loop and keep trying the operation until
 * it succeeds.
 */
void bitset(unsigned char * array, int index){
	int newval;
	int oldval;
	int bitset_index = index / BITS_PER_INDEX;
	int bit_index = index % BITS_PER_INDEX;
	do{
		oldval = array[bitset_index];
		newval = oldval | (1 << (bit_index));
	}while(!__sync_bool_compare_and_swap(&array[bitset_index], oldval, newval));
}