1 /* 2 * Copyright © 2008-2011 Kristian Høgsberg 3 * Copyright © 2011 Intel Corporation 4 * Copyright © 2013-2015 Red Hat, Inc. 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a 7 * copy of this software and associated documentation files (the "Software"), 8 * to deal in the Software without restriction, including without limitation 9 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 10 * and/or sell copies of the Software, and to permit persons to whom the 11 * Software is furnished to do so, subject to the following conditions: 12 * 13 * The above copyright notice and this permission notice (including the next 14 * paragraph) shall be included in all copies or substantial portions of the 15 * Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 20 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 22 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 23 * DEALINGS IN THE SOFTWARE. 24 */ 25 26 #pragma once 27 28 #include "config.h" 29 30 #include <stdbool.h> 31 #include <stddef.h> 32 33 /* 34 * This list data structure is a verbatim copy from wayland-util.h from the 35 * Wayland project; except that wl_ prefix has been removed. 36 */ 37 38 39 /** 40 * Doubly linked list implementation. This struct is used for both the list 41 * nodes and the list head. Use like this: 42 * 43 * @code 44 * 45 * struct foo { 46 * struct list list_of_bars; // the list head 47 * }; 48 * 49 * struct bar { 50 * struct list link; // links between the bars 51 * }; 52 * 53 * struct foo *f = zalloc(sizeof *f); 54 * struct bar *b = make_some_bar(); 55 * 56 * list_init(&f->list_of_bars); 57 * list_append(&f->list_of_bars, &b->link); 58 * list_remove(&b->link); 59 * @endcode 60 */ 61 struct list { 62 struct list *prev; 63 struct list *next; 64 }; 65 66 /** 67 * Initialize a list head. This function *must* be called once for each list 68 * head. This function *must not* be called for a node to be added to a 69 * list. 70 */ 71 void list_init(struct list *list); 72 73 /** 74 * Insert an element at the front of the list 75 */ 76 void list_insert(struct list *list, struct list *elm); 77 /** 78 * Append an element to the back of the list 79 */ 80 void list_append(struct list *list, struct list *elm); 81 82 /** 83 * Remove an element from list. 84 * 85 * Removing a list element is only possible once, the caller must track 86 * whether the list node has already been removed. 87 * 88 */ 89 void list_remove(struct list *elm); 90 /** 91 * Returns true if the given list head is an empty list. 92 */ 93 bool list_empty(const struct list *list); 94 95 /** 96 * Return the 'type' parent container struct of 'ptr' of which 97 * 'member' is our 'ptr' field. For example: 98 * 99 * @code 100 * struct foo { // the parent container struct 101 * uint32_t a; 102 * struct bar bar_member; // the member field 103 * }; 104 * 105 * struct foo *f = zalloc(sizeof *f); 106 * struct bar *b = &f->bar_member; 107 * struct foo *f2 = container_of(b, struct foo, bar_member); 108 * 109 * assert(f == f2); 110 * @endcode 111 */ 112 #define container_of(ptr, type, member) \ 113 (__typeof__(type) *)((char *)(ptr) - \ 114 offsetof(__typeof__(type), member)) 115 116 /** 117 * Given a list 'head', return the first entry of type 'pos' that has a 118 * member 'link'. 119 * 120 * The 'pos' argument is solely used to determine the type be returned and 121 * not modified otherwise. It is common to use the same pointer that the 122 * return value of list_first_entry() is assigned to, for example: 123 * 124 * @code 125 * struct foo { 126 * struct list list_of_bars; 127 * }; 128 * 129 * struct bar { 130 * struct list link; 131 * } 132 * 133 * struct foo *f = get_a_foo(); 134 * struct bar *b = 0; // initialize to avoid static analysis errors 135 * b = list_first_entry(&f->list_of_bars, b, link); 136 * @endcode 137 */ 138 #define list_first_entry(head, pointer_of_type, member) \ 139 container_of((head)->next, __typeof__(*pointer_of_type), member) 140 141 /** 142 * Given a list 'head', return the first entry of type 'container_type' that 143 * has a member 'link'. 144 * 145 * @code 146 * struct foo { 147 * struct list list_of_bars; 148 * }; 149 * 150 * struct bar { 151 * struct list link; 152 * } 153 * 154 * struct foo *f = get_a_foo(); 155 * struct bar *b = list_first_entry(&f->list_of_bars, struct bar, link); 156 * @endcode 157 */ 158 #define list_first_entry_by_type(head, container_type, member) \ 159 container_of((head)->next, container_type, member) 160 161 /** 162 * Iterate through the list. 163 * 164 * @code 165 * struct foo *f = get_a_foo(); 166 * struct bar *element; 167 * list_for_each(element, &f->list_of_bars, link) { 168 * } 169 * @endcode 170 * 171 * If a list node needs to be removed during iteration, use 172 * list_for_each_safe(). 173 */ 174 #define list_for_each(pos, head, member) \ 175 for (pos = list_first_entry_by_type(head, __typeof__(*pos), member); \ 176 &pos->member != (head); \ 177 pos = list_first_entry_by_type(&pos->member, __typeof__(*pos), member)) 178 179 /** 180 * Iterate through the list. Equivalent to list_for_each() but allows 181 * calling list_remove() on the element. 182 * 183 * @code 184 * struct foo *f = get_a_foo(); 185 * struct bar *element; 186 * list_for_each(element, tmp, &f->list_of_bars, link) { 187 * list_remove(&element->link); 188 * } 189 * @endcode 190 */ 191 #define list_for_each_safe(pos, head, member) \ 192 for (__typeof__(pos) _tmp = ({ \ 193 pos = list_first_entry_by_type(head, __typeof__(*pos), member); \ 194 list_first_entry_by_type(&pos->member, __typeof__(*_tmp), member); \ 195 }); \ 196 &pos->member != (head); \ 197 pos = _tmp, \ 198 _tmp = list_first_entry_by_type(&pos->member, __typeof__(*_tmp), member)) 199