Stablq of linked list

STAILQ Sketch Map

STAILQ and LIST The difference is that the ,head There's a pointer inside stqh_last, Pointing to the last node stqe_next

Be careful ： Some places also put STAILQ It's called simple queue, Change the interface prefix to SIMPLEQ_

Interface and implementation

Post the code first .（ Be careful ： Different versions of code may be different ）

/* * Singly-linked Tail queue declarations. */
#define STAILQ_HEAD(name, type) \ struct name {
       \ struct type *stqh_first;/* first element */ \ struct type **stqh_last;/* addr of last next element */ \ }

#define STAILQ_HEAD_INITIALIZER(head) \ {
       NULL, &(head).stqh_first }

#define STAILQ_ENTRY(type) \ struct {
       \ struct type *stqe_next; /* next element */ \ }

/* * Singly-linked Tail queue functions. */
#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)

#define STAILQ_FIRST(head) ((head)->stqh_first)

#define STAILQ_FOREACH(var, head, field) \ for((var) = STAILQ_FIRST((head)); \ (var); \ (var) = STAILQ_NEXT((var), field))

#define STAILQ_INIT(head) do {
       \ STAILQ_FIRST((head)) = NULL; \ (head)->stqh_last = &STAILQ_FIRST((head)); \ } while (0)

#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {
       \ if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ (head)->stqh_last = &STAILQ_NEXT((elm), field); \ STAILQ_NEXT((tqelm), field) = (elm); \ } while (0)

#define STAILQ_INSERT_HEAD(head, elm, field) do {
       \ if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ (head)->stqh_last = &STAILQ_NEXT((elm), field); \ STAILQ_FIRST((head)) = (elm); \ } while (0)

#define STAILQ_INSERT_TAIL(head, elm, field) do {
       \ STAILQ_NEXT((elm), field) = NULL; \ *(head)->stqh_last = (elm); \ (head)->stqh_last = &STAILQ_NEXT((elm), field); \ } while (0)

#define STAILQ_LAST(head, type, field) \ (STAILQ_EMPTY(head) ? \ NULL : \ ((struct type *) \ ((char *)((head)->stqh_last) - offsetof(struct type, field))))

#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)

