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