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_SIMPLE_LIST_HEADER_ 55 #define _SCI_SIMPLE_LIST_HEADER_ 56 57 /** 58 * @file 59 * 60 * @brief This header file contains simple linked list manipulation macros. 61 * These macros differ from the SCI_FAST_LIST in that deletion of 62 * an element from the list is O(n). 63 * The reason for using this implementation over the SCI_FAST_LIST 64 * is 65 * 1) space savings as there is only a single link element instead 66 * of the 2 link elements used in the SCI_FAST_LIST and 67 * 2) it is possible to detach the entire list from its anchor 68 * element for processing. 69 * 70 * @note Do not use the SCI_SIMPLE_LIST if you need to remove elements from 71 * random locations within the list use instead the SCI_FAST_LIST. 72 */ 73 74 75 //****************************************************************************** 76 //* 77 //* P U B L I C M E T H O D S 78 //* 79 //****************************************************************************** 80 81 /** 82 * Initialize the singely linked list anchor. The other macros require the 83 * list anchor to be properly initialized. 84 */ 85 #define sci_simple_list_init(anchor) \ 86 { \ 87 (anchor)->list_head = NULL; \ 88 (anchor)->list_tail = NULL; \ 89 (anchor)->list_count = 0; \ 90 } 91 92 /** 93 * Initialze the singely linked list element. The other macros require the 94 * list element to be properly initialized. 95 */ 96 #define sci_simple_list_element_init(list_object, element) \ 97 { \ 98 (element)->next = NULL; \ 99 (element)->object = (list_object); \ 100 } 101 102 /** 103 * See if there are any list elements on this list. 104 */ 105 #define sci_simple_list_is_empty(anchor) ((anchor)->list_head == NULL) 106 107 /** 108 * Return a pointer to the list element at the head of the list. The list 109 * element is not removed from the list. 110 */ 111 #define sci_simple_list_get_head(anchor) ((anchor)->list_head) 112 113 /** 114 * Retuen a pointer to the lsit element at the tail of the list. The list 115 * element is not removed from the list. 116 */ 117 #define sci_simple_list_get_tail(anchor) ((anchor)->list_tail) 118 119 /** 120 * Return the count of the number of elements in this list. 121 */ 122 #define sci_simple_list_get_count(anchor) ((anchor)->list_count) 123 124 /** 125 * Return a pointer to the list element following this list element. 126 * If this is the last element in the list then NULL is returned. 127 */ 128 #define sci_simple_list_get_next(element) ((element)->next) 129 130 /** 131 * Return the object represented by the list element. 132 */ 133 #define sci_simple_list_get_object(element) ((element)->object) 134 135 136 //****************************************************************************** 137 //* 138 //* T Y P E S 139 //* 140 //****************************************************************************** 141 142 /** 143 * @struct 144 * 145 * @brief This structure defines the list owner for singely linked list. 146 */ 147 typedef struct SCI_SIMPLE_LIST 148 { 149 struct SCI_SIMPLE_LIST_ELEMENT *list_head; 150 struct SCI_SIMPLE_LIST_ELEMENT *list_tail; 151 U32 list_count; 152 } SCI_SIMPLE_LIST_T; 153 154 /** 155 * @struct SCI_SIMPLE_LIST_ELEMENT 156 * 157 * @brief This structure defines what a singely linked list element contains. 158 */ 159 typedef struct SCI_SIMPLE_LIST_ELEMENT 160 { 161 struct SCI_SIMPLE_LIST_ELEMENT *next; 162 void *object; 163 } SCI_SIMPLE_LIST_ELEMENT_T; 164 165 /** 166 * This method will insert the list element to the head of the list contained 167 * by the anchor. 168 * 169 * @note Pushing new elements onto a list is more efficient than inserting 170 * them to the tail of the list though both are O(1) operations. 171 */ 172 INLINE 173 static void sci_simple_list_insert_head( 174 SCI_SIMPLE_LIST_T * anchor, 175 SCI_SIMPLE_LIST_ELEMENT_T *element 176 ) 177 { 178 if (anchor->list_tail == NULL) 179 { 180 anchor->list_tail = element; 181 } 182 183 element->next = anchor->list_head; 184 anchor->list_head = element; 185 anchor->list_count++; 186 } 187 188 /** 189 * This methos will insert the list element to the tail of the list contained 190 * by the anchor. 191 * 192 * @param[in, out] anchor this is the list into which the element is to be 193 * inserted 194 * @param[in] element this is the element which to insert into the list. 195 * 196 * @note Pushing new elements onto a list is more efficient than inserting 197 * them to the tail of the list though both are O(1) operations. 198 */ 199 INLINE 200 static void sci_simple_list_insert_tail( 201 SCI_SIMPLE_LIST_T * anchor, 202 SCI_SIMPLE_LIST_ELEMENT_T *element 203 ) 204 { 205 if (anchor->list_tail == NULL) 206 { 207 anchor->list_head = element; 208 } 209 else 210 { 211 anchor->list_tail->next = element; 212 } 213 214 anchor->list_tail = element; 215 anchor->list_count++; 216 } 217 218 /** 219 * This method will remove the list element from the anchor and return the 220 * object pointed to by that list element. 221 * 222 * @param[in, out] anchor this is the list into which the element is to be 223 * inserted 224 * 225 * @return the list element at the head of the list. 226 */ 227 INLINE 228 static void * sci_simple_list_remove_head( 229 SCI_SIMPLE_LIST_T * anchor 230 ) 231 { 232 void * object = NULL; 233 234 if (anchor->list_head != NULL) 235 { 236 object = anchor->list_head->object; 237 238 anchor->list_head = anchor->list_head->next; 239 240 if (anchor->list_head == NULL) 241 { 242 anchor->list_tail = NULL; 243 } 244 245 anchor->list_count--; 246 } 247 248 return object; 249 } 250 251 /** 252 * Move all the list elements from source anchor to the dest anchor. 253 * The source anchor will have all of its elements removed making it 254 * an empty list and the dest anchor will contain all of the source 255 * and dest list elements. 256 * 257 * @param[in, out] dest_anchor this is the list into which all elements from 258 * the source list are to be moved. 259 * @param[in, out] source_anchor this is the list which is to be moved to the 260 * destination list. This list will be empty on return. 261 * 262 * @return the list element at the head of the list. 263 * @note If the destination has list elements use the insert at head 264 * or tail routines instead. 265 */ 266 INLINE 267 static void sci_simple_list_move_list( 268 SCI_SIMPLE_LIST_T * dest_anchor, 269 SCI_SIMPLE_LIST_T * source_anchor 270 ) 271 { 272 *dest_anchor = *source_anchor; 273 274 sci_simple_list_init(source_anchor); 275 } 276 277 /** 278 * This method will insert the list elements from the source anchor to the 279 * destination list before all previous elements on the destination list. 280 * 281 * @param[in, out] dest_anchor this is the list into which all elements from 282 * the source list are to be moved. The destination list will 283 * now contain both sets of list elements. 284 * @param[in, out] source_anchor this is the list which is to be moved to the 285 * destination list. This list will be empty on return. 286 */ 287 INLINE 288 static void sci_simple_list_insert_list_at_head( 289 SCI_SIMPLE_LIST_T * dest_anchor, 290 SCI_SIMPLE_LIST_T * source_anchor 291 ) 292 { 293 if (!sci_simple_list_is_empty(source_anchor)) 294 { 295 if (sci_simple_list_is_empty(dest_anchor)) 296 { 297 // Destination is empty just copy the source on over 298 *dest_anchor = *source_anchor; 299 } 300 else 301 { 302 source_anchor->list_tail->next = dest_anchor->list_head; 303 dest_anchor->list_head = source_anchor->list_head; 304 dest_anchor->list_count += source_anchor->list_count; 305 } 306 307 // Wipe the source list to make sure the list elements can not be accessed 308 // from two separate lists at the same time. 309 sci_simple_list_init(source_anchor); 310 } 311 } 312 313 /** 314 * This method will insert the list elements from the source anchor to the 315 * destination anchor after all list elements on the destination anchor. 316 * 317 * @param[in, out] dest_anchor this is the list into which all elements from 318 * the source list are to be moved. The destination list will 319 * contain both the source and destination list elements. 320 * @param[in, out] source_anchor this is the list which is to be moved to the 321 * destination list. This list will be empty on return. 322 */ 323 INLINE 324 static void sci_simple_list_insert_list_at_tail( 325 SCI_SIMPLE_LIST_T * dest_anchor, 326 SCI_SIMPLE_LIST_T * source_anchor 327 ) 328 { 329 if (!sci_simple_list_is_empty(source_anchor)) 330 { 331 if (sci_simple_list_is_empty(dest_anchor)) 332 { 333 // Destination is empty just copy the source on over 334 *dest_anchor = *source_anchor; 335 } 336 else 337 { 338 // If the source list is empty the desination list is the result. 339 dest_anchor->list_tail->next = source_anchor->list_head; 340 dest_anchor->list_tail = source_anchor->list_tail; 341 dest_anchor->list_count += source_anchor->list_count; 342 } 343 344 // Wipe the source list to make sure the list elements can not be accessed 345 // from two separate lists at the same time. 346 sci_simple_list_init(source_anchor); 347 } 348 } 349 350 #endif // _SCI_SIMPLE_LIST_HEADER_ 351