Skip to content

Instantly share code, notes, and snippets.

@santisbon
Last active July 13, 2023 15:16
Show Gist options
  • Save santisbon/42580049705ba3d8fbef7168e4668e3c to your computer and use it in GitHub Desktop.
Save santisbon/42580049705ba3d8fbef7168e4668e3c to your computer and use it in GitHub Desktop.
What makes good taste? #linux #linus #torvalds

On Good Taste

Linus Torvalds in an interview talked about the idea of good taste in code or what I like to call elegance. As one might expect from two slides meant to make a point during a talk, he omits a lot of details to keep it short and simple. This post digs into the specifics of his example (deleting an element from a list) and adds another example (inserting an element in a list) including working code.

Example from Linus

This is an example of removing an element from a singly-linked list. It's one of the first data structures you learn about when you start learning about computer science and programming. The reason it doesn't show particularly good taste is because we have that condition at the end where we take a different action depending on whether the element we want to remove is at the beginning of the list or somewhere in the middle.

Bad taste

The following is better. More elegant. It doesn't matter which element we are trying to remove, we always take the same action and it works for both cases.

Good taste

Some things to keep in mind:

  • This example shows how we could do it when we're deleting the item from within the same function where our list was defined, meaning where our head pointer is defined. In a moment we'll look at the case where we use a separate function to manipulate the list. For now let's stick to the case where we're deleting it from within our main() function.
  • It assumes we already have a pointer to the element we want to delete.

Implementation

I'll use C because we don't need any C++ features to illustrate this point.

First we'll define our node type.

typedef struct node_t {
  int value;
  struct node_t *next;
} node;

Delete entry

Good taste

Now the fun part: The implementation of the good taste example keeping the same outline from Torvalds's slide. I'll skip the less elegant version because you can easily implement that once you know the better one. As a reminder, the member access through pointer (->) operator has precedence over both the dereference (*) and address-of (&) operators. Also, the * and & operators have right-to-left associativity.

As part of the main() function
int main() {
  // Create an empty list
  node *head = NULL;

  /*
    Add some entries.
    When we start out with an empty list the function that adds an entry 
    (which we'll talk about later) needs to modify the head pointer itself 
    so instead of passing it a copy of the pointer we send a reference to it.
  */
  add_entry(&head, 3);
  add_entry(&head, 10);
  add_entry(&head, 2);
  add_entry(&head, 7);

  // Get a pointer to the entry we want to delete, 
  // in this example the node containing a "3" in it.
  node *entry = find_entry(head, 3);
  
  // Create a pointer to the pointer that points to the head of the list
  node **indirect = &head;

  // As long as what is referenced by our double pointer doesn't point 
  // to the same place as our entry pointer
  while((*indirect) != entry) {
    // Advance our double pointer by making it point to the "next" pointer.
    indirect = &(*indirect)->next;
  }

  /*
    Now our double pointer points to a pointer that points to the same node as 
    the entry pointer (the one we're deleting) so we change the "previous" pointer, 
    which could be the head, to the node that comes after the entry, removing it.
  */
  *indirect = entry->next;
  
  // Free up the allocated memory
  free(entry);
  
  return 0;
}

If we want to create a separate function to do the deletion, we'll need to change the pointer itself, not a copy of it. In C++ you can just declare the pointer parameter as a reference argument (&) and the compiler will take care of the details. In C we need to handle it ourselves so we add one more level of indirection for any parameters that need to be updated including pointers.

As a separate function
/*
  The head pointer may need to be modified so we need a double pointer.
  The entry pointer is also passed by reference as we'll free that memory.
*/
void remove_entry(node **head, node **entry) {
  /*
  The indirect pointer points to the pointer that we'll update
  */
  node ***indirect = &head;

  /*
    Walk the list as long as we haven't found the pointer we're looking for
  */
  while((**indirect) != *entry) {
    *indirect = &(**indirect)->next;
  }

  /*
    We remove it.
    indirect, which now points to either null or to the pointer that points to
    the entry we want to delete, is set to whatever comes after that entry.
  */
  **indirect = (*entry)->next;

  free(*entry);
}

Add entry

Now let's look at the add_entry function we used. As it turns out, this one is also a good example of something we can do in a pretty straightforward way but also in a very elegant, better way.

When adding an entry, we need to know if we're working with an empty list and therefore need to change the head pointer or if the list already contains elements, in which case we don't change the head but add the new node after the last one.

Poor taste

/*
  When the list is empty adding an element requires modifying the head
  pointer itself so the add function needs the address of the pointer,
  that is, a pointer to a pointer.
*/
void add_entry(node **head, int new_value) {
  node *current = *head;
  node *new_node = malloc(sizeof(node));
  new_node->value = new_value;
  new_node->next = NULL;

  if(*head == NULL) {
    *head = new_node;
  }
  else {
    while(current->next != NULL) {
      current = current->next;
    }
    current->next = new_node;
  }
}

Good taste

The following is a way to do it without having to worry about whether the list already has elements. It's more elegant. Let's start with the case where we're doing it from within our main() function.

