dynamically resizing array in queue implementation [closed]

Question

Closed. This question is not reproducible or was caused by typos. It is not currently accepting answers.

This question was caused by a typo or a problem that can no longer be reproduced. While similar questions may be on-topic here, this one was resolved in a way less likely to help future readers.

Closed 3 months ago.

Improve this question

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

The realloc allocation only allocates queue->capacity bytes where it should be sizeof(char *) * queue->capacity. — nielsen
– nielsen, Commented Jul 16 at 6:41
Btw., there are several needed improvements. What is the plan for the deQueue() function? Either you have to shift the entire array or make it a circular buffer. In the first case, there is no point in having a head pointer. In the second case, which I would prefer, the existing functions must be revised. — nielsen
– nielsen, Commented Jul 16 at 6:49
...and if circular, the comparisons need to be revised. Another obvious weakness is the fixed length of each string's array, into which you dangerously strcpy the data. — Weather Vane
– Weather Vane, Commented Jul 16 at 6:52

Serge Ballesta · Accepted Answer · 2025-07-16 06:55:37Z

0

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

answered Jul 16 at 6:55

Serge Ballesta

150k13 gold badges137 silver badges267 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ctx Jul 23 at 13:35

Casting the result of malloc() has advantages and drawbacks, saying that it should not be done is wrong.

Serge Ballesta Jul 24 at 12:48

Little more than my opinion, but beginners tend to cast the result of malloc simply because it would be required in C++. The reason why I advise not to do so - in addition to the reasons explained in the linked post. There may be good reasons to do the cast, but consistently doing so is a poor habit in C language.

Collectives™ on Stack Overflow

dynamically resizing array in queue implementation [closed]

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related