CODEWITHSUNDEEP
clistdata-structureslinked-list
slideyourwayonoverr
slideyourwayonoverr

Reputation: 23

Why does BSD use a double pointer in a linked list entry?

This is the BSD implementation of an entry in a double linked list?

#define LIST_ENTRY(type)                        \
struct {                                \
    struct type *le_next;   /* next element */          \
    struct type **le_prev;  /* address of previous next element */  \
}

Why do they use a double pointer? Why not just have

#define LIST_ENTRY(type)                        \
struct {                                \
    struct type *le_next, *le_prev;     \
}

I dont see any problem with that, and it looks simpler in my opinion, so why not use it? Am I missing something?

Upvotes: 2

Views: 267

Answers (1)

John Bollinger
John Bollinger

Reputation: 180998

Why do they use a double pointer?

The source file contains reasonably good explanatory comments. The ones that apply to this particular kind of data structure are:

 * A list is headed by a single forward pointer (or an array of forward
 * pointers for a hash table header). The elements are doubly linked
 * so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before
 * or after an existing element or at the head of the list. A list
 * may only be traversed in the forward direction.

There are several key things to note about that, among them:

  1. Even though the nodes have pointers by which the previous node can be accessed, this kind of list is intended for forward traversal only.

  2. The list is headed by a single pointer. It is implied, and this can be verified elsewhere in the source, that that single pointer is not a member of a list node object.

  3. The reason for the double-linkage is stated as "so that an arbitrary element can be removed without a need to traverse the list". Reading just a little between the lines, we can take that to mean that if I have a pointer to a node then I can remove that node from the list to which it belongs, outside the context of a list traversal, and even if it is the first node in the list.

    Note well in this regard that the first node in such a list does not have a predecessor node that a struct type * could point to (see (2) above), but for a node to be in such a list at all, there must be a struct type * pointing to it, whether in another node or in the list object. Given a struct type ** pointing to that pointer, we can effect removals by modifying that pointer directly, instead of through the structure containing it.

  4. New elements can be added before or after any node. For much the same reason that the double pointer facilitates deleting the first node, it also facilitates inserting a new node before the first -- again, without traversing the list or knowing that the node is in fact first, or even which list it belongs to.

Why not just have

#define LIST_ENTRY(type)                        \
struct {                                \
    struct type *le_next, *le_prev;     \
}

I dont see any problem with that, and it looks simpler in my opinion, so why not use it? Am I missing something?

That would be the conventional form for a node in a doubly-linked list. It could provide the same removal and insertion semantics described in (3) and (4) above, provided that the list was structured with a dummy head node. The details of how BSD uses this LIST_ENTRY macro in practice to define lists are a bit obscure to me, however, so perhaps there's a reason why a dummy head node would be unworkable. Or perhaps this choice is simply for a little bit of space efficiency.

In any case, that's not how the list is structured (see (2)). Given the chosen structure for the list head, the double pointer structure for previous nodes is required to serve the stated purposes of this list and its nodes ((3) and maybe (4)). Because the list is intended to be traversed in the forward direction only, the double-pointer structure is not an impediment.

Upvotes: 2

Related Questions