1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause OR GPL-2.0 3 * 4 * This file is provided under a dual BSD/GPLv2 license. When using or 5 * redistributing this file, you may do so under either license. 6 * 7 * GPL LICENSE SUMMARY 8 * 9 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved. 10 * 11 * This program is free software; you can redistribute it and/or modify 12 * it under the terms of version 2 of the GNU General Public License as 13 * published by the Free Software Foundation. 14 * 15 * This program is distributed in the hope that it will be useful, but 16 * WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 18 * General Public License for more details. 19 * 20 * You should have received a copy of the GNU General Public License 21 * along with this program; if not, write to the Free Software 22 * Foundation, Inc., 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA. 23 * The full GNU General Public License is included in this distribution 24 * in the file called LICENSE.GPL. 25 * 26 * BSD LICENSE 27 * 28 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved. 29 * All rights reserved. 30 * 31 * Redistribution and use in source and binary forms, with or without 32 * modification, are permitted provided that the following conditions 33 * are met: 34 * 35 * * Redistributions of source code must retain the above copyright 36 * notice, this list of conditions and the following disclaimer. 37 * * Redistributions in binary form must reproduce the above copyright 38 * notice, this list of conditions and the following disclaimer in 39 * the documentation and/or other materials provided with the 40 * distribution. 41 * 42 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 43 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 44 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 45 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 46 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 47 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 48 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 49 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 50 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 51 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 52 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 53 * 54 * $FreeBSD$ 55 */ 56 #ifndef _SCI_FAST_LIST_HEADER_ 57 #define _SCI_FAST_LIST_HEADER_ 58 59 /** 60 * @file 61 * 62 * @brief Header file that contains basic Linked List manipulation macros. 63 * These macros implement a double linked list (SCI_FAST_LIST_T) that is 64 * circular in nature. This means that the next and prev pointers for 65 * an empty queue head always the address of the queue head 66 * SCI_FAST_LIST_T. Likewise an element that has been removed from 67 * a queue will have its next and prev pointer set to the address of 68 * the SCI_FAST_LIST_T found in the structure just removed from the 69 * queue. Pointers in this implementation never == NULL. 70 * 71 * Definitions: 72 * - anchor : This is the list container and has a 73 * pointer to both the head and tail of the 74 * list elements 75 * - element: This is the list element not the actual 76 * object but the list element which has a 77 * pointer to the object. 78 */ 79 80 //****************************************************************************** 81 //* 82 //* P U B L I C M E T H O D S 83 //* 84 //****************************************************************************** 85 86 /** 87 * Initialize the double linked list anchor. The other macros require the list 88 * anchor to be set up using this macro. 89 */ 90 #define sci_fast_list_init(anchor) \ 91 { \ 92 (anchor)->list_head = NULL; \ 93 (anchor)->list_tail = NULL; \ 94 (anchor)->element_count = 0; \ 95 } 96 97 /** 98 * Initialize the sci_fast_list_element to point to its owning object 99 */ 100 #define sci_fast_list_element_init(list_object, element) \ 101 { \ 102 (element)->object = (list_object); \ 103 (element)->next = (element)->prev = NULL; \ 104 (element)->owning_list = NULL; \ 105 } 106 107 /** 108 * See if there is anything on the list by checking the list anchor. 109 */ 110 #define sci_fast_list_is_empty(anchor) ((anchor)->list_head == NULL) 111 112 /** 113 * Return a pointer to the element at the head of the sci_fast_list. The 114 * item is NOT removed from the list. 115 * 116 * NOTE: This macro will always return a value, even if the list is empty. 117 * You must insure the list is not empty or use Dlist_safeGetHead. 118 * 119 * element - A pointer into which to save the address of the structure 120 * containing the SCI_FAST_LIST at the list head. 121 */ 122 #define sci_fast_list_get_head(anchor) \ 123 ((anchor)->list_head == NULL ? NULL: (anchor)->list_head->object) 124 125 /** 126 * Return a pointer to the element at the tail of the sci_fast_list. The item 127 * is NOT removed from the list. 128 * 129 * NOTE: This macro will always return a value, even if the list is empty. 130 * You must insure the list is not empty or use Dlist_safeGetHead. 131 * 132 * element - A pointer into which to save the address of the structure 133 * containing the SCI_FAST_LIST at the list head. 134 */ 135 #define sci_fast_list_get_tail(anchor) \ 136 ((anchor)->list_tail == NULL ? NULL: (anchor)->list_head->object) 137 138 /** 139 * This method will get the next dListField in the SCI_FAST_LIST. This method 140 * returns a pointer to a SCI_FAST_LIST object. 141 */ 142 #define sci_fast_list_get_next(element) ((element)->next) 143 144 /** 145 * This method will get the prev dListField in the SCI_FAST_LIST. This method 146 * returns a pointer to a SCI_FAST_LIST object. 147 */ 148 #define sci_fast_list_get_prev(element) ((element)->prev) 149 150 151 /** 152 * This method returns the object that is represented by this 153 * sci_fast_list_element 154 */ 155 #define sci_fast_list_get_object(element) ((element)->object) 156 157 /** 158 * This method will determine if the supplied dListField is on a SCI_FAST_LIST. 159 * If the element has only one dListField but can be on more than one list, 160 * this will only tell you that it is on one of them. If the element has 161 * multiple dListFields and can exist on multiple lists at the same time, this 162 * macro can tell you exactly which list it is on. 163 */ 164 #define sci_fast_list_is_on_a_list(element) ((element)->owning_list != NULL) 165 166 /** 167 * This method will determine if the supplied dListFieldName is on the given 168 * specified list? If the element can be on more than one list, this 169 * allows you to determine exactly which list it is on. Performs a linear 170 * search through the list. 171 * result - BOOL_T that will contain the result of the search. 172 * TRUE - item is on the list described by head. 173 * FALSE - item is not on the list. 174 */ 175 #define sci_fast_list_is_on_this_list(anchor, element) \ 176 ((element)->owning_list == (anchor)) 177 178 //****************************************************************************** 179 //* 180 //* T Y P E S 181 //* 182 //****************************************************************************** 183 184 /** 185 * @struct SCI_FAST_LIST 186 * 187 * @brief the list owner or list anchor for a set of SCI_FAST_LIST 188 * elements. 189 */ 190 typedef struct SCI_FAST_LIST 191 { 192 struct SCI_FAST_LIST_ELEMENT *list_head; 193 struct SCI_FAST_LIST_ELEMENT *list_tail; 194 int element_count; 195 } SCI_FAST_LIST_T; 196 197 /** 198 * @struct SCI_FAST_LIST_ELEMENT 199 * 200 * @brief This structure defines what a doubly linked list element contains. 201 */ 202 typedef struct SCI_FAST_LIST_ELEMENT 203 { 204 struct SCI_FAST_LIST_ELEMENT *next; 205 struct SCI_FAST_LIST_ELEMENT *prev; 206 struct SCI_FAST_LIST *owning_list; 207 void *object; 208 } SCI_FAST_LIST_ELEMENT_T; 209 210 211 /** 212 * Insert an element to be the new head of the list hanging off of the list 213 * anchor. An empty list has the list anchor pointing to itself. 214 * dListAnchor - The name of the SCI_FAST_LIST_T element that is the anchor 215 * of the queue. 216 * dListFieldBeingInserted - The SCI_FAST_LIST_T field in the data structure 217 * being queued. This SCI_FAST_LIST will become 218 * the new list head. 219 */ 220 INLINE 221 static void sci_fast_list_insert_head( 222 SCI_FAST_LIST_T *anchor, 223 SCI_FAST_LIST_ELEMENT_T *element 224 ) 225 { 226 element->owning_list = anchor; 227 element->prev = NULL; 228 if ( anchor->list_head == NULL ) 229 anchor->list_tail = element; 230 else 231 anchor->list_head->prev = element; 232 element->next = anchor->list_head; 233 anchor->list_head = element; 234 anchor->element_count++; 235 } 236 237 /** 238 * Insert an element at the tail of the list. Since the list is circular we 239 * can add the element at the tail through use the list anchors previous 240 * pointer. 241 * dListAnchor - The name of the SCI_FAST_LIST_T element that is the anchor 242 * of the queue. 243 * dListFieldBeingInserted - The SCI_FAST_LIST_T field in the data structure 244 * being queued. This SCI_FAST_LIST will become 245 * the new list head. 246 */ 247 INLINE 248 static void sci_fast_list_insert_tail( 249 SCI_FAST_LIST_T *anchor, 250 SCI_FAST_LIST_ELEMENT_T *element 251 ) 252 { 253 element->owning_list = anchor; 254 element->next = NULL; 255 if ( anchor->list_tail == NULL ) { 256 anchor->list_head = element; 257 } else { 258 anchor->list_tail->next = element; 259 } 260 element->prev = anchor->list_tail; 261 anchor->list_tail = element; 262 anchor->element_count++; 263 } 264 265 /** 266 * This method will remove a dListFieldName from the head of the list. 267 * 268 * NOTE: This macro will always return a value, even if the list is empty. 269 * You must insure the list is not empty or use Dlist_safeRemoveHead. 270 * 271 * element - A pointer into which to save the address of the structure 272 * containing the SCI_FAST_LIST at the list head. 273 */ 274 INLINE 275 static void *sci_fast_list_remove_head( 276 SCI_FAST_LIST_T *anchor 277 ) 278 { 279 void *object = NULL; 280 SCI_FAST_LIST_ELEMENT_T *element; 281 if ( anchor->list_head != NULL ) 282 { 283 element = anchor->list_head; 284 object = anchor->list_head->object; 285 anchor->list_head = anchor->list_head->next; 286 if ( anchor->list_head == NULL ) 287 { 288 anchor->list_tail = NULL; 289 } 290 anchor->element_count--; 291 element->next = element->prev = NULL; 292 element->owning_list = NULL; 293 } 294 return object; 295 } 296 297 INLINE 298 static void *sci_fast_list_remove_tail( 299 SCI_FAST_LIST_T *anchor 300 ) 301 { 302 void *object = NULL; 303 SCI_FAST_LIST_ELEMENT_T *element; 304 if ( anchor->list_tail != NULL ) 305 { 306 element = anchor->list_tail; 307 object = element->object; 308 anchor->list_tail = element->prev; 309 if ( anchor->list_tail == NULL ) 310 anchor->list_head = NULL; 311 anchor->element_count--; 312 element->next = element->prev = NULL; 313 element->owning_list = NULL; 314 } 315 return object; 316 } 317 318 /** 319 * Remove an element from anywhere in the list referenced by name. 320 */ 321 INLINE 322 static void sci_fast_list_remove_element( 323 SCI_FAST_LIST_ELEMENT_T *element 324 ) 325 { 326 if ( element->next == NULL ) 327 element->owning_list->list_tail = element->prev; 328 else 329 element->next->prev = element->prev; 330 331 if ( element->prev == NULL ) 332 element->owning_list->list_head = element->next; 333 else 334 element->prev->next = element->next; 335 336 element->owning_list->element_count--; 337 element->next = element->prev = NULL; 338 element->owning_list = NULL; 339 } 340 341 #endif // _SCI_FAST_LIST_HEADER_ 342