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