Circleq of linked list

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 .

/*
 * Circular queue declarations.
 */
#define	CIRCLEQ_HEAD(name, type)					\
struct name {								\
	struct type *cqh_first;		/* first element */		\
	struct type *cqh_last;		/* last element */		\
}

#define	CIRCLEQ_HEAD_INITIALIZER(head)					\
	{ (void *)&(head), (void *)&(head) }

#define	CIRCLEQ_ENTRY(type)						\
struct {								\
	struct type *cqe_next;		/* next element */		\
	struct type *cqe_prev;		/* previous element */		\
}

/*
 * Circular queue functions.
 */
#define	CIRCLEQ_EMPTY(head)	((head)->cqh_first == (void *)(head))

#define	CIRCLEQ_FIRST(head)	((head)->cqh_first)

#define	CIRCLEQ_FOREACH(var, head, field)				\
	for ((var) = CIRCLEQ_FIRST((head));				\
	    (var) != (void *)(head) || ((var) = NULL);			\
	    (var) = CIRCLEQ_NEXT((var), field))

#define	CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
	for ((var) = CIRCLEQ_LAST((head));				\
	    (var) != (void *)(head) || ((var) = NULL);			\
	    (var) = CIRCLEQ_PREV((var), field))

#define	CIRCLEQ_INIT(head) do {						\
	CIRCLEQ_FIRST((head)) = (void *)(head);				\
	CIRCLEQ_LAST((head)) = (void *)(head);				\
} while (0)

#define	CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
	CIRCLEQ_NEXT((elm), field) = CIRCLEQ_NEXT((listelm), field);	\
	CIRCLEQ_PREV((elm), field) = (listelm);				\
	if (CIRCLEQ_NEXT((listelm), field) == (void *)(head))		\
		CIRCLEQ_LAST((head)) = (elm);				\
	else								\
		CIRCLEQ_PREV(CIRCLEQ_NEXT((listelm), field), field) = (elm);\
	CIRCLEQ_NEXT((listelm), field) = (elm);				\
} while (0)

#define	CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
	CIRCLEQ_NEXT((elm), field) = (listelm);				\
	CIRCLEQ_PREV((elm), field) = CIRCLEQ_PREV((listelm), field);	\
	if (CIRCLEQ_PREV((listelm), field) == (void *)(head))		\
		CIRCLEQ_FIRST((head)) = (elm);				\
	else								\
		CIRCLEQ_NEXT(CIRCLEQ_PREV((listelm), field), field) = (elm);\
	CIRCLEQ_PREV((listelm), field) = (elm);				\
} while (0)

#define	CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
	CIRCLEQ_NEXT((elm), field) = CIRCLEQ_FIRST((head));		\
	CIRCLEQ_PREV((elm), field) = (void *)(head);			\
	if (CIRCLEQ_LAST((head)) == (void *)(head))			\
		CIRCLEQ_LAST((head)) = (elm);				\
	else								\
		CIRCLEQ_PREV(CIRCLEQ_FIRST((head)), field) = (elm);	\
	CIRCLEQ_FIRST((head)) = (elm);					\
} while (0)

#define	CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
	CIRCLEQ_NEXT((elm), field) = (void *)(head);			\
	CIRCLEQ_PREV((elm), field) = CIRCLEQ_LAST((head));		\
	if (CIRCLEQ_FIRST((head)) == (void *)(head))			\
		CIRCLEQ_FIRST((head)) = (elm);				\
	else								\
		CIRCLEQ_NEXT(CIRCLEQ_LAST((head)), field) = (elm);	\
	CIRCLEQ_LAST((head)) = (elm);					\
} while (0)

#define	CIRCLEQ_LAST(head)	((head)->cqh_last)

#define	CIRCLEQ_NEXT(elm,field)	((elm)->field.cqe_next)

#define	CIRCLEQ_PREV(elm,field)	((elm)->field.cqe_prev)

#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
	if (CIRCLEQ_NEXT((elm), field) == (void *)(head))		\
		CIRCLEQ_LAST((head)) = CIRCLEQ_PREV((elm), field);	\
	else								\
		CIRCLEQ_PREV(CIRCLEQ_NEXT((elm), field), field) =	\
		    CIRCLEQ_PREV((elm), field);				\
	if (CIRCLEQ_PREV((elm), field) == (void *)(head))		\
		CIRCLEQ_FIRST((head)) = CIRCLEQ_NEXT((elm), field);	\
	else								\
		CIRCLEQ_NEXT(CIRCLEQ_PREV((elm), field), field) =	\
		    CIRCLEQ_NEXT((elm), field);				\
} while (0)

Example

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include "bsd_queue.h" //  It's the code I posted above 

struct entry {
    
    int data;
    CIRCLEQ_ENTRY(entry) entries;           /* Queue */
};

CIRCLEQ_HEAD(circlehead, entry);


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

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

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

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

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

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

    CIRCLEQ_REMOVE(&head, n2, entries);     /* Deletion */
    free(n2);
                                            /* Forward traversal */
    i = 0;
    CIRCLEQ_FOREACH(np, &head, entries)
        np->data = i++;
                                            /* Reverse traversal */
    CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
        printf("%i\n", np->data);
                                            /* Queue deletion */
    n1 = CIRCLEQ_FIRST(&head);
    while (n1 != (void *)&head) {
    
        n2 = CIRCLEQ_NEXT(n1, entries);
        free(n1);
        n1 = n2;
    }
    CIRCLEQ_INIT(&head);

    exit(EXIT_SUCCESS);
}

The code analysis

Let's look at the above examples bit by bit .

Let's start with a diagram drawn by myself . Red means I don't feel very “ normal ” The place of , The type of the pointer does not match , Cast required .

CIRCLEQ_ENTRY and CIRCLEQ_HEAD

struct entry {
    
    int data;
    CIRCLEQ_ENTRY(entry) entries;           /* Queue */
};

CIRCLEQ_HEAD(circlehead, entry);

Macro expansion yes ：

struct entry {
    
    int data;
    struct {
     
        struct entry *cqe_next; 
        struct entry *cqe_prev; 
    } entries;
};
struct circlehead {
     
    struct entry *cqh_first; 
    struct entry *cqh_last; 
};

Different from other linked lists , There is no secondary pointer ,cqe_prev and cqh_last All are struct entry * type .（ Why? ）

The previous articles I wrote are all about studying the code after Hongzhan , Let's change our thinking this time , Look directly at the definition of macros

CIRCLEQ_HEAD_INITIALIZER

#define CIRCLEQ_HEAD_INITIALIZER(head) \ {
       (void *)&(head), (void *)&(head) }

After initializing a linked list , Both pointers of the header point to themselves .

CIRCLEQ_FIRST and CIRCLEQ_LAST

#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
#define CIRCLEQ_LAST(head) ((head)->cqh_last)

These two are easy to understand , No explanation. .

CIRCLEQ_PREV and CIRCLEQ_NEXT

#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next)

field Is the first definition of entries

CIRCLEQ_INIT

#define CIRCLEQ_INIT(head) do {
       \ CIRCLEQ_FIRST((head)) = (void *)(head); \ CIRCLEQ_LAST((head)) = (void *)(head); \ } while (0)

After initializing a linked list , Both pointers of the header point to themselves . Here's the picture

CIRCLEQ_EMPTY

#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))

CIRCLEQ_INSERT_TAIL

#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {
       \ CIRCLEQ_NEXT((elm), field) = (void *)(head); \ CIRCLEQ_PREV((elm), field) = CIRCLEQ_LAST((head)); \ if (CIRCLEQ_FIRST((head)) == (void *)(head)) \ CIRCLEQ_FIRST((head)) = (elm); \ else \ CIRCLEQ_NEXT(CIRCLEQ_LAST((head)), field) = (elm); \ CIRCLEQ_LAST((head)) = (elm); \ } while (0)

hold elm Insert at the end of the list , Which pointers need to be changed ？

1. elm Of field.cqe_next, Because it is the last , So it should be equal to (void *)(head)
2. elm Of field.cqe_prev
3. After inserting ,elm Of the previous node field.cqe_next（ If the previous node is the header , Then modify CIRCLEQ_FIRST(head) ）
4. modify (head)->cqh_last Point to elm

Code No. 2、3 OK, solve it separately 1、2

Code No. 4、5 OK, it's solved 3 The situation in brackets

The first 7 OK, it's solved 3,elm The previous node is the original last node ,CIRCLEQ_LAST(head), its cqe_next Namely CIRCLEQ_NEXT(CIRCLEQ_LAST((head)), field)

The first 8 OK, it's solved 4

CIRCLEQ_INSERT_HEAD

#define	CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
	CIRCLEQ_NEXT((elm), field) = CIRCLEQ_FIRST((head));		\
	CIRCLEQ_PREV((elm), field) = (void *)(head);			\
	if (CIRCLEQ_LAST((head)) == (void *)(head))			\
		CIRCLEQ_LAST((head)) = (elm);				\
	else								\
		CIRCLEQ_PREV(CIRCLEQ_FIRST((head)), field) = (elm);	\
	CIRCLEQ_FIRST((head)) = (elm);					\
} while (0)

hold elm Insert into the head of the list , Which pointers need to be changed ？

1. elm Of field.cqe_next
2. elm Of field.cqe_prev, It should be equal to (void *)(head)
3. (head)->cqh_first
4. After inserting ,elm The next node field.cqe_prev（ If you insert elm The front linked list is empty , Then modify CIRCLEQ_LAST(head) ）

The first 2 OK, it's solved 1

The first 3 OK, it's solved 2

The first 4-5 OK, it's solved 4 The situation in brackets

The first 7 OK, it's solved 4

The first 8 OK, it's solved 3

Code 4-7 Line description , Because there is no secondary pointer , Therefore, we need to consider the situation when inserting the head . But there are also advantages to not using secondary pointers , That is, the code is better understood .

CIRCLEQ_INSERT_AFTER

#define	CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
	CIRCLEQ_NEXT((elm), field) = CIRCLEQ_NEXT((listelm), field);	\
	CIRCLEQ_PREV((elm), field) = (listelm);				\
	if (CIRCLEQ_NEXT((listelm), field) == (void *)(head))		\
		CIRCLEQ_LAST((head)) = (elm);				\
	else								\
		CIRCLEQ_PREV(CIRCLEQ_NEXT((listelm), field), field) = (elm);\
	CIRCLEQ_NEXT((listelm), field) = (elm);				\
} while (0)

To put elm Insert into listelm After element , Which pointers should be modified ？

1. elm Of field.cqe_next
2. elm Of field.cqe_prev
3. listelm Of field.cqe_next
4. Before insertion ,listelm The next node field.cqe_prev（ If listelm There are no nodes behind , Just modify CIRCLEQ_LAST(head)）

2-3 OK, solve it separately 1、2

4-5 OK, it's solved 4 The situation in brackets

The first 7 OK, it's solved 4

The first 8 OK, it's solved 3

CIRCLEQ_INSERT_BEFORE

#define	CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
	CIRCLEQ_NEXT((elm), field) = (listelm);				\
	CIRCLEQ_PREV((elm), field) = CIRCLEQ_PREV((listelm), field);	\
	if (CIRCLEQ_PREV((listelm), field) == (void *)(head))		\
		CIRCLEQ_FIRST((head)) = (elm);				\
	else								\
		CIRCLEQ_NEXT(CIRCLEQ_PREV((listelm), field), field) = (elm);\
	CIRCLEQ_PREV((listelm), field) = (elm);				\
} while (0)

To put elm Insert into listelm In front of the element , Which pointers should be modified ？

1. elm Of field.cqe_next
2. elm Of field.cqe_prev
3. listelm Of field.cqe_prev
4. Before insertion ,listelm Of the previous node field.cqe_next（ If listelm The front is the header , Just modify CIRCLEQ_FIRST(head)）

2-3 OK, solve it separately 1、2

4-5 OK, it's solved 4 The situation in brackets

The first 7 OK, it's solved 4

The first 8 OK, it's solved 3

CIRCLEQ_FOREACH

#define CIRCLEQ_FOREACH(var, head, field) \ for ((var) = CIRCLEQ_FIRST((head)); \ (var) != (void *)(head) || ((var) = NULL); \ (var) = CIRCLEQ_NEXT((var), field))

Sequential traversal , as long as (var) != (void *)(head) Will proceed , If it is equal to head, according to || Evaluation rules of operators , Will execute (var) = NULL, The result of this expression is false, So it ends for loop

CIRCLEQ_FOREACH_REVERSE

#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ for ((var) = CIRCLEQ_LAST((head)); \ (var) != (void *)(head) || ((var) = NULL); \ (var) = CIRCLEQ_PREV((var), field))

Traversal in reverse order , Similar to sequential traversal , No explanation. .

CIRCLEQ_REMOVE

#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
	if (CIRCLEQ_NEXT((elm), field) == (void *)(head))		\
		CIRCLEQ_LAST((head)) = CIRCLEQ_PREV((elm), field);	\
	else								\
		CIRCLEQ_PREV(CIRCLEQ_NEXT((elm), field), field) =	\
		    CIRCLEQ_PREV((elm), field);				\
	if (CIRCLEQ_PREV((elm), field) == (void *)(head))		\
		CIRCLEQ_FIRST((head)) = CIRCLEQ_NEXT((elm), field);	\
	else								\
		CIRCLEQ_NEXT(CIRCLEQ_PREV((elm), field), field) =	\
		    CIRCLEQ_NEXT((elm), field);				\
} while (0)

Remove node elm, Need to modify those pointers ？

1. elm Of the previous node field.cqe_next

2. elm At the next node field.cqe_prev

3. about 1, If elm The previous node is head, Then it needs to be modified CIRCLEQ_FIRST(head)

4. about 2, If elm There are no nodes behind , Then it needs to be modified CIRCLEQ_LAST(head)

Code 2-3 OK, it's solved 4

5-6 OK, it's solved 2

Code 7-8 OK, it's solved 3

10-11 It's solved 1

【end】