2
\$\begingroup\$

This is a follow on from this question - Delete node from singly linked list with tail pointer in C

I've attempted to implement node deletion using the offsetof() macro mentioned by the answerer and after a lot of debugging I found that I needed to cast my pointer to a char* in order to be able to increment or decrement by 1 byte instead of 1 whole unit. The relevant line is commented below as //(RELEVANT LINE)

Is this the correct way to go about achieve this with only one double pointer? Is there a better way, avoiding casting to char*? Have I missed some fundamental of pointer arithmetic and I just got lucky here that my code hasn't fallen over?

For reference offsetof(lrsll_node, next) is 8, sizeof(lrsll_node) is 16

typedef struct lrsll_node {
    char *data;
    struct lrsll_node *next;
} lrsll_node;

typedef struct lrsll_list {
    lrsll_node *head;
    lrsll_node *tail;
} lrsll_list;

 lrsll_node *lrsll_delete(lrsll_list *list, char *data) {
        lrsll_node **node = &list->head;
        while (*node && strcmp((*node)->data, data) != 0) {
            node = &(*node)->next;
        }
        if (*node == NULL)
            return NULL;
        lrsll_node *deleted = *node;
        *node = deleted->next;


        if (deleted == list->tail) {

            //RELEVANT LINE
            list->tail = (node == &list->head) ? 
                    NULL : (lrsll_node*) ((char*)node - offsetof(lrsll_node, next));
        }

        return deleted;
    };
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'm the original answer guy. I'm surprised and delighted you're following up on offsetof. +1 \$\endgroup\$ Commented Sep 22, 2017 at 22:22
  • \$\begingroup\$ Something is wrong with your IDE. It doesn't format the code correctly, the indentation is inconsistent. \$\endgroup\$ Commented Sep 22, 2017 at 22:32

2 Answers 2

Reset to default
3
\$\begingroup\$

Can be simplified

You chose to use a "pointer to pointer" technique to find and delete your node, but this led to using an offsetof macro in order to back up your tail pointer to the previous node. If you instead used a "previous pointer" technique, your code would be much simpler to read and you wouldn't have to use any strange pointer subtraction tricks in order to find the previous node. Here is how it would look like:

lrsll_node *lrsll_delete(lrsll_list *list, const char *data)
{
    lrsll_node *prev = NULL;
    lrsll_node *node = list->head;

    while (node != NULL && strcmp(node->data, data) != 0) {
        prev = node;
        node = node->next;
    }

    if (node == NULL)
        return NULL;

    if (prev == NULL)
        list->head = node->next;
    else
        prev->next = node->next;

    if (node == list->tail)
        list->tail = prev;

    return node;
}

Addendum: Linus Torvalds' comments

Apparently this whole code was motivated by something Linus Torvalds wrote about using pointers to pointers. Here is the example demonstrating what he meant, taken from this blog post:

Given this list type:

typedef struct list_entry {
    int val;
    struct list_entry *next;
} list_entry;

This is the "wrong way" to delete a node:

list_entry *entry = head; /* assuming head exists and is the first entry of the list */
list_entry *prev = NULL;

while (entry) {
    if (entry->val == to_remove)     /* this is the one to remove */
        if (prev)
           prev->next = entry->next; /* remove the entry */
        else
           head = entry->next;      /* special case - first entry */

    /* move on to the next entry */
    prev = entry;
    entry = entry->next;
}

And here is what Linus considered the "correct way":

list_entry **pp = &head; /* pointer to a pointer */
list_entry *entry = head;

while (entry) {
    if (entry->val == to_remove)
        *pp = entry->next;

    pp = &entry->next;
    entry = entry->next;
}

And I will agree with Linus that for this case, the "double pointer" solution is better than the "prev pointer" version. But there is an important difference between this example and the OP's code, which is that the list in this example has no special List structure containing a head and tail pointer.

Because you may need to set the tail pointer to the previous node, the benefit of using the double pointer disappears, because now you need to convert the double pointer back into a node pointer using the awful offsetof trick. So for the particular data structure used by the OP, I would argue that the "prev pointer" solution is preferable.

In other words, you shouldn't always use the double pointer solution just because Linus said to use double pointers. You should consider whether or not your code would benefit from using double pointers and then use them if they provide a net benefit.

\$\endgroup\$
6
  • \$\begingroup\$ Thanks I'm sorry I should have mentioned I was trying to avoid using a second pointer, I'll edit the question now ( it was mentioned in the original question ) \$\endgroup\$ Commented Sep 22, 2017 at 19:08
  • \$\begingroup\$ I agree with @JS1 - this code is a lot easier to read, to maintain and to avoid bugs. I do not see where the OP's code set's the next pointer of the prev node for example. I see not a single positive reason for using tricks with offsets to solve such trivial task \$\endgroup\$ Commented Sep 22, 2017 at 19:17
  • 1
    \$\begingroup\$ @SMC But what is the justification to avoid using a second pointer, if using a second pointer makes the code easier to read and understand? \$\endgroup\$ Commented Sep 22, 2017 at 20:44
  • \$\begingroup\$ Perhaps this isn't the right area to ask about this code, the original question was because of Linus Torvald's comments on understanding pointers correctly so I've tried to implement a robust solution using only a double pointer to increase my understanding. I'm hoping for a review of this relevant function if one needed to use the offset for a non trivial example, the rest of the code was provided for context. Would this be better placed on a different SE site? \$\endgroup\$ Commented Sep 22, 2017 at 20:52
  • \$\begingroup\$ @SMC It's fine to put this code on this site, but 1) we tend to review all aspects of the code not just the ones you specify and 2) prior to your edit you never mentioned that you were specifically required to use a pointer-to-pointer. But also please read the addendum to my answer (coming soon). \$\endgroup\$ Commented Sep 22, 2017 at 21:47
2
\$\begingroup\$

Variation on @JS1 fine answer.

Walk the list with a previous pointer. This is something of a hybrid between OP's and JS1 code. Make a temporary top node. Only its .next member is important. 

lrsll_node *lrsll_delete(lrsll_list *list, const char *data) {
  lrsll_node top = { .next = list->head };
  lrsll_node *p = ⊤  // p = previous node

  // walk list with one pointer.
  while (p->next != NULL && strcmp(p->next->data, data) != 0) {
    p = p->next;
  }

  if (p->next == NULL) {  // data not found - nothing to delete
    return NULL;
  }
  lrsll_node *node_to_return = p->next;

  // detect if node to delete is the tail.
  if (list->tail == node_to_return) {
    if (p == &top) {
      list->tail = NULL;
    } else { 
      list->tail = p;
    }
  }

  // unlink 
  if (p == &top) {
    list->head = p->next->next;
  }
  else {
    p->next = p->next->next;
  }



  // Optional: for a little information hiding, scrub the .next member
  // so the calling code does not mess with it.
  node_to_return->next = NULL;

  return node_to_return;
}

This could have been done more clearly had OP posted the definition of lrsll_list here and a sample call to lrsll_delete().

Design idea: lrsll_list *list can be replaced with lrsll_node **list and still allow for O(1) to add before the head, O(1) to append to the tail and O(1) to delete from the head.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.