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 <stdbool.h> 29 #include <stddef.h> 30 31 /* 32 * This list data structure is a verbatim copy from wayland-util.h from the 33 * Wayland project; except that wl_ prefix has been removed. 34 */ 35 36 37 /** 38 * Doubly linked list implementation. This struct is used for both the list 39 * nodes and the list head. Use like this: 40 * 41 * @code 42 * 43 * struct foo { 44 * struct list list_of_bars; // the list head 45 * }; 46 * 47 * struct bar { 48 * struct list link; // links between the bars 49 * }; 50 * 51 * struct foo *f = zalloc(sizeof *f); 52 * struct bar *b = make_some_bar(); 53 * 54 * list_init(&f->list_of_bars); 55 * list_append(&f->list_of_bars, &b->link); 56 * list_remove(&b->link); 57 * @endcode 58 */ 59 struct list { 60 struct list *prev; 61 struct list *next; 62 }; 63 64 /** 65 * Initialize a list head. This function *must* be called once for each list 66 * head. This function *must not* be called for a node to be added to a 67 * list. 68 */ 69 void list_init(struct list *list); 70 71 /** 72 * Insert an element at the front of the list 73 */ 74 void list_insert(struct list *list, struct list *elm); 75 /** 76 * Append an element to the back of the list 77 */ 78 void list_append(struct list *list, struct list *elm); 79 80 /** 81 * Remove an element from list. 82 * 83 * Removing a list element is only possible once, the caller must track 84 * whether the list node has already been removed. 85 * 86 */ 87 void list_remove(struct list *elm); 88 /** 89 * Returns true if the given list head is an empty list. 90 */ 91 bool list_empty(const struct list *list); 92 93 /** 94 * Return the 'type' parent container struct of 'ptr' of which 95 * 'member' is our 'ptr' field. For example: 96 * 97 * @code 98 * struct foo { // the parent container struct 99 * uint32_t a; 100 * struct bar bar_member; // the member field 101 * }; 102 * 103 * struct foo *f = zalloc(sizeof *f); 104 * struct bar *b = &f->bar_member; 105 * struct foo *f2 = container_of(b, struct foo, bar_member); 106 * 107 * assert(f == f2); 108 * @endcode 109 */ 110 #define container_of(ptr, type, member) \ 111 (__typeof__(type) *)((char *)(ptr) - \ 112 offsetof(__typeof__(type), member)) 113 114 /** 115 * Given a list 'head', return the first entry of type 'pos' that has a 116 * member 'link'. 117 * 118 * The 'pos' argument is solely used to determine the type be returned and 119 * not modified otherwise. It is common to use the same pointer that the 120 * return value of list_first_entry() is assigned to, for example: 121 * 122 * @code 123 * struct foo { 124 * struct list list_of_bars; 125 * }; 126 * 127 * struct bar { 128 * struct list link; 129 * } 130 * 131 * struct foo *f = get_a_foo(); 132 * struct bar *b = 0; // initialize to avoid static analysis errors 133 * b = list_first_entry(&f->list_of_bars, b, link); 134 * @endcode 135 */ 136 #define list_first_entry(head, pointer_of_type, member) \ 137 container_of((head)->next, __typeof__(*pointer_of_type), member) 138 139 /** 140 * Given a list 'head', return the first entry of type 'container_type' that 141 * has a member 'link'. 142 * 143 * @code 144 * struct foo { 145 * struct list list_of_bars; 146 * }; 147 * 148 * struct bar { 149 * struct list link; 150 * } 151 * 152 * struct foo *f = get_a_foo(); 153 * struct bar *b = list_first_entry(&f->list_of_bars, struct bar, link); 154 * @endcode 155 */ 156 #define list_first_entry_by_type(head, container_type, member) \ 157 container_of((head)->next, container_type, member) 158 159 /** 160 * Iterate through the list. 161 * 162 * @code 163 * struct foo *f = get_a_foo(); 164 * struct bar *element; 165 * list_for_each(element, &f->list_of_bars, link) { 166 * } 167 * @endcode 168 * 169 * If a list node needs to be removed during iteration, use 170 * list_for_each_safe(). 171 */ 172 #define list_for_each(pos, head, member) \ 173 for (pos = list_first_entry_by_type(head, __typeof__(*pos), member); \ 174 &pos->member != (head); \ 175 pos = list_first_entry_by_type(&pos->member, __typeof__(*pos), member)) 176 177 /** 178 * Iterate through the list. Equivalent to list_for_each() but allows 179 * calling list_remove() on the element. 180 * 181 * @code 182 * struct foo *f = get_a_foo(); 183 * struct bar *element; 184 * list_for_each(element, tmp, &f->list_of_bars, link) { 185 * list_remove(&element->link); 186 * } 187 * @endcode 188 */ 189 #define list_for_each_safe(pos, head, member) \ 190 pos = list_first_entry_by_type(head, __typeof__(*pos), member); \ 191 for (__typeof__(pos) _tmp = list_first_entry_by_type(&pos->member, __typeof__(*_tmp), member); \ 192 &pos->member != (head); \ 193 pos = _tmp, \ 194 _tmp = list_first_entry_by_type(&pos->member, __typeof__(*_tmp), member)) 195