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

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