I am trying to implement a queue which has variable size of array but am having problem that it is giving me realloc: invalid next size; the capacity initialized to 1 the it could only reach capacity=8 then if I want to insert more elements it gives me the error

Here is my implementation:

typedef int element;

typedef struct cell {
    element *array;
    int capacity;
    int front, length;
} queue;

queue CreateQueue() {
    queue q;
    q.capacity = 1; 
    q.array=(element *)malloc(sizeof(element) * q.capacity);
    q.front = 0;
    q.length = 0;
    return q;
}

int isFullQueue(queue q) {
    return (q.length == q.capacity);
}

int isEmptyQueue(queue q) {
    return ((q.length) == 0);
}

int Enqueue(queue *q, element e) {
    if (isFullQueue(*q)) {
        q->capacity = q->capacity * 2;
        q->array = (int *)realloc(q->array, q->capacity);
        if (!(q->array))
            return 0;
        for (int i = 0; i < q->front; i  ) {
            *(q->array   q->length   i) = *(q->array   i);
        }
     }
     q->array[(q->front   q->length) % q->capacity] = e;
     q->length = q->length   1;
     return 1;
}

CodePudding user response：

At least this problem:

Wrong size calculation @Eugene Sh.

// q->array=(int*)realloc(q->array,q->capacity);
//                               v----------------v Scale by referenced object
q->array=      realloc(q->array, sizeof q->array[0] * q->capacity);
//       ^----^ Cast not needed. 

Notice that there is no need to code the type in a *alloc() line-of-code. Using the size of the object pointed to and avoiding a type improves correct initial coding, review and maintenance.

Better code would save the new pointer to a temporary and then test. With OP's code, on re-allocation failure the original pointer value is lost.

void *t = realloc(q->array, sizeof q->array[0] * q->capacity);
if (t == NULL) {
  return 0;
}
q->array = t;

CodePudding user response：

There are 2 problems in the Enqueue function:

• the reallocation size in incorrect: you must give a number of bytes, hence write:

   q->array = realloc(q->array, sizeof(*q->array) * q->capacity);
  

• you should not overwrite q->array directly, as coded you have a memory leak in case realloc fails.

The other functions should also take a pointer to a queue instead of a structure copy.

Here is a modified version:

#include <stdlib.h>

typedef int element;

typedef struct cell {
    element *array;
    int capacity;
    int front, length;
} queue;

queue CreateQueue() {
    queue q;
    q.capacity = 1; 
    q.array = malloc(sizeof(*q.array) * q.capacity);
    q.front = 0;
    q.length = 0;
    return q;
}

int isFullQueue(const queue *q) {
    return q->length == q->capacity;
}

int isEmptyQueue(const queue *q) {
    return q->length == 0;
}

int Enqueue(queue *q, element e) {
    if (isFullQueue(q)) {
        element *array = realloc(q->array, sizeof(*q->array) * q->capacity * 2);
        if (array == NULL)
            return 0;
        q->array = array;
        q->capacity = q->capacity * 2;
        for (int i = 0; i < q->front; i  ) {
            q->array[q->length   i] = q->array[i];
        }
     }
     q->array[(q->front   q->length) % q->capacity] = e;
     q->length  = 1;
     return 1;
}