List of linked lists

Last blog post Linked list SLIST_ The car （chezi）-CSDN Blog Said ,queue.h There are 5 Species linked list , Namely ：

1. SLIST
2. LIST
3. STAILQ
4. TAILQ
5. CIRCLEQ

This article says LIST

LIST Sketch Map

LIST It is a two-way tailless acyclic linked list . A two-way linked list has a forward pointer , Therefore, some forward operations can be performed .

Look closely at the picture and you will find ,le_next This pointer points to the large structure behind , This is not unusual ; What's strange is that ,le_prev This pointer , It does not refer to the large structure in front , It's the one in front le_next. Why is it so designed ？ Fetch a imprison son , The answer is in my future articles .

Interface and implementation

Be careful ： Different versions , The code may be different .

/*
 * List declarations.
 */
#define	LIST_HEAD(name, type)						\
struct name {								\
	struct type *lh_first;	/* first element */			\
}

#define	LIST_HEAD_INITIALIZER(head)					\
	{ NULL }

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

/*
 * List functions.
 */

#define	LIST_EMPTY(head)	((head)->lh_first == NULL)

#define	LIST_FIRST(head)	((head)->lh_first)

#define	LIST_FOREACH(var, head, field)					\
	for ((var) = LIST_FIRST((head));				\
	    (var);							\
	    (var) = LIST_NEXT((var), field))

#define	LIST_INIT(head) do {						\
	LIST_FIRST((head)) = NULL;					\
} while (0)

#define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
		LIST_NEXT((listelm), field)->field.le_prev =		\
		    &LIST_NEXT((elm), field);				\
	LIST_NEXT((listelm), field) = (elm);				\
	(elm)->field.le_prev = &LIST_NEXT((listelm), field);		\
} while (0)

#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
	(elm)->field.le_prev = (listelm)->field.le_prev;		\
	LIST_NEXT((elm), field) = (listelm);				\
	*(listelm)->field.le_prev = (elm);				\
	(listelm)->field.le_prev = &LIST_NEXT((elm), field);		\
} while (0)

#define	LIST_INSERT_HEAD(head, elm, field) do {				\
	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)	\
		LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
	LIST_FIRST((head)) = (elm);					\
	(elm)->field.le_prev = &LIST_FIRST((head));			\
} while (0)

#define	LIST_NEXT(elm, field)	((elm)->field.le_next)

#define	LIST_REMOVE(elm, field) do {					\
	if (LIST_NEXT((elm), field) != NULL)				\
		LIST_NEXT((elm), field)->field.le_prev = 		\
		    (elm)->field.le_prev;				\
	*(elm)->field.le_prev = LIST_NEXT((elm), field);		\
} while (0)

give an example

Let's give an example of , Code from https://manpages.courier-mta.org/htmlman3/list.3.html, I changed it a little bit .

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/queue.h>

struct entry {
    
    int data;
    LIST_ENTRY(entry) entries;              /* List */
};

LIST_HEAD(listhead, entry);

int
main(void)
{
    
    struct entry *n1, *n2, *n3, *np;
    struct listhead head;                   /* List head */
    int i;

    LIST_INIT(&head);                       /* Initialize the list */

    n1 = malloc(sizeof(struct entry));      /* Insert at the head */
    n1->data = 1; // I add the 
    LIST_INSERT_HEAD(&head, n1, entries);

    n2 = malloc(sizeof(struct entry));      /* Insert after */
    n2->data = 2; // I add the 
    LIST_INSERT_AFTER(n1, n2, entries);

    n3 = malloc(sizeof(struct entry));      /* Insert before */
    n3->data = 3; // I add the 
    LIST_INSERT_BEFORE(n2, n3, entries);

    /* Forward traversal */
    LIST_FOREACH(np, &head, entries)
        printf("%i\n", np->data);

    LIST_REMOVE(n2, entries);               /* Deletion */
    free(n2);
                                            /* Forward traversal */
    LIST_FOREACH(np, &head, entries)
        printf("%i\n", np->data);
                                            /* List deletion */
    n1 = LIST_FIRST(&head);
    while (n1 != NULL) {
    
        n2 = LIST_NEXT(n1, entries);
        free(n1);
        n1 = n2;
    }
    LIST_INIT(&head);

    exit(EXIT_SUCCESS);
}

The code analysis

What about code? , It's just such a code . Let's watch it bit by bit .

LIST_ENTRY and LIST_HEAD

struct entry {
    
    int data;
    LIST_ENTRY(entry) entries;   /* List */
};

LIST_HEAD(listhead, entry);

Macro expansion is ：

struct entry {
    
    int data;
    struct {
      //  Structure without label 
        struct entry *le_next; 
        struct entry **le_prev; 
    } entries; 
};
struct listhead {
     
    struct entry *lh_first; 
};

and slist Very similar , The only difference is entries There are 2 A pointer to the , Because it's two-way , Of course. 2 It's a pointer . Be careful ,le_prev The type of is a pointer to a pointer , I.e. secondary pointer , Why is that ？

LIST_INIT and LIST_INSERT_HEAD

    struct entry *n1, *n2, *n3, *np;
    struct listhead head;                   /* List head */
    int i;

    LIST_INIT(&head);                       /* Initialize the list */

    n1 = malloc(sizeof(struct entry));      /* Insert at the head */
    n1->data = 1; // I add the 
    LIST_INSERT_HEAD(&head, n1, entries);

The first 5 Line is (&head)->lh_first = NULL; Initialize an empty linked list