#define STAILQ_REMOVE(head, elm, type, field) do {
       \ if (STAILQ_FIRST((head)) == (elm)) {
       \ STAILQ_REMOVE_HEAD(head, field); \ } \ else {
       \ struct type *curelm = STAILQ_FIRST((head)); \ while (STAILQ_NEXT(curelm, field) != (elm)) \ curelm = STAILQ_NEXT(curelm, field); \ if ((STAILQ_NEXT(curelm, field) = \ STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ } \ } while (0)

#define STAILQ_REMOVE_HEAD(head, field) do {
       \ if ((STAILQ_FIRST((head)) = \ STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ (head)->stqh_last = &STAILQ_FIRST((head)); \ } while (0)

#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {
       \ if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ (head)->stqh_last = &STAILQ_FIRST((head)); \ } while (0)

#define STAILQ_REMOVE_AFTER(head, elm, field) do {
       \ if ((STAILQ_NEXT(elm, field) = \ STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ (head)->stqh_last = &STAILQ_NEXT((elm), field); \ } while (0)

give an example

Let's take an example , Examples come from ：https://manpages.courier-mta.org/htmlman3/stailq.3.html

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

struct entry {
    
    int data;
    STAILQ_ENTRY(entry) entries;        /* Singly linked tail queue */
};

STAILQ_HEAD(stailhead, entry);

int
main(void)
{
    
    struct entry *n1, *n2, *n3, *np;
    struct stailhead head;                  /* Singly linked tail queue head */

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

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

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

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

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

    n3 = STAILQ_FIRST(&head);
    STAILQ_REMOVE_HEAD(&head, entries);     /* Deletion from the head */
    free(n3);

    n1 = STAILQ_FIRST(&head);
    n1->data = 0;
    for (int i = 1; i < 5; i++) {
    
        n1 = malloc(sizeof(struct entry));
        STAILQ_INSERT_HEAD(&head, n1, entries);
        n1->data = i;
    }
                                            /* Forward traversal */
    STAILQ_FOREACH(np, &head, entries)
        printf("%i\n", np->data);
                                            /* TailQ deletion */
    n1 = STAILQ_FIRST(&head);
    while (n1 != NULL) {
    
        n2 = STAILQ_NEXT(n1, entries);
        free(n1);
        n1 = n2;
    }
    STAILQ_INIT(&head);

    exit(EXIT_SUCCESS);
}

The code analysis

STAILQ_ENTRY and STAILQ_HEAD

struct entry {
    
    int data;
    STAILQ_ENTRY(entry) entries;        /* Singly linked tail queue */
};

STAILQ_HEAD(stailhead, entry);

The macro is replaced by

struct entry {
    
    int data;
    struct {
     
        struct entry *stqe_next; 
    } entries;
};

struct stailhead {
     
    struct entry *stqh_first; 
    struct entry **stqh_last; 
};

Actually sum SLIST almost , The only difference is 10 That's ok , There is an extra pointer to the tail node （ To be exact, it points to the tail node stqe_next）

STAILQ_INIT and STAILQ_INSERT_HEAD

    struct entry *n1, *n2, *n3, *np;
    struct stailhead head;                  /* Singly linked tail queue head */

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

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

5： Macro expansion yes

(&head)->stqh_first = ((void *)0); 
(&head)->stqh_last = &(&head)->stqh_first; 

The initialization of the linked list is empty ,stqh_first be equal to NULL,stqh_last self-directed stqh_first

8： Macro expansion yes

if (((n1)->entries.stqe_next = (&head)->stqh_first) == ((void *)0)) 
	(&head)->stqh_last = &(n1)->entries.stqe_next; 
(&head)->stqh_first = (n1); 

hold n1 Insert the first position of the linked list , Which pointer value will be affected ？

1. stqh_first
2. n1 Of stqe_next
3. If the list is empty , So insert n1 after ,stqh_last Change, too

The first 1 OK, it's solved 2

The first 2 OK, it's solved 3

The first 3 OK, it's solved 1

STAILQ_INSERT_TAIL

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

2： Macro replacement is

    (n1)->entries.stqe_next = ((void *)0); 
    *(&head)->stqh_last = (n1); 
    (&head)->stqh_last = &(n1)->entries.stqe_next; 

hold n1 Insert the last position of the linked list , Which pointer values will be affected ？

1. stqh_last
2. n1 Of stqe_next, Need to be for NULL
3. The original last node （ The assumption is n8） Of stqe_next

The first 1 OK, it's solved 2

The first 2 OK, a little trouble ,(&head)->stqh_last Point to n8 Node stqe_next,*(&head)->stqh_last Namely n8 Node stqe_next, assignment n1 Give it , It's solved 3

The first 3 OK, it's solved 1

STAILQ_INSERT_AFTER

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

The first 2 OK means to put n2 Insert into n1 Behind

After the code is expanded

if (((n2)->entries.stqe_next = (n1)->entries.stqe_next) == ((void *)0)) 
    (&head)->stqh_last = &(n2)->entries.stqe_next; 
(n1)->entries.stqe_next = (n2);

hold n2 Insert into n1 Behind , Which pointer values will be affected ？

1. n1 Of stqe_next
2. n2 Of stqe_next
3. If n2 It's the last node , Still have to amend (&head)->stqh_last

The first 1 Yes (n2)->entries.stqe_next = (n1)->entries.stqe_next) It's solved 2

The first 3 OK, it's solved 1

The first 2 OK, it's solved 3

STAILQ_REMOVE

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

The first 1 Row expansion yes , A little longer

if ((&head)->stqh_first == (n2)) {
     
    if ((((&head))->stqh_first = ((&head))->stqh_first->entries.stqe_next) == ((void *)0)) 
        ((&head))->stqh_last = &((&head))->stqh_first; 
} else {
     
    struct entry *curelm = (&head)->stqh_first; 
    while (curelm->entries.stqe_next != (n2)) 
        curelm = curelm->entries.stqe_next; 
    if ((curelm->entries.stqe_next = curelm->entries.stqe_next->entries.stqe_next) == ((void *)0)) 
        (&head)->stqh_last = &(curelm)->entries.stqe_next; 
} 

branch 2 In this case .n2 Is it the first node （ The first 1 Line code ）, If it is , The pointers that need to be modified are

1. (&head)->stqh_first
2. If n2 Is the only node , Then you need to modify (&head))->stqh_last

The first 2 The first half of the line solves 1

The first 3 OK, it's solved 2

