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