The first 9 Line macro replacement is ：

        if (((n1)->entries.le_next = (&head)->lh_first) != ((void *)0)) 
            (&head)->lh_first->entries.le_prev = &(n1)->entries.le_next; 
        (&head)->lh_first = (n1); 
        (n1)->entries.le_prev = &(&head)->lh_first; 

The first 1 The first half of the line ((n1)->entries.le_next = (&head)->lh_first) And the 3 Line completion header insertion

The second half of the first line determines whether the original is an empty linked list , If it is ,if Conditions not established , Otherwise, the second 2 That's ok .

The first 4 That's ok ： Give Way n1 Of entries.le_prev Point to (&head)->lh_first;lh_first The type is struct entry *, and le_prev The type is struct entry **

The first 2 OK, it's hard to understand , Let the first node before inserting entries.le_prev Point to n1 Of entries.le_next.

therefore ,le_prev Defined as struct entry ** You can understand , The author's intention is to make it point to struct entry * type , such as lh_first and le_next

At this time, look at the figure at the beginning of this article , I understand. .

node It is equivalent to struct entry

SLIST_INSERT_HEAD(&head, n1, entries) It means ： hold n1 Insert the node into the linked list head The head of ; The first parameter is the address of the header , The second parameter is the address of the node to be inserted , The third parameter is the member name of the unlabeled structure .

LIST_INSERT_AFTER

    n2 = malloc(sizeof(struct entry));      /* Insert after */
    n2->data = 2; // I add the 
    LIST_INSERT_AFTER(n1, n2, entries);

LIST_INSERT_AFTER(n1, n2, entries) Indicates that the node n2 Insert into n1 Behind .

The first 3 That's ok , The macro is replaced by

    if (((n2)->entries.le_next = (n1)->entries.le_next) != ((void *)0)) 
        (n1)->entries.le_next->entries.le_prev = &(n2)->entries.le_next; 
    (n1)->entries.le_next = (n2); 
    (n2)->entries.le_prev = &(n1)->entries.le_next; 

Node n2 Insert into n1 Behind , Let's see which pointers need to be changed

1. n1 Of entries.le_next
2. n2 Of entries.le_next
3. n2 Of entries.le_prev
4. Before insertion n1 The back node （ Call it n0 Well ） Of entries.le_prev; If n0 be equal to NULL, You don't need to think about it

The first 1 Yes (n2)->entries.le_next = (n1)->entries.le_next The solution is 2

The first 2 Line code solves 4

The first 3 Line of code solves 1

The first 4 Line of code solves 3

LIST_INSERT_BEFORE

    n3 = malloc(sizeof(struct entry));      /* Insert before */
    n3->data = 3; // I add the 
    LIST_INSERT_BEFORE(n2, n3, entries);

LIST_INSERT_BEFORE(n2, n3, entries) Meaning is to put the n3 Insert into n2 In front of

The first 3 The line macro is replaced by ：

  (n3)->entries.le_prev = (n2)->entries.le_prev; 
  (n3)->entries.le_next = (n2); 
  *(n2)->entries.le_prev = (n3); 
  (n2)->entries.le_prev = &(n3)->entries.le_next; 

hold n3 Insert into n2 In front of , Let's see which pointers need to be changed

1. n2 Of entries.le_prev
2. n3 Of entries.le_next
3. n3 Of entries.le_prev
4. In the insert n3 Before , n2 The front node （ Call it n1 Well ） Of entries.le_next;

The first 1 OK, it's solved 3

The first 2 OK, it's solved 2

The first 3 OK, it's solved 4, It's a little complicated .(n2)->entries.le_prev Point to n1 Of entries.le_next, Yes (n2)->entries.le_prev Quoting , What you get is n1 Of entries.le_next, After inserting , because n1 At the back is n3, therefore n1 Of entries.le_next = n3;

The first 4 OK, it's solved 1

LIST_FOREACH

    /* Forward traversal */
    LIST_FOREACH(np, &head, entries)
        printf("%i\n", np->data);

After macro expansion is ：

for ((np) = ((&head)->lh_first); (np); (np) = ((np)->entries.le_next))
    printf("%i\n", np->data);

Traverse each node , This is easier to understand .

Be careful , This traversal cannot be deleted , Because if you put np The node pointed to is deleted ,

(np) = ((np)->entries.le_next) This sentence is wrong .

LIST_FOREACH(np, &head, entries) Used to traverse each node of the linked list . The first parameter is a temporary variable , Point to the current node , The second parameter is the address of the header , Third entries Is the member name of the unlabeled structure .

LIST_REMOVE

LIST_REMOVE(n2, entries);               /* Deletion */

The macro is replaced by

  if ((n2)->entries.le_next != ((void *)0)) 
      (n2)->entries.le_next->entries.le_prev = (n2)->entries.le_prev; 
  *(n2)->entries.le_prev = (n2)->entries.le_next; 

To delete n2, Let's see which pointers need to be changed

1. n2 The front node （ The assumption is n1） Of entries.le_next
2. n2 The back node （ The assumption is n3） Of entries.le_prev; If n3 yes NULL, No need

The first 3 OK, it's solved 1

1-2 OK, it's solved 2

LIST_FIRST and LIST_NEXT

    n1 = LIST_FIRST(&head);
    while (n1 != NULL) {
    
        n2 = LIST_NEXT(n1, entries);
        free(n1);
        n1 = n2;
    }

1： After deployment is n1 = ((&head)->lh_first);

LIST_FIRST(&head) Represents the first node of the linked list

3： After deployment is n2 = ((n1)->entries.le_next);

LIST_NEXT(n1, entries) It means taking nodes n1 The next node of

---

Reference material

https://manpages.courier-mta.org/htmlman3/list.3.html