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 */ 147typedef 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 */ 159typedef 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 */ 172INLINE 173static 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 */ 199INLINE 200static 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 */ 227INLINE 228static 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 */ 266INLINE 267static 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 */ 287INLINE 288static 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 seperate 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 */ 323INLINE 324static 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 seperate lists at the same time. 346 sci_simple_list_init(source_anchor); 347 } 348} 349 350#endif // _SCI_SIMPLE_LIST_HEADER_ 351