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.
7 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved.
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.
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.
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.
26 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved.
27 * All rights reserved.
29 * Redistribution and use in source and binary forms, with or without
30 * modification, are permitted provided that the following conditions
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
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.
54 #ifndef _SCI_FAST_LIST_HEADER_
55 #define _SCI_FAST_LIST_HEADER_
60 * @brief Header file that contains basic Linked List manipulation macros.
61 * These macros implement a double linked list (SCI_FAST_LIST_T) that is
62 * circular in nature. This means that the next and prev pointers for
63 * an empty queue head always the address of the queue head
64 * SCI_FAST_LIST_T. Likewise an element that has been removed from
65 * a queue will have its next and prev pointer set to the address of
66 * the SCI_FAST_LIST_T found in the structure just removed from the
67 * queue. Pointers in this implementation never == NULL.
70 * - anchor : This is ths list container and has a
71 * pointer to both the head and tail of the
73 * - element: This is the list element not the actual
74 * object but the list element which has a
75 * pointer to the object.
78 //******************************************************************************
80 //* P U B L I C M E T H O D S
82 //******************************************************************************
85 * Initialize the double linked list anchor. The other macros require the list
86 * anchor to be set up using this macro.
88 #define sci_fast_list_init(anchor) \
90 (anchor)->list_head = NULL; \
91 (anchor)->list_tail = NULL; \
92 (anchor)->element_count = 0; \
96 * Initialize the sci_fast_list_element to point to its owning object
98 #define sci_fast_list_element_init(list_object, element) \
100 (element)->object = (list_object); \
101 (element)->next = (element)->prev = NULL; \
102 (element)->owning_list = NULL; \
106 * See if there is anything on the list by checking the list anchor.
108 #define sci_fast_list_is_empty(anchor) ((anchor)->list_head == NULL)
111 * Return a pointer to the element at the head of the sci_fast_list. The
112 * item is NOT removed from the list.
114 * NOTE: This macro will always return a value, even if the list is empty.
115 * You must insure the list is not empty or use Dlist_safeGetHead.
117 * element - A pointer into which to save the address of the structure
118 * containing the SCI_FAST_LIST at the list head.
120 #define sci_fast_list_get_head(anchor) \
121 ((anchor)->list_head == NULL ? NULL: (anchor)->list_head->object)
124 * Return a pointer to the element at the tail of the sci_fast_list. The item
125 * is NOT removed from the list.
127 * NOTE: This macro will always return a value, even if the list is empty.
128 * You must insure the list is not empty or use Dlist_safeGetHead.
130 * element - A pointer into which to save the address of the structure
131 * containing the SCI_FAST_LIST at the list head.
133 #define sci_fast_list_get_tail(anchor) \
134 ((anchor)->list_tail == NULL ? NULL: (anchor)->list_head->object)
137 * This method will get the next dListField in the SCI_FAST_LIST. This method
138 * returns a pointer to a SCI_FAST_LIST object.
140 #define sci_fast_list_get_next(element) ((element)->next)
143 * This method will get the prev dListField in the SCI_FAST_LIST. This method
144 * returns a pointer to a SCI_FAST_LIST object.
146 #define sci_fast_list_get_prev(element) ((element)->prev)
150 * This method returns the object that is represented by this
151 * sci_fast_list_element
153 #define sci_fast_list_get_object(element) ((element)->object)
156 * This method will determine if the supplied dListField is on a SCI_FAST_LIST.
157 * If the element has only one dListField but can be on more than one list,
158 * this will only tell you that it is on one of them. If the element has
159 * multiple dListFields and can exist on multiple lists at the same time, this
160 * macro can tell you exactly which list it is on.
162 #define sci_fast_list_is_on_a_list(element) ((element)->owning_list != NULL)
165 * This method will determine if the supplied dListFieldName is on the given
166 * specified list? If the element can be on more than one list, this
167 * allows you to determine exactly which list it is on. Performs a linear
168 * search through the list.
169 * result - BOOL_T that will contain the result of the search.
170 * TRUE - item is on the list described by head.
171 * FALSE - item is not on the list.
173 #define sci_fast_list_is_on_this_list(anchor, element) \
174 ((element)->owning_list == (anchor))
176 //******************************************************************************
180 //******************************************************************************
183 * @struct SCI_FAST_LIST
185 * @brief the list owner or list anchor for a set of SCI_FAST_LIST
188 typedef struct SCI_FAST_LIST
190 struct SCI_FAST_LIST_ELEMENT *list_head;
191 struct SCI_FAST_LIST_ELEMENT *list_tail;
196 * @struct SCI_FAST_LIST_ELEMENT
198 * @brief This structure defines what a doubly linked list element contains.
200 typedef struct SCI_FAST_LIST_ELEMENT
202 struct SCI_FAST_LIST_ELEMENT *next;
203 struct SCI_FAST_LIST_ELEMENT *prev;
204 struct SCI_FAST_LIST *owning_list;
206 } SCI_FAST_LIST_ELEMENT_T;
210 * Insert an element to be the new head of the list hanging off of the list
211 * anchor. An empty list has the list anchor pointing to itself.
212 * dListAnchor - The name of the SCI_FAST_LIST_T element that is the anchor
214 * dListFieldBeingInserted - The SCI_FAST_LIST_T field in the data structure
215 * being queued. This SCI_FAST_LIST will become
219 static void sci_fast_list_insert_head(
220 SCI_FAST_LIST_T *anchor,
221 SCI_FAST_LIST_ELEMENT_T *element
224 element->owning_list = anchor;
225 element->prev = NULL;
226 if ( anchor->list_head == NULL )
227 anchor->list_tail = element;
229 anchor->list_head->prev = element;
230 element->next = anchor->list_head;
231 anchor->list_head = element;
232 anchor->element_count++;
236 * Insert an element at the tail of the list. Since the list is circular we
237 * can add the element at the tail through use the list anchors previous
239 * dListAnchor - The name of the SCI_FAST_LIST_T element that is the anchor
241 * dListFieldBeingInserted - The SCI_FAST_LIST_T field in the data structure
242 * being queued. This SCI_FAST_LIST will become
246 static void sci_fast_list_insert_tail(
247 SCI_FAST_LIST_T *anchor,
248 SCI_FAST_LIST_ELEMENT_T *element
251 element->owning_list = anchor;
252 element->next = NULL;
253 if ( anchor->list_tail == NULL ) {
254 anchor->list_head = element;
256 anchor->list_tail->next = element;
258 element->prev = anchor->list_tail;
259 anchor->list_tail = element;
260 anchor->element_count++;
264 * This method will remove a dListFieldName from the head of the list.
266 * NOTE: This macro will always return a value, even if the list is empty.
267 * You must insure the list is not empty or use Dlist_safeRemoveHead.
269 * element - A pointer into which to save the address of the structure
270 * containing the SCI_FAST_LIST at the list head.
273 static void *sci_fast_list_remove_head(
274 SCI_FAST_LIST_T *anchor
278 SCI_FAST_LIST_ELEMENT_T *element;
279 if ( anchor->list_head != NULL )
281 element = anchor->list_head;
282 object = anchor->list_head->object;
283 anchor->list_head = anchor->list_head->next;
284 if ( anchor->list_head == NULL )
286 anchor->list_tail = NULL;
288 anchor->element_count--;
289 element->next = element->prev = NULL;
290 element->owning_list = NULL;
296 static void *sci_fast_list_remove_tail(
297 SCI_FAST_LIST_T *anchor
301 SCI_FAST_LIST_ELEMENT_T *element;
302 if ( anchor->list_tail != NULL )
304 element = anchor->list_tail;
305 object = element->object;
306 anchor->list_tail = element->prev;
307 if ( anchor->list_tail == NULL )
308 anchor->list_head = NULL;
309 anchor->element_count--;
310 element->next = element->prev = NULL;
311 element->owning_list = NULL;
317 * Remove an element from anywhere in the list referenced by name.
320 static void sci_fast_list_remove_element(
321 SCI_FAST_LIST_ELEMENT_T *element
324 if ( element->next == NULL )
325 element->owning_list->list_tail = element->prev;
327 element->next->prev = element->prev;
329 if ( element->prev == NULL )
330 element->owning_list->list_head = element->next;
332 element->prev->next = element->next;
334 element->owning_list->element_count--;
335 element->next = element->prev = NULL;
336 element->owning_list = NULL;
339 #endif // _SCI_FAST_LIST_HEADER_