Tailq of linked list

TAILQ Introduce

TAILQ The queue is FreeBSD A queue data structure in the kernel , In some famous open source libraries ( Such as DPDK、libevent) It has a wide range of applications .

TAILQ and Linux in list They are organized differently , The latter is simply to struct list_head As the hanging point of the linked list , No user information , Their differences are shown in the following figure .

Linux Medium list Only will struct list_head As the hook point of user elements , Therefore, when traversing the linked list in the forward direction , Need to use container_of This kind of interface can obtain user data , and TAILQ because tqe_next The pointer points directly to the user element , So theoretically , Positive traversal TAILQ Than list faster .

The header file

The header file is from the project I recently saw ：apache-mynewt-core-1.9.0\sys\sys\include\sys\queue.h

Only part of .

// "bsd_queue.h"  In order to test , I have a new name 

/* * @(#)queue.h 8.5 (Berkeley) 8/20/94 * $FreeBSD: src/sys/sys/queue.h,v 1.32.2.7 2002/04/17 14:21:02 des Exp $ */

/* * Tail queue declarations. */
#define TAILQ_HEAD(name, type) \ struct name {
       \ struct type *tqh_first; /* first element */ \ struct type **tqh_last; /* addr of last next element */ \ }

#define TAILQ_HEAD_INITIALIZER(head) \ {
       NULL, &(head).tqh_first }

#define TAILQ_ENTRY(type) \ struct {
       \ struct type *tqe_next; /* next element */ \ struct type **tqe_prev; /* address of previous next element */ \ }

/* * Tail queue functions. */
#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)

#define TAILQ_FIRST(head) ((head)->tqh_first)

#define TAILQ_FOREACH(var, head, field) \ for ((var) = TAILQ_FIRST((head)); \ (var); \ (var) = TAILQ_NEXT((var), field))

#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ for ((var) = TAILQ_LAST((head), headname); \ (var); \ (var) = TAILQ_PREV((var), headname, field))

#define TAILQ_INIT(head) do {
       \ TAILQ_FIRST((head)) = NULL; \ (head)->tqh_last = &TAILQ_FIRST((head)); \ } while (0)

#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {
       \ if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ TAILQ_NEXT((elm), field)->field.tqe_prev = \ &TAILQ_NEXT((elm), field); \ else \ (head)->tqh_last = &TAILQ_NEXT((elm), field); \ TAILQ_NEXT((listelm), field) = (elm); \ (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ } while (0)

#define TAILQ_INSERT_BEFORE(listelm, elm, field) do {
       \ (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ TAILQ_NEXT((elm), field) = (listelm); \ *(listelm)->field.tqe_prev = (elm); \ (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ } while (0)

#define TAILQ_INSERT_HEAD(head, elm, field) do {
       \ if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ TAILQ_FIRST((head))->field.tqe_prev = \ &TAILQ_NEXT((elm), field); \ else \ (head)->tqh_last = &TAILQ_NEXT((elm), field); \ TAILQ_FIRST((head)) = (elm); \ (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ } while (0)

#define TAILQ_INSERT_TAIL(head, elm, field) do {
       \ TAILQ_NEXT((elm), field) = NULL; \ (elm)->field.tqe_prev = (head)->tqh_last; \ *(head)->tqh_last = (elm); \ (head)->tqh_last = &TAILQ_NEXT((elm), field); \ } while (0)

#define TAILQ_LAST(head, headname) \ (*(((struct headname *)((head)->tqh_last))->tqh_last))

#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)

#define TAILQ_PREV(elm, headname, field) \ (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

#define TAILQ_REMOVE(head, elm, field) do {
       \ if ((TAILQ_NEXT((elm), field)) != NULL) \ TAILQ_NEXT((elm), field)->field.tqe_prev = \ (elm)->field.tqe_prev; \ else \ (head)->tqh_last = (elm)->field.tqe_prev; \ *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ } while (0)

give an example

come from https://manpages.courier-mta.org/htmlman3/tailq.3.html

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include "bsd_queue.h" // of no avail  Linux  Of , It's my own 

struct entry {
    
    int data;
    TAILQ_ENTRY(entry) entries;             /* Tail queue */
};

TAILQ_HEAD(tailhead, entry);

