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