blob: cb905da096cb123112801dc4bd2517a7b132154d [file] [log] [blame]
willy tarreau80862a32006-04-12 19:15:57 +02001/*
Willy Tarreau3dd717c2014-12-23 13:58:43 +01002 * include/common/mini-clist.h
3 * Circular list manipulation macros and structures.
willy tarreau80862a32006-04-12 19:15:57 +02004 *
Willy Tarreau3dd717c2014-12-23 13:58:43 +01005 * Copyright (C) 2002-2014 Willy Tarreau - w@1wt.eu
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation, version 2.1
10 * exclusively.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
willy tarreau80862a32006-04-12 19:15:57 +020020 */
21
Willy Tarreau2dd0d472006-06-29 17:53:05 +020022#ifndef _COMMON_MINI_CLIST_H
23#define _COMMON_MINI_CLIST_H
willy tarreau80862a32006-04-12 19:15:57 +020024
Willy Tarreaue3ba5f02006-06-29 18:54:54 +020025#include <common/config.h>
26
willy tarreau80862a32006-04-12 19:15:57 +020027/* these are circular or bidirectionnal lists only. Each list pointer points to
28 * another list pointer in a structure, and not the structure itself. The
29 * pointer to the next element MUST be the first one so that the list is easily
30 * cast as a single linked list or pointer.
31 */
32struct list {
33 struct list *n; /* next */
34 struct list *p; /* prev */
35};
36
Willy Tarreaubc04ce72008-12-07 20:00:15 +010037/* a back-ref is a pointer to a target list entry. It is used to detect when an
38 * element being deleted is currently being tracked by another user. The best
39 * example is a user dumping the session table. The table does not fit in the
40 * output buffer so we have to set a mark on a session and go on later. But if
41 * that marked session gets deleted, we don't want the user's pointer to go in
42 * the wild. So we can simply link this user's request to the list of this
43 * session's users, and put a pointer to the list element in ref, that will be
44 * used as the mark for next iteration.
45 */
46struct bref {
47 struct list users;
48 struct list *ref; /* pointer to the target's list entry */
49};
50
Willy Tarreaudeb9ed82010-01-03 21:03:22 +010051/* a word list is a generic list with a pointer to a string in each element. */
52struct wordlist {
53 struct list list;
54 char *s;
55};
56
Willy Tarreauf4f04122010-01-28 18:10:50 +010057/* this is the same as above with an additional pointer to a condition. */
58struct cond_wordlist {
59 struct list list;
60 void *cond;
61 char *s;
62};
63
Willy Tarreaubd578bb2007-10-28 11:41:06 +010064/* First undefine some macros which happen to also be defined on OpenBSD,
65 * in sys/queue.h, used by sys/event.h
66 */
67#undef LIST_HEAD
68#undef LIST_INIT
69#undef LIST_NEXT
70
Willy Tarreaudc13c112013-06-21 23:16:39 +020071/* ILH = Initialized List Head : used to prevent gcc from moving an empty
72 * list to BSS. Some older version tend to trim all the array and cause
73 * corruption.
74 */
75#define ILH { .n = (struct list *)1, .p = (struct list *)2 }
76
Willy Tarreaubaaee002006-06-26 02:48:02 +020077#define LIST_HEAD(a) ((void *)(&(a)))
78
willy tarreau80862a32006-04-12 19:15:57 +020079#define LIST_INIT(l) ((l)->n = (l)->p = (l))
80
Willy Tarreau2b1dccd2007-05-07 00:18:32 +020081#define LIST_HEAD_INIT(l) { &l, &l }
82
willy tarreau80862a32006-04-12 19:15:57 +020083/* adds an element at the beginning of a list ; returns the element */
84#define LIST_ADD(lh, el) ({ (el)->n = (lh)->n; (el)->n->p = (lh)->n = (el); (el)->p = (lh); (el); })
85
86/* adds an element at the end of a list ; returns the element */
87#define LIST_ADDQ(lh, el) ({ (el)->p = (lh)->p; (el)->p->n = (lh)->p = (el); (el)->n = (lh); (el); })
88
89/* removes an element from a list and returns it */
90#define LIST_DEL(el) ({ typeof(el) __ret = (el); (el)->n->p = (el)->p; (el)->p->n = (el)->n; (__ret); })
91
92/* returns a pointer of type <pt> to a structure containing a list head called
93 * <el> at address <lh>. Note that <lh> can be the result of a function or macro
94 * since it's used only once.
95 * Example: LIST_ELEM(cur_node->args.next, struct node *, args)
96 */
97#define LIST_ELEM(lh, pt, el) ((pt)(((void *)(lh)) - ((void *)&((pt)NULL)->el)))
98
99/* checks if the list head <lh> is empty or not */
100#define LIST_ISEMPTY(lh) ((lh)->n == (lh))
101
102/* returns a pointer of type <pt> to a structure following the element
103 * which contains list head <lh>, which is known as element <el> in
104 * struct pt.
105 * Example: LIST_NEXT(args, struct node *, list)
106 */
107#define LIST_NEXT(lh, pt, el) (LIST_ELEM((lh)->n, pt, el))
108
109
110/* returns a pointer of type <pt> to a structure preceeding the element
111 * which contains list head <lh>, which is known as element <el> in
112 * struct pt.
113 */
114#define LIST_PREV(lh, pt, el) (LIST_ELEM((lh)->p, pt, el))
115
116/*
Willy Tarreaub9c62b92007-05-02 20:46:49 +0200117 * Simpler FOREACH_ITEM macro inspired from Linux sources.
118 * Iterates <item> through a list of items of type "typeof(*item)" which are
119 * linked via a "struct list" member named <member>. A pointer to the head of
120 * the list is passed in <list_head>. No temporary variable is needed. Note
121 * that <item> must not be modified during the loop.
122 * Example: list_for_each_entry(cur_acl, known_acl, list) { ... };
123 */
124#define list_for_each_entry(item, list_head, member) \
125 for (item = LIST_ELEM((list_head)->n, typeof(item), member); \
126 &item->member != (list_head); \
127 item = LIST_ELEM(item->member.n, typeof(item), member))
128
129/*
130 * Simpler FOREACH_ITEM_SAFE macro inspired from Linux sources.
131 * Iterates <item> through a list of items of type "typeof(*item)" which are
132 * linked via a "struct list" member named <member>. A pointer to the head of
133 * the list is passed in <list_head>. A temporary variable <back> of same type
134 * as <item> is needed so that <item> may safely be deleted if needed.
135 * Example: list_for_each_entry_safe(cur_acl, tmp, known_acl, list) { ... };
136 */
137#define list_for_each_entry_safe(item, back, list_head, member) \
138 for (item = LIST_ELEM((list_head)->n, typeof(item), member), \
139 back = LIST_ELEM(item->member.n, typeof(item), member); \
140 &item->member != (list_head); \
141 item = back, back = LIST_ELEM(back->member.n, typeof(back), member))
142
143
Willy Tarreau2dd0d472006-06-29 17:53:05 +0200144#endif /* _COMMON_MINI_CLIST_H */