I want to implement a queue in C. In particular i want the queue to be dynamically allocated or fixed size based on user preference.
My issue is that I don't want to shift all values every time something is popped, so i essentially keep track of a cursor indicating the start of the queue in an array and length. When user sets the queue to be dynamically allocated, it adds some complexity to that wrapping around and the code becomes messy.
I was curios if I could somehow free just the first element of dynamically allocated memory and whether it would have weird implications for my code.
So I wonder if anyone could tell me whether:
- It is possible to free only a part of memory allocated with malloc? (I considered using reallocarray on the ptr 1 and ptr and then calling free on original pointer, but that seems like ub cuz there is probably some info about size of memory allocated stored internally by os)
- If i keep on reallocating in this fashion, would my array by the virtue of being contiguous "walk" out of the process memory? (I hope not since i assume OS does some smart mapping and array is not actually contiguous down there, but better to know that for sure)
Because even i find my questions quite confusingly formulated attached are the diagrams illustrating two points above:
-
-
CodePudding user response：
Yes, it is possible to free only a part of the memory allocated with malloc. You can use the realloc() function to resize the allocated memory and then call free() on the original pointer.
No, your array will not "walk" out of the process memory. The OS does smart memory mapping that prevents this from happening.
#include<stdio.h>
#include<stdlib.h>
// A structure to represent a queue
struct Queue {
int front, rear, size;
unsigned capacity;
int* array; };
// function to create a queue of given capacity.
// It initializes size of queue as 0
struct Queue* createQueue(unsigned capacity) {
struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
queue->capacity = capacity; queue->front = queue->size = 0;
queue->rear = capacity - 1; // This is important, see the enqueue
queue->array = (int*) malloc(queue->capacity * sizeof(int));
return queue;
}
// Queue is full when size becomes equal to the capacity
int isFull(struct Queue* queue) {
return (queue->size == queue->capacity);
}
// Queue is empty when size is 0
int isEmpty(struct Queue* queue) {
return (queue->size == 0);
}
// Function to add an item to the queue.
// It changes rear and size
void enqueue(struct Queue* queue, int item) {
if (isFull(queue)) return; queue->rear = (queue->rear % queue->capacity;
queue->array[queue->rear] = item; queue->size = queue->size 1;
printf("%d enqueued to queue\n", item);
}
// Function to remove an item from queue.
// It changes front and size
int dequeue(struct Queue* queue) {
if (isEmpty(queue)) return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front 1)%queue->capacity;
queue->size = queue->size - 1;
return item;
}
// Function to get front of queue
int front(struct Queue* queue) {
if (isEmpty(queue)) return INT_MIN;
return queue->array[queue->front];
}
// Function to get rear of queue
int rear(struct Queue* queue) {
if (isEmpty(queue)) return INT_MIN;
return queue->array[queue->rear];
}
// Driver program to test above functions./
int main() {
struct Queue* queue = createQueue(1000);
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);
printf("%d dequeued from queue\n\n;, dequeue(queue));
printf("Front item is %d\n;, front(queue));
printf("Rear item is %d\n", rear(queue));
return 0;
}
CodePudding user response：
memmove can be used to shift the elements.
This keeps the allocated memory until the program terminates.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INC 50
typedef struct queue_s queue;
struct queue_s {
size_t size;
size_t used;
int *arr;
};
queue pop ( queue q) {
if ( q.used) {
q.used -= 1;
memmove ( &q.arr[0], &q.arr[1], sizeof *q.arr * q.used);
}
else {
printf ( "queue is empty\n");
}
return q;
}
queue push ( int data, queue q) {
int *temp = NULL;
if ( q.used >= q.size) {
if ( NULL == ( temp = realloc ( q.arr, sizeof *temp * (q.size INC)))) {
fprintf ( stderr, "problem realloc q.arr");
return q;
}
q.arr = temp;
q.size = INC;
}
q.arr[q.used] = data;
q.used = 1;
return q;
}
void show ( queue q) {
if ( q.used) {
for ( size_t each = 0; each < q.used; each) {
if ( each) {
printf ( "->%d", q.arr[each]);
}
else {
printf ( "%d", q.arr[each]);
}
}
}
else {
printf ( "nothing to show\n");
}
printf ( "\n");
}
int main ( void) {
queue qu = { 0, 0, NULL};
qu = push ( 0, qu);
qu = push ( 1, qu);
qu = push ( 2, qu);
qu = push ( 3, qu);
qu = push ( 4, qu);
qu = push ( 5, qu);
qu = push ( 6, qu);
qu = push ( 7, qu);
qu = push ( 8, qu);
qu = push ( 9, qu);
for ( int each = 0; each < 100000; each) {
qu = push ( each, qu);
}
printf ( "pushed\n");
for ( int each = 0; each < 100000; each) {
qu = pop ( qu);
}
printf ( "popped\n");
show ( qu);
qu = pop ( qu);
show ( qu);
qu = push ( 10, qu);
show ( qu);
qu = pop ( qu);
qu = pop ( qu);
qu = pop ( qu);
show ( qu);
qu = push ( 11, qu);
qu = push ( 12, qu);
show ( qu);
qu = pop ( qu);
qu = pop ( qu);
qu = pop ( qu);
qu = pop ( qu);
qu = pop ( qu);
qu = pop ( qu);
show ( qu);
qu = pop ( qu);
qu = pop ( qu);
qu = pop ( qu);
qu = pop ( qu);
qu = pop ( qu);
qu = pop ( qu);
show ( qu);
free ( qu.arr);
return 0;
}