int
main(void)
{
    
    struct entry *n1, *n2, *n3, *np;
    struct tailhead head;                   /* Tail queue head */
    int i;

    TAILQ_INIT(&head);                      /* Initialize the queue */

    n1 = malloc(sizeof(struct entry));      /* Insert at the head */
    TAILQ_INSERT_HEAD(&head, n1, entries);

    n1 = malloc(sizeof(struct entry));      /* Insert at the tail */
    TAILQ_INSERT_TAIL(&head, n1, entries);

    n2 = malloc(sizeof(struct entry));      /* Insert after */
    TAILQ_INSERT_AFTER(&head, n1, n2, entries);

    n3 = malloc(sizeof(struct entry));      /* Insert before */
    TAILQ_INSERT_BEFORE(n2, n3, entries);

    TAILQ_REMOVE(&head, n2, entries);       /* Deletion */
    free(n2);
                                            /* Forward traversal */
    i = 0;
    TAILQ_FOREACH(np, &head, entries)
        np->data = i++;
                                            /* Reverse traversal */
    TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
        printf("%i\n", np->data);
                                            /* TailQ deletion */
    n1 = TAILQ_FIRST(&head);
    while (n1 != NULL) {
    
        n2 = TAILQ_NEXT(n1, entries);
        free(n1);
        n1 = n2;
    }
    TAILQ_INIT(&head);

    exit(EXIT_SUCCESS);
}

The code analysis

TAILQ_ENTRY and TAILQ_HEAD

struct entry {
    
    int data;
    TAILQ_ENTRY(entry) entries;             /* Tail queue */
};

TAILQ_HEAD(tailhead, entry);

TAILQ_ENTRY(entry) entries Medium entry Specified by the user , It is the label of the outer large structure , After the macro is expanded, the following page 1,4,5 In a row entry;entries Also specified by the user , Is the member name of the unlabeled structure , After the macro is expanded, the following page 6 In a row entries

struct entry {
    
    int data;
    struct {
     
        struct entry *tqe_next; 
        struct entry **tqe_prev; 
    } entries;
};

struct tailhead {
     
    struct entry *tqh_first; 
    struct entry **tqh_last; 
};

TAILQ_HEAD(tailhead, entry) Medium tailhead Specified by the user , It is the label of the header structure , As in paragraph above 9 Yes tailhead,entry Want to be with TAILQ_ENTRY The first parameter in is consistent .

struct entry **tqh_last and struct entry **tqe_prev It looks a little strange , Why is it a secondary pointer ？

Is it OK to change it to level one ？

If you put the 5 Change line to struct entry *tqe_prev, Definitely not , What if the head node is in front of it , There is no struct entry ah ！

Take a closer look , Whether it's a header node or a normal node , There are struct entry * This type , Then define a type as struct entry ** Variable of . In this way, the forward insertion can be handled uniformly , For example, see TAILQ_INSERT_BEFORE

To sum up , Definition TAILQ When , Yes 3 Basic elements ：

1. Structure struct entry：TAILQ_ENTRY() Parameters and TAILQ_HEAD() Second parameter of

2. Structure struct tailhead：TAILQ_HEAD() The first parameter of

3. Variable entries： Keep up with the TAILQ_ENTRY() Back

   TAILQ_INIT

    struct entry *n1, *n2, *n3, *np;
    struct tailhead head;                   /* Tail queue head */
    int i;

    TAILQ_INIT(&head);                      /* Initialize the queue */

The first 5 That's ok , Macro expansion yes

(((&head))->tqh_first) = ((void *)0); 
(&head)->tqh_last = &(((&head))->tqh_first); 

It means header tqh_first by NULL,tqh_last self-directed tqh_first

TAILQ_INSERT_HEAD

    n1 = malloc(sizeof(struct entry));      /* Insert at the head */
    TAILQ_INSERT_HEAD(&head, n1, entries);

2: Macro expansion

if (((((n1))->entries.tqe_next) = (((&head))->tqh_first)) != ((void *)0)) 
    (((&head))->tqh_first)->entries.tqe_prev = &(((n1))->entries.tqe_next); 
else 
    (&head)->tqh_last = &(((n1))->entries.tqe_next); 

(((&head))->tqh_first) = (n1); 
(n1)->entries.tqe_prev = &(((&head))->tqh_first); 

To put n1 Insert into the first position of the queue , Which pointers need to be modified ？

1. n1 Of entries.tqe_next
2. n1 Of entries.tqe_prev
3. (&head))->tqh_first
4. Of the first node before entries.tqe_prev
5. If n1 Is the only node , It needs to be revised (&head)->tqh_last

good , Let's see how the code solves .

The first 1 OK, it's solved 1

The first 2 OK, it's solved 4, This needs to be explained ,(((&head))->tqh_first)->entries.tqe_prev Indicates insertion n1 Of the previous first node tqe_prev, After inserting , It should point to n1 Of tqe_next

The first 4 OK, it's solved 5

The first 6 OK, it's solved 3

The first 7 OK, it's solved 2

TAILQ_INSERT_TAIL

    n1 = malloc(sizeof(struct entry));      /* Insert at the tail */
    TAILQ_INSERT_TAIL(&head, n1, entries);

hold n1 Insert at the end of the queue , Which pointers need to be modified ？

1. (&head)->tqh_last
2. n1 Of entries.tqe_next Should be NULL
3. n1 Of entries.tqe_prev
4. n1 The last node before inserting （ It's called n0 Well ） Of entries.tqe_next

The first 2 That's ok , Expand macro

(((n1))->entries.tqe_next) = ((void *)0); 
(n1)->entries.tqe_prev = (&head)->tqh_last; 
*(&head)->tqh_last = (n1); 
(&head)->tqh_last = &(((n1))->entries.tqe_next);

The first 1 OK, it's solved 2

The first 2 OK, it's solved 3

The first 3 OK, it's solved 4, Because before inserting (&head)->tqh_last Point to n0 Of entries.tqe_next, Yes (&head)->tqh_last Quoting , You get the variable n0 Of entries.tqe_next, It should be equal to n1

The first 4 OK, it's solved 1

TAILQ_INSERT_AFTER

    n2 = malloc(sizeof(struct entry));      /* Insert after */
    TAILQ_INSERT_AFTER(&head, n1, n2, entries);

hold n2 Insert into n1 Behind , Which pointers need to be modified ？

1. n1 Of entries.tqe_next
2. n2 Of entries.tqe_prev
3. n2 Of entries.tqe_next
4. Insert n2 Before , If n1 Behind a n3, It needs to be modified n3 Of entries.tqe_prev;
5. Insert n2 Before , If n1 It's the last node , Then modify (&head)->tqh_last

The first 2 Line macro expansion ：

if (((((n2))->entries.tqe_next) = (((n1))->entries.tqe_next)) != ((void *)0)) 
    (((n2))->entries.tqe_next)->entries.tqe_prev = &(((n2))->entries.tqe_next); 
else 
    (&head)->tqh_last = &(((n2))->entries.tqe_next); 

(((n1))->entries.tqe_next) = (n2); 
(n2)->entries.tqe_prev = &(((n1))->entries.tqe_next); 

The first 1 OK, it's solved 3

The first 2 OK, it's solved 4

The first 4 OK, it's solved 5

The first 6 OK, it's solved 1

The first 7 OK, it's solved 2

TAILQ_INSERT_BEFORE

    n3 = malloc(sizeof(struct entry));      /* Insert before */
    TAILQ_INSERT_BEFORE(n2, n3, entries);

hold n3 Insert into n2 In front of , Which pointers need to be modified ？

1. n3 Of entries.tqe_next

2. n2 Of entries.tqe_prev

3. n3 Of entries.tqe_prev

4. Insert n3 Before , If n2 In front of n1, It needs to be modified n1 Of entries.tqe_next,

   namely (n1)->entries.tqe_next = n3;

5. Insert n3 Before , If n2 It's the first node , Then modify (&head)->tqh_first,

   namely (&head)->tqh_first = n3;

The first 2 Line macro expansion

 (n3)->entries.tqe_prev = (n2)->entries.tqe_prev; 
 (((n3))->entries.tqe_next) = (n2); 
 *(n2)->entries.tqe_prev = (n3); 
 (n2)->entries.tqe_prev = &(((n3))->entries.tqe_next); 

The first 1 OK, it's solved 3

The first 2 OK, it's solved 1

The first 3 OK, it's solved 4 and 5（ I'll explain right away ）

The first 4 OK, it's solved 2

