List and Queue, the BSD way

The BSD comes with a macro facility to manage lists and queues

  • Single linked structures ie. singly-linked list and singly-linked tailq
  • Double linked structures ie. list and tailq

Capabilities array

SLIST STAILQ LIST TAILQ
Insert an element at the head of the list YES YES YES YES
Insert an element at the end of the list NO YES NO YES
Insert an element before another element NO YES NO YES
Insert an element after another element YES YES YES YES
Remove an element at the head of the list YES YES YES YES
Remove an element at the end of the list NO YES NO YES
Remove an element before another element YES YES YES YES
Remove an element after another element NO YES NO YES
Can be traversed forward YES YES YES YES
Can be traversed backwards NO YES NO YES
Can be concatenated with another same structure NO YES NO YES
Pointers per head 1 2 1 2
Pointers per node 1 1 2 2

What the structures looks like

SLIST
Head
+------+
| Begin|
+------+
 |  +---+   +---+   +---+
 `->|N0 |-->|N1 |-->|N2 |
    +---+   +---+   +---+
    
STAILQ
Head
+------+
| End  |--------------,
+------+              |
| begin|              |
+------+              V
 |  +---+   +---+   +---+
 `->|N0 |-->|N1 |-->|N2 |
    +---+   +---+   +---+
   
LIST
Head
+------+
| Begin|
+------+
 |  +---+   +---+   +---+
 `->|N0 |-->|N1 |-->|N2 |
    +---+   +---+   +---+
        ^---'   ^---'
        
TAILQ
Head
+------+
| End  |--------------,
+------+              |
| begin|              |
+------+              V
 |  +---+   +---+   +---+
 `->|N0 |-->|N1 |-->|N2 |
    +---+   +---+   +---+
        ^---'   ^---'

Using SLIST

% cat exemple_slist.c 
#include <sys/queue.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node_t {
    int value;
    SLIST_ENTRY (node_t) next;
} node_t;

int main()
{
    int i;
    node_t * pnode;

    /* SLIST head :
     * struct head_t {
     *   struct node_t *sle_next;
     * }
     */
    SLIST_HEAD (head_t, node_t);

    struct head_t head;

    /* Initialize head 
     * head->sle_next = NULL;
     */
    SLIST_INIT (&head);
  
    /* Create 6 node and insert them in head */
    for (i=1;i<6;i++){
        /* Alloc the fists node */
        pnode = malloc (sizeof(struct node_t));
        pnode->value = i;
        /* Insert the newnode in head */
        SLIST_INSERT_HEAD(&head,pnode,next);
        printf("Insert Node %d\n",pnode->value);
    }

    SLIST_FOREACH(pnode,&head, next){
        printf("Dump Node %d\n",pnode->value);
    }

    while ((pnode = SLIST_FIRST(&head)) != NULL) {
      printf("Delete Node %d\n",pnode->value);
      SLIST_REMOVE(&head,pnode,node_t,next);
      free(pnode);
    }
  }

Compile & run

cc exemple_slist.c -o exemple_slist
./exemple_slist

The output is:

Insert Node 1
Insert Node 2
Insert Node 3
Insert Node 4
Insert Node 5
Dump Node 5
Dump Node 4
Dump Node 3
Dump Node 2
Dump Node 1
Delete Node 5
Delete Node 4
Delete Node 3
Delete Node 2
Delete Node 1