Insert a node at the head of doubly linked list in C-CodePudding

void insertNode(struct obj_metadata *block){
    block->next = NULL;
    block->prev = NULL;
    block->is_free = 1;
    if (head == NULL) {
        head = block;
    }
    else{
        head->prev = block;
        block->next = head;
        head = block;
    } 
}

void myfree(void *ptr)
{
    struct obj_metadata *block;
    block = (struct obj_metadata*)ptr- 1;
    //size_t newSize;
    block->is_free = 1;
    insertNode(block);
}

I have to create my own malloc and free functions in C. For the free function I am setting the block free and want to add to the free linked list by using the function insertNode. However, the test keep going too long and the time expires. Is there any problem with my functions.

CodePudding user response：

A basic doubly linked list struct in C should look like:

struct dlist {
    void *data; // or whatever...
    
    struct dlist *prev;
    struct dlist *next;
};

Assuming head is the head of your list, here is how you can do it:

struct dlist *insert_head(struct dlist **head, struct dlist *block)
{
    block->prev = NULL;
    block->next = *head;
    if (*head)
        (*head)->prev = block;
    *head = block;
    
    return block;
}

CodePudding user response：

Probably the simplest approach to the double-linked list is to make head a list node and initialize is as a circular "pico-list" with both sub-pointers pointing to the head.

struct dlish head = { .prev = &head, .next = &head };

Adding new_node to the list would be:

// place node between `head` and `head.next`
new_node->prev = &head;
new_node->next = head.next;
// fix pointers in the new neighbors to point to `new_node`
head.next->prev = new_node;
head.next = new_node;

The main advantage of this approach is the lack of any corner cases.

Iteration is simple as well:

for(struct dlist *p = head.next; p != &head; p = p->next) {
  ...
}

CodePudding user response：

Your problem statement is incomplete, since you do not explain what the test is trying to do.

However, one problem I do see is that the code is not checking the is_free flag to see if the block being freed is already free. That is usually the reason to have such a flag in the first place.

assert(!block->is_free);
block->is_free = 1;

If the test has called myfree() twice on the same memory, it may cause your list to have a loop. Infinite loops are certain trigger a test timeout, if there is a function trying to iterate through the list.