If n2 Not the first node , Then perform 5-10, To find the first n2 (6-7 That's ok ), When it's found , curelm representative n2 The front node . The pointers that need to be modified at this time are ：

1. curelm Of stqe_next
2. If n2 It's the last node , It needs to be modified after deletion (&head))->stqh_last

The first 8 The first half of the line solves 1

The first 9 OK, it's solved 2

STAILQ_FIRST and STAILQ_REMOVE_HEAD

    n3 = STAILQ_FIRST(&head);
    STAILQ_REMOVE_HEAD(&head, entries);     /* Deletion from the head */
    free(n3);

STAILQ_FIRST Relatively simple , Is to get the first node of the linked list , Be careful , Not delete

The first 1 OK, expand ：n3 = ((&head)->stqh_first);

STAILQ_REMOVE_HEAD Is to delete the first node

The first 2 OK, expand ：

if (((&head)->stqh_first = (&head)->stqh_first->entries.stqe_next) == ((void *)0)) 
    (&head)->stqh_last = &(&head)->stqh_first; 

If before deletion , Only one node , Then it needs to be modified stqh_last, That is the first. 2 That's ok

If you have multiple nodes , Then just modify stqh_first（ The first 1 The first half of the line ）

STAILQ_FOREACH

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

STAILQ_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 .

The first 2 OK, expand ：

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

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

(np)->entries.stqe_next This sentence is wrong .

STAILQ_NEXT

/* TailQ deletion */
    n1 = STAILQ_FIRST(&head);
    while (n1 != NULL) {
    
        n2 = STAILQ_NEXT(n1, entries);
        free(n1);
        n1 = n2;
    }

STAILQ_NEXT(n1, entries) It means take n1 The next node of

The first 4 Row expansion yes n2 = ((n1)->entries.stqe_next); Relatively simple .

This code also shows how to delete the entire linked list .

How many macros are there , There is no use in the example , Let's have a look .

STAILQ_EMPTY

#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)

It's easy to understand , No explanation. .

STAILQ_LAST

#define STAILQ_LAST(head, type, field) \ (STAILQ_EMPTY(head) ? \ NULL : \ ((struct type *) \ ((char *)((head)->stqh_last) - offsetof(struct type, field))))

Be careful , my Linux On the operating system , This macro is not included , therefore , If you want to use , You need to include this code manually .

The meaning of this macro is to find the last node of the queue . It works like this ：

n1 = STAILQ_LAST(&head, entry, entries);

At the beginning of this article , Yes

struct entry {
    
    int data;
    STAILQ_ENTRY(entry) entries;        /* Singly linked tail queue */
};

STAILQ_HEAD(stailhead, entry);

n1 = STAILQ_LAST(&head, entry, entries) The last two parameters of should correspond to 3 Definition of line .

Let's look back STAILQ_LAST Code for

#define STAILQ_LAST(head, type, field) \ (STAILQ_EMPTY(head) ? \ NULL : \ ((struct type *) \ ((char *)((head)->stqh_last) - offsetof(struct type, field))))

If the list is empty , Just go back to NULL, What if it is not empty ？ Of course, follow (head)->stqh_last Find the right last node .

The problem is ,(head)->stqh_last It points to the last node entries.stqe_next Domain

struct entry {
    
    int data;
    struct {
     
        struct entry *stqe_next; 
    } entries;
};

That is the first. 4 That's ok ,(head)->stqh_last The value of is struct entry *stqe_next The address of , instead of struct entry The address of , So we need to change . Conversion needs to use

offsetof(struct type, field)

This is also a macro , The code is probably /usr/src/linux-headers-4.8.0-36-generic/include/linux/stddef.h

#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)

there TYPE Represents a structure type ,MEMBER Represents a member in the structure , This macro calculates the position offset of the member in the structure （ In bytes ）

Suppose a structural variable （ The type is struct entry） The starting address of is 0x1234, One of its members is data, Excuse me, data What is the address of the variable ？

You can ask ：

&((struct entry *)0x1234)->data

-> Higher priority than type conversion , So we need to add parentheses .((struct entry *)0x1234)->data You get members , Take the address again , Get the address of the member , Another type conversion , Turn to unsigned integer ：

(size_t)&((struct entry *)0x1234)->data

Finally get the starting address of the member , At this time, let's look at its offset from the starting address of the structure variable ？ That is, subtract the address of the structure variable from the address of the member ：

(size_t)&((struct entry *)0x1234)->data - 0x1234

It's not hard to see. , there 0x1234 You can change it into any number , Because the offset is a relative quantity , It has nothing to do with the starting address

For simplicity , Then put 0x1234 Switch to 0 Well .

We do general treatment , hold struct entry It's called TYPE, hold data It's called MEMBER, So there it is

((size_t)&((TYPE *)0)->MEMBER)

Let's get back to the point ,(head)->stqh_last The value of is struct entry *stqe_next The address of , instead of struct entry The address of ,* If we knew struct entry stqe_next be relative to struct entry The migration x, Then use (head)->stqh_last subtract x That's all right. .

utilize offsetof(struct type, field) To find the offset , At the same time, notice struct entry *stqe_next and entries It's the same address , So the offset is ：offsetof(struct entry , entries )

The address of the last node is ：

(struct entry *)((char*)((head)->stqh_last) - offsetof(struct entry, entries)))

Generalize the above formula ,entry Switch to type,entries Switch to field, You get the ：

 ((struct type *)					\
		((char *)((head)->stqh_last) - offsetof(struct type, field))))

There's actually a simpler way , Directly use the container_of macro , Here is just a hint , I'm not going to expand it .

【end】