1 /* $NetBSD: list.h,v 1.1.1.1 2008/12/22 00:17:54 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 29 struct 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) } 38 void 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 */ 44 void 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 */ 50 void 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 */ 57 void dm_list_del(struct dm_list *elem); 58 59 /* 60 * Remove an element from existing list and insert before 'head'. 61 */ 62 void dm_list_move(struct dm_list *head, struct dm_list *elem); 63 64 /* 65 * Is the list empty? 66 */ 67 int dm_list_empty(const struct dm_list *head); 68 69 /* 70 * Is this the first element of the list? 71 */ 72 int 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 */ 77 int 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 */ 82 struct dm_list *dm_list_first(const struct dm_list *head); 83 84 /* 85 * Return last element of the list or NULL if empty 86 */ 87 struct 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 */ 92 struct 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 */ 97 struct 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 */ 208 unsigned int dm_list_size(const struct dm_list *head); 209 210 #endif 211