1/*	$NetBSD: list.h,v 1.1.1.1 2008/12/22 00:18:36 haad Exp $	*/
2
3/*
4 * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.
5 * Copyright (C) 2004-2007 Red Hat, Inc. All rights reserved.
6 *
7 * This file is part of LVM2.
8 *
9 * This copyrighted material is made available to anyone wishing to use,
10 * modify, copy, or redistribute it subject to the terms and conditions
11 * of the GNU Lesser General Public License v.2.1.
12 *
13 * You should have received a copy of the GNU Lesser General Public License
14 * along with this program; if not, write to the Free Software Foundation,
15 * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16 */
17
18#ifndef _LVM_LIST_H
19#define _LVM_LIST_H
20
21#include <assert.h>
22
23/*
24 * A list consists of a list head plus elements.
25 * Each element has 'next' and 'previous' pointers.
26 * The list head's pointers point to the first and the last element.
27 */
28
29struct dm_list {
30	struct dm_list *n, *p;
31};
32
33/*
34 * Initialise a list before use.
35 * The list head's next and previous pointers point back to itself.
36 */
37#define DM_LIST_INIT(name)	struct dm_list name = { &(name), &(name) }
38void dm_list_init(struct dm_list *head);
39
40/*
41 * Insert an element before 'head'.
42 * If 'head' is the list head, this adds an element to the end of the list.
43 */
44void dm_list_add(struct dm_list *head, struct dm_list *elem);
45
46/*
47 * Insert an element after 'head'.
48 * If 'head' is the list head, this adds an element to the front of the list.
49 */
50void dm_list_add_h(struct dm_list *head, struct dm_list *elem);
51
52/*
53 * Delete an element from its list.
54 * Note that this doesn't change the element itself - it may still be safe
55 * to follow its pointers.
56 */
57void dm_list_del(struct dm_list *elem);
58
59/*
60 * Remove an element from existing list and insert before 'head'.
61 */
62void dm_list_move(struct dm_list *head, struct dm_list *elem);
63
64/*
65 * Is the list empty?
66 */
67int dm_list_empty(const struct dm_list *head);
68
69/*
70 * Is this the first element of the list?
71 */
72int dm_list_start(const struct dm_list *head, const struct dm_list *elem);
73
74/*
75 * Is this the last element of the list?
76 */
77int dm_list_end(const struct dm_list *head, const struct dm_list *elem);
78
79/*
80 * Return first element of the list or NULL if empty
81 */
82struct dm_list *dm_list_first(const struct dm_list *head);
83
84/*
85 * Return last element of the list or NULL if empty
86 */
87struct dm_list *dm_list_last(const struct dm_list *head);
88
89/*
90 * Return the previous element of the list, or NULL if we've reached the start.
91 */
92struct dm_list *dm_list_prev(const struct dm_list *head, const struct dm_list *elem);
93
94/*
95 * Return the next element of the list, or NULL if we've reached the end.
96 */
97struct dm_list *dm_list_next(const struct dm_list *head, const struct dm_list *elem);
98
99/*
100 * Given the address v of an instance of 'struct dm_list' called 'head'
101 * contained in a structure of type t, return the containing structure.
102 */
103#define dm_list_struct_base(v, t, head) \
104    ((t *)((uintptr_t)(v) - (uintptr_t)&((t *) 0)->head))
105
106/*
107 * Given the address v of an instance of 'struct dm_list list' contained in
108 * a structure of type t, return the containing structure.
109 */
110#define dm_list_item(v, t) dm_list_struct_base((v), t, list)
111
112/*
113 * Given the address v of one known element e in a known structure of type t,
114 * return another element f.
115 */
116#define dm_struct_field(v, t, e, f) \
117    (((t *)((uintptr_t)(v) - (uintptr_t)&((t *) 0)->e))->f)
118
119/*
120 * Given the address v of a known element e in a known structure of type t,
121 * return the list head 'list'
122 */
123#define dm_list_head(v, t, e) dm_struct_field(v, t, e, list)
124
125/*
126 * Set v to each element of a list in turn.
127 */
128#define dm_list_iterate(v, head) \
129	for (v = (head)->n; v != head; v = v->n)
130
131/*
132 * Set v to each element in a list in turn, starting from the element
133 * in front of 'start'.
134 * You can use this to 'unwind' a list_iterate and back out actions on
135 * already-processed elements.
136 * If 'start' is 'head' it walks the list backwards.
137 */
138#define dm_list_uniterate(v, head, start) \
139	for (v = (start)->p; v != head; v = v->p)
140
141/*
142 * A safe way to walk a list and delete and free some elements along
143 * the way.
144 * t must be defined as a temporary variable of the same type as v.
145 */
146#define dm_list_iterate_safe(v, t, head) \
147	for (v = (head)->n, t = v->n; v != head; v = t, t = v->n)
148
149/*
150 * Walk a list, setting 'v' in turn to the containing structure of each item.
151 * The containing structure should be the same type as 'v'.
152 * The 'struct dm_list' variable within the containing structure is 'field'.
153 */
154#define dm_list_iterate_items_gen(v, head, field) \
155	for (v = dm_list_struct_base((head)->n, typeof(*v), field); \
156	     &v->field != (head); \
157	     v = dm_list_struct_base(v->field.n, typeof(*v), field))
158
159/*
160 * Walk a list, setting 'v' in turn to the containing structure of each item.
161 * The containing structure should be the same type as 'v'.
162 * The list should be 'struct dm_list list' within the containing structure.
163 */
164#define dm_list_iterate_items(v, head) dm_list_iterate_items_gen(v, (head), list)
165
166/*
167 * Walk a list, setting 'v' in turn to the containing structure of each item.
168 * The containing structure should be the same type as 'v'.
169 * The 'struct dm_list' variable within the containing structure is 'field'.
170 * t must be defined as a temporary variable of the same type as v.
171 */
172#define dm_list_iterate_items_gen_safe(v, t, head, field) \
173	for (v = dm_list_struct_base((head)->n, typeof(*v), field), \
174	     t = dm_list_struct_base(v->field.n, typeof(*v), field); \
175	     &v->field != (head); \
176	     v = t, t = dm_list_struct_base(v->field.n, typeof(*v), field))
177/*
178 * Walk a list, setting 'v' in turn to the containing structure of each item.
179 * The containing structure should be the same type as 'v'.
180 * The list should be 'struct dm_list list' within the containing structure.
181 * t must be defined as a temporary variable of the same type as v.
182 */
183#define dm_list_iterate_items_safe(v, t, head) \
184	dm_list_iterate_items_gen_safe(v, t, (head), list)
185
186/*
187 * Walk a list backwards, setting 'v' in turn to the containing structure
188 * of each item.
189 * The containing structure should be the same type as 'v'.
190 * The 'struct dm_list' variable within the containing structure is 'field'.
191 */
192#define dm_list_iterate_back_items_gen(v, head, field) \
193	for (v = dm_list_struct_base((head)->p, typeof(*v), field); \
194	     &v->field != (head); \
195	     v = dm_list_struct_base(v->field.p, typeof(*v), field))
196
197/*
198 * Walk a list backwards, setting 'v' in turn to the containing structure
199 * of each item.
200 * The containing structure should be the same type as 'v'.
201 * The list should be 'struct dm_list list' within the containing structure.
202 */
203#define dm_list_iterate_back_items(v, head) dm_list_iterate_back_items_gen(v, (head), list)
204
205/*
206 * Return the number of elements in a list by walking it.
207 */
208unsigned int dm_list_size(const struct dm_list *head);
209
210#endif
211