0

I have a doubly linked list with *head and **ptail. I wrote code to add to the list and remove from the list, but my problem is freeing the information.

This is the declaration of my node and my linked list:

struct tcb_t { //Node
    int         thread_id;
    int         thread_priority;
    ucontext_t *thread_context;
    struct tcb_t *next;
}; typedef struct tcb_t tcb_t; 

struct queue_t { //Linked List
    tcb_t *head, **ptail; 
}; typedef struct queue_t queue_t;

This is my code for initializing a doubly linked list:

struct queue_t* queue_create() { //Good
  struct queue_t *q = (queue_t *) calloc(1,sizeof(queue_t));
  q->head = NULL;
  q->ptail = &q->head; // problem
  return q;
}

My problem stems from the following function. This function is intended to free all the nodes in the list, but the while loop is infinite. I think this is due to the tail pointing to the head in the linked list creation, but I am not sure if there is a way for me to fix it without rewriting the queue_create().

void t_shutdown() { //Fix
  if(ready != NULL){
    tcb_t *helper = ready->head;
    while(helper->next != NULL){ 
      tcb_t *temp = helper;
      helper = helper->next;
      if(temp->thread_id > 0){
        free(temp->thread_context->uc_stack.ss_sp);
      }
      free(temp->thread_context);
      free(temp);
    }
    free(ready);
  }
  
  ready = NULL;
}

I would like to loop through the list and free all the data but the helper->next is ever NULL.

Any help would be greatly appreciated.

Edit 1

These functions show how data is added and removed from the lists:

void queue_add(struct queue_t *q, tcb_t *ptr) { //Good
    *q->ptail = ptr;
    q->ptail = &ptr->next;
}

tcb_t *queue_remove(struct queue_t *q) { //Good
    struct tcb_t *ptr = q->head;
    if (ptr) {
        q->head = ptr->next;
        if (q->ptail == &ptr->next) {
            q->head == NULL;
            q->ptail = &q->head; // problem
        }
    }
    return ptr;
}
Community
  • 1
  • 1
