1/** 2 * \file simple_list.h 3 * Simple macros for type-safe, intrusive lists. 4 * 5 * Intended to work with a list sentinal which is created as an empty 6 * list. Insert & delete are O(1). 7 * 8 * \author 9 * (C) 1997, Keith Whitwell 10 */ 11 12/* 13 * Mesa 3-D graphics library 14 * Version: 3.5 15 * 16 * Copyright (C) 1999-2001 Brian Paul All Rights Reserved. 17 * 18 * Permission is hereby granted, free of charge, to any person obtaining a 19 * copy of this software and associated documentation files (the "Software"), 20 * to deal in the Software without restriction, including without limitation 21 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 22 * and/or sell copies of the Software, and to permit persons to whom the 23 * Software is furnished to do so, subject to the following conditions: 24 * 25 * The above copyright notice and this permission notice shall be included 26 * in all copies or substantial portions of the Software. 27 * 28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 29 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 30 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 31 * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 32 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 33 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 34 */ 35 36 37#ifndef _U_SIMPLE_LIST_H_ 38#define _U_SIMPLE_LIST_H_ 39 40/** 41 * Remove an element from list. 42 * 43 * \param elem element to remove. 44 */ 45#define remove_from_list(elem) \ 46do { \ 47 (elem)->next->prev = (elem)->prev; \ 48 (elem)->prev->next = (elem)->next; \ 49 (elem)->next = elem; \ 50 (elem)->prev = elem; \ 51} while (0) 52 53/** 54 * Insert an element to the list head. 55 * 56 * \param list list. 57 * \param elem element to insert. 58 */ 59#define insert_at_head(list, elem) \ 60do { \ 61 (elem)->prev = list; \ 62 (elem)->next = (list)->next; \ 63 (list)->next->prev = elem; \ 64 (list)->next = elem; \ 65} while(0) 66 67/** 68 * Insert an element to the list tail. 69 * 70 * \param list list. 71 * \param elem element to insert. 72 */ 73#define insert_at_tail(list, elem) \ 74do { \ 75 (elem)->next = list; \ 76 (elem)->prev = (list)->prev; \ 77 (list)->prev->next = elem; \ 78 (list)->prev = elem; \ 79} while(0) 80 81/** 82 * Move an element to the list head. 83 * 84 * \param list list. 85 * \param elem element to move. 86 */ 87#define move_to_head(list, elem) \ 88do { \ 89 remove_from_list(elem); \ 90 insert_at_head(list, elem); \ 91} while (0) 92 93/** 94 * Move an element to the list tail. 95 * 96 * \param list list. 97 * \param elem element to move. 98 */ 99#define move_to_tail(list, elem) \ 100do { \ 101 remove_from_list(elem); \ 102 insert_at_tail(list, elem); \ 103} while (0) 104 105/** 106 * Make a empty list empty. 107 * 108 * \param sentinal list (sentinal element). 109 */ 110#define make_empty_list(sentinal) \ 111do { \ 112 (sentinal)->next = sentinal; \ 113 (sentinal)->prev = sentinal; \ 114} while (0) 115 116/** 117 * Get list first element. 118 * 119 * \param list list. 120 * 121 * \return pointer to first element. 122 */ 123#define first_elem(list) ((list)->next) 124 125/** 126 * Get list last element. 127 * 128 * \param list list. 129 * 130 * \return pointer to last element. 131 */ 132#define last_elem(list) ((list)->prev) 133 134/** 135 * Get next element. 136 * 137 * \param elem element. 138 * 139 * \return pointer to next element. 140 */ 141#define next_elem(elem) ((elem)->next) 142 143/** 144 * Get previous element. 145 * 146 * \param elem element. 147 * 148 * \return pointer to previous element. 149 */ 150#define prev_elem(elem) ((elem)->prev) 151 152/** 153 * Test whether element is at end of the list. 154 * 155 * \param list list. 156 * \param elem element. 157 * 158 * \return non-zero if element is at end of list, or zero otherwise. 159 */ 160#define at_end(list, elem) ((elem) == (list)) 161 162/** 163 * Test if a list is empty. 164 * 165 * \param list list. 166 * 167 * \return non-zero if list empty, or zero otherwise. 168 */ 169#define is_empty_list(list) ((list)->next == (list)) 170 171/** 172 * Walk through the elements of a list. 173 * 174 * \param ptr pointer to the current element. 175 * \param list list. 176 * 177 * \note It should be followed by a { } block or a single statement, as in a \c 178 * for loop. 179 */ 180#define foreach(ptr, list) \ 181 for( ptr=(list)->next ; ptr!=list ; ptr=(ptr)->next ) 182 183/** 184 * Walk through the elements of a list. 185 * 186 * Same as #foreach but lets you unlink the current value during a list 187 * traversal. Useful for freeing a list, element by element. 188 * 189 * \param ptr pointer to the current element. 190 * \param t temporary pointer. 191 * \param list list. 192 * 193 * \note It should be followed by a { } block or a single statement, as in a \c 194 * for loop. 195 */ 196#define foreach_s(ptr, t, list) \ 197 for(ptr=(list)->next,t=(ptr)->next; list != ptr; ptr=t, t=(t)->next) 198 199#endif /* _U_SIMPLE_LIST_H_ */ 200