[thirdparty/systemd.git] / src / basic / list.h

/* SPDX-License-Identifier: LGPL-2.1+ */
#pragma once

/***
  This file is part of systemd.

  Copyright 2010 Lennart Poettering

  systemd is free software; you can redistribute it and/or modify it
  under the terms of the GNU Lesser General Public License as published by
  the Free Software Foundation; either version 2.1 of the License, or
  (at your option) any later version.

  systemd 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
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with systemd; If not, see <http://www.gnu.org/licenses/>.
***/

/* The head of the linked list. Use this in the structure that shall
 * contain the head of the linked list */
#define LIST_HEAD(t,name)                                               \
        t *name

/* The pointers in the linked list's items. Use this in the item structure */
#define LIST_FIELDS(t,name)                                             \
        t *name##_next, *name##_prev

/* Initialize the list's head */
#define LIST_HEAD_INIT(head)                                            \
        do {                                                            \
                (head) = NULL; }                                        \
        while (false)

/* Initialize a list item */
#define LIST_INIT(name,item)                                            \
        do {                                                            \
                typeof(*(item)) *_item = (item);                        \
                assert(_item);                                          \
                _item->name##_prev = _item->name##_next = NULL;         \
        } while (false)

/* Prepend an item to the list */
#define LIST_PREPEND(name,head,item)                                    \
        do {                                                            \
                typeof(*(head)) **_head = &(head), *_item = (item);     \
                assert(_item);                                          \
                if ((_item->name##_next = *_head))                      \
                        _item->name##_next->name##_prev = _item;        \
                _item->name##_prev = NULL;                              \
                *_head = _item;                                         \
        } while (false)

/* Append an item to the list */
#define LIST_APPEND(name,head,item)                                     \
        do {                                                            \
                typeof(*(head)) *_tail;                                 \
                LIST_FIND_TAIL(name,head,_tail);                        \
                LIST_INSERT_AFTER(name,head,_tail,item);                \
        } while (false)

/* Remove an item from the list */
#define LIST_REMOVE(name,head,item)                                     \
        do {                                                            \
                typeof(*(head)) **_head = &(head), *_item = (item);     \
                assert(_item);                                          \
                if (_item->name##_next)                                 \
                        _item->name##_next->name##_prev = _item->name##_prev; \
                if (_item->name##_prev)                                 \
                        _item->name##_prev->name##_next = _item->name##_next; \
                else {                                                  \
                        assert(*_head == _item);                        \
                        *_head = _item->name##_next;                    \
                }                                                       \
                _item->name##_next = _item->name##_prev = NULL;         \
        } while (false)

/* Find the head of the list */
#define LIST_FIND_HEAD(name,item,head)                                  \
        do {                                                            \
                typeof(*(item)) *_item = (item);                        \
                if (!_item)                                             \
                        (head) = NULL;                                  \
                else {                                                  \
                        while (_item->name##_prev)                      \
                                _item = _item->name##_prev;             \
                        (head) = _item;                                 \
                }                                                       \
        } while (false)

/* Find the tail of the list */
#define LIST_FIND_TAIL(name,item,tail)                                  \
        do {                                                            \
                typeof(*(item)) *_item = (item);                        \
                if (!_item)                                             \
                        (tail) = NULL;                                  \
                else {                                                  \
                        while (_item->name##_next)                      \
                                _item = _item->name##_next;             \
                        (tail) = _item;                                 \
                }                                                       \
        } while (false)

/* Insert an item after another one (a = where, b = what) */
#define LIST_INSERT_AFTER(name,head,a,b)                                \
        do {                                                            \
                typeof(*(head)) **_head = &(head), *_a = (a), *_b = (b); \
                assert(_b);                                             \
                if (!_a) {                                              \
                        if ((_b->name##_next = *_head))                 \
                                _b->name##_next->name##_prev = _b;      \
                        _b->name##_prev = NULL;                         \
                        *_head = _b;                                    \
                } else {                                                \
                        if ((_b->name##_next = _a->name##_next))        \
                                _b->name##_next->name##_prev = _b;      \
                        _b->name##_prev = _a;                           \
                        _a->name##_next = _b;                           \
                }                                                       \
        } while (false)

/* Insert an item before another one (a = where, b = what) */
#define LIST_INSERT_BEFORE(name,head,a,b)                               \
        do {                                                            \
                typeof(*(head)) **_head = &(head), *_a = (a), *_b = (b); \
                assert(_b);                                             \
                if (!_a) {                                              \
                        if (!*_head) {                                  \
                                _b->name##_next = NULL;                 \
                                _b->name##_prev = NULL;                 \
                                *_head = _b;                            \
                        } else {                                        \
                                typeof(*(head)) *_tail = (head);        \
                                while (_tail->name##_next)              \
                                        _tail = _tail->name##_next;     \
                                _b->name##_next = NULL;                 \
                                _b->name##_prev = _tail;                \
                                _tail->name##_next = _b;                \
                        }                                               \
                } else {                                                \
                        if ((_b->name##_prev = _a->name##_prev))        \
                                _b->name##_prev->name##_next = _b;      \
                        else                                            \
                                *_head = _b;                            \
                        _b->name##_next = _a;                           \
                        _a->name##_prev = _b;                           \
                }                                                       \
        } while (false)

#define LIST_JUST_US(name,item)                                         \
        (!(item)->name##_prev && !(item)->name##_next)                  \

#define LIST_FOREACH(name,i,head)                                       \
        for ((i) = (head); (i); (i) = (i)->name##_next)

#define LIST_FOREACH_SAFE(name,i,n,head)                                \
        for ((i) = (head); (i) && (((n) = (i)->name##_next), 1); (i) = (n))

#define LIST_FOREACH_BEFORE(name,i,p)                                   \
        for ((i) = (p)->name##_prev; (i); (i) = (i)->name##_prev)

#define LIST_FOREACH_AFTER(name,i,p)                                    \
        for ((i) = (p)->name##_next; (i); (i) = (i)->name##_next)

/* Iterate through all the members of the list p is included in, but skip over p */
#define LIST_FOREACH_OTHERS(name,i,p)                                   \
        for (({                                                         \
                (i) = (p);                                              \
                while ((i) && (i)->name##_prev)                         \
                        (i) = (i)->name##_prev;                         \
                if ((i) == (p))                                         \
                        (i) = (p)->name##_next;                         \
             });                                                        \
             (i);                                                       \
             (i) = (i)->name##_next == (p) ? (p)->name##_next : (i)->name##_next)

/* Loop starting from p->next until p->prev.
   p can be adjusted meanwhile. */
#define LIST_LOOP_BUT_ONE(name,i,head,p)                                \
        for ((i) = (p)->name##_next ? (p)->name##_next : (head);        \
             (i) != (p);                                                \
             (i) = (i)->name##_next ? (i)->name##_next : (head))
Commit	Line	Data
53e1b683	1	/* SPDX-License-Identifier: LGPL-2.1+ */
c2f1db8f	2	#pragma once
60918275	3
a7334b09 LP	4	/***
	5	This file is part of systemd.
	6
	7	Copyright 2010 Lennart Poettering
	8
	9	systemd is free software; you can redistribute it and/or modify it
5430f7f2 LP	10	under the terms of the GNU Lesser General Public License as published by
5430f7f2 LP	11	the Free Software Foundation; either version 2.1 of the License, or
a7334b09 LP	12	(at your option) any later version.
	13
	14	systemd is distributed in the hope that it will be useful, but
	15	WITHOUT ANY WARRANTY; without even the implied warranty of
	16	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
5430f7f2	17	Lesser General Public License for more details.
a7334b09	18
5430f7f2	19	You should have received a copy of the GNU Lesser General Public License
a7334b09 LP	20	along with systemd; If not, see <http://www.gnu.org/licenses/>.
	21	***/
	22
60918275 LP	23	/* The head of the linked list. Use this in the structure that shall
	24	* contain the head of the linked list */
	25	#define LIST_HEAD(t,name) \
034c6ed7	26	t *name
60918275 LP	27
60918275 LP	28	/* The pointers in the linked list's items. Use this in the item structure */
034c6ed7 LP	29	#define LIST_FIELDS(t,name) \
034c6ed7 LP	30	t name##_next, name##_prev
60918275 LP	31
60918275 LP	32	/* Initialize the list's head */
71fda00f	33	#define LIST_HEAD_INIT(head) \
60918275	34	do { \
034c6ed7	35	(head) = NULL; } \
9ed794a3	36	while (false)
60918275 LP	37
60918275 LP	38	/* Initialize a list item */
71fda00f	39	#define LIST_INIT(name,item) \
60918275	40	do { \
71fda00f	41	typeof((item)) _item = (item); \
60918275	42	assert(_item); \
034c6ed7	43	_item->name##_prev = _item->name##_next = NULL; \
9ed794a3	44	} while (false)
60918275 LP	45
60918275 LP	46	/* Prepend an item to the list */
71fda00f	47	#define LIST_PREPEND(name,head,item) \
60918275	48	do { \
71fda00f	49	typeof((head)) _head = &(head), _item = (item); \
60918275	50	assert(_item); \
034c6ed7 LP	51	if ((_item->name##_next = *_head)) \
	52	_item->name##_next->name##_prev = _item; \
	53	_item->name##_prev = NULL; \
60918275	54	*_head = _item; \
9ed794a3	55	} while (false)
60918275	56
502f1733 ZJS	57	/* Append an item to the list */
	58	#define LIST_APPEND(name,head,item) \
	59	do { \
	60	typeof((head)) _tail; \
	61	LIST_FIND_TAIL(name,head,_tail); \
	62	LIST_INSERT_AFTER(name,head,_tail,item); \
9ed794a3	63	} while (false)
502f1733	64
60918275	65	/* Remove an item from the list */
71fda00f	66	#define LIST_REMOVE(name,head,item) \
60918275	67	do { \
71fda00f	68	typeof((head)) _head = &(head), _item = (item); \
60918275	69	assert(_item); \
034c6ed7 LP	70	if (_item->name##_next) \
	71	_item->name##_next->name##_prev = _item->name##_prev; \
	72	if (_item->name##_prev) \
	73	_item->name##_prev->name##_next = _item->name##_next; \
60918275 LP	74	else { \
60918275 LP	75	assert(*_head == _item); \
034c6ed7	76	*_head = _item->name##_next; \
60918275	77	} \
034c6ed7	78	_item->name##_next = _item->name##_prev = NULL; \
9ed794a3	79	} while (false)
60918275 LP	80
60918275 LP	81	/* Find the head of the list */
71fda00f	82	#define LIST_FIND_HEAD(name,item,head) \
60918275	83	do { \
71fda00f	84	typeof((item)) _item = (item); \
376cd3b8 LP	85	if (!_item) \
	86	(head) = NULL; \
	87	else { \
	88	while (_item->name##_prev) \
	89	_item = _item->name##_prev; \
	90	(head) = _item; \
	91	} \
034c6ed7 LP	92	} while (false)
034c6ed7 LP	93
3b18ae68	94	/* Find the tail of the list */
71fda00f	95	#define LIST_FIND_TAIL(name,item,tail) \
034c6ed7	96	do { \
71fda00f	97	typeof((item)) _item = (item); \
376cd3b8 LP	98	if (!_item) \
	99	(tail) = NULL; \
	100	else { \
	101	while (_item->name##_next) \
	102	_item = _item->name##_next; \
	103	(tail) = _item; \
	104	} \
60918275 LP	105	} while (false)
	106
	107	/* Insert an item after another one (a = where, b = what) */
71fda00f	108	#define LIST_INSERT_AFTER(name,head,a,b) \
60918275	109	do { \
71fda00f	110	typeof((head)) _head = &(head), _a = (a), *_b = (b); \
60918275 LP	111	assert(_b); \
60918275 LP	112	if (!_a) { \
034c6ed7 LP	113	if ((_b->name##_next = *_head)) \
	114	_b->name##_next->name##_prev = _b; \
	115	_b->name##_prev = NULL; \
60918275 LP	116	*_head = _b; \
60918275 LP	117	} else { \
034c6ed7 LP	118	if ((_b->name##_next = _a->name##_next)) \
	119	_b->name##_next->name##_prev = _b; \
	120	_b->name##_prev = _a; \
	121	_a->name##_next = _b; \
60918275	122	} \
9ed794a3	123	} while (false)
60918275	124
dbe465c9 AC	125	/* Insert an item before another one (a = where, b = what) */
	126	#define LIST_INSERT_BEFORE(name,head,a,b) \
	127	do { \
	128	typeof((head)) _head = &(head), _a = (a), *_b = (b); \
	129	assert(_b); \
	130	if (!_a) { \
	131	if (!*_head) { \
	132	_b->name##_next = NULL; \
	133	_b->name##_prev = NULL; \
	134	*_head = _b; \
	135	} else { \
	136	typeof((head)) _tail = (head); \
	137	while (_tail->name##_next) \
	138	_tail = _tail->name##_next; \
	139	_b->name##_next = NULL; \
	140	_b->name##_prev = _tail; \
	141	_tail->name##_next = _b; \
	142	} \
	143	} else { \
	144	if ((_b->name##_prev = _a->name##_prev)) \
	145	_b->name##_prev->name##_next = _b; \
5076f421 MO	146	else \
5076f421 MO	147	*_head = _b; \
dbe465c9 AC	148	_b->name##_next = _a; \
	149	_a->name##_prev = _b; \
	150	} \
9ed794a3	151	} while (false)
dbe465c9	152
6210e7fc LP	153	#define LIST_JUST_US(name,item) \
	154	(!(item)->name##_prev && !(item)->name##_next) \
	155
034c6ed7 LP	156	#define LIST_FOREACH(name,i,head) \
034c6ed7 LP	157	for ((i) = (head); (i); (i) = (i)->name##_next)
60918275	158
034c6ed7 LP	159	#define LIST_FOREACH_SAFE(name,i,n,head) \
034c6ed7 LP	160	for ((i) = (head); (i) && (((n) = (i)->name##_next), 1); (i) = (n))
60918275	161
e04aad61 LP	162	#define LIST_FOREACH_BEFORE(name,i,p) \
	163	for ((i) = (p)->name##_prev; (i); (i) = (i)->name##_prev)
	164
	165	#define LIST_FOREACH_AFTER(name,i,p) \
	166	for ((i) = (p)->name##_next; (i); (i) = (i)->name##_next)
2bc8ca0c	167
7663df37 LP	168	/* Iterate through all the members of the list p is included in, but skip over p */
	169	#define LIST_FOREACH_OTHERS(name,i,p) \
	170	for (({ \
	171	(i) = (p); \
	172	while ((i) && (i)->name##_prev) \
	173	(i) = (i)->name##_prev; \
cdda4aa8 LP	174	if ((i) == (p)) \
cdda4aa8 LP	175	(i) = (p)->name##_next; \
7663df37 LP	176	}); \
	177	(i); \
	178	(i) = (i)->name##_next == (p) ? (p)->name##_next : (i)->name##_next)
	179
2bc8ca0c ZJS	180	/* Loop starting from p->next until p->prev.
	181	p can be adjusted meanwhile. */
	182	#define LIST_LOOP_BUT_ONE(name,i,head,p) \
	183	for ((i) = (p)->name##_next ? (p)->name##_next : (head); \
	184	(i) != (p); \
	185	(i) = (i)->name##_next ? (i)->name##_next : (head))