I'm trying to write a queue that will store strings. Using GDB I can tell that I make a memory allocation error in the function resizeQueue.
Here's the exact message:
Program received signal SIGTRAP, Trace/breakpoint trap.
#13 0x00007ffd7348d235 in ucrtbase!_realloc_base () from C:\WINDOWS\System32\ucrtbase.dll
#14 0x00007ff7727c175b in resizeQueue (queue=0x5ffeb0) at queue.c:45
I would appreciate if someone could look over my code and see if they see what's wrong. I attached a complete example below.
To clarify one point, I'm aware that the tail is 5 when there is no array index 5, that's intentional because it's that fact that triggers the condition to tell my program to resize. It's not dereferenced when it's out-of-bounds. However, I could be wrong in my logic... When stepping through it seemed like it failed allocating space for the 10 element (9 index).
Relevant queue code
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct Queue
{
int tail; // index of the last element
int head; // index of the first element
int capacity;
char** head_pt;
} Queue;
void allocQueue(Queue* queue)
{
assert(queue->capacity != 0);
queue->head_pt = (char**)malloc(sizeof(char*) * queue->capacity);
for (int i = 0; i < queue->capacity; i++)
{
queue->head_pt[i] = (char*)malloc(sizeof(char) * QUEUE_ELEM_SIZE);
if (!queue->head_pt[i]) {
printf("Queue Error: failed reallocating memory for a string");
exit(1);
}
}
}
void resizeQueue(Queue* queue)
{
printf("RESIZE\n");
queue->capacity *= 2;
queue->head_pt = (char**) realloc(queue->head_pt, queue->capacity);
if (!queue->head_pt) {
printf("Queue Error: failed reallocating memory for head");
exit(1);
}
for(int i = queue->tail; i < queue->capacity; i++) {
queue->head_pt[i] = (char*)malloc(sizeof(char) * QUEUE_ELEM_SIZE);
if (!queue->head_pt[i]) {
printf("Queue Error: failed reallocating memory for a string");
exit(1);
}
}
}
void enQueue(Queue* queue, char* data)
{
if (queue->head == -1 && queue->tail == -1) {
queue->head = 0;
queue->tail = 0;
}
if(queue->tail == queue->capacity)
{
resizeQueue(queue);
}
strcpy(queue->head_pt[queue->tail], data);
queue->tail++;
}
This is the test file
int main(void) {
printf("------test Queue-----\n");
Queue queue = {
.capacity = 5,
.tail = -1,
.head = -1,
};
allocQueue(&queue);
assert(queue.head_pt != NULL);
printf("PASSED: allocating memory\n");
char string [] = "a,b,c,d,e,f,g,h,i,j,k,";
for (char* data = strtok(string, ","); data != NULL; data = strtok(NULL, ",") ) {
enQueue(&queue, data);
// printQueue(&queue);
}
return 0;
}
Thanks to anyone who actually read all of that :)
First of all, in C language, you should never cast the result of malloc (please read Should I cast the result of malloc (in C)? to know why).
Next, resizeQueue
blindly assumes that it can only be called when tail == capacity
. That's correct in you tiny example, but it should at least deserve a comment...
But the real cause of your error is the way you call realloc. Just look at the way you call first malloc
, then realloc
(I have removed the ugly cast):
queue->head_pt = malloc(sizeof(char*) * queue->capacity);
queue->head_pt = realloc(queue->head_pt, queue->capacity);
When calling realloc
you only allocate queue->capacity
bytes when you need pointers to integers. It should be
queue->head_pt = realloc(queue->head_pt, sizeof(char*) * queue->capacity);