C - Queue's Segmentation Fault when wrapping around with dequeue

Question

Alright, so I am suppose to create 3 functions with Queue's. They are create_queue(), enqueue(), and dequeue(). I created all three and am testing them out in main that if it's full it should throw error and whether head or tail hit the end it should wrap around. In my case I got the enqueue() to wrap around but not the dequeue(). I'm stuck here trying to figure out where I am making the mistake. If anyone could spot it and let me know how to fix it, I would much appreciate it! ^.^

queuetest.c

#include <stdlib.h>
#include <stdio.h>
#include "queue.h"
#include <errno.h>

typedef struct {
  int x;
  double y;
} Foo; // Just some arbitrary struct


int main() {

  const int max_entries = 4; // size of stack
  Foo* new_foo1;
  Foo* new_foo2;
  Foo* new_foo3;
  Foo* new_foo4;
  Foo* new_foo5;
  Foo* returned_foo;

  // First, create a stack
  Queue *new_queue = create_queue(max_entries);

  // Allocate a Foo and push it onto the queue.
  new_foo1 = (Foo *) malloc(sizeof(Foo));
  new_foo1->x = 100;
  new_foo1->y = 1.11;
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo1->x, new_foo1->y);
  enqueue(new_queue, (void *) new_foo1);

  // Allocate another Foo and push it onto the queue.
  new_foo2 = (Foo *) malloc(sizeof(Foo));
  new_foo2->x = 200;
  new_foo2->y = 2.22;
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo2->x, new_foo2->y);
  enqueue(new_queue, (void *) new_foo2);

  // Allocate another Foo and push it onto the queue.
  new_foo3 = (Foo *) malloc(sizeof(Foo));
  new_foo3->x = 300;
  new_foo3->y = 3.33;
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo3->x, new_foo3->y);
  enqueue(new_queue, (void *) new_foo3);

  // Allocate another Foo and push it onto the queue.
  new_foo4 = (Foo *) malloc(sizeof(Foo));
  new_foo4->x = 400;
  new_foo4->y = 4.44;
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo4->x, new_foo4->y);
  enqueue(new_queue, (void *) new_foo4);

 // Allocate another Foo and push it onto the queue.
  new_foo5 = (Foo *) malloc(sizeof(Foo));
  new_foo5->x = 500;
  new_foo5->y = 5.55;
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo5->x, new_foo5->y);
  enqueue(new_queue, (void *) new_foo5);

  /////////////////////////////////////////////////////////////////

  // Dequeue two  Foos and print them.
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);

  /////////////////////////////////////////////////////////////////

  // Add 3 Foos
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo5->x, new_foo5->y);
  enqueue(new_queue, (void *) new_foo5);
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo1->x, new_foo1->y);
  enqueue(new_queue, (void *) new_foo1);
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo2->x, new_foo2->y);
  enqueue(new_queue, (void *) new_foo2);

  /////////////////////////////////////////////////////////////////

  // Dequeue 5 Foos and print them.
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);

}

queue.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "queue.h"

/** Create a queue by allocating a Queue structure, initializing it,
 *  and allocating memory to hold the queue entries.
 * @param max_cells Maximum entries in the queue
 * @return Pointer to newly-allocated Queue structure, NULL if error.
 */
Queue *create_queue(int max_cells) {
  Queue *new_queue; // Holds pointer to the newly-allocated queue structure.
  new_queue = (Queue *) malloc(sizeof(Queue));

  if (new_queue == NULL) return NULL; // Error--unable to allocate.

  // Fill in the struct
  new_queue->max_cells = max_cells;
  new_queue->cells_used = 0; // Empty to start
  new_queue->ePos = 1; //Starts at first position
  new_queue->dPos = 1; //Starts at first position

  // Now allocate space for the queue entries.
  new_queue->head = (void **) calloc(sizeof(void *), max_cells);
  if (new_queue->head == NULL) {
    free(new_queue); // Unable to allocate queue entries, so free struct.
    return NULL;
  }
  new_queue->tail = new_queue->head; // Start at head

  return new_queue;
}

/** Deletes a queue, including the structure and the memory
 * for holding the queue entries, but not the entries themselves.
 * @param which_queue Pointer to Queue structure.
 */
void delete_queue(Queue *which_queue) {
  free(which_queue->head); // Free memory block with queue entries.
  free(which_queue); // Then free the struct.
}

/** Pushes a pointer onto a Queue.
 * @param which_queue Pointer to queue you want to push onto.
 * @param ptr Pointer to be pushed.
 * @return 0 if successful, -1 if not.
 */
int enqueue(Queue *which_queue, void *ptr) {

 // Check if queue is already full
  if ((which_queue->cells_used) >= (which_queue->max_cells)) {
    which_queue->cells_used = which_queue->max_cells;
    printf("Error: Queue overflow\n");
    return -1;  // Queue overflow.
  }

  // Check if tail is at the end of the Queue
  if ((which_queue->ePos) == (which_queue->max_cells)) {

    //Sets tail to the beginning of queue
    (which_queue->tail) = (which_queue->tail) - (which_queue->max_cells);
    //Sets position back to beginning
    (which_queue->ePos) = 1;
  }

  // Push onto queue.
  *(which_queue->tail) = ptr;  // Store the pointer on the stack
  (which_queue->tail)++;       // Point to next free cell
  (which_queue->cells_used)++;
  (which_queue->ePos)++;
  return 0;  // Success
}

/** Removes head of queue, and returns it.
 * @param which_queue Pointer to Queue you want to dequeue from.
 * @return Head entry of the queue, NULL if queue is empty.
 */
void* dequeue(Queue *which_queue) {

  // Check if queue is empty
  if ((which_queue->cells_used) <= 0) {
    which_queue->cells_used = 0;
    printf("Error: Queue underflow\n");
    return NULL;  // Queue empty
  }

  // Check if head is at the end of the Queue
  if ((which_queue->dPos) == (which_queue->max_cells)) {

    //Sets head to the beginning of queue
    (which_queue->head) = (which_queue->head) - 3;
    //Sets position back to beginning
    (which_queue->dPos) = 1;
    (which_queue->cells_used)--;
    return (*((which_queue->head) + 3));
  }

  // Remove head from queue.
  (which_queue->cells_used)--;
  (which_queue->head)++;
  (which_queue->dPos)++;
  return (*((which_queue->head) - 1));
}

Note: I know I used - 3 and + 3 instead of max_cells - 1 etc. I was just trying to see if that was an issue but it wasn't. Another note is that if i substitue -3 or +3 with 1 2 3 it still gives me a seg error.

queue.h

/** Struct to define a queue; each entry can hold a pointer to anything.
 */
struct queue {
  void **head; // Pointer to head of queue
  void **tail;  // Pointer to next free cell (tail);
  int max_cells; // Maximum number of entries in the queue
  int cells_used; // Currently used number of cells
  int ePos; //Position of the enqueue
  int dPos; //Position of the dequeue
};

typedef struct queue Queue;

// Function prototypes

Queue *create_queue(int max_cells);

void delete_queue(Queue *which_queue);

int enqueue(Queue *which_queue, void *ptr);

void* dequeue(Queue *which_queue);

So the seg fault occurs on the print line after the second dequeue() has been called. This means that returned_foo has a bad value which is caused by the dequeue function not running the wrap around properly in the if statement section (at least I think that's the error >.>). Any help would be helpful! Thanks in advance.

Answer 1

Your implementation of enqueue() never fills the last element in the queue.

create_queue();  // ePos = 1, queue: x x x x
enqueue(A);      // ePos = 2, queue: A x x x
enqueue(B);      // ePos = 3, queue: A B x x
enqueue(C);      // ePos = 4, queue: A B C x
enqueue(D);      // This already wraps because ePos == max_cells!
                 // ePos = 2, queue: D B C x

When dequeue() gets to the last element of the queue, it reads NULL (this is what the last element contains, because calloc fills the memory block with zeroes), and the program crashes.