Anthony Sette
  • 777
  • 1
  • 10
  • 26
  • 3
    Your nodes are not doubly-linked. Why is tail a pointer to a pointer? Why does `queue_create()` create a struct of two pointers on the heap? [Don't cast the result of `*alloc()`](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). – Swordfish May 19 '19 at 23:31
  • @Swordfish The queue is the doubly liked list. It has a head and a tail and is intended to make it easier to add/remove from the list. Check out the edit to see how it is used. – Anthony Sette May 19 '19 at 23:35
  • 1
    Why **ptail? You may want to link the tail with the head, but why not q->ptail->next = q->head ? – Israel Figueirido May 19 '19 at 23:35
  • 2
    @AnthonySette Then please look up what a [doubly-linked list](https://en.wikipedia.org/wiki/Doubly_linked_list) is. A pointer to the tail is nice to have but not sufficient for a list to be doubly-linked. – Swordfish May 19 '19 at 23:37
  • @Swordfish Okay. I initially had a normal doubly linked list but a recommendation from another user made me change it. – Anthony Sette May 19 '19 at 23:40
  • @isragram It was a recommendation from another user. And I don't think I want to point my tail->next to the head since it's hard to determine free all the items in the list. Should I rewrite with a standard doubly linked list? – Anthony Sette May 19 '19 at 23:43
  • 1
    @AnthonySette Yes, you should, but check out how a linked list must be implemented before. – Israel Figueirido May 19 '19 at 23:44
  • @Swordfish Should the `queue_create()` not be a struct of 2 pointers? If can remove the double pointer. – Anthony Sette May 19 '19 at 23:46
  • 1
    To be doubly linked, the _node_ (e.g. `tcb_t`) needs a `next` [which you have] _and_ a `prev` [which you _don't_ have]. And, the queue should have (e.g.) `tcb_t *head` and `tcb_t *tail` and _not_ what you currently have (e.g. `tcb_t **ptail`) – Craig Estey May 19 '19 at 23:47
  • @CraigEstey I made a mistake it is not doubly linked, I guess I just wanted easy access to head and to tail. I will be rewriting it to not have a double pointer. Thank you! – Anthony Sette May 19 '19 at 23:48
  • See my answers: https://stackoverflow.com/a/39177002/5382650 and https://stackoverflow.com/a/49582147/5382650 as they may give you some additional info. A straight up doubly linked list is the overall best way to go as insertions at the list tail and deletions of nodes are `O(1)` because a DL-list doesn't require a scan to find the tail or previous node. The tail is in the list header and the previous node is part of the node structure. And, there are many existing SO questions that have full implementations. – Craig Estey May 20 '19 at 00:00
  • @AnthonySette *Should the `queue_create()` not be a struct of 2 pointers?* – I don't get what you're trying to say. `queue_create()` is a function. I just mentioned above that there is no good reason to allocate `q` with `*alloc()` because its a very small structure only containing two pointers. – Swordfish May 20 '19 at 00:01

1 Answers1

1

Quick fix:

#include <stdlib.h>

typedef int ucontext_t;

typedef struct tcb_tag {
    int         thread_id;
    int         thread_priority;
    ucontext_t *thread_context;
    struct tcb_tag *prev;
    struct tcb_tag *next;
} tcb_t;

typedef struct queue_tag {
    tcb_t *head;
    tcb_t *tail;
} queue_t;

queue_t queue_create()
{
    queue_t queue = { NULL, NULL };
    return queue;
}

void queue_add(queue_t *queue, tcb_t *node)  // aka push_back()
{
    if (queue->tail) {
        queue->tail->next = node;
        node->prev = queue->tail;
        node->next = NULL;  // just to make sure. Idk where those nodes come from.
    }

    queue->tail = node;

    if (!queue->head)
        queue->head = queue->tail;
}

tcb_t* queue_remove(queue_t *queue)  // aka pop_front()
{
    if (!queue->head)
        return NULL;

    tcb_t *old_head = queue->head;
    queue->head = old_head->next;

    if (queue->head)
        queue->head->prev = NULL;
    else queue->tail = NULL;  // No head - no tail.

    return old_head;
}

void t_shutdown(queue_t *queue)
{
    for (tcb_t *curr_node = queue->head, *next_node; curr_node; curr_node = next_node) {
        next_node = curr_node->next;

        // do what you have to with curr_node->thread_context here

        free(curr_node);
    }
}

int main(void)
{
    queue_t q = queue_create();
    queue_add(&q, calloc(1, sizeof(tcb_t)));
    queue_add(&q, calloc(1, sizeof(tcb_t)));
    queue_add(&q, calloc(1, sizeof(tcb_t)));
    queue_add(&q, calloc(1, sizeof(tcb_t)));
    queue_add(&q, calloc(1, sizeof(tcb_t)));
    queue_remove(&q);
    queue_remove(&q);
    queue_remove(&q);
    t_shutdown(&q);
}
Swordfish
  • 12,971
  • 3
  • 21
  • 43
  • 1
    Please explain what the problem was, don't just provide code. – Geoffrey May 20 '19 at 01:16
  • Thank you so much! I was able to neatly work this into my code and I completely understand it. Now my test files run and there is no segfault when running `t_shutdown()` :) – Anthony Sette May 20 '19 at 02:47
  • The only thing is I don't understand am not sure why you passed the addresses in. When I pass the address I get a warning, but without it works flawlessly. – Anthony Sette May 20 '19 at 02:50
  • @AnthonySette In `queue_add()` and `queue_remove()` the queue gets passed as a pointer to it because these functions might need to modify the original queue. It wouldn't suffice to modify a copy. In `t_shutdown()` it doesn't matter. What warning did you get? – Swordfish May 20 '19 at 04:56