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