I'm trying to write a program which first dynamically initialises a queue array for 100 int elements. Whenever the queue is full and another element is supposed to be queued, the original array is supposed to double it's size so new elements can be inserted. In case elements are dequeued, and the amount of elements the queue consists of falls below half of its actual size, the queue size is supposed to be cut in half. However, its size should never fall below 10.
I'm trying to expand and shrink the array with realloc, however I'm having some problems understanding its mechanics, especially when returning a new pointer. Here is my program (with some redundant printf for debugging reasons):
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <iso646.h>
void enqueue(int arr[], int* lastElementIdx, int *length, int element);
int dequeue (int arr[], int* lastElementIdx, int *length);
void printQueue(const int arr[], int lastElementIdx);
int expandArray(int *arr, int length);
int shrinkArray(int *arr, int length, bool min);
void test1(int *arr, int* lastElementIdx, int *length)
{
int* temp = arr;
printf("\nprintQueue #1:\n"); //print queue, should be empty
printQueue(temp, *lastElementIdx);
for(int i = 1; i <= 100; i++) //insert elemnts to queue
enqueue(temp, lastElementIdx, length, i);
printf("\nprintQueue #2:\n"); //print queue
printQueue(temp,*lastElementIdx);
printf("\nAusgabe von dequeue:\n"); // dequeue array
while(*lastElementIdx > *length/4)
printf("\naddress: %p\tElement: %d\n", temp, dequeue(temp, lastElementIdx, length));
free(temp);
}
void test2(int *arr, int* lastElementIdx, int *length)
{
int *temp = arr;
printf("\n************\nEnqueue beyond queue[N-1]:\n");
puts("Queue aufbauen...");
for(int i = 1; i <= 150; i++)
enqueue(temp, lastElementIdx, length, i);
printf("\nprintQueue:\n");
printQueue(temp,*lastElementIdx);
printf("\nDequeue:\n");
while(*lastElementIdx > *length/4)
printf("\naddress: %p\tElement: %d\n", temp, dequeue(temp, lastElementIdx, length));
free(temp);
}
int main(int argc, char const *argv[])
{
int startingPoint = -1, *lastElementIdx = &startingPoint, N = 100, *length = &N;
int *queue = (int*) calloc(*length, sizeof(*queue));
test2(queue, lastElementIdx, length);
queue = (int*) calloc(*length, sizeof(*queue));
test1(queue, lastElementIdx, length);
return 0;
}
int expandArray(int *arr, int length)
{
/*function to double the array size*/
length *= 2;
int *temp;
temp = (int*) realloc(arr, sizeof(*arr)*length);
if (!temp) {
free(temp);
}
else{
if (arr != temp) {
free(arr);
arr = temp;
}
else{
arr = temp;
}
}
printf("EXPAND ARRAY: %p\n", arr);
return length;
}
int shrinkArray(int *arr, int length, bool min)
{
/*function that cuts array in half*/
int *temp;
if (min){
length = 10;
}
else{
length /= 2;
}
temp = (int*) realloc(arr,sizeof(*arr)*length);
if (!temp) {
free(temp);
}
else{
arr = temp;
}
printf("SHRINK ARRAY: %p\n",arr);
return length;
}
void enqueue(int arr[], int* lastElementIdx, int *length, int element)
{
if ( *lastElementIdx < *length - 1){ //checks if there's space for another element
arr[*lastElementIdx + 1] = element; //if yes, insert element after lastElementIdx
(*lastElementIdx)++; //increment lastElementIdx
}
else{
*length = expandArray(arr, *length); //if not, expand array
}
}
int dequeue (int arr[], int* lastElementIdx, int *length)
{
printf("address before:\t%p\tLast Element: %d\tLength: %d\n", arr,*lastElementIdx, *length);
int *p = arr;
if(*lastElementIdx > -1){ //Checks if there is an element in the queue
if (*lastElementIdx + 2 < *length/2 and *lastElementIdx + 2 > 10) {
bool min = false;
*length = shrinkArray(arr, *length, min);
}
else if (*lastElementIdx + 2 < 10){
bool min = true;
*length = shrinkArray(arr, *length, min);
}
(*lastElementIdx)--; //shift position of last element
printf("address afterw:\t%p\tLast Element: %d\tLength: %d\n", arr, *lastElementIdx,*length);
return *(p + *lastElementIdx + 1);
}
return 0;
}
void printQueue(const int arr[], int lastElementIdx)
{
while( lastElementIdx > -1){
printf("%d\t", *(arr + lastElementIdx));
lastElementIdx--;
}
}
However I keep getting 2 errors. The first one is here:
if (arr != temp) {
free(arr);
arr = temp;
}
saying error for object 0x1001013b0: pointer being freed was not allocated.
I implemented this line in the first place, because after a while I figured out the pointer address of the reallocated memory changes sometimes. If I delete that if statement I still keep getting an error, this time being in this line:
temp = (int*) realloc(arr, sizeof(*arr)*length);
the message being: malloc: *** error for object 0x100500000: pointer being realloc'd was not allocated
I should also add, that in both cases, sometimes the program is executed without any problems. In the latter case, the error is alternating between the realloc line in expandArray and the one in shrinkArray.
I don't really understand why this happens, and how to handle the situation when realloc returns a new pointer address. Inspired by similar posts, I tried different approaches, like passing int **arr instead of int *arr to both expandArray and shrinkArray. I also tried different methods to free the original array after realloc like
temp = (int*) realloc(arr,sizeof(*arr)*length);
if (!temp) {
free(temp);
}
else{
free(arr);
arr = temp;
}
always with the same error message. And I hoped freeing the memory after each test function and allocating new memory in the main function for the queue array before calling the second test functions would solve the problem, when in fact it didn't.
I really appreciate any kind of help on this.
<iso646.h>header. Eyeballing the code, I spotted one instance ofandin place of&&. I wonder if that's really an advantage. It isn't technically wrong; it is unusual, though. – Jessrealloc()may returnNULLin cases other than out-of-memory as inrealloc(arr,sizeof(*arr)*length);, iflength == 0. So rather thanif (!temp) {free(temp);useif (!temp && length != 0) {free(temp);Better yet, detectif (length <= 0)beforehand and simply callfree(arr). 2) Better to usesize_t length. – Impunity