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 #ifndef _SCI_FAST_LIST_HEADER_
55 #define _SCI_FAST_LIST_HEADER_
56
57 /**
58 * @file
59 *
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.
68 *
69 * Definitions:
70 * - anchor : This is the list container and has a
71 * pointer to both the head and tail of the
72 * list elements
73 * - element: This is the list element not the actual
74 * object but the list element which has a
75 * pointer to the object.
76 */
77
78 //******************************************************************************
79 //*
80 //* P U B L I C M E T H O D S
81 //*
82 //******************************************************************************
83
84 /**
85 * Initialize the double linked list anchor. The other macros require the list
86 * anchor to be set up using this macro.
87 */
88 #define sci_fast_list_init(anchor) \
89 { \
90 (anchor)->list_head = NULL; \
91 (anchor)->list_tail = NULL; \
92 (anchor)->element_count = 0; \
93 }
94
95 /**
96 * Initialize the sci_fast_list_element to point to its owning object
97 */
98 #define sci_fast_list_element_init(list_object, element) \
99 { \
100 (element)->object = (list_object); \
101 (element)->next = (element)->prev = NULL; \
102 (element)->owning_list = NULL; \
103 }
104
105 /**
106 * See if there is anything on the list by checking the list anchor.
107 */
108 #define sci_fast_list_is_empty(anchor) ((anchor)->list_head == NULL)
109
110 /**
111 * Return a pointer to the element at the head of the sci_fast_list. The
112 * item is NOT removed from the list.
113 *
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.
116 *
117 * element - A pointer into which to save the address of the structure
118 * containing the SCI_FAST_LIST at the list head.
119 */
120 #define sci_fast_list_get_head(anchor) \
121 ((anchor)->list_head == NULL ? NULL: (anchor)->list_head->object)
122
123 /**
124 * Return a pointer to the element at the tail of the sci_fast_list. The item
125 * is NOT removed from the list.
126 *
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.
129 *
130 * element - A pointer into which to save the address of the structure
131 * containing the SCI_FAST_LIST at the list head.
132 */
133 #define sci_fast_list_get_tail(anchor) \
134 ((anchor)->list_tail == NULL ? NULL: (anchor)->list_head->object)
135
136 /**
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.
139 */
140 #define sci_fast_list_get_next(element) ((element)->next)
141
142 /**
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.
145 */
146 #define sci_fast_list_get_prev(element) ((element)->prev)
147
148
149 /**
150 * This method returns the object that is represented by this
151 * sci_fast_list_element
152 */
153 #define sci_fast_list_get_object(element) ((element)->object)
154
155 /**
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.
161 */
162 #define sci_fast_list_is_on_a_list(element) ((element)->owning_list != NULL)
163
164 /**
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.
172 */
173 #define sci_fast_list_is_on_this_list(anchor, element) \
174 ((element)->owning_list == (anchor))
175
176 //******************************************************************************
177 //*
178 //* T Y P E S
179 //*
180 //******************************************************************************
181
182 /**
183 * @struct SCI_FAST_LIST
184 *
185 * @brief the list owner or list anchor for a set of SCI_FAST_LIST
186 * elements.
187 */
188 typedef struct SCI_FAST_LIST
189 {
190 struct SCI_FAST_LIST_ELEMENT *list_head;
191 struct SCI_FAST_LIST_ELEMENT *list_tail;
192 int element_count;
193 } SCI_FAST_LIST_T;
194
195 /**
196 * @struct SCI_FAST_LIST_ELEMENT
197 *
198 * @brief This structure defines what a doubly linked list element contains.
199 */
200 typedef struct SCI_FAST_LIST_ELEMENT
201 {
202 struct SCI_FAST_LIST_ELEMENT *next;
203 struct SCI_FAST_LIST_ELEMENT *prev;
204 struct SCI_FAST_LIST *owning_list;
205 void *object;
206 } SCI_FAST_LIST_ELEMENT_T;
207
208
209 /**
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
213 * of the queue.
214 * dListFieldBeingInserted - The SCI_FAST_LIST_T field in the data structure
215 * being queued. This SCI_FAST_LIST will become
216 * the new list head.
217 */
218 INLINE
sci_fast_list_insert_head(SCI_FAST_LIST_T * anchor,SCI_FAST_LIST_ELEMENT_T * element)219 static void sci_fast_list_insert_head(
220 SCI_FAST_LIST_T *anchor,
221 SCI_FAST_LIST_ELEMENT_T *element
222 )
223 {
224 element->owning_list = anchor;
225 element->prev = NULL;
226 if ( anchor->list_head == NULL )
227 anchor->list_tail = element;
228 else
229 anchor->list_head->prev = element;
230 element->next = anchor->list_head;
231 anchor->list_head = element;
232 anchor->element_count++;
233 }
234
235 /**
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
238 * pointer.
239 * dListAnchor - The name of the SCI_FAST_LIST_T element that is the anchor
240 * of the queue.
241 * dListFieldBeingInserted - The SCI_FAST_LIST_T field in the data structure
242 * being queued. This SCI_FAST_LIST will become
243 * the new list head.
244 */
245 INLINE
sci_fast_list_insert_tail(SCI_FAST_LIST_T * anchor,SCI_FAST_LIST_ELEMENT_T * element)246 static void sci_fast_list_insert_tail(
247 SCI_FAST_LIST_T *anchor,
248 SCI_FAST_LIST_ELEMENT_T *element
249 )
250 {
251 element->owning_list = anchor;
252 element->next = NULL;
253 if ( anchor->list_tail == NULL ) {
254 anchor->list_head = element;
255 } else {
256 anchor->list_tail->next = element;
257 }
258 element->prev = anchor->list_tail;
259 anchor->list_tail = element;
260 anchor->element_count++;
261 }
262
263 /**
264 * This method will remove a dListFieldName from the head of the list.
265 *
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.
268 *
269 * element - A pointer into which to save the address of the structure
270 * containing the SCI_FAST_LIST at the list head.
271 */
272 INLINE
sci_fast_list_remove_head(SCI_FAST_LIST_T * anchor)273 static void *sci_fast_list_remove_head(
274 SCI_FAST_LIST_T *anchor
275 )
276 {
277 void *object = NULL;
278 SCI_FAST_LIST_ELEMENT_T *element;
279 if ( anchor->list_head != NULL )
280 {
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 )
285 {
286 anchor->list_tail = NULL;
287 }
288 anchor->element_count--;
289 element->next = element->prev = NULL;
290 element->owning_list = NULL;
291 }
292 return object;
293 }
294
295 INLINE
sci_fast_list_remove_tail(SCI_FAST_LIST_T * anchor)296 static void *sci_fast_list_remove_tail(
297 SCI_FAST_LIST_T *anchor
298 )
299 {
300 void *object = NULL;
301 SCI_FAST_LIST_ELEMENT_T *element;
302 if ( anchor->list_tail != NULL )
303 {
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;
312 }
313 return object;
314 }
315
316 /**
317 * Remove an element from anywhere in the list referenced by name.
318 */
319 INLINE
sci_fast_list_remove_element(SCI_FAST_LIST_ELEMENT_T * element)320 static void sci_fast_list_remove_element(
321 SCI_FAST_LIST_ELEMENT_T *element
322 )
323 {
324 if ( element->next == NULL )
325 element->owning_list->list_tail = element->prev;
326 else
327 element->next->prev = element->prev;
328
329 if ( element->prev == NULL )
330 element->owning_list->list_head = element->next;
331 else
332 element->prev->next = element->next;
333
334 element->owning_list->element_count--;
335 element->next = element->prev = NULL;
336 element->owning_list = NULL;
337 }
338
339 #endif // _SCI_FAST_LIST_HEADER_
340