Hello everyone, I am the Mixed Bag Master.
queue.h is a header file in Linux and FreeBSD.
FreeBSD: FreeBSD is a UNIX-like operating system.
This is a very practical header file because it contains all macro definitions, making it usable not only in Linux/Embedded Linux projects but also conveniently in microcontroller projects.
It implements the following data structures using macros:
- SLIST: Singly linked list without a tail
- LIST: Doubly linked list without a tail
- STAILQ: Singly linked list with a tail (can be used as a queue)
- TAILQ: Doubly linked list with a tail (can be used as a queue)
All data structures support the following functionalities:
- Insert a node at the head of the list
- Insert a node after any given node
- Delete a node
- Traverse nodes
We can find this header file in the following path on a Linux system:
/usr/include/sys/queue.h
It can also be viewed at the following URL:
https://code.woboq.org/userspace/glibc/misc/sys/queue.h.html
Usage of sys/queue.h
Next, we will demonstrate its usage based on SLIST.
SLIST related macro definitions:
/*
* Singly-linked List definitions.
*/
#define SLIST_HEAD(name, type) \
struct name { \
struct type *slh_first; /* first element */ \
}
#define SLIST_HEAD_INITIALIZER(head) \
{ NULL }
#define SLIST_ENTRY(type) \
struct { \
struct type *sle_next; /* next element */ \
}
/*
* Singly-linked List functions.
*/
#define SLIST_INIT(head) do { \
(head)->slh_first = NULL; \
} while (/*CONSTCOND*/0)
#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
(elm)->field.sle_next = (slistelm)->field.sle_next; \
(slistelm)->field.sle_next = (elm); \
} while (/*CONSTCOND*/0)
#define SLIST_INSERT_HEAD(head, elm, field) do { \
(elm)->field.sle_next = (head)->slh_first; \
(head)->slh_first = (elm); \
} while (/*CONSTCOND*/0)
#define SLIST_REMOVE_HEAD(head, field) do { \
(head)->slh_first = (head)->slh_first->field.sle_next; \
} while (/*CONSTCOND*/0)
#define SLIST_REMOVE(head, elm, type, field) do { \
if ((head)->slh_first == (elm)) { \
SLIST_REMOVE_HEAD((head), field); \
} \
else { \
struct type *curelm = (head)->slh_first; \
while(curelm->field.sle_next != (elm)) \
curelm = curelm->field.sle_next; \
curelm->field.sle_next = \
curelm->field.sle_next->field.sle_next; \
} \
} while (/*CONSTCOND*/0)
#define SLIST_FOREACH(var, head, field) \
for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
/*
* Singly-linked List access methods.
*/
#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
#define SLIST_FIRST(head) ((head)->slh_first)
#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
Next, we will operate through an example.
First, create the head node of the list and other node structures using the SLIST_HEAD and SLIST_ENTRY macros:
#define ELEM_TYPE int
/* Linked list node */
typedef struct node
{
ELEM_TYPE data;
SLIST_ENTRY(node) field;
}node_st;
/* Linked list head */
typedef SLIST_HEAD(head, node) head_st;
We define the data type of the linked list as int, and field represents the pointer field.
① Create a head node:
/* Create and initialize the head node of the linked list */
head_st *head = (head_st *)malloc(sizeof(head_st));
SLIST_INIT(head);
Head node: An empty node that does not store any data, usually serves as the first node of the linked list.
② Insert nodes node1 and node2 at the head of the linked list:
/* Insert a node node1 at the head */
node_st *node1 = (node_st *)malloc(sizeof(node_st));
node1->data = 1;
SLIST_INSERT_HEAD(head, node1, field);
/* Insert a node node2 at the head */
node_st *node2 = (node_st *)malloc(sizeof(node_st));
node2->data = 2;
SLIST_INSERT_HEAD(head, node2, field);
Head pointer: Always points to the position of the first node in the linked list.
SLIST_INSERT_HEAD inserts a node from the head of the list, with the new node always inserted after the head node.
③ Insert node3 after node2 in the linked list:
node_st *node3 = (node_st *)malloc(sizeof(node_st));
node3->data = 3;
SLIST_INSERT_AFTER(node2, node3, field);
SLIST_INSERT_AFTER inserts a new node elm after the specified node slistelm.
④ Traverse the linked list:
node_st *tmp_elm;
SLIST_FOREACH(tmp_elm, head, field)
{
printf("%d ", tmp_elm->data);
}
The output is accessed via tmp_elm.
⑤ Delete a specific node node2:
SLIST_REMOVE(head, node2, node, field);
free(node2);
node2 = NULL;
⑥ Destroy the entire linked list:
while (!SLIST_EMPTY(head))
{
node_st *p = SLIST_FIRST(head);
SLIST_REMOVE_HEAD(head, field);
free(p);
p = NULL;
}
free(head);
head = NULL;
Complete test code:
#include <stdio.h>
#include <stdlib.h>
#include <sys/queue.h>
#define ELEM_TYPE int
/* Linked list node */
typedef struct node
{
ELEM_TYPE data;
SLIST_ENTRY(node) field;
}node_st;
/* Linked list head */
typedef SLIST_HEAD(head, node) head_st;
int main(void)
{
/* Create and initialize the head node of the linked list */
head_st *head = (head_st *)malloc(sizeof(head_st));
SLIST_INIT(head);
/* Insert a node node1 at the head */
node_st *node1 = (node_st *)malloc(sizeof(node_st));
node1->data = 1;
SLIST_INSERT_HEAD(head, node1, field);
/* Insert a node node2 at the head */
node_st *node2 = (node_st *)malloc(sizeof(node_st));
node2->data = 2;
SLIST_INSERT_HEAD(head, node2, field);
/* Traverse and print the current linked list nodes */
printf("list:\n");
node_st *tmp_elm;
SLIST_FOREACH(tmp_elm, head, field)
{
printf("%d ", tmp_elm->data);
}
printf("\n");
/* Insert a node node3 at the tail */
printf("insert node3:\n");
node_st *node3 = (node_st *)malloc(sizeof(node_st));
node3->data = 3;
SLIST_INSERT_AFTER(node2, node3, field);
SLIST_FOREACH(tmp_elm, head, field)
{
printf("%d ", tmp_elm->data);
}
printf("\n");
/* Delete node2 */
printf("delete node2:\n");
SLIST_REMOVE(head, node2, node, field);
free(node2);
node2 = NULL;
SLIST_FOREACH(tmp_elm, head, field)
{
printf("%d ", tmp_elm->data);
}
printf("\n");
/* Destroy the linked list */
while (!SLIST_EMPTY(head))
{
node_st *p = SLIST_FIRST(head);
SLIST_REMOVE_HEAD(head, field);
free(p);
p = NULL;
}
free(head);
head = NULL;
return 0;
}
Compile and run:
The results are consistent with our analysis above.
This time we only shared the simplest data structure in queue.h. Examples of other data structures and related macro descriptions can be viewed using the man command.
man is a help command in Linux.
We can input <span>man queue</span> to find the relevant description of queue.h:
As we can see, the man command is very powerful, providing detailed help instructions for queue, including macro descriptions and usage examples.
That concludes our sharing for this time, see you next time~
END
Source:Embedded Mixed Bag
Copyright belongs to the original author, if there is any infringement, please contact for deletion..▍Recommended ReadingSharing several BootLoaders suitable for MCUWhy some domestic chips do not disclose data sheets?Incredible! These 17 C pointer tricks have been collected overnight by countless programmers→ Follow for more updates ←