Branchless linked list remove entry in C

Question

In this TED talk, Torvalds proposes a remove entry function without if conditions. I've tried to emulate in the code below, but it doesn't work if the entry to remove is the head of the list. 1.) Why does this fail to remove the head specifically? 2.) Doesn't this method generate a memory leak since we never free the entry?

/** a data structure representing a node **/
struct node {
        int data;
        struct node* next;
};

/** create a new node and return a pointer to it**/
struct node* new_Node(int data)
{
        struct node* newP = malloc(sizeof(struct node));
        newP-> data = data;
        newP-> next = NULL;
        return newP;
}
/** function to print out a list**/
void list_print(struct node* head)
{
        printf("Begin List Print:\n");
        struct node* tmp = malloc(sizeof(struct node));
        tmp = head;

        while(tmp != NULL ) {
                printf("%d\n", tmp->data);
                tmp = tmp->next;
        }
        printf("End List Print\n\n");

}
 /** function to delete one node **/
void list_remove_entry(struct node* head, struct node* entry)
{
        struct node** indirect = &head;
    
        while((*indirect) != entry) {
                indirect = &(*indirect)->next;
        }
        *indirect = (*indirect)->next;
}
    
/** the program entry point**/
int main()
{
        struct node* head = new_Node(1);
        struct node* n1 = new_Node(2);
        struct node* n2 = new_Node(3);
        head->next = n1;
        n1->next = n2;
    
        list_print(head);
    
        list_remove_entry(head, head);
        list_print(head);
    
        return 0;
}

Yes, if you never free the entry you get a memory leak. He could be assuming a garbage-collected language. — Barmar, Feb 18 '21 at 01:41

Barmar · Accepted Answer · 2021-02-18T19:00:03.357

The code in the TED talk doesn't take head as a parameter, it's a global variable.

As a result, when it does

*indirect = entry->next;

it will modify the head variable if the entry to be removed is equal to head, because the while loop stops immediately and indirect still contains &head.

This doesn't work the same when you make head a parameter, because now you're just modifying the local variable, not the caller's variable. See Changing address contained by pointer using function for how you can redesign the function to solve this (it's also in @tadman's answer).

In answer to your second question, yes, this will create a memory leak. Linus's example is just meant to illustrate one particular aspect of the two ways to code this function, so he left out everything unrelated to that difference. You solve this by replacing the assignment with:

(*indirect)->next = (*indirect)->next->next;
free(*indirect);

Note that he also left out error checking. His code assumes that the entry will be found, so he never checks for *indirect == NULL before dereferencing it (and my above assignment doesn't check the double indirection).

It's not a coding lesson, it's just a simple example that needs to fit on a slide.

passing struct node** head was indeed the solution. However, free(*indirect); before *indirect = (*indirect)->next; appears to remove the entire list. — Shawn, Feb 18 '21 at 18:22

score 1 · Answer 2 · answered Feb 18 '21 at 01:36

You're doing a lot of voodoo programming here:

void list_remove_entry(struct node* head, struct node* entry)
{
  // Takes the address of a local argument
  struct node** indirect = &head;
    
  while((*indirect) != entry) {
    indirect = &(*indirect)->next;
  }

  // Updates local variable, no impact on caller's version of same
  *indirect = (*indirect)->next;
}

If you didn't get an indirect variable to start with, it's too late to turn it into one inside a function. This is something that needs to be established at the caller level.

What you want is to accept that variable indirectly (e.g. a pointer to a pointer) so you can manipulate it:

void list_remove_entry(struct node** head, struct node* entry)
{
  // Use the "indirect" argument directly
  while(*head != entry) {
    indirect = &(*head)->next;
  }

  // Updates caller's variable
  *head = (*head)->next;
}

Now you call it properly:

list_remove_entry(&head, head);

It's worth noting you can also do this without the double pointer if you can give a return value:

struct node* list_remove_entry(struct node* head, struct node* entry)
{
  while(head != entry) {
    head = head->next;
  }

  // Caller can update with this value
  return head->next;
}

Where calling it now looks like:

head = list_remove_entry(head, head);

That aside, your list_remove_entry function can only remove the first element. Theoretically it should be able to remove any element in the chain.

Your last version never removes anything from the list. It just returns the node after the one to be removed. — Barmar, Feb 18 '21 at 01:41
@Barmar Added a note about that. This fixes the original code, in as much as it does the same thing, but actually manipulates `head`. — tadman, Feb 18 '21 at 01:42

Branchless linked list remove entry in C

2 Answers2