Within the main() function
int main() {
  // We start with an empty list but it could also be an existing list 
  // with elements.
  node *head = NULL;
  // A reference to the last pointer. Starts out pointing to the head.
  node **indirect = &head;

  // We'll add a node with the value "4" in it
  node *new_node = malloc(sizeof(node));
  new_node->value = 4; 
  new_node->next = NULL;

  // Walk the list until indirect points to the last pointer of the list
  while(*indirect != NULL) {
    indirect = &(*indirect)->next;
  }

  // indirect now points to the last pointer in the list whether it was 
  // empty or not so we just add the new node there.
  *indirect = new_node;
  
  return 0;
}

And now let's see how we would do the same but in a separate function. This adds another level of indirection just as it did for the delete function.

As a separate function
/*
  We'll have to update the head pointer when the list is empty
  so we get a reference to it, not a copy.
*/
void add_entry(node **head, int new_value) {
  // A reference to the last pointer. Starts out pointing to the head.
  node ***indirect = &head;

  node *new_node = malloc(sizeof(node));
  new_node->value = new_value;
  new_node->next = NULL;

  while(**indirect != NULL) {
    *indirect = &(**indirect)->next;
  }

  // indirect now points to the last pointer in the list 
  // whether it was empty or not
  **indirect = new_node;
}

One final note: There's nothing wrong with the less elegant versions. They work just as well and are easy to implement. Coming up with clean, elegant solutions to problems is harder and you need to evaluate the costs and benefits of each approach including both efficiency and maintainability.

Below you'll find the file taste.c with full working examples of these concepts.

// gcc -o taste taste.c
// ./taste
#include <stdio.h>
#include <stdlib.h>
typedef struct node_t {
int value;
struct node_t *next;
} node;
/*
We'll have to update the head pointer when the list is empty
so we get a reference to it, not a copy.
*/
void add_entry(node **head, int new_value) {
// A reference to the last pointer. Starts out pointing to the head.
node ***indirect = &head;
node *new_node = malloc(sizeof(node));
new_node->value = new_value;
new_node->next = NULL;
while(**indirect != NULL) {
*indirect = &(**indirect)->next;
}
// indirect now points to the last pointer in the list whether it was empty or not
**indirect = new_node;
}
/*
Returns a pointer to the node that contains the value we're looking for
or NULL if not found.
*/
node *find_entry(node *head, int value) {
node *current = head;
while(current != NULL && current->value != value) {
current = current->next;
}
return current;
}
/*
The head pointer may need to be modified so we need a double pointer.
The entry pointer is also passed by reference as we'll free that memory.
*/
void remove_entry(node **head, node **entry) {
/*
The indirect pointer point to the pointer that we'll update
*/
node ***indirect = &head;
/*
Walk the list as long as we haven't found the pointer we're looking for
*/
while((**indirect) != *entry) {
*indirect = &(**indirect)->next;
}
/*
We remove it.
indirect, which now points to either null or to the pointer that points to
the entry we want to delete, is set to whatever comes after that entry.
*/
**indirect = (*entry)->next;
free(*entry);
}
void print_list(node *head) {
node *current = head;
while(current != NULL) {
printf("%d ", current->value);
current = current->next;
}
printf("\n");
}
int main(int argc, char const *argv[]) {
node *head = NULL;
print_list(head);
add_entry(&head, 4);
add_entry(&head, 3);
add_entry(&head, 10);
add_entry(&head, 2);
add_entry(&head, 7);
print_list(head);
node *entry = find_entry(head, 2);
remove_entry(&head, &entry);
entry = find_entry(head, 4);
remove_entry(&head, &entry);
print_list(head);
return 0;
}
@AkosUzonyi
Copy link

In the "As a separate function" sections you are using too much pointers:

The "indirect" pointer doesn't need to be triple, you could simply write:
node **indirect = head;
(and then use less dereferencing everywhere)

Also you don't need to pass a pointer to the entry pointer, you can free it if you are just passing it normally.

By the way the indirect variable can be also ommitted by just simply writing:
void remove_entry(node **head, node *entry) {
while((*head) != entry) {
head= &(*head)->next;
}
*head= entry->next;
free(entry);
}

@hpchang
Copy link

hpchang commented Sep 14, 2017

They both are good examples! I fork this and modify it to be less dereferencing as @AkosUzonyi mentioned.

void add_entry(node **head, int new_value) {
  // A reference to the last pointer. Starts out pointing to the head.
  node **indirect = head;

  node *new_node = malloc(sizeof(node));
  new_node->value = new_value;
  new_node->next = NULL;

  while(*indirect != NULL) {
    indirect = &(*indirect)->next;
  }

  // indirect now points to the last pointer in the list whether it was empty or not
  *indirect = new_node;
}
void remove_entry(node **head, node *entry) {
  /*
  The indirect pointer point to the pointer that we'll update
  */
  node **indirect = head;

  /*
    Walk the list as long as we haven't found the pointer we're looking for
  */
  while((*indirect) != entry) {
    indirect = &(*indirect)->next;
  }

  /*
    We remove it.
    indirect, which now points to either null or to the pointer that points to
    the entry we want to delete, is set to whatever comes after that entry.
  */
  *indirect = entry->next;

  free(entry);
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment