cdata-structuresqueuedynamic-memory-allocationdynamic-arrays

dynamically resizing array in queue implementation


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 :)


Solution

  • 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);