explain ：

Insert n3 Before , If n2 In front of n1,

that *(n2)->entries.tqe_prev On behalf of the variable (n1)->entries.tqe_next

Insert n3 Before , If n2 It's the first node ,

that *(n2)->entries.tqe_prev On behalf of the variable (&head)->tqh_first

So these two situations can be combined , It's written in

*(n2)->entries.tqe_prev = (n3);

TAILQ_REMOVE

    TAILQ_REMOVE(&head, n2, entries);       /* Deletion */
    free(n2);

To put n2 Remove... From the linked list , Which pointers need to be modified ？

1. n2 The front node （ The assumption is n1） Of entries.tqe_next
2. n2 The back node （ The assumption is n3） Of entries.tqe_prev
3. If n2 It's the last node , Then we need to modify it (&head)->tqh_last

The first 1 Line macro expansion

if (((((n2))->entries.tqe_next)) != ((void *)0)) 
    (((n2))->entries.tqe_next)->entries.tqe_prev = (n2)->entries.tqe_prev; 
else 
    (&head)->tqh_last = (n2)->entries.tqe_prev; 
*(n2)->entries.tqe_prev = (((n2))->entries.tqe_next); 

The first 1 Line judgment n2 Whether it is the last node

The first 2 OK, it's solved 2

The first 4 OK, it's solved 3

The first 5 OK, it's solved 1, Let's explain .(n2)->entries.tqe_prev Pointing to n1 Of entries.tqe_next, Yes (n2)->entries.tqe_prev Quoting , Get the variable (n1)->entries.tqe_next, It needs to be assigned n3 The address of , namely (n2)->entries.tqe_next; If (n2)->entries.tqe_prev Pointing to the header tqh_first, The first 5 Line is also established

TAILQ_FOREACH

    i = 0;/* Forward traversal */
    TAILQ_FOREACH(np, &head, entries)
        np->data = i++;

The first 2 Line is

for ((np) = (((&head))->tqh_first); (np); (np) = (((np))->entries.tqe_next))

Relatively simple , There is no need to explain .

TAILQ_FOREACH_REVERSE

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

Let's change our mind this time , Don't look at what it is after expansion , Instead, look at the definition of macros

#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ for ((var) = TAILQ_LAST((head), headname); \ (var); \ (var) = TAILQ_PREV((var), headname, field))

#define TAILQ_LAST(head, headname) \ (*(((struct headname *)((head)->tqh_last))->tqh_last))

#define TAILQ_PREV(elm, headname, field) \ (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

The first 7 That's ok , You can get the address of the last node . Explain it. ：

(head)->tqh_last Is the last node entries.tqe_next The address of , But this address is not what the user wants , What the user wants is the address of the node , It's a big structure （ struct entry ） The address of , So we have to save the country by curving , Here's the picture , from 1 To 2 Until then 3

from entries.tqe_next How to get the address of entries.tqe_prev The value of ？

It's not hard , although struct entry Inside entries This structural variable has no label , But its element composition and struct headname Exactly the same as , It's all one struct entry * and One struct entry **, So you can put entries.tqe_next Cast address to (struct headname *) type : (struct headname *)((head)->tqh_last)

Then visit its tqh_last member （ That's what this is prev）：

((struct headname *)((head)->tqh_last))->tqh_last

In this way, we get the of the previous node entries.tqe_next The address of , Then dereference it ：

*(((struct headname *)((head)->tqh_last))->tqh_last)

Got it. entries.tqe_next Variable , This happens to be a large structure （ struct entry ） The address of

We'll see TAILQ_PREV This macro , The reason is similar to .

As shown in the figure , from 1 To 2 Until then 3

Let the address of the current node be elm（ The last node is used to illustrate ）,(elm)->field.tqe_prev , Indicates following 1, Get the node in front of it next The address of , Force this address to struct headname *, namely

(struct headname *)((elm)->field.tqe_prev)

Revisit prev, That is to follow 2, Got it elm In front of the front node next Address

namely ((struct headname *)((elm)->field.tqe_prev))->tqh_last

Dereference it , You get elm In front of the front node next, namely

*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)

It happens to be 3 This pointer represents the address .

Other macros are simpler , No introduction

Reference material

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

TAILQ One or two things in the queue - SegmentFault Think no