Deleting all items from a queue

Question

Lets say I have the following structure

typedef struct node {
    unsigned long data;
    struct node* next;
} node;

typedef struct queue {
    node* head;
    node* tail;
    int size;
    int capacity;
} queue;

queue* buildar()
{
    queue* arr = malloc(num * sizeof(queue));
    int i;
    for (i = 0; i < num; i++)
    {
        queue* r = malloc(sizeof(queue));
        r->head = NULL;
        r->tail = NULL;
        r->size = 0;
        r->capacity = assoc;
        arr[i] = *r;
    }
    return arr;
}

How can I free all the items in the queue? I've already tried doing this

    for (size_t i = 0; i < numberofsets; i++)
    {
        node* temp = arr[i].head;
        arr[i].head = arr[i].head->next;
        free(temp);
    }
    free(arr);

but it doesn't seem to be working. Any help is appreciated.

Answer 1

You are looking for an array of arrays (I think/hope). Basically, you want to create n queues that are all index-able (is that a word?) from one "master" array.

So you are looking at it like this:

idx
of
big
arry
_________________________________  
|000|   ----->  [ one big queue ]  
|001|   ----->  [ one big queue ]  
|002|   ----->  [ one big queue ]  
|003|   ----->  [ one big queue ]  
|004|   ----->  [ one big queue ]  
|...|   ----->  .................   
|nth|   ----->  [ one big queue ]  
_________________________________  

#include <stdlib.h>


typedef struct node
{
    unsigned long data;
    struct node*  next;
}
node;

typedef struct queue
{
    int   size;
    int   capacity;
    node* head;
    node* tail;
    
}
queue;


queue** build_queue(int num  ,
                    int assoc
                   )
{
    //here you create an array of arrays
    //result is an array of pointers, each pointer going to a separate array 
    queue** result = malloc(num * sizeof(queue*));
    
    int i;
    for (i = 0; i < num; i++)
    {
        queue* q    = malloc(sizeof(queue));  //memory for actual queue
        result[i]   = q;

        q->head     = NULL;
        q->tail     = NULL;
        q->size     = 0;
        q->capacity = assoc;
    }

    return result;
}



void free_queues(int     num_queues,
                 queue** qs
                )
{
    int i;
    for (i = 0; i < num_queues; i++)
    {
       /*
        * NOTE: you must use a while loop here to FIRST free the linked list qs[i]
        * node* head = qs[i]->head;
        * while(head != qs[i]->tail)
        * {
        *     node* temp = head->next;
              free(head);
              head = temp;
        * }
        * free(qs[i]->tail);
        */
       free(qs[i]);  //frees the actual queue struct   
    }
    free(qs);        //frees the array of pointers to queues
}



int main(void)
{
   int num   = 5;
   int assoc = 4;
 
   queue** qs = build_queue(num, assoc);
   free_queues(num, qs);

   return 1;
}

Finally, use valgrind to check if there are leaks. For above solution:

$ gcc please_work.c
$ valgrind ./a.out 
==5974== Memcheck, a memory error detector
==5974== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5974== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==5974== Command: ./a.out
==5974== 
==5974== 
==5974== HEAP SUMMARY:
==5974==     in use at exit: 0 bytes in 0 blocks
==5974==   total heap usage: 6 allocs, 6 frees, 160 bytes allocated
==5974== 
==5974== All heap blocks were freed -- no leaks are possible
==5974== 
==5974== For lists of detected and suppressed errors, rerun with: -s
==5974== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Answer 2

It is hard to guess what "doesn't seem to be working" means, but there are several issues with the code.

In buildar() you use two undefined variables. You might have them as global vars, but you probably want them as arguments to the function. You also leak memory, because you malloc() a new link, initialise it, copy the values there into the array, and then throw away the allocated memory, that now will never be freed.

// added num & assoc here--assuming it should be a parameter
queue* buildar(int num, int assoc) 
{
    queue* arr = malloc(num * sizeof(queue));
    int i;
    for (i = 0; i < num; i++)
    {
        // This will leak memory. You allocate a root
        // that you initialise, then you copy the data
        // and then you throw away the allocated memory
        // when you update r, or it goes out of scope
        queue* r = malloc(sizeof(queue));
        r->head = NULL;
        r->tail = NULL;
        r->size = 0;
        r->capacity = assoc;
        arr[i] = *r;
    }
    return arr;
}

Since you already have root links in the array, you could just update those, and avoid the malloc():

queue* buildar(int num, int assoc) 
{
    queue* arr = malloc(num * sizeof *arr);
    for (int i = 0; i < num; i++)
    {
        arr[i].head = NULL;
        arr[i].tail = NULL;
        arr[i].size = 0;
        arr[i].capacity = assoc;
    }
    return arr;
}

In the freeing code, if the root nodes are freshly initialised, their head pointer is NULL. That will be a problem when you dereference them to get head->next. Technically, dereferencing NULL is undefined behaviour, but in practice, it will be a segmentation fault that will crash your program. If there is more than one node per entry, you will leak memory. You free the first after the root, then point the root's head to the next, and then free the array that holds the root.

As far as I can see, the code will work as intended if there is exactly one node (after the root) for each index, but crash if there is zero and leak if there are more. If there is supposed to be a variable number of nodes, that is one source of "doesn't seem to work". Might that be it?

void free_queues(queue *arr, int numberofsets)
{
  for (size_t i = 0; i < numberofsets; i++)
  {
    node* temp = arr[i].head;
    // if the queue was empty, arr[i].head->next
    // dereferences a NULL pointer, which is
    // undefined behaviour
    arr[i].head = arr[i].head->next;
    // This only removes one link from the queue.
    // If there are more, you leak memory when you
    // free arr below
    free(temp);
  }
  free(arr);
}

If that is the case, you might want something like:

void free_queues(queue *arr, int numberofsets)
{
  for (size_t i = 0; i < numberofsets; i++) {
    node* temp = arr[i].head, *next;
    while (temp) {
      next = temp->next;
      free(temp);
      temp = next;
    }
  }
  free(arr);
}