1/*-
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.
4 *
5 * GPL LICENSE SUMMARY
6 *
7 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved.
8 *
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.
12 *
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.
17 *
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.
23 *
24 * BSD LICENSE
25 *
26 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved.
27 * All rights reserved.
28 *
29 * Redistribution and use in source and binary forms, with or without
30 * modification, are permitted provided that the following conditions
31 * are met:
32 *
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
38 *     distribution.
39 *
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.
51 *
52 * $FreeBSD$
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 ths 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 */
188typedef 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 */
200typedef 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 */
218INLINE
219static 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 */
245INLINE
246static 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 */
272INLINE
273static 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
295INLINE
296static 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 */
319INLINE
320static 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