当前位置:网站首页>Circleq of linked list
Circleq of linked list
2022-07-05 08:06:00 【Car chezi】
List of articles
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 ?
- elm Of field.cqe_next, Because it is the last , So it should be equal to (void *)(head)
- elm Of field.cqe_prev
- After inserting ,elm Of the previous node field.cqe_next( If the previous node is the header , Then modify
CIRCLEQ_FIRST(head)
) - 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 ?
- elm Of field.cqe_next
- elm Of field.cqe_prev, It should be equal to (void *)(head)
- (head)->cqh_first
- 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 ?
- elm Of field.cqe_next
- elm Of field.cqe_prev
- listelm Of field.cqe_next
- 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 ?
- elm Of field.cqe_next
- elm Of field.cqe_prev
- listelm Of field.cqe_prev
- 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 ?
elm Of the previous node field.cqe_next
elm At the next node field.cqe_prev
about 1, If elm The previous node is head, Then it needs to be modified CIRCLEQ_FIRST(head)
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】
边栏推荐
- WiFi wpa_ Detailed description of supplicant hostpad interface
- Verilog -- state machine coding method
- How to migrate the device data accessed by the RTSP of the easycvr platform to easynvr?
- C # joint configuration with Halcon
- [tutorial 19 of trio basic from introduction to proficiency] detailed introduction of trio as a slave station connecting to the third-party bus (anybus PROFIBUS DP...)
- Sql Server的存儲過程詳解
- Programming knowledge -- basis of C language
- Baiwen 7-day smart home learning experience of Internet of things
- [untitled] record the visual shock of the Winter Olympics and the introduction of the display screen
- Cadence simulation encountered "input.scs": can not open input file change path problem
猜你喜欢
Altium designer learning (I)
Altium designer 19.1.18 - clear information generated by measuring distance
Measurement fitting based on Halcon learning [III] PM_ measure_ board. Hdev routine
Reasons for rapid wear of conductive slip rings
Semiconductor devices (I) PN junction
LED display equipment records of the opening ceremony of the Beijing Winter Olympics
Hardware 1 -- relationship between gain and magnification
Can't find real-time chat software? Recommend to you what e-commerce enterprises are using!
Class of color image processing based on Halcon learning_ ndim_ norm. hdev
Network communication model -- Network OSI tcp/ip layering
随机推荐
Altium designer 19.1.18 - change the transparency of copper laying
MLPerf Training v2.0 榜单发布,在同等GPU配置下百度飞桨性能世界第一
Correlation based template matching based on Halcon learning [II] find_ ncc_ model_ defocused_ precision. hdev
After installing the new version of keil5 or upgrading the JLINK firmware, you will always be prompted about the firmware update
Extern keyword function
Ten thousand words detailed eight sorting must read (code + dynamic diagram demonstration)
Global and Chinese market of urban rail connectors 2022-2028: Research Report on technology, participants, trends, market size and share
C WinForm [exit application] - practice 3
【云原生 | 从零开始学Kubernetes】三、Kubernetes集群管理工具kubectl
Record the torch encountered by win10 cuda. is_ False problem in available()
IC software learning
C, Numerical Recipes in C, solution of linear algebraic equations, LU decomposition source program
C WinForm [view status bar -- statusstrip] - Practice 2
Create inf module in AMI code
Factors affecting the quality of slip rings in production
C WinForm [change the position of the form after running] - Practical Exercise 4
Network communication model -- Network OSI tcp/ip layering
Introduction of air gap, etc
Volatile of C language
导电滑环磨损快的原因