C: Implementing a Queue

[alexfort93]

Hey all, need some help for my Systems Programming course. Trying to implement a queue...

struct queue {
	void** head; // Pointer to top element in queue
	void** tail; // Pointer to next open spot in queue
	int max_cells; // Number of space in queue
	int cells_used; // Number of cells used in queue
	void* top; // Pointer to top of the queue
	void* bottom; // Pointer to bottom of the queue
};

So, I need to account for wrap-around. My idea was to store the address of the top and bottom blocks of memory, to use and compare. i.e. if the tail pointer was pointing to the same place as the bottom pointer, set it equal to the top pointer.

Just having trouble how to initally set the bottom pointer when I create_queue:

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

	// 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 the head
	new_queue->top = new_queue->head; // Set top equal to the head
	new_queue->bottom = new_queue->head + max_cells; // Set to bottom of the allocated space

	return new_queue;
}

This is what I came up with, but not sure if it will work the way I want it to... Anyone have any input? Thanks.

 

[Spun Ducky]

So first off I am assuming this is a circular queue with an underlying data struct of a linked list.

State 1: Empty Queue/Full Queue

If the queue is empty and it is circular in this state the head and tail point to the same element which should be a NULL pointer. The same dilemma comes in when the queue is completely full so the solution to both these scenarios would be to either keep a node count variable or use a NULL node to signify the end of the structure.

State 2: One Element:

This will vary slightly on how you handle state one but simply put TAIL = Head.

State 3: K <= n-1 : K = Current Number Of Nodes, n = max size

This is the easiest state to deal with and you seem to understand this one.

 

[alexfort93]

So first off I am assuming this is a circular queue with an underlying data struct of a linked list.

State 1: Empty Queue/Full Queue

If the queue is empty and it is circular in this state the head and tail point to the same element which should be a NULL pointer. The same dilemma comes in when the queue is completely full so the solution to both these scenarios would be to either keep a node count variable or use a NULL node to signify the end of the structure.

Right, that is how it initializes up top. Essentially, if it gets to that point after enqueueing then dequeueing, they will both end up pointing to the same block of memory.
If the queue is full, I am going to do a simply check to compare the count to the max cells and return -1 to indicate an overflow, and do nothing

State 2: One Element:

This will vary slightly on how you handle state one but simply put TAIL = Head.

Not sure what you mean by this state, just adding one element?

State 3: K <= n-1 : K = Current Number Of Nodes, n = max size

This is the easiest state to deal with and you seem to understand this one.

My only issue is dealing with the wrap-around portion of code. Like I said, I figured getting the address for the top and bottom blocks of memory to compare would be a good way to do it, I just don't know how to get the addresses with the above code I have.

 

[alexfort93]

Well, I did this:

struct queue {
	void** head; // Pointer to top element in queue
	void** tail; // Pointer to next open spot in queue
	int max_cells; // Number of space in queue
	int cells_used; // Number of cells used in queue
	void** top; // Pointer to top of the queue
	void** bottom; // Pointer to bottom of the queue
};

Changed top and bottom to double pointers. Then kept the same structure in create_queue.

printf("%p", new_queue->head, top, and tail) all gave the same address, and ->bottom gave an address in memory 8 * 5 bytes away. So I think that is all set?

 

[Blazestorm]

I'm thinking you could get away with a few less variables, maybe 4 instead of 6. I was thinking 3 but you need a separate variable for the "head"... but you can calculate tail and bottom from the other information. That is assuming this is a contiguous array, which I'd think it should be. I don't know, haven't implemented a queue yet.

  //given variables
  void* top;
  void* head;
  int max_cells;
  int used_cells;
  
  //calculated variables
  void* bottom = top + max_cells;
  void* tail   = top + ( head - top + cells_used ) % max_cells;

( head - top ) gives you the distance from the start, which gives you a nice starting point (if head and top are equal, then you get 0). Then you add on how many cells are used, and mod the result by the max_cells, this will wrap you back around inside your array. Then you add the original start of your array to get you into valid memory.

Then the question is, is it worth recalculating every time you need it, or just using the extra 8-16 bytes (64bit == 8 byte pointers) for storing them. You'll still need calculations to update some of them...

Unless I'm missing something completely .

 

[alexfort93]

Hmm, that is the question. Do I want to recalculate each time I run functions like enqueue() or dequeue()?

I think the four variables I definitely need are

void** head;
void** tail;
int max_cells;
int cells_used;

I don't think I can get away without those four, for sure. I just don't how I would calculate the top and bottom of the queue give those four though. That's why I'm thinking leave them in as an extra 2 variables.

 

[mikeblas]

No need for a linked list, since you've allocated an array of pointers to the elements in the queue.