[mirror_frr.git] / lib / queue.h

/*
 * lists and queues implementations
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 * more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; see the file COPYING; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#ifndef _FRR_QUEUE_H
#define _FRR_QUEUE_H

#if defined(__OpenBSD__) && !defined(STAILQ_HEAD)
#include "openbsd-queue.h"

/* Try to map FreeBSD implementation to OpenBSD one. */
#define STAILQ_HEAD(name, type)				SIMPLEQ_HEAD(name, type)
#define STAILQ_HEAD_INITIALIZER(head)			SIMPLEQ_HEAD_INITIALIZER(head)
#define STAILQ_ENTRY(entry)				SIMPLEQ_ENTRY(entry)

#define STAILQ_CONCAT(head1, head2)			SIMPLEQ_CONCAT(head1, head2)
#define STAILQ_EMPTY(head)				SIMPLEQ_EMPTY(head)
#define STAILQ_FIRST(head)				SIMPLEQ_FIRST(head)
#define STAILQ_FOREACH(var, head, field)		SIMPLEQ_FOREACH(var, head, field)
#define STAILQ_FOREACH_SAFE(var, head, field, tvar)	SIMPLEQ_FOREACH_SAFE(var, head, field, tvar)
#define STAILQ_INIT(head)				SIMPLEQ_INIT(head)
#define STAILQ_INSERT_AFTER(head, tqelm, elm, field)	SIMPLEQ_INSERT_AFTER(head, tqelm, elm, field)
#define STAILQ_INSERT_HEAD(head, elm, field)		SIMPLEQ_INSERT_HEAD(head, elm, field)
#define STAILQ_INSERT_TAIL(head, elm, field)		SIMPLEQ_INSERT_TAIL(head, elm, field)
#define STAILQ_LAST(head, type, field)                                         \
	(SIMPLEQ_EMPTY((head))                                                 \
		 ? NULL                                                        \
		 : ((struct type *)(void *)((char *)((head)->sqh_last)         \
					    - offsetof(struct type, field))))
#define STAILQ_NEXT(elm, field)				SIMPLEQ_NEXT(elm, field)
#define STAILQ_REMOVE(head, elm, type, field)                                  \
	do {                                                                   \
		if (SIMPLEQ_FIRST((head)) == (elm)) {                          \
			SIMPLEQ_REMOVE_HEAD((head), field);                    \
		} else {                                                       \
			struct type *curelm = SIMPLEQ_FIRST((head));           \
			while (SIMPLEQ_NEXT(curelm, field) != (elm))           \
				curelm = SIMPLEQ_NEXT(curelm, field);          \
			SIMPLEQ_REMOVE_AFTER(head, curelm, field);             \
		}                                                              \
	} while (0)
#define STAILQ_REMOVE_AFTER(head, elm, field)		SIMPLEQ_REMOVE_AFTER(head, elm, field)
#define STAILQ_REMOVE_HEAD(head, field)			SIMPLEQ_REMOVE_HEAD(head, field)
#define STAILQ_SWAP(head1, head2, type)                                        \
	do {                                                                   \
		struct type *swap_first = STAILQ_FIRST(head1);                 \
		struct type **swap_last = (head1)->sqh_last;                   \
		STAILQ_FIRST(head1) = STAILQ_FIRST(head2);                     \
		(head1)->sqh_last = (head2)->sqh_last;                         \
		STAILQ_FIRST(head2) = swap_first;                              \
		(head2)->sqh_last = swap_last;                                 \
		if (STAILQ_EMPTY(head1))                                       \
			(head1)->sqh_last = &STAILQ_FIRST(head1);              \
		if (STAILQ_EMPTY(head2))                                       \
			(head2)->sqh_last = &STAILQ_FIRST(head2);              \
	} while (0)
#else
#include "freebsd-queue.h"
#endif /* defined(__OpenBSD__) && !defined(STAILQ_HEAD) */

#ifndef TAILQ_POP_FIRST
#define TAILQ_POP_FIRST(head, field)                                           \
	({  typeof((head)->tqh_first) _elm = TAILQ_FIRST(head);                \
	    if (_elm) {                                                        \
		if ((TAILQ_NEXT((_elm), field)) != NULL)                       \
			TAILQ_NEXT((_elm), field)->field.tqe_prev =            \
				&TAILQ_FIRST(head);                            \
		else                                                           \
			(head)->tqh_last = &TAILQ_FIRST(head);                 \
		TAILQ_FIRST(head) = TAILQ_NEXT((_elm), field);                 \
	}; _elm; })
#endif

#endif /* _FRR_QUEUE_H */
Commit	Line	Data
04f7dd64	1	/*
cd85bc2e	2	* lists and queues implementations
04f7dd64	3	*
cd85bc2e JB	4	* This program is free software; you can redistribute it and/or modify it
	5	* under the terms of the GNU General Public License as published by the Free
	6	* Software Foundation; either version 2 of the License, or (at your option)
	7	* any later version.
04f7dd64	8	*
cd85bc2e JB	9	* This program is distributed in the hope that it will be useful, but WITHOUT
	10	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	11	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
	12	* more details.
04f7dd64	13	*
cd85bc2e JB	14	* You should have received a copy of the GNU General Public License along
	15	* with this program; see the file COPYING; if not, write to the Free Software
	16	* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
04f7dd64	17	*/
d62a17ae	18
cd85bc2e JB	19	#ifndef _FRR_QUEUE_H
	20	#define _FRR_QUEUE_H
	21
	22	#if defined(__OpenBSD__) && !defined(STAILQ_HEAD)
	23	#include "openbsd-queue.h"
	24
	25	/* Try to map FreeBSD implementation to OpenBSD one. */
	26	#define STAILQ_HEAD(name, type) SIMPLEQ_HEAD(name, type)
	27	#define STAILQ_HEAD_INITIALIZER(head) SIMPLEQ_HEAD_INITIALIZER(head)
	28	#define STAILQ_ENTRY(entry) SIMPLEQ_ENTRY(entry)
	29
	30	#define STAILQ_CONCAT(head1, head2) SIMPLEQ_CONCAT(head1, head2)
	31	#define STAILQ_EMPTY(head) SIMPLEQ_EMPTY(head)
	32	#define STAILQ_FIRST(head) SIMPLEQ_FIRST(head)
	33	#define STAILQ_FOREACH(var, head, field) SIMPLEQ_FOREACH(var, head, field)
	34	#define STAILQ_FOREACH_SAFE(var, head, field, tvar) SIMPLEQ_FOREACH_SAFE(var, head, field, tvar)
	35	#define STAILQ_INIT(head) SIMPLEQ_INIT(head)
	36	#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) SIMPLEQ_INSERT_AFTER(head, tqelm, elm, field)
	37	#define STAILQ_INSERT_HEAD(head, elm, field) SIMPLEQ_INSERT_HEAD(head, elm, field)
	38	#define STAILQ_INSERT_TAIL(head, elm, field) SIMPLEQ_INSERT_TAIL(head, elm, field)
d62a17ae	39	#define STAILQ_LAST(head, type, field) \
cd85bc2e	40	(SIMPLEQ_EMPTY((head)) \
d62a17ae	41	? NULL \
cd85bc2e	42	: ((struct type )(void )((char *)((head)->sqh_last) \
996c9314	43	- offsetof(struct type, field))))
cd85bc2e	44	#define STAILQ_NEXT(elm, field) SIMPLEQ_NEXT(elm, field)
d62a17ae	45	#define STAILQ_REMOVE(head, elm, type, field) \
d62a17ae	46	do { \
cd85bc2e JB	47	if (SIMPLEQ_FIRST((head)) == (elm)) { \
cd85bc2e JB	48	SIMPLEQ_REMOVE_HEAD((head), field); \
d62a17ae	49	} else { \
cd85bc2e JB	50	struct type *curelm = SIMPLEQ_FIRST((head)); \
	51	while (SIMPLEQ_NEXT(curelm, field) != (elm)) \
	52	curelm = SIMPLEQ_NEXT(curelm, field); \
	53	SIMPLEQ_REMOVE_AFTER(head, curelm, field); \
d62a17ae	54	} \
d62a17ae	55	} while (0)
cd85bc2e JB	56	#define STAILQ_REMOVE_AFTER(head, elm, field) SIMPLEQ_REMOVE_AFTER(head, elm, field)
cd85bc2e JB	57	#define STAILQ_REMOVE_HEAD(head, field) SIMPLEQ_REMOVE_HEAD(head, field)
d62a17ae	58	#define STAILQ_SWAP(head1, head2, type) \
	59	do { \
	60	struct type *swap_first = STAILQ_FIRST(head1); \
cd85bc2e	61	struct type **swap_last = (head1)->sqh_last; \
d62a17ae	62	STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \
cd85bc2e	63	(head1)->sqh_last = (head2)->sqh_last; \
d62a17ae	64	STAILQ_FIRST(head2) = swap_first; \
cd85bc2e	65	(head2)->sqh_last = swap_last; \
d62a17ae	66	if (STAILQ_EMPTY(head1)) \
cd85bc2e	67	(head1)->sqh_last = &STAILQ_FIRST(head1); \
d62a17ae	68	if (STAILQ_EMPTY(head2)) \
cd85bc2e	69	(head2)->sqh_last = &STAILQ_FIRST(head2); \
d62a17ae	70	} while (0)
04f7dd64	71	#else
cd85bc2e JB	72	#include "freebsd-queue.h"
cd85bc2e JB	73	#endif /* defined(__OpenBSD__) && !defined(STAILQ_HEAD) */
04f7dd64	74
a43ad4fe DL	75	#ifndef TAILQ_POP_FIRST
	76	#define TAILQ_POP_FIRST(head, field) \
	77	({ typeof((head)->tqh_first) _elm = TAILQ_FIRST(head); \
	78	if (_elm) { \
	79	if ((TAILQ_NEXT((_elm), field)) != NULL) \
	80	TAILQ_NEXT((_elm), field)->field.tqe_prev = \
	81	&TAILQ_FIRST(head); \
	82	else \
	83	(head)->tqh_last = &TAILQ_FIRST(head); \
	84	TAILQ_FIRST(head) = TAILQ_NEXT((_elm), field); \
	85	}; _elm; })
	86	#endif
	87
cd85bc2e	88	#endif /* _FRR_QUEUE_H */