• 广度优先遍历一个目录下的所有文件BFS

    SIMPLEQ_INSERT_TAIL

    breadth-first-search

    * main.c

    1. #include 
    2. #include 
    3. #include "dir_tree.h"
    4.  
    5. void *fn_path(char *path, void *param) {
    6.     printf("%s\n", path);
    7. }
    8.  
    9. int main() {
    10.     char path[256];
    11.  
    12.     strncpy(path, "/mnt/e/CLionProjects/tree", 256);
    13.     /* @ref: https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/ */
    14.     dir_tree(path, fn_path, NULL);
    15.  
    16.     return 0;
    17. }

    * dir_tree.h

    1. #ifndef TREE_DIR_TREE_H
    2. #define TREE_DIR_TREE_H
    3.  
    4. typedef void *fn_path_t(char *path, void *param);
    5.  
    6. int dir_tree(const char *dirPath, fn_path_t fn, void *param);
    7.  
    8. #endif //TREE_DIR_TREE_H

    * dir_tree.c

    1. #include  /* malloc */
    2. #include  /* LIST_ENTRY, LIST_HEAD, LIST_INSERT_HEAD */
    3. #include  /* strncpy */
    4. #include  /* DIR */
    5.  
    6. #include "errlog.h"
    7. #include "dir_tree.h"
    8.  
    9. /* @ref: https://man7.org/linux/man-pages/man3/list.3.html */
    10. struct s_entry {
    11.     char data[256];
    12.     SIMPLEQ_ENTRY(s_entry) entries;              /* List */
    13. };
    14. SIMPLEQ_HEAD(stailhead, s_entry);
    15.  
    16. int dir_tree(const char *dirPath, fn_path_t fn, void *param) {
    17.     struct s_entry *n1, *n2;
    18.     struct stailhead head;                   /* List head */
    19.     DIR *dir = NULL;
    20.     struct dirent *pd = NULL;
    21.     char dir_buf[256];
    22.     char path_buf[512];
    23.  
    24.     SIMPLEQ_INIT(&head);                       /* Initialize the list */
    25.  
    26.     n1 = malloc(sizeof(struct s_entry));      /* Insert at the head */
    27.     strncpy(n1->data, dirPath, 256);
    28.     SIMPLEQ_INSERT_HEAD(&head, n1, entries);
    29.     while (!SIMPLEQ_EMPTY(&head)) {
    30.         n2 = SIMPLEQ_FIRST(&head);
    31.         strncpy(dir_buf, n2->data, 256);
    32.         SIMPLEQ_REMOVE_HEAD(&head, entries);               /* Deletion */
    33.         free(n2);
    34.  
    35.         dir = opendir(dir_buf);
    36.         if (NULL == dir) {
    37.             bclerrlog(E_OSCALL, _FL_, "opendir()");
    38.             return E_FAIL;
    39.         }
    40.         while (NULL != (pd = readdir(dir))) {
    41.             if (0 == strncmp(".", pd->d_name, 3) ||
    42.                 (0 == strncmp("..", pd->d_name, 3)))
    43.             { continue; }
    44.             if (pd->d_type == DT_DIR) {
    45.                 /* printf("d "); */
    46.                 n1 = malloc(sizeof(struct s_entry));
    47.                 strncpy(n1->data, dir_buf, 256);
    48.                 strcat(n1->data, "/"); strcat(n1->data, pd->d_name);
    49.                 SIMPLEQ_INSERT_TAIL(&head, n1, entries);
    50.             } else {
    51.                 /* printf("- "); */
    52.                 strncpy(path_buf, dir_buf, 256);
    53.                 strcat(path_buf, "/"); strcat(path_buf, pd->d_name);
    54.                 fn && fn(path_buf, param);
    55.             }
    56.             /* printf("%s/%s\n", dir_buf, pd->d_name); */
    57.         }
    58.         closedir(dir);
    59.     }
    60.     /* SIMPLEQ_FOREACH(np, &head, entries) {printf("%s\n", np->data);} */
    61.     return E_OK;
    62. }

    pd->d_type == DT_DIR, 有的系统不支持这种写法, struct dirent没有d_type字段

    1. int path_is_dir(const char *path) {
    2.     struct stat f_buf;
    3.     if (0 == strncmp(path, "stdin", 5)) {
    4.         return FALSE;
    5.     }
    6.     stat(path, &f_buf);
    7.     if (S_ISSOCK(f_buf.st_mode)) {
    8.         return FALSE;
    9.     }
    10.     return S_ISDIR(f_buf.st_mode);
    11. }

    用队列实现，不需要函数递归

    * errlog.h

    1. #ifndef TREE_ERRLOG_H
    2. #define TREE_ERRLOG_H
    3.  
    4. int bclerrlog(int appcode, char *file, long line, const char *fmt, ...);
    5.  
    6. #define E_FAIL -1
    7. #define E_OK 0
    8.  
    9. #define _FL_ __FILE__,__LINE__
    10.  
    11. #define E_MESSAGE 10000
    12. #define E_ALLOC  10300
    13. #define E_SOCKFD_SEND  10359
    14. #define E_SOCKFD_RECV  10360
    15. #define E_OSCALL    10201  /* 系统函数(%s)调用出错 */
    16. #define E_FUNCALL   10202  /* 平台函数(%s)调用出错 */
    17.  
    18. #endif //TREE_ERRLOG_H

    * errlog.c

    1. #include 
    2. #include  /* errno */
    3. #include  /* strerror */
    4. #include  /* va_start, va_end */
    5. #include    /* time_t, localtime */
    6.  
    7. #ifndef pid_t
    8. typedef int pid_t;
    9. #endif
    10. extern  pid_t getpid(void);
    11.  
    12. int bclerrlog(int appcode, char *file, long line, const char *fmt, ...) {
    13.     time_t now_time;
    14.     struct tm *info;
    15.     char dt_buf[64];
    16.     char appmsg[512];
    17.     va_list ap;
    18.  
    19.     va_start(ap, fmt);
    20.     vsnprintf(appmsg, 512, fmt, ap);
    21.  
    22.     time( &now_time );
    23.     info = localtime( &now_time );
    24.     strftime(dt_buf, 80, "%Y-%m-%d %H:%M:%S", info);
    25.     fprintf(stderr, "---- %s ----\n", dt_buf);
    26.  
    27.     fprintf(stderr, "PID: %d\tFile: %s\tLine: %ld\n", getpid(), file, line);
    28.     fprintf(stderr, "App Error: %d - %s\n", appcode, appmsg);
    29.     fprintf(stderr, "System Error: %d - %s\n", errno, strerror(errno));
    30.     va_end(ap);
    31.     return 0;
    32. }

    C:\Windows\system32\wsl.exe --distribution Ubuntu --exec /bin/bash -c "cd /mnt/e/CLionProjects/tree/cmake-build-debug && /mnt/e/CLionProjects/tree/cmake-build-debug/tree"
    /mnt/e/CLionProjects/tree/CMakeLists.txt
    /mnt/e/CLionProjects/tree/dir_tree.c
    /mnt/e/CLionProjects/tree/dir_tree.h
    /mnt/e/CLionProjects/tree/errlog.c
    /mnt/e/CLionProjects/tree/errlog.h
    /mnt/e/CLionProjects/tree/main.c
    /mnt/e/CLionProjects/tree/.idea/.gitignore
    /mnt/e/CLionProjects/tree/.idea/deployment.xml
    /mnt/e/CLionProjects/tree/.idea/misc.xml
    /mnt/e/CLionProjects/tree/.idea/modules.xml
    /mnt/e/CLionProjects/tree/.idea/tree.iml
    /mnt/e/CLionProjects/tree/.idea/workspace.xml
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeCache.txt
    /mnt/e/CLionProjects/tree/cmake-build-debug/cmake_install.cmake
    /mnt/e/CLionProjects/tree/cmake-build-debug/Makefile
    /mnt/e/CLionProjects/tree/cmake-build-debug/tree
    /mnt/e/CLionProjects/tree/cmake-build-debug/tree.cbp
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/clion-Debug-log.txt
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/clion-environment.txt
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/cmake.check_cache
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/CMakeDirectoryInformation.cmake
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/CMakeOutput.log
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/Makefile.cmake
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/Makefile2
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/progress.marks
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/TargetDirectories.txt
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/3.16.3/CMakeCCompiler.cmake
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/3.16.3/CMakeCXXCompiler.cmake
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/3.16.3/CMakeDetermineCompilerABI_C.bin
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/3.16.3/CMakeDetermineCompilerABI_CXX.bin
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/3.16.3/CMakeSystem.cmake
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/build.make
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/C.includecache
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/cmake_clean.cmake
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/CXX.includecache
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/depend.internal
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/depend.make
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/DependInfo.cmake
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/dir_tree.c.o
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/errlog.c.o
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/flags.make
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/link.txt
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/main.c.o
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/tree.dir/progress.make
    /mnt/e/CLionProjects/tree/cmake-build-debug/Testing/Temporary/LastTest.log
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/3.16.3/CompilerIdC/a.out
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/3.16.3/CompilerIdC/CMakeCCompilerId.c
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/3.16.3/CompilerIdCXX/a.out
    /mnt/e/CLionProjects/tree/cmake-build-debug/CMakeFiles/3.16.3/CompilerIdCXX/CMakeCXXCompilerId.cpp

    Process finished with exit code 0
     

    \\wsl$\Ubuntu\usr\include\x86_64-linux-gnu\sys\queue.h

    1. /*
    2.  * Copyright (c) 1991, 1993
    3.  *	The Regents of the University of California.  All rights reserved.
    4.  *
    5.  * Redistribution and use in source and binary forms, with or without
    6.  * modification, are permitted provided that the following conditions
    7.  * are met:
    8.  * 1. Redistributions of source code must retain the above copyright
    9.  *    notice, this list of conditions and the following disclaimer.
    10.  * 2. Redistributions in binary form must reproduce the above copyright
    11.  *    notice, this list of conditions and the following disclaimer in the
    12.  *    documentation and/or other materials provided with the distribution.
    13.  * 3. Neither the name of the University nor the names of its contributors
    14.  *    may be used to endorse or promote products derived from this software
    15.  *    without specific prior written permission.
    16.  *
    17.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
    18.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    19.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    20.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
    21.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
    22.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
    23.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
    24.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
    25.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
    26.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    27.  * SUCH DAMAGE.
    28.  *
    29.  *	@(#)queue.h	8.5 (Berkeley) 8/20/94
    30.  */
    31.  
    32. #ifndef	_SYS_QUEUE_H_
    33. #define	_SYS_QUEUE_H_
    34.  
    35. /*
    36.  * This file defines five types of data structures: singly-linked lists,
    37.  * lists, simple queues, tail queues, and circular queues.
    38.  *
    39.  * A singly-linked list is headed by a single forward pointer. The
    40.  * elements are singly linked for minimum space and pointer manipulation
    41.  * overhead at the expense of O(n) removal for arbitrary elements. New
    42.  * elements can be added to the list after an existing element or at the
    43.  * head of the list.  Elements being removed from the head of the list
    44.  * should use the explicit macro for this purpose for optimum
    45.  * efficiency. A singly-linked list may only be traversed in the forward
    46.  * direction.  Singly-linked lists are ideal for applications with large
    47.  * datasets and few or no removals or for implementing a LIFO queue.
    48.  *
    49.  * A list is headed by a single forward pointer (or an array of forward
    50.  * pointers for a hash table header). The elements are doubly linked
    51.  * so that an arbitrary element can be removed without a need to
    52.  * traverse the list. New elements can be added to the list before
    53.  * or after an existing element or at the head of the list. A list
    54.  * may only be traversed in the forward direction.
    55.  *
    56.  * A simple queue is headed by a pair of pointers, one the head of the
    57.  * list and the other to the tail of the list. The elements are singly
    58.  * linked to save space, so elements can only be removed from the
    59.  * head of the list. New elements can be added to the list after
    60.  * an existing element, at the head of the list, or at the end of the
    61.  * list. A simple queue may only be traversed in the forward direction.
    62.  *
    63.  * A tail queue is headed by a pair of pointers, one to the head of the
    64.  * list and the other to the tail of the list. The elements are doubly
    65.  * linked so that an arbitrary element can be removed without a need to
    66.  * traverse the list. New elements can be added to the list before or
    67.  * after an existing element, at the head of the list, or at the end of
    68.  * the list. A tail queue may be traversed in either direction.
    69.  *
    70.  * A circle queue is headed by a pair of pointers, one to the head of the
    71.  * list and the other to the tail of the list. The elements are doubly
    72.  * linked so that an arbitrary element can be removed without a need to
    73.  * traverse the list. New elements can be added to the list before or after
    74.  * an existing element, at the head of the list, or at the end of the list.
    75.  * A circle queue may be traversed in either direction, but has a more
    76.  * complex end of list detection.
    77.  *
    78.  * For details on the use of these macros, see the queue(3) manual page.
    79.  */
    80.  
    81. /*
    82.  * List definitions.
    83.  */
    84. #define	LIST_HEAD(name, type)						\
    85. struct name {								\
    86. 	struct type *lh_first;	/* first element */			\
    87. }
    88.  
    89. #define	LIST_HEAD_INITIALIZER(head)					\
    90. 	{ NULL }
    91.  
    92. #define	LIST_ENTRY(type)						\
    93. struct {								\
    94. 	struct type *le_next;	/* next element */			\
    95. 	struct type **le_prev;	/* address of previous next element */	\
    96. }
    97.  
    98. /*
    99.  * List functions.
    100.  */
    101. #define	LIST_INIT(head) do {						\
    102. 	(head)->lh_first = NULL;					\
    103. } while (/*CONSTCOND*/0)
    104.  
    105. #define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
    106. 	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
    107. 		(listelm)->field.le_next->field.le_prev =		\
    108. 		    &(elm)->field.le_next;				\
    109. 	(listelm)->field.le_next = (elm);				\
    110. 	(elm)->field.le_prev = &(listelm)->field.le_next;		\
    111. } while (/*CONSTCOND*/0)
    112.  
    113. #define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
    114. 	(elm)->field.le_prev = (listelm)->field.le_prev;		\
    115. 	(elm)->field.le_next = (listelm);				\
    116. 	*(listelm)->field.le_prev = (elm);				\
    117. 	(listelm)->field.le_prev = &(elm)->field.le_next;		\
    118. } while (/*CONSTCOND*/0)
    119.  
    120. #define	LIST_INSERT_HEAD(head, elm, field) do {				\
    121. 	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
    122. 		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
    123. 	(head)->lh_first = (elm);					\
    124. 	(elm)->field.le_prev = &(head)->lh_first;			\
    125. } while (/*CONSTCOND*/0)
    126.  
    127. #define	LIST_REMOVE(elm, field) do {					\
    128. 	if ((elm)->field.le_next != NULL)				\
    129. 		(elm)->field.le_next->field.le_prev = 			\
    130. 		    (elm)->field.le_prev;				\
    131. 	*(elm)->field.le_prev = (elm)->field.le_next;			\
    132. } while (/*CONSTCOND*/0)
    133.  
    134. #define	LIST_FOREACH(var, head, field)					\
    135. 	for ((var) = ((head)->lh_first);				\
    136. 		(var);							\
    137. 		(var) = ((var)->field.le_next))
    138.  
    139. /*
    140.  * List access methods.
    141.  */
    142. #define	LIST_EMPTY(head)		((head)->lh_first == NULL)
    143. #define	LIST_FIRST(head)		((head)->lh_first)
    144. #define	LIST_NEXT(elm, field)		((elm)->field.le_next)
    145.  
    146.  
    147. /*
    148.  * Singly-linked List definitions.
    149.  */
    150. #define	SLIST_HEAD(name, type)						\
    151. struct name {								\
    152. 	struct type *slh_first;	/* first element */			\
    153. }
    154.  
    155. #define	SLIST_HEAD_INITIALIZER(head)					\
    156. 	{ NULL }
    157.  
    158. #define	SLIST_ENTRY(type)						\
    159. struct {								\
    160. 	struct type *sle_next;	/* next element */			\
    161. }
    162.  
    163. /*
    164.  * Singly-linked List functions.
    165.  */
    166. #define	SLIST_INIT(head) do {						\
    167. 	(head)->slh_first = NULL;					\
    168. } while (/*CONSTCOND*/0)
    169.  
    170. #define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
    171. 	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
    172. 	(slistelm)->field.sle_next = (elm);				\
    173. } while (/*CONSTCOND*/0)
    174.  
    175. #define	SLIST_INSERT_HEAD(head, elm, field) do {			\
    176. 	(elm)->field.sle_next = (head)->slh_first;			\
    177. 	(head)->slh_first = (elm);					\
    178. } while (/*CONSTCOND*/0)
    179.  
    180. #define	SLIST_REMOVE_HEAD(head, field) do {				\
    181. 	(head)->slh_first = (head)->slh_first->field.sle_next;		\
    182. } while (/*CONSTCOND*/0)
    183.  
    184. #define	SLIST_REMOVE(head, elm, type, field) do {			\
    185. 	if ((head)->slh_first == (elm)) {				\
    186. 		SLIST_REMOVE_HEAD((head), field);			\
    187. 	}								\
    188. 	else {								\
    189. 		struct type *curelm = (head)->slh_first;		\
    190. 		while(curelm->field.sle_next != (elm))			\
    191. 			curelm = curelm->field.sle_next;		\
    192. 		curelm->field.sle_next =				\
    193. 		    curelm->field.sle_next->field.sle_next;		\
    194. 	}								\
    195. } while (/*CONSTCOND*/0)
    196.  
    197. #define	SLIST_FOREACH(var, head, field)					\
    198. 	for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
    199.  
    200. /*
    201.  * Singly-linked List access methods.
    202.  */
    203. #define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
    204. #define	SLIST_FIRST(head)	((head)->slh_first)
    205. #define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
    206.  
    207.  
    208. /*
    209.  * Singly-linked Tail queue declarations.
    210.  */
    211. #define	STAILQ_HEAD(name, type)					\
    212. struct name {								\
    213. 	struct type *stqh_first;	/* first element */			\
    214. 	struct type **stqh_last;	/* addr of last next element */		\
    215. }
    216.  
    217. #define	STAILQ_HEAD_INITIALIZER(head)					\
    218. 	{ NULL, &(head).stqh_first }
    219.  
    220. #define	STAILQ_ENTRY(type)						\
    221. struct {								\
    222. 	struct type *stqe_next;	/* next element */			\
    223. }
    224.  
    225. /*
    226.  * Singly-linked Tail queue functions.
    227.  */
    228. #define	STAILQ_INIT(head) do {						\
    229. 	(head)->stqh_first = NULL;					\
    230. 	(head)->stqh_last = &(head)->stqh_first;				\
    231. } while (/*CONSTCOND*/0)
    232.  
    233. #define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
    234. 	if (((elm)->field.stqe_next = (head)->stqh_first) == NULL)	\
    235. 		(head)->stqh_last = &(elm)->field.stqe_next;		\
    236. 	(head)->stqh_first = (elm);					\
    237. } while (/*CONSTCOND*/0)
    238.  
    239. #define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
    240. 	(elm)->field.stqe_next = NULL;					\
    241. 	*(head)->stqh_last = (elm);					\
    242. 	(head)->stqh_last = &(elm)->field.stqe_next;			\
    243. } while (/*CONSTCOND*/0)
    244.  
    245. #define	STAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
    246. 	if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
    247. 		(head)->stqh_last = &(elm)->field.stqe_next;		\
    248. 	(listelm)->field.stqe_next = (elm);				\
    249. } while (/*CONSTCOND*/0)
    250.  
    251. #define	STAILQ_REMOVE_HEAD(head, field) do {				\
    252. 	if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
    253. 		(head)->stqh_last = &(head)->stqh_first;			\
    254. } while (/*CONSTCOND*/0)
    255.  
    256. #define	STAILQ_REMOVE(head, elm, type, field) do {			\
    257. 	if ((head)->stqh_first == (elm)) {				\
    258. 		STAILQ_REMOVE_HEAD((head), field);			\
    259. 	} else {							\
    260. 		struct type *curelm = (head)->stqh_first;		\
    261. 		while (curelm->field.stqe_next != (elm))			\
    262. 			curelm = curelm->field.stqe_next;		\
    263. 		if ((curelm->field.stqe_next =				\
    264. 			curelm->field.stqe_next->field.stqe_next) == NULL) \
    265. 			    (head)->stqh_last = &(curelm)->field.stqe_next; \
    266. 	}								\
    267. } while (/*CONSTCOND*/0)
    268.  
    269. #define	STAILQ_FOREACH(var, head, field)				\
    270. 	for ((var) = ((head)->stqh_first);				\
    271. 		(var);							\
    272. 		(var) = ((var)->field.stqe_next))
    273.  
    274. #define	STAILQ_CONCAT(head1, head2) do {				\
    275. 	if (!STAILQ_EMPTY((head2))) {					\
    276. 		*(head1)->stqh_last = (head2)->stqh_first;		\
    277. 		(head1)->stqh_last = (head2)->stqh_last;		\
    278. 		STAILQ_INIT((head2));					\
    279. 	}								\
    280. } while (/*CONSTCOND*/0)
    281.  
    282. /*
    283.  * Singly-linked Tail queue access methods.
    284.  */
    285. #define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)
    286. #define	STAILQ_FIRST(head)	((head)->stqh_first)
    287. #define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
    288.  
    289.  
    290. /*
    291.  * Simple queue definitions.
    292.  */
    293. #define	SIMPLEQ_HEAD(name, type)					\
    294. struct name {								\
    295. 	struct type *sqh_first;	/* first element */			\
    296. 	struct type **sqh_last;	/* addr of last next element */		\
    297. }
    298.  
    299. #define	SIMPLEQ_HEAD_INITIALIZER(head)					\
    300. 	{ NULL, &(head).sqh_first }
    301.  
    302. #define	SIMPLEQ_ENTRY(type)						\
    303. struct {								\
    304. 	struct type *sqe_next;	/* next element */			\
    305. }
    306.  
    307. /*
    308.  * Simple queue functions.
    309.  */
    310. #define	SIMPLEQ_INIT(head) do {						\
    311. 	(head)->sqh_first = NULL;					\
    312. 	(head)->sqh_last = &(head)->sqh_first;				\
    313. } while (/*CONSTCOND*/0)
    314.  
    315. #define	SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
    316. 	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
    317. 		(head)->sqh_last = &(elm)->field.sqe_next;		\
    318. 	(head)->sqh_first = (elm);					\
    319. } while (/*CONSTCOND*/0)
    320.  
    321. #define	SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
    322. 	(elm)->field.sqe_next = NULL;					\
    323. 	*(head)->sqh_last = (elm);					\
    324. 	(head)->sqh_last = &(elm)->field.sqe_next;			\
    325. } while (/*CONSTCOND*/0)
    326.  
    327. #define	SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
    328. 	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
    329. 		(head)->sqh_last = &(elm)->field.sqe_next;		\
    330. 	(listelm)->field.sqe_next = (elm);				\
    331. } while (/*CONSTCOND*/0)
    332.  
    333. #define	SIMPLEQ_REMOVE_HEAD(head, field) do {				\
    334. 	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
    335. 		(head)->sqh_last = &(head)->sqh_first;			\
    336. } while (/*CONSTCOND*/0)
    337.  
    338. #define	SIMPLEQ_REMOVE(head, elm, type, field) do {			\
    339. 	if ((head)->sqh_first == (elm)) {				\
    340. 		SIMPLEQ_REMOVE_HEAD((head), field);			\
    341. 	} else {							\
    342. 		struct type *curelm = (head)->sqh_first;		\
    343. 		while (curelm->field.sqe_next != (elm))			\
    344. 			curelm = curelm->field.sqe_next;		\
    345. 		if ((curelm->field.sqe_next =				\
    346. 			curelm->field.sqe_next->field.sqe_next) == NULL) \
    347. 			    (head)->sqh_last = &(curelm)->field.sqe_next; \
    348. 	}								\
    349. } while (/*CONSTCOND*/0)
    350.  
    351. #define	SIMPLEQ_FOREACH(var, head, field)				\
    352. 	for ((var) = ((head)->sqh_first);				\
    353. 		(var);							\
    354. 		(var) = ((var)->field.sqe_next))
    355.  
    356. /*
    357.  * Simple queue access methods.
    358.  */
    359. #define	SIMPLEQ_EMPTY(head)		((head)->sqh_first == NULL)
    360. #define	SIMPLEQ_FIRST(head)		((head)->sqh_first)
    361. #define	SIMPLEQ_NEXT(elm, field)	((elm)->field.sqe_next)
    362.  
    363.  
    364. /*
    365.  * Tail queue definitions.
    366.  */
    367. #define	_TAILQ_HEAD(name, type, qual)					\
    368. struct name {								\
    369. 	qual type *tqh_first;		/* first element */		\
    370. 	qual type *qual *tqh_last;	/* addr of last next element */	\
    371. }
    372. #define TAILQ_HEAD(name, type)	_TAILQ_HEAD(name, struct type,)
    373.  
    374. #define	TAILQ_HEAD_INITIALIZER(head)					\
    375. 	{ NULL, &(head).tqh_first }
    376.  
    377. #define	_TAILQ_ENTRY(type, qual)					\
    378. struct {								\
    379. 	qual type *tqe_next;		/* next element */		\
    380. 	qual type *qual *tqe_prev;	/* address of previous next element */\
    381. }
    382. #define TAILQ_ENTRY(type)	_TAILQ_ENTRY(struct type,)
    383.  
    384. /*
    385.  * Tail queue functions.
    386.  */
    387. #define	TAILQ_INIT(head) do {						\
    388. 	(head)->tqh_first = NULL;					\
    389. 	(head)->tqh_last = &(head)->tqh_first;				\
    390. } while (/*CONSTCOND*/0)
    391.  
    392. #define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
    393. 	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
    394. 		(head)->tqh_first->field.tqe_prev =			\
    395. 		    &(elm)->field.tqe_next;				\
    396. 	else								\
    397. 		(head)->tqh_last = &(elm)->field.tqe_next;		\
    398. 	(head)->tqh_first = (elm);					\
    399. 	(elm)->field.tqe_prev = &(head)->tqh_first;			\
    400. } while (/*CONSTCOND*/0)
    401.  
    402. #define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
    403. 	(elm)->field.tqe_next = NULL;					\
    404. 	(elm)->field.tqe_prev = (head)->tqh_last;			\
    405. 	*(head)->tqh_last = (elm);					\
    406. 	(head)->tqh_last = &(elm)->field.tqe_next;			\
    407. } while (/*CONSTCOND*/0)
    408.  
    409. #define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
    410. 	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
    411. 		(elm)->field.tqe_next->field.tqe_prev = 		\
    412. 		    &(elm)->field.tqe_next;				\
    413. 	else								\
    414. 		(head)->tqh_last = &(elm)->field.tqe_next;		\
    415. 	(listelm)->field.tqe_next = (elm);				\
    416. 	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
    417. } while (/*CONSTCOND*/0)
    418.  
    419. #define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
    420. 	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
    421. 	(elm)->field.tqe_next = (listelm);				\
    422. 	*(listelm)->field.tqe_prev = (elm);				\
    423. 	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
    424. } while (/*CONSTCOND*/0)
    425.  
    426. #define	TAILQ_REMOVE(head, elm, field) do {				\
    427. 	if (((elm)->field.tqe_next) != NULL)				\
    428. 		(elm)->field.tqe_next->field.tqe_prev = 		\
    429. 		    (elm)->field.tqe_prev;				\
    430. 	else								\
    431. 		(head)->tqh_last = (elm)->field.tqe_prev;		\
    432. 	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
    433. } while (/*CONSTCOND*/0)
    434.  
    435. #define	TAILQ_FOREACH(var, head, field)					\
    436. 	for ((var) = ((head)->tqh_first);				\
    437. 		(var);							\
    438. 		(var) = ((var)->field.tqe_next))
    439.  
    440. #define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
    441. 	for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));	\
    442. 		(var);							\
    443. 		(var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
    444.  
    445. #define	TAILQ_CONCAT(head1, head2, field) do {				\
    446. 	if (!TAILQ_EMPTY(head2)) {					\
    447. 		*(head1)->tqh_last = (head2)->tqh_first;		\
    448. 		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\
    449. 		(head1)->tqh_last = (head2)->tqh_last;			\
    450. 		TAILQ_INIT((head2));					\
    451. 	}								\
    452. } while (/*CONSTCOND*/0)
    453.  
    454. /*
    455.  * Tail queue access methods.
    456.  */
    457. #define	TAILQ_EMPTY(head)		((head)->tqh_first == NULL)
    458. #define	TAILQ_FIRST(head)		((head)->tqh_first)
    459. #define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
    460.  
    461. #define	TAILQ_LAST(head, headname) \
    462. 	(*(((struct headname *)((head)->tqh_last))->tqh_last))
    463. #define	TAILQ_PREV(elm, headname, field) \
    464. 	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
    465.  
    466.  
    467. /*
    468.  * Circular queue definitions.
    469.  */
    470. #define	CIRCLEQ_HEAD(name, type)					\
    471. struct name {								\
    472. 	struct type *cqh_first;		/* first element */		\
    473. 	struct type *cqh_last;		/* last element */		\
    474. }
    475.  
    476. #define	CIRCLEQ_HEAD_INITIALIZER(head)					\
    477. 	{ (void *)&head, (void *)&head }
    478.  
    479. #define	CIRCLEQ_ENTRY(type)						\
    480. struct {								\
    481. 	struct type *cqe_next;		/* next element */		\
    482. 	struct type *cqe_prev;		/* previous element */		\
    483. }
    484.  
    485. /*
    486.  * Circular queue functions.
    487.  */
    488. #define	CIRCLEQ_INIT(head) do {						\
    489. 	(head)->cqh_first = (void *)(head);				\
    490. 	(head)->cqh_last = (void *)(head);				\
    491. } while (/*CONSTCOND*/0)
    492.  
    493. #define	CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
    494. 	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
    495. 	(elm)->field.cqe_prev = (listelm);				\
    496. 	if ((listelm)->field.cqe_next == (void *)(head))		\
    497. 		(head)->cqh_last = (elm);				\
    498. 	else								\
    499. 		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
    500. 	(listelm)->field.cqe_next = (elm);				\
    501. } while (/*CONSTCOND*/0)
    502.  
    503. #define	CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
    504. 	(elm)->field.cqe_next = (listelm);				\
    505. 	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
    506. 	if ((listelm)->field.cqe_prev == (void *)(head))		\
    507. 		(head)->cqh_first = (elm);				\
    508. 	else								\
    509. 		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
    510. 	(listelm)->field.cqe_prev = (elm);				\
    511. } while (/*CONSTCOND*/0)
    512.  
    513. #define	CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
    514. 	(elm)->field.cqe_next = (head)->cqh_first;			\
    515. 	(elm)->field.cqe_prev = (void *)(head);				\
    516. 	if ((head)->cqh_last == (void *)(head))				\
    517. 		(head)->cqh_last = (elm);				\
    518. 	else								\
    519. 		(head)->cqh_first->field.cqe_prev = (elm);		\
    520. 	(head)->cqh_first = (elm);					\
    521. } while (/*CONSTCOND*/0)
    522.  
    523. #define	CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
    524. 	(elm)->field.cqe_next = (void *)(head);				\
    525. 	(elm)->field.cqe_prev = (head)->cqh_last;			\
    526. 	if ((head)->cqh_first == (void *)(head))			\
    527. 		(head)->cqh_first = (elm);				\
    528. 	else								\
    529. 		(head)->cqh_last->field.cqe_next = (elm);		\
    530. 	(head)->cqh_last = (elm);					\
    531. } while (/*CONSTCOND*/0)
    532.  
    533. #define	CIRCLEQ_REMOVE(head, elm, field) do {				\
    534. 	if ((elm)->field.cqe_next == (void *)(head))			\
    535. 		(head)->cqh_last = (elm)->field.cqe_prev;		\
    536. 	else								\
    537. 		(elm)->field.cqe_next->field.cqe_prev =			\
    538. 		    (elm)->field.cqe_prev;				\
    539. 	if ((elm)->field.cqe_prev == (void *)(head))			\
    540. 		(head)->cqh_first = (elm)->field.cqe_next;		\
    541. 	else								\
    542. 		(elm)->field.cqe_prev->field.cqe_next =			\
    543. 		    (elm)->field.cqe_next;				\
    544. } while (/*CONSTCOND*/0)
    545.  
    546. #define	CIRCLEQ_FOREACH(var, head, field)				\
    547. 	for ((var) = ((head)->cqh_first);				\
    548. 		(var) != (const void *)(head);				\
    549. 		(var) = ((var)->field.cqe_next))
    550.  
    551. #define	CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
    552. 	for ((var) = ((head)->cqh_last);				\
    553. 		(var) != (const void *)(head);				\
    554. 		(var) = ((var)->field.cqe_prev))
    555.  
    556. /*
    557.  * Circular queue access methods.
    558.  */
    559. #define	CIRCLEQ_EMPTY(head)		((head)->cqh_first == (void *)(head))
    560. #define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
    561. #define	CIRCLEQ_LAST(head)		((head)->cqh_last)
    562. #define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
    563. #define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
    564.  
    565. #define CIRCLEQ_LOOP_NEXT(head, elm, field)				\
    566. 	(((elm)->field.cqe_next == (void *)(head))			\
    567. 	    ? ((head)->cqh_first)					\
    568. 	    : (elm->field.cqe_next))
    569. #define CIRCLEQ_LOOP_PREV(head, elm, field)				\
    570. 	(((elm)->field.cqe_prev == (void *)(head))			\
    571. 	    ? ((head)->cqh_last)					\
    572. 	    : (elm->field.cqe_prev))
    573.  
    574. #endif	/* sys/queue.h */

    /usr/include/sys/queue.h 不同的系统有差别, sys/queue.h不依赖其他头文件，直接搬过来就好。

  • 相关阅读:
    非肿瘤纯生信拿下7+，多种机器学习算法，搭配WGCNA。
    七、【套索工具组】
    python选择排序
    程序员的数学课10 信息熵：事件的不确定性如何计算？
    tomcat8.5处理get请求时，控制台输出中文乱码问题的解决
    ansible自动化部署web服务
    AWTK UI 自动化测试工具发布
    1382. 将二叉搜索树变平衡 ●●
    rviz中引入SW的模型
    使用Flink批处理实现WordCount
  • 原文地址：https://blog.csdn.net/fareast_mzh/article/details/133693818