A wait-free queue

We will now explain of how one actually can design non-blocking programs for larger operations, as example for ordinary data structures. In the code below the program code is shown for a "wait-free" queue.

#define MAX_QUEUE_SIZE 1000

void *buffer[MAX_QUEUE_SIZE];
int volatile indexHead=0;
int volatile indexTail=0;
 
int Enqueue(void *item) {
  int nextTail=(indexTail+1)%MAX_QUEUE_SIZE;
  if(nextTail==indexHead)
    return 0;
  buffer[indexTail]=item;
  indexTail=nextTail;
  return 1;
}
 
void *Dequeue() {
  void *item;
  if(indexHead==indexTail)
    return NULL;
  item=buffer[indexHead];
  indexHead=(indexHead+1)%MAX_QUEUE_SIZE;
  return item;
}

It is built upon a cyclic buffer for saving the elements in the queue, where the index "indexTail" indicates the next free position and "indexHead" indicates the latest not collected position. In order to make it wait-free, the variable "indexTail" is only updated by the "Enqueue" function, and the variable "indexHead" is only updated by the "Dequeue" function. Observe though that this queue implementation only works for up to two threads, one thread that are performing "Enqueue" and another thread that is performing "Dequeue". If we want to permit more threads, it becomes at once much more complicated.