当前位置:网站首页>List of linked lists
List of linked lists
2022-07-05 08:06:00 【Car chezi】
List of articles
Last blog post Linked list SLIST_ The car (chezi)-CSDN Blog Said ,queue.h There are 5 Species linked list , Namely :
- SLIST
- LIST
- STAILQ
- TAILQ
- 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
- n1 Of entries.le_next
- n2 Of entries.le_next
- n2 Of entries.le_prev
- 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
- n2 Of entries.le_prev
- n3 Of entries.le_next
- n3 Of entries.le_prev
- 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
- n2 The front node ( The assumption is n1) Of entries.le_next
- 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
边栏推荐
- Record the torch encountered by win10 cuda. is_ False problem in available()
- Altium designer 19.1.18 - clear information generated by measuring distance
- Shell脚本基本语法
- Live555 push RTSP audio and video stream summary (III) flower screen problem caused by pushing H264 real-time stream
- Ten thousand words detailed eight sorting must read (code + dynamic diagram demonstration)
- Design a clock frequency division circuit that can be switched arbitrarily
- My-basic application 1: introduction to my-basic parser
- Pointnet++ classification practice
- Markdown tips
- Network communication model -- Network OSI tcp/ip layering
猜你喜欢
Shape template matching based on Halcon learning [VII] reuse_ model. Hdev routine
Consul安装
C language # and #
UEFI development learning 6 - creation of protocol
Cadence simulation encountered "input.scs": can not open input file change path problem
Hardware and software solution of FPGA key chattering elimination
Shell script basic syntax
UEFI development learning 3 - create UEFI program
Programming knowledge -- basis of C language
Measurement fitting based on Halcon learning [II] meaure_ pin. Hdev routine
随机推荐
IC software learning
Random function usage notes
Gradle composite construction
Shape template matching based on Halcon learning [viii] PM_ multiple_ models. Hdev routine
Imx6ull bare metal development learning 1-assembly lit LED
Hardware and software solution of FPGA key chattering elimination
C # joint configuration with Halcon
Sql Server的存储过程详解
C WinForm [change the position of the form after running] - Practical Exercise 4
PMSM dead time compensation
Explain task scheduling based on Cortex-M3 in detail (Part 1)
Semiconductor devices (I) PN junction
C WinForm [realize the previous and next selection pictures] - practice 7
Class of color image processing based on Halcon learning_ ndim_ norm. hdev
Altium designer 19.1.18 - change the transparency of copper laying
Shape template matching based on Halcon learning [v] find_ cocoa_ packages_ max_ deformation. Hdev routine
Live555 push RTSP audio and video stream summary (I) cross compilation
C WinForm [display real-time time in the status bar] - practical exercise 1
Soem EtherCAT source code analysis II (list of known configuration information)
LED display equipment records of the opening ceremony of the Beijing Winter Olympics