Skip to content

sparse: inline linked list pointers into 'node_data_struct'

Matthew Fernandez requested to merge smattr/graphviz:smattr/9c33e78d-f11e-419f-b4e7-26545b3e870c into main

There are two common ways to implement a linked-list in C. The first stores the actual element data out of line:

  struct item {
    void *data;
    struct item *next;
  };

  struct item *prepend(struct item *list, void *element) {
    struct item *n = xalloc(sizeof(struct item));
    n->data = element;
    n->next = list;
    return n;
  }

The second stores the link pointers inline within the data struct itself:

  struct foo {
    int x;
    char y;
    struct foo *next;
  };

  struct foo *prepend(strct foo *list, struct foo *element) {
    element->next = list;
    return element;
  }

The first technique has two main disadvantages: loss of type safety (data must be stored and retrieved as void*) and separate allocations for data+link. But its main advantage is that you implement the linked-list exactly once, instead of once per type.

The code touched in this MR was using the first design. But it was only instantiated once. So there is no advantage to preferring this over the second design. This change switches to the second.

Merge request reports