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_FAST_LIST_HEADER_
57 #define _SCI_FAST_LIST_HEADER_
62 * @brief Header file that contains basic Linked List manipulation macros.
63 * These macros implement a double linked list (SCI_FAST_LIST_T) that is
64 * circular in nature. This means that the next and prev pointers for
65 * an empty queue head always the address of the queue head
66 * SCI_FAST_LIST_T. Likewise an element that has been removed from
67 * a queue will have its next and prev pointer set to the address of
68 * the SCI_FAST_LIST_T found in the structure just removed from the
69 * queue. Pointers in this implementation never == NULL.
72 * - anchor : This is the list container and has a
73 * pointer to both the head and tail of the
75 * - element: This is the list element not the actual
76 * object but the list element which has a
77 * pointer to the object.
80 //******************************************************************************
82 //* P U B L I C M E T H O D S
84 //******************************************************************************
87 * Initialize the double linked list anchor. The other macros require the list
88 * anchor to be set up using this macro.
90 #define sci_fast_list_init(anchor) \
92 (anchor)->list_head = NULL; \
93 (anchor)->list_tail = NULL; \
94 (anchor)->element_count = 0; \
98 * Initialize the sci_fast_list_element to point to its owning object
100 #define sci_fast_list_element_init(list_object, element) \
102 (element)->object = (list_object); \
103 (element)->next = (element)->prev = NULL; \
104 (element)->owning_list = NULL; \
108 * See if there is anything on the list by checking the list anchor.
110 #define sci_fast_list_is_empty(anchor) ((anchor)->list_head == NULL)
113 * Return a pointer to the element at the head of the sci_fast_list. The
114 * item is NOT removed from the list.
116 * NOTE: This macro will always return a value, even if the list is empty.
117 * You must insure the list is not empty or use Dlist_safeGetHead.
119 * element - A pointer into which to save the address of the structure
120 * containing the SCI_FAST_LIST at the list head.
122 #define sci_fast_list_get_head(anchor) \
123 ((anchor)->list_head == NULL ? NULL: (anchor)->list_head->object)
126 * Return a pointer to the element at the tail of the sci_fast_list. The item
127 * is NOT removed from the list.
129 * NOTE: This macro will always return a value, even if the list is empty.
130 * You must insure the list is not empty or use Dlist_safeGetHead.
132 * element - A pointer into which to save the address of the structure
133 * containing the SCI_FAST_LIST at the list head.
135 #define sci_fast_list_get_tail(anchor) \
136 ((anchor)->list_tail == NULL ? NULL: (anchor)->list_head->object)
139 * This method will get the next dListField in the SCI_FAST_LIST. This method
140 * returns a pointer to a SCI_FAST_LIST object.
142 #define sci_fast_list_get_next(element) ((element)->next)
145 * This method will get the prev dListField in the SCI_FAST_LIST. This method
146 * returns a pointer to a SCI_FAST_LIST object.
148 #define sci_fast_list_get_prev(element) ((element)->prev)
152 * This method returns the object that is represented by this
153 * sci_fast_list_element
155 #define sci_fast_list_get_object(element) ((element)->object)
158 * This method will determine if the supplied dListField is on a SCI_FAST_LIST.
159 * If the element has only one dListField but can be on more than one list,
160 * this will only tell you that it is on one of them. If the element has
161 * multiple dListFields and can exist on multiple lists at the same time, this
162 * macro can tell you exactly which list it is on.
164 #define sci_fast_list_is_on_a_list(element) ((element)->owning_list != NULL)
167 * This method will determine if the supplied dListFieldName is on the given
168 * specified list? If the element can be on more than one list, this
169 * allows you to determine exactly which list it is on. Performs a linear
170 * search through the list.
171 * result - BOOL_T that will contain the result of the search.
172 * TRUE - item is on the list described by head.
173 * FALSE - item is not on the list.
175 #define sci_fast_list_is_on_this_list(anchor, element) \
176 ((element)->owning_list == (anchor))
178 //******************************************************************************
182 //******************************************************************************
185 * @struct SCI_FAST_LIST
187 * @brief the list owner or list anchor for a set of SCI_FAST_LIST
190 typedef struct SCI_FAST_LIST
192 struct SCI_FAST_LIST_ELEMENT *list_head;
193 struct SCI_FAST_LIST_ELEMENT *list_tail;
198 * @struct SCI_FAST_LIST_ELEMENT
200 * @brief This structure defines what a doubly linked list element contains.
202 typedef struct SCI_FAST_LIST_ELEMENT
204 struct SCI_FAST_LIST_ELEMENT *next;
205 struct SCI_FAST_LIST_ELEMENT *prev;
206 struct SCI_FAST_LIST *owning_list;
208 } SCI_FAST_LIST_ELEMENT_T;
212 * Insert an element to be the new head of the list hanging off of the list
213 * anchor. An empty list has the list anchor pointing to itself.
214 * dListAnchor - The name of the SCI_FAST_LIST_T element that is the anchor
216 * dListFieldBeingInserted - The SCI_FAST_LIST_T field in the data structure
217 * being queued. This SCI_FAST_LIST will become
221 static void sci_fast_list_insert_head(
222 SCI_FAST_LIST_T *anchor,
223 SCI_FAST_LIST_ELEMENT_T *element
226 element->owning_list = anchor;
227 element->prev = NULL;
228 if ( anchor->list_head == NULL )
229 anchor->list_tail = element;
231 anchor->list_head->prev = element;
232 element->next = anchor->list_head;
233 anchor->list_head = element;
234 anchor->element_count++;
238 * Insert an element at the tail of the list. Since the list is circular we
239 * can add the element at the tail through use the list anchors previous
241 * dListAnchor - The name of the SCI_FAST_LIST_T element that is the anchor
243 * dListFieldBeingInserted - The SCI_FAST_LIST_T field in the data structure
244 * being queued. This SCI_FAST_LIST will become
248 static void sci_fast_list_insert_tail(
249 SCI_FAST_LIST_T *anchor,
250 SCI_FAST_LIST_ELEMENT_T *element
253 element->owning_list = anchor;
254 element->next = NULL;
255 if ( anchor->list_tail == NULL ) {
256 anchor->list_head = element;
258 anchor->list_tail->next = element;
260 element->prev = anchor->list_tail;
261 anchor->list_tail = element;
262 anchor->element_count++;
266 * This method will remove a dListFieldName from the head of the list.
268 * NOTE: This macro will always return a value, even if the list is empty.
269 * You must insure the list is not empty or use Dlist_safeRemoveHead.
271 * element - A pointer into which to save the address of the structure
272 * containing the SCI_FAST_LIST at the list head.
275 static void *sci_fast_list_remove_head(
276 SCI_FAST_LIST_T *anchor
280 SCI_FAST_LIST_ELEMENT_T *element;
281 if ( anchor->list_head != NULL )
283 element = anchor->list_head;
284 object = anchor->list_head->object;
285 anchor->list_head = anchor->list_head->next;
286 if ( anchor->list_head == NULL )
288 anchor->list_tail = NULL;
290 anchor->element_count--;
291 element->next = element->prev = NULL;
292 element->owning_list = NULL;
298 static void *sci_fast_list_remove_tail(
299 SCI_FAST_LIST_T *anchor
303 SCI_FAST_LIST_ELEMENT_T *element;
304 if ( anchor->list_tail != NULL )
306 element = anchor->list_tail;
307 object = element->object;
308 anchor->list_tail = element->prev;
309 if ( anchor->list_tail == NULL )
310 anchor->list_head = NULL;
311 anchor->element_count--;
312 element->next = element->prev = NULL;
313 element->owning_list = NULL;
319 * Remove an element from anywhere in the list referenced by name.
322 static void sci_fast_list_remove_element(
323 SCI_FAST_LIST_ELEMENT_T *element
326 if ( element->next == NULL )
327 element->owning_list->list_tail = element->prev;
329 element->next->prev = element->prev;
331 if ( element->prev == NULL )
332 element->owning_list->list_head = element->next;
334 element->prev->next = element->next;
336 element->owning_list->element_count--;
337 element->next = element->prev = NULL;
338 element->owning_list = NULL;
341 #endif // _SCI_FAST_LIST_HEADER_