Freeing memory in C: Queue

Question

void insert_queue (queue *this, queue_item_t item) {

   //Inserts a new item at the end of queue.
   queue_node *temp = malloc(sizeof (struct queue_node));
   temp->item = item;

   if (isempty_queue(this)) this->front = temp; 
   else this->rear->link = temp;
   this->rear = temp;
   //free(temp);
}

queue_item_t remove_queue (queue *this) {
   assert (! isempty_queue (this));
   //This removes the first item from queue.
   queue_item_t temp = this->front->item;
   this->front = this->front->link;
   return temp;
}

I'm getting a seg fault error when I try to free 'temp'. I'm supposed to free a node after using it, right? So, how would I prevent memory leak in this situation? Any ideas? Thanks.

When I remove free(temp), everything works fine, but I'm getting memory leaks. I'm not sure where to put free if it doesn't belong in this function. I also added my remove function. Should free go in here?

EDIT EDIT: Thank you everyone, here is my updated code.

queue_item_t remove_queue (queue *this) {
   assert (! isempty_queue (this));

   queue_node *temp = this->front;
   queue_item_t rVal = temp->item;

   //Moves on to the next one.
   this->front = this->front->link;
   //Free the unlinked node.
   //free(temp->item); <<<<---- This causes program to fail.
   free(temp);
   return rVal;
}

Memory leaks are still occurring.

Answer 1

Well, if you're creating and inserting a new queue, why would you want to delete it? Remember, when you use malloc() you're reserving some data independent of the block you are in. Free() is what you use to destroy this memory created with malloc(). All locally scoped (NOT created with malloc) data/variables will automatically be destroyed at the end of they're respected blocks. Data created with malloc() will (in most cases) not.

void insert_queue (queue *this, queue_item_t item)
{
    //Inserts a new item at the end of queue.
    queue_node *temp = malloc(sizeof (struct queue_node));
    temp->item = item;

    if (isempty_queue(this))
        this->front = temp; 
    else
        this->rear->link = temp;
    this->rear = temp;
    //free(temp);    // remember tmp is still referring to
                               // the node, so you will be erasing the
                               // node you just put inside the queue.

}     // end of code block. Variable *temp will be
      // automatically freed from memory, but
      // its malloc'd data will not. This is good
      // because its data is being used inside our
      // queue, until it is removed with remove_queue().

Later on inside your remove function you could delete "temp" (its actually the memory allocated using malloc()) using free. Or you could use free(remove_queue(&myq)), and it will yield the exact same result because we are dealing with pointers.

Answer 2

First of all "this" is shadowning a keyword in c++. You should not use it in a c-context either if you ask me - just to avoid misunderstandings.

Second a queue is something where an item, request, person or something is queued at the end and earlier or later removed from the front when it is time (dequed). You seem to implement this as a linked list what is ok.

Next queue_item_t item is allocated on the stack here as copy from the original value, since I do not see that it is a pointer comming in the momory allocated for it will be deleted on the closing }.

I would not call a variable temp if it actually has meaning like newQueueNode. Meaningful application/class/variable/function names are one of the best ways to comment your code.

At last comment, the choosen return and pass by value without an ok parameter, or you will run into issues when you can not return a copy (see my example for size==0), and there is no way to tell the user of the function that something went wrong (queue is empty, in this case)

Here is my (quickly produced and tested) minimum solution for your problem:

#include <stdlib.h>
#include <stdio.h>

struct queue_item_t
{
    int exampleItemData;
};

struct queue_node
{
    struct queue_item_t *item;
    struct queue_node *next;
};

struct queue
{
    struct queue_node *firstItem;
    struct queue_node *lastItem;
    int size;
};


struct queue* createQueue()
{
    struct queue *queuePtr = (struct queue *)malloc(sizeof (struct queue));
    queuePtr->firstItem = NULL;
    queuePtr->lastItem = NULL;
    queuePtr->size = 0;
    return queuePtr;
}

void queue(struct queue* queueData, struct queue_item_t itemToQueue)
{
    // Create new node
    struct queue_node* newNode = (struct queue_node*)malloc(sizeof(struct queue_node));

    // Create new item
    newNode->item = (struct queue_item_t*)malloc(sizeof(struct queue_item_t));

    // Copy the item data from itemToQueue that will be deleted on the end of this function
    newNode->item->exampleItemData = itemToQueue.exampleItemData;

    // Insert the item into the queue
    if(0 == queueData->size)
    {
        queueData->firstItem = newNode;
        queueData->lastItem = newNode;
        newNode->next = newNode;
    }
    else
    {
        queueData->lastItem->next = newNode;
        queueData->lastItem = newNode;
    }

    queueData->size += 1;

    // ! itemToQueue will deleted here we must have a copy of the data in the queue }
}

struct queue_item_t dequeue(struct queue* queueData)
{
    struct queue_item_t item;

    if (1 > queueData->size)
    {
        // !!! Serious problem if this happens:
        // What will you return, an initialized queue_item_t?
        // You can not return a null pointer ...
        // Better you write ok to a boolean comming in ass parameter or something
    }
    else if(1 == queueData->size)
    {
        item.exampleItemData = queueData->firstItem->item->exampleItemData;

        free(queueData->firstItem->item);
        free(queueData->firstItem);
        queueData->firstItem = NULL;
        queueData->lastItem = NULL;
    }
    else if(2 == queueData->size)
    {
        item.exampleItemData = queueData->firstItem->item->exampleItemData;

        struct queue_node* dequeuedNode = queueData->firstItem;
        queueData->firstItem = dequeuedNode->next;
        queueData->lastItem = dequeuedNode->next;
        free(dequeuedNode->item);
        free(dequeuedNode);
    }
    else if (1 < queueData->size)
    {
        item.exampleItemData = queueData->firstItem->item->exampleItemData;

        struct queue_node* dequeuedNode = queueData->firstItem;
        queueData->firstItem = dequeuedNode->next;
        free(dequeuedNode->item);
        free(dequeuedNode);
    }

    queueData->size -= 1;

    return item;
}


int main() {
    struct queue* myQueue = createQueue();
    struct queue_item_t item;
    item.exampleItemData = 665;
    queue(myQueue, item);

    item.exampleItemData = 666;
    queue(myQueue, item);

    item.exampleItemData = 667;
    queue(myQueue, item);

    for(int i = myQueue->size; i > 0; --i)
    {
        struct queue_item_t dequeuedItem = dequeue(myQueue);
        printf("Dequed ITem data = %i\n",  dequeuedItem.exampleItemData);
    }

    // Now the next shows an undefined state if someone dequeues with size 0 or smaller:
    struct queue_item_t dequeuedItem = dequeue(myQueue);
    printf("Dequed ITem data = %i\n",  dequeuedItem.exampleItemData);

    // I recommend using a boolean like mentioned above

    return 0;
}

Answer 3

You are not done using the node when insert_queue finishes. The insert_queue routine uses temp to hold a pointer to the node, and insert_queue is done using temp when it returns, but the node itself is part of the linked list, so it is in use.

You finish using the node when remove_queue removes it from the list. remove_queue should pass the pointer to the node to free to release its memory.

Do not think of temp as a node. It is only an object that temporarily holds a pointer to the node. The node itself is a separate thing.