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 * $FreeBSD$
55 */
56#ifndef _SCI_SIMPLE_LIST_HEADER_
57#define _SCI_SIMPLE_LIST_HEADER_
58
59/**
60 * @file
61 *
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
66 *        is
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.
71 *
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.
74 */
75
76
77//******************************************************************************
78//*
79//*     P U B L I C    M E T H O D S
80//*
81//******************************************************************************
82
83/**
84 * Initialize the singely linked list anchor.  The other macros require the
85 * list anchor to be properly initialized.
86 */
87#define sci_simple_list_init(anchor) \
88{ \
89   (anchor)->list_head = NULL; \
90   (anchor)->list_tail = NULL; \
91   (anchor)->list_count = 0; \
92}
93
94/**
95 * Initialze the singely linked list element. The other macros require the
96 * list element to be properly initialized.
97 */
98#define sci_simple_list_element_init(list_object, element) \
99{ \
100   (element)->next = NULL; \
101   (element)->object = (list_object); \
102}
103
104/**
105 * See if there are any list elements on this list.
106 */
107#define sci_simple_list_is_empty(anchor)  ((anchor)->list_head == NULL)
108
109/**
110 * Return a pointer to the list element at the head of the list.  The list
111 * element is not removed from the list.
112 */
113#define sci_simple_list_get_head(anchor) ((anchor)->list_head)
114
115/**
116 * Retuen a pointer to the lsit element at the tail of the list.  The list
117 * element is not removed from the list.
118 */
119#define sci_simple_list_get_tail(anchor) ((anchor)->list_tail)
120
121/**
122 * Return the count of the number of elements in this list.
123 */
124#define sci_simple_list_get_count(anchor) ((anchor)->list_count)
125
126/**
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.
129 */
130#define sci_simple_list_get_next(element) ((element)->next)
131
132/**
133 * Return the object represented by the list element.
134 */
135#define sci_simple_list_get_object(element) ((element)->object)
136
137
138//******************************************************************************
139//*
140//*     T Y P E S
141//*
142//******************************************************************************
143
144/**
145 * @struct
146 *
147 * @brief This structure defines the list owner for singely linked list.
148 */
149typedef struct SCI_SIMPLE_LIST
150{
151   struct SCI_SIMPLE_LIST_ELEMENT *list_head;
152   struct SCI_SIMPLE_LIST_ELEMENT *list_tail;
153   U32                             list_count;
154} SCI_SIMPLE_LIST_T;
155
156/**
157 * @struct SCI_SIMPLE_LIST_ELEMENT
158 *
159 * @brief This structure defines what a singely linked list element contains.
160 */
161typedef struct SCI_SIMPLE_LIST_ELEMENT
162{
163   struct SCI_SIMPLE_LIST_ELEMENT *next;
164   void                           *object;
165} SCI_SIMPLE_LIST_ELEMENT_T;
166
167/**
168 * This method will insert the list element to the head of the list contained
169 * by the anchor.
170 *
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.
173 */
174INLINE
175static void sci_simple_list_insert_head(
176   SCI_SIMPLE_LIST_T * anchor,
177   SCI_SIMPLE_LIST_ELEMENT_T *element
178)
179{
180   if (anchor->list_tail == NULL)
181   {
182      anchor->list_tail = element;
183   }
184
185   element->next = anchor->list_head;
186   anchor->list_head = element;
187   anchor->list_count++;
188}
189
190/**
191 * This methos will insert the list element to the tail of the list contained
192 * by the anchor.
193 *
194 * @param[in, out] anchor this is the list into which the element is to be
195 *                 inserted
196 * @param[in] element this is the element which to insert into the list.
197 *
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.
200 */
201INLINE
202static void sci_simple_list_insert_tail(
203   SCI_SIMPLE_LIST_T * anchor,
204   SCI_SIMPLE_LIST_ELEMENT_T *element
205)
206{
207   if (anchor->list_tail == NULL)
208   {
209      anchor->list_head = element;
210   }
211   else
212   {
213      anchor->list_tail->next = element;
214   }
215
216   anchor->list_tail = element;
217   anchor->list_count++;
218}
219
220/**
221 * This method will remove the list element from the anchor and return the
222 * object pointed to by that list element.
223 *
224 * @param[in, out] anchor this is the list into which the element is to be
225 *                 inserted
226 *
227 * @return the list element at the head of the list.
228 */
229INLINE
230static void * sci_simple_list_remove_head(
231   SCI_SIMPLE_LIST_T * anchor
232)
233{
234   void * object = NULL;
235
236   if (anchor->list_head != NULL)
237   {
238      object = anchor->list_head->object;
239
240      anchor->list_head = anchor->list_head->next;
241
242      if (anchor->list_head == NULL)
243      {
244         anchor->list_tail = NULL;
245      }
246
247      anchor->list_count--;
248   }
249
250   return object;
251}
252
253/**
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.
258 *
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.
263 *
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.
267 */
268INLINE
269static void sci_simple_list_move_list(
270   SCI_SIMPLE_LIST_T * dest_anchor,
271   SCI_SIMPLE_LIST_T * source_anchor
272)
273{
274   *dest_anchor = *source_anchor;
275
276   sci_simple_list_init(source_anchor);
277}
278
279/**
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.
282 *
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.
288 */
289INLINE
290static void sci_simple_list_insert_list_at_head(
291   SCI_SIMPLE_LIST_T * dest_anchor,
292   SCI_SIMPLE_LIST_T * source_anchor
293)
294{
295   if (!sci_simple_list_is_empty(source_anchor))
296   {
297      if (sci_simple_list_is_empty(dest_anchor))
298      {
299         // Destination is empty just copy the source on over
300         *dest_anchor = *source_anchor;
301      }
302      else
303      {
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;
307      }
308
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);
312   }
313}
314
315/**
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.
318 *
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.
324 */
325INLINE
326static void sci_simple_list_insert_list_at_tail(
327   SCI_SIMPLE_LIST_T * dest_anchor,
328   SCI_SIMPLE_LIST_T * source_anchor
329)
330{
331   if (!sci_simple_list_is_empty(source_anchor))
332   {
333      if (sci_simple_list_is_empty(dest_anchor))
334      {
335         // Destination is empty just copy the source on over
336         *dest_anchor = *source_anchor;
337      }
338      else
339      {
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;
344      }
345
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);
349   }
350}
351
352#endif // _SCI_SIMPLE_LIST_HEADER_
353