2 * SPDX-License-Identifier: BSD-2-Clause OR GPL-2.0
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.
9 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved.
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.
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.
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.
28 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved.
29 * All rights reserved.
31 * Redistribution and use in source and binary forms, with or without
32 * modification, are permitted provided that the following conditions
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
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.
56 #ifndef _SCI_SIMPLE_LIST_HEADER_
57 #define _SCI_SIMPLE_LIST_HEADER_
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
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.
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.
77 //******************************************************************************
79 //* P U B L I C M E T H O D S
81 //******************************************************************************
84 * Initialize the singely linked list anchor. The other macros require the
85 * list anchor to be properly initialized.
87 #define sci_simple_list_init(anchor) \
89 (anchor)->list_head = NULL; \
90 (anchor)->list_tail = NULL; \
91 (anchor)->list_count = 0; \
95 * Initialze the singely linked list element. The other macros require the
96 * list element to be properly initialized.
98 #define sci_simple_list_element_init(list_object, element) \
100 (element)->next = NULL; \
101 (element)->object = (list_object); \
105 * See if there are any list elements on this list.
107 #define sci_simple_list_is_empty(anchor) ((anchor)->list_head == NULL)
110 * Return a pointer to the list element at the head of the list. The list
111 * element is not removed from the list.
113 #define sci_simple_list_get_head(anchor) ((anchor)->list_head)
116 * Retuen a pointer to the lsit element at the tail of the list. The list
117 * element is not removed from the list.
119 #define sci_simple_list_get_tail(anchor) ((anchor)->list_tail)
122 * Return the count of the number of elements in this list.
124 #define sci_simple_list_get_count(anchor) ((anchor)->list_count)
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.
130 #define sci_simple_list_get_next(element) ((element)->next)
133 * Return the object represented by the list element.
135 #define sci_simple_list_get_object(element) ((element)->object)
138 //******************************************************************************
142 //******************************************************************************
147 * @brief This structure defines the list owner for singely linked list.
149 typedef struct SCI_SIMPLE_LIST
151 struct SCI_SIMPLE_LIST_ELEMENT *list_head;
152 struct SCI_SIMPLE_LIST_ELEMENT *list_tail;
157 * @struct SCI_SIMPLE_LIST_ELEMENT
159 * @brief This structure defines what a singely linked list element contains.
161 typedef struct SCI_SIMPLE_LIST_ELEMENT
163 struct SCI_SIMPLE_LIST_ELEMENT *next;
165 } SCI_SIMPLE_LIST_ELEMENT_T;
168 * This method will insert the list element to the head of the list contained
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.
175 static void sci_simple_list_insert_head(
176 SCI_SIMPLE_LIST_T * anchor,
177 SCI_SIMPLE_LIST_ELEMENT_T *element
180 if (anchor->list_tail == NULL)
182 anchor->list_tail = element;
185 element->next = anchor->list_head;
186 anchor->list_head = element;
187 anchor->list_count++;
191 * This methos will insert the list element to the tail of the list contained
194 * @param[in, out] anchor this is the list into which the element is to be
196 * @param[in] element this is the element which to insert into the list.
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.
202 static void sci_simple_list_insert_tail(
203 SCI_SIMPLE_LIST_T * anchor,
204 SCI_SIMPLE_LIST_ELEMENT_T *element
207 if (anchor->list_tail == NULL)
209 anchor->list_head = element;
213 anchor->list_tail->next = element;
216 anchor->list_tail = element;
217 anchor->list_count++;
221 * This method will remove the list element from the anchor and return the
222 * object pointed to by that list element.
224 * @param[in, out] anchor this is the list into which the element is to be
227 * @return the list element at the head of the list.
230 static void * sci_simple_list_remove_head(
231 SCI_SIMPLE_LIST_T * anchor
234 void * object = NULL;
236 if (anchor->list_head != NULL)
238 object = anchor->list_head->object;
240 anchor->list_head = anchor->list_head->next;
242 if (anchor->list_head == NULL)
244 anchor->list_tail = NULL;
247 anchor->list_count--;
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.
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.
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.
269 static void sci_simple_list_move_list(
270 SCI_SIMPLE_LIST_T * dest_anchor,
271 SCI_SIMPLE_LIST_T * source_anchor
274 *dest_anchor = *source_anchor;
276 sci_simple_list_init(source_anchor);
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.
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.
290 static void sci_simple_list_insert_list_at_head(
291 SCI_SIMPLE_LIST_T * dest_anchor,
292 SCI_SIMPLE_LIST_T * source_anchor
295 if (!sci_simple_list_is_empty(source_anchor))
297 if (sci_simple_list_is_empty(dest_anchor))
299 // Destination is empty just copy the source on over
300 *dest_anchor = *source_anchor;
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;
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);
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.
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.
326 static void sci_simple_list_insert_list_at_tail(
327 SCI_SIMPLE_LIST_T * dest_anchor,
328 SCI_SIMPLE_LIST_T * source_anchor
331 if (!sci_simple_list_is_empty(source_anchor))
333 if (sci_simple_list_is_empty(dest_anchor))
335 // Destination is empty just copy the source on over
336 *dest_anchor = *source_anchor;
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;
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);
352 #endif // _SCI_SIMPLE_LIST_HEADER_