blob: fca2d76270a9961e244b2621a5f349766e375302 [file] [log] [blame]
willy tarreau80862a32006-04-12 19:15:57 +02001/*
2 * list.h : list manipulation macros and structures.
Willy Tarreau47d94042008-06-23 22:39:37 +02003 * Copyright 2002-2008 Willy Tarreau <w@1wt.eu>
willy tarreau80862a32006-04-12 19:15:57 +02004 *
5 */
6
Willy Tarreau2dd0d472006-06-29 17:53:05 +02007#ifndef _COMMON_MINI_CLIST_H
8#define _COMMON_MINI_CLIST_H
willy tarreau80862a32006-04-12 19:15:57 +02009
Willy Tarreaue3ba5f02006-06-29 18:54:54 +020010#include <common/config.h>
11
willy tarreau80862a32006-04-12 19:15:57 +020012/* these are circular or bidirectionnal lists only. Each list pointer points to
13 * another list pointer in a structure, and not the structure itself. The
14 * pointer to the next element MUST be the first one so that the list is easily
15 * cast as a single linked list or pointer.
16 */
17struct list {
18 struct list *n; /* next */
19 struct list *p; /* prev */
20};
21
Willy Tarreaubd578bb2007-10-28 11:41:06 +010022/* First undefine some macros which happen to also be defined on OpenBSD,
23 * in sys/queue.h, used by sys/event.h
24 */
25#undef LIST_HEAD
26#undef LIST_INIT
27#undef LIST_NEXT
28
Willy Tarreaubaaee002006-06-26 02:48:02 +020029#define LIST_HEAD(a) ((void *)(&(a)))
30
willy tarreau80862a32006-04-12 19:15:57 +020031#define LIST_INIT(l) ((l)->n = (l)->p = (l))
32
Willy Tarreau2b1dccd2007-05-07 00:18:32 +020033#define LIST_HEAD_INIT(l) { &l, &l }
34
willy tarreau80862a32006-04-12 19:15:57 +020035/* dual linked lists :
36 * Start = (struct list *) pointer to the next elem's prev list entry
37 * For each element :
38 * - prev = pointer to previous element's next (or start). Cannot be NULL
39 * - next = pointer to next element's prev. NULL = end.
40 *
41 */
42
Willy Tarreau40cf67d2007-04-28 12:42:06 +020043/* adds an element at the beginning of a dual-linked list ; returns the element */
Willy Tarreau47d94042008-06-23 22:39:37 +020044#define DLIST_ADD(lh, el) ({ typeof(el) __ret = (el); __ret->n = (void *)(lh); __ret->p = (void *)&(lh); if (likely(__ret->n != NULL)) __ret->n->p = __ret; (lh) = (typeof(lh))&__ret->n; __ret; })
Willy Tarreau40cf67d2007-04-28 12:42:06 +020045
46/* removes an element from a dual-linked list and returns it */
Willy Tarreau47d94042008-06-23 22:39:37 +020047#define DLIST_DEL(el) ({ typeof(el) __ret = (el); if (likely(__ret->n != NULL)) __ret->n->p = __ret->p; __ret->p->n = __ret->n; __ret; })
Willy Tarreau40cf67d2007-04-28 12:42:06 +020048
49/*
50 * iterates through a list of items of type "<struct_type>" which are
51 * linked via a "struct list" member named <struct_member>. The head of the
52 * list is stored at a location designed by <list_head>, which should be a
53 * "struct list *". A variable <end_item> of type "<struct_type>" will
54 * be used as temporary end of list pointer. It can be derived from <list_head>
55 * since this one is only used before. <list_head> will be modified except for
56 * foreach_dlist_item_cst which is slightly slower.
57 * Major difference between FOREACH_ITEM is that it stops at NULL.
58 * Example: foreach_dlist_item(cur_node, args, struct node *, list) { ... };
59 * foreach_dlist_item_cst(cur_node, &node->args, struct node *, list) { ... };
60 */
61#define foreach_dlist_item_cst(iterator, list_head, struct_type, struct_member) \
62 for ((iterator) = LIST_ELEM(&(list_head), struct_type, struct_member.n); \
63 ((iterator)->struct_member.n != NULL) && \
64 (((iterator) = LIST_ELEM((iterator)->struct_member.n, struct_type, struct_member.n)), 1);\
65 )
66
67#define foreach_dlist_item(iterator, var_list_head, struct_type, struct_member) \
68 while ((var_list_head != NULL) && \
69 ((var_list_head=((iterator)=LIST_ELEM(var_list_head, struct_type, struct_member.n))->struct_member.n), 1))
70
71/*
72 * Like foreach_dlist_item, except that this one only operates on the head of
73 * the list. It's to the inner instructions to iterate the list head. If not,
74 * this will be an endless loop.
75 */
76#define while_dlist_item(iterator, var_list_head, struct_type, struct_member) \
77 while ((var_list_head != NULL) && \
78 (((iterator)=LIST_ELEM(var_list_head, struct_type, struct_member.n)),1))
79
80
willy tarreau80862a32006-04-12 19:15:57 +020081/****** circular lists ********/
82
83/* 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 * DEPRECATED !!! Use list_for_each_entry() below instead !
118 *
willy tarreau80862a32006-04-12 19:15:57 +0200119 * iterates through a list of items of type "<struct_type>" which are
120 * linked via a "struct list" member named <struct_member>. The head of the
121 * list is stored at a location designed by <list_head>, which should be a
122 * "struct list *". A variable <end_item> of type "<struct_type>" will
123 * be used as temporary end of list pointer. It can be derived from <list_head>
124 * since this one is only used before.
125 * Example: FOREACH_ITEM(cur_node, &node->args, node, struct node *, neigh) { ... };
126 */
127#define FOREACH_ITEM(iterator, list_head, end_item, struct_type, struct_member) \
128 iterator = end_item = LIST_ELEM(list_head, struct_type, struct_member); \
129 while (((iterator) = LIST_ELEM((iterator)->struct_member.n, \
130 struct_type, struct_member)) != (end_item))
131
132/*
Willy Tarreaub9c62b92007-05-02 20:46:49 +0200133 * DEPRECATED !!! Use list_for_each_entry_safe() below instead !
134 *
willy tarreau80862a32006-04-12 19:15:57 +0200135 * idem except that this one is safe against deletion, but it needs a backup
136 * pointer of the element after the iterator.
137 * Example: FOREACH_ITEM_SAFE(cur_node, backup, &node->args, node, struct node *, neigh) { ... };
138 */
139#define FOREACH_ITEM_SAFE(iterator, backup, list_head, end_item, struct_type, struct_member) \
140 end_item = LIST_ELEM(list_head, struct_type, struct_member); \
141 iterator = LIST_ELEM((end_item)->struct_member.n, struct_type, struct_member); \
142 if ((iterator) != (end_item)) \
143 backup = LIST_ELEM((iterator)->struct_member.n, struct_type, struct_member); \
144 for ( ; (iterator) != (end_item); (iterator) = (backup), \
145 backup = LIST_ELEM((iterator)->struct_member.n, struct_type, struct_member))
146
Willy Tarreaub9c62b92007-05-02 20:46:49 +0200147/*
148 * Simpler FOREACH_ITEM macro inspired from Linux sources.
149 * Iterates <item> through a list of items of type "typeof(*item)" which are
150 * linked via a "struct list" member named <member>. A pointer to the head of
151 * the list is passed in <list_head>. No temporary variable is needed. Note
152 * that <item> must not be modified during the loop.
153 * Example: list_for_each_entry(cur_acl, known_acl, list) { ... };
154 */
155#define list_for_each_entry(item, list_head, member) \
156 for (item = LIST_ELEM((list_head)->n, typeof(item), member); \
157 &item->member != (list_head); \
158 item = LIST_ELEM(item->member.n, typeof(item), member))
159
160/*
161 * Simpler FOREACH_ITEM_SAFE macro inspired from Linux sources.
162 * Iterates <item> through a list of items of type "typeof(*item)" which are
163 * linked via a "struct list" member named <member>. A pointer to the head of
164 * the list is passed in <list_head>. A temporary variable <back> of same type
165 * as <item> is needed so that <item> may safely be deleted if needed.
166 * Example: list_for_each_entry_safe(cur_acl, tmp, known_acl, list) { ... };
167 */
168#define list_for_each_entry_safe(item, back, list_head, member) \
169 for (item = LIST_ELEM((list_head)->n, typeof(item), member), \
170 back = LIST_ELEM(item->member.n, typeof(item), member); \
171 &item->member != (list_head); \
172 item = back, back = LIST_ELEM(back->member.n, typeof(back), member))
173
174
Willy Tarreau2dd0d472006-06-29 17:53:05 +0200175#endif /* _COMMON_MINI_CLIST_H */