external/gpl2/lvm2/dist/lib/datastruct/list.h

   1 /*      $NetBSD$        */
   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