1230557Sjimharris/*-
2230557Sjimharris * This file is provided under a dual BSD/GPLv2 license.  When using or
3230557Sjimharris * redistributing this file, you may do so under either license.
4230557Sjimharris *
5230557Sjimharris * GPL LICENSE SUMMARY
6230557Sjimharris *
7230557Sjimharris * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved.
8230557Sjimharris *
9230557Sjimharris * This program is free software; you can redistribute it and/or modify
10230557Sjimharris * it under the terms of version 2 of the GNU General Public License as
11230557Sjimharris * published by the Free Software Foundation.
12230557Sjimharris *
13230557Sjimharris * This program is distributed in the hope that it will be useful, but
14230557Sjimharris * WITHOUT ANY WARRANTY; without even the implied warranty of
15230557Sjimharris * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16230557Sjimharris * General Public License for more details.
17230557Sjimharris *
18230557Sjimharris * You should have received a copy of the GNU General Public License
19230557Sjimharris * along with this program; if not, write to the Free Software
20230557Sjimharris * Foundation, Inc., 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
21230557Sjimharris * The full GNU General Public License is included in this distribution
22230557Sjimharris * in the file called LICENSE.GPL.
23230557Sjimharris *
24230557Sjimharris * BSD LICENSE
25230557Sjimharris *
26230557Sjimharris * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved.
27230557Sjimharris * All rights reserved.
28230557Sjimharris *
29230557Sjimharris * Redistribution and use in source and binary forms, with or without
30230557Sjimharris * modification, are permitted provided that the following conditions
31230557Sjimharris * are met:
32230557Sjimharris *
33230557Sjimharris *   * Redistributions of source code must retain the above copyright
34230557Sjimharris *     notice, this list of conditions and the following disclaimer.
35230557Sjimharris *   * Redistributions in binary form must reproduce the above copyright
36230557Sjimharris *     notice, this list of conditions and the following disclaimer in
37230557Sjimharris *     the documentation and/or other materials provided with the
38230557Sjimharris *     distribution.
39230557Sjimharris *
40230557Sjimharris * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
41230557Sjimharris * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
42230557Sjimharris * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
43230557Sjimharris * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
44230557Sjimharris * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
45230557Sjimharris * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
46230557Sjimharris * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
47230557Sjimharris * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
48230557Sjimharris * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
49230557Sjimharris * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
50230557Sjimharris * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
51230557Sjimharris *
52230557Sjimharris * $FreeBSD$
53230557Sjimharris */
54230557Sjimharris#ifndef _SCI_FAST_LIST_HEADER_
55230557Sjimharris#define _SCI_FAST_LIST_HEADER_
56230557Sjimharris
57230557Sjimharris/**
58230557Sjimharris * @file
59230557Sjimharris *
60230557Sjimharris * @brief Header file that contains basic Linked List manipulation macros.
61230557Sjimharris *        These macros implement a double linked list (SCI_FAST_LIST_T) that is
62230557Sjimharris *        circular in nature.  This means that the next and prev pointers for
63230557Sjimharris *        an empty queue head always the address of the queue head
64230557Sjimharris *        SCI_FAST_LIST_T.  Likewise an element that has been removed from
65230557Sjimharris *        a queue will have its next and prev pointer set to the address of
66230557Sjimharris *        the SCI_FAST_LIST_T found in the structure just removed from the
67230557Sjimharris *        queue.   Pointers in this implementation never == NULL.
68230557Sjimharris *
69230557Sjimharris *        Definitions:
70230557Sjimharris *        - anchor : This is ths list container and has a
71230557Sjimharris *                   pointer to both the head and tail of the
72230557Sjimharris *                   list elements
73230557Sjimharris *        - element: This is the list element not the actual
74230557Sjimharris *                   object but the list element which has a
75230557Sjimharris *                   pointer to the object.
76230557Sjimharris */
77230557Sjimharris
78230557Sjimharris//******************************************************************************
79230557Sjimharris//*
80230557Sjimharris//*     P U B L I C   M E T H O D S
81230557Sjimharris//*
82230557Sjimharris//******************************************************************************
83230557Sjimharris
84230557Sjimharris/**
85230557Sjimharris * Initialize the double linked list anchor.  The other macros require the list
86230557Sjimharris * anchor to be set up using this macro.
87230557Sjimharris */
88230557Sjimharris#define sci_fast_list_init(anchor)                                            \
89230557Sjimharris{                                                                             \
90230557Sjimharris   (anchor)->list_head = NULL;                                                \
91230557Sjimharris   (anchor)->list_tail = NULL;                                                \
92230557Sjimharris   (anchor)->element_count = 0;                                               \
93230557Sjimharris}
94230557Sjimharris
95230557Sjimharris/**
96230557Sjimharris * Initialize the sci_fast_list_element to point to its owning object
97230557Sjimharris */
98230557Sjimharris#define sci_fast_list_element_init(list_object, element)                      \
99230557Sjimharris{                                                                             \
100230557Sjimharris   (element)->object = (list_object);                                         \
101230557Sjimharris   (element)->next = (element)->prev = NULL;                                  \
102230557Sjimharris   (element)->owning_list = NULL;                                             \
103230557Sjimharris}
104230557Sjimharris
105230557Sjimharris/**
106230557Sjimharris * See if there is anything on the list by checking the list anchor.
107230557Sjimharris */
108230557Sjimharris#define sci_fast_list_is_empty(anchor) ((anchor)->list_head == NULL)
109230557Sjimharris
110230557Sjimharris/**
111230557Sjimharris * Return a pointer to the element at the head of the sci_fast_list.  The
112230557Sjimharris * item is NOT removed from the list.
113230557Sjimharris *
114230557Sjimharris * NOTE: This macro will always return a value, even if the list is empty.
115230557Sjimharris *       You must insure the list is not empty or use Dlist_safeGetHead.
116230557Sjimharris *
117230557Sjimharris * element - A pointer into which to save the address of the structure
118230557Sjimharris *           containing the SCI_FAST_LIST at the list head.
119230557Sjimharris */
120230557Sjimharris#define sci_fast_list_get_head(anchor)                                        \
121230557Sjimharris   ((anchor)->list_head == NULL ? NULL: (anchor)->list_head->object)
122230557Sjimharris
123230557Sjimharris/**
124230557Sjimharris * Return a pointer to the element at the tail of the sci_fast_list.  The item
125230557Sjimharris * is NOT removed from the list.
126230557Sjimharris *
127230557Sjimharris * NOTE: This macro will always return a value, even if the list is empty.
128230557Sjimharris *       You must insure the list is not empty or use Dlist_safeGetHead.
129230557Sjimharris *
130230557Sjimharris * element - A pointer into which to save the address of the structure
131230557Sjimharris *           containing the SCI_FAST_LIST at the list head.
132230557Sjimharris */
133230557Sjimharris#define sci_fast_list_get_tail(anchor)                                        \
134230557Sjimharris   ((anchor)->list_tail == NULL ? NULL: (anchor)->list_head->object)
135230557Sjimharris
136230557Sjimharris/**
137230557Sjimharris * This method will get the next dListField in the SCI_FAST_LIST.  This method
138230557Sjimharris * returns a pointer to a SCI_FAST_LIST object.
139230557Sjimharris */
140230557Sjimharris#define sci_fast_list_get_next(element) ((element)->next)
141230557Sjimharris
142230557Sjimharris/**
143230557Sjimharris * This method will get the prev dListField in the SCI_FAST_LIST.  This method
144230557Sjimharris * returns a pointer to a SCI_FAST_LIST object.
145230557Sjimharris */
146230557Sjimharris#define sci_fast_list_get_prev(element) ((element)->prev)
147230557Sjimharris
148230557Sjimharris
149230557Sjimharris/**
150230557Sjimharris * This method returns the object that is represented by this
151230557Sjimharris * sci_fast_list_element
152230557Sjimharris */
153230557Sjimharris#define sci_fast_list_get_object(element) ((element)->object)
154230557Sjimharris
155230557Sjimharris/**
156230557Sjimharris * This method will determine if the supplied dListField is on a SCI_FAST_LIST.
157230557Sjimharris * If the element has only one dListField but can be on more than one list,
158230557Sjimharris * this will only tell you that it is on one of them.  If the element has
159230557Sjimharris * multiple dListFields and can exist on multiple lists at the same time, this
160230557Sjimharris * macro can tell you exactly which list it is on.
161230557Sjimharris */
162230557Sjimharris#define sci_fast_list_is_on_a_list(element) ((element)->owning_list != NULL)
163230557Sjimharris
164230557Sjimharris/**
165230557Sjimharris * This method will determine if the supplied dListFieldName is on the given
166230557Sjimharris * specified list?  If the element can be on more than one list, this
167230557Sjimharris * allows you to determine exactly which list it is on.  Performs a linear
168230557Sjimharris * search through the list.
169230557Sjimharris * result - BOOL_T that will contain the result of the search.
170230557Sjimharris *          TRUE - item is on the list described by head.
171230557Sjimharris *          FALSE - item is not on the list.
172230557Sjimharris */
173230557Sjimharris#define sci_fast_list_is_on_this_list(anchor, element) \
174230557Sjimharris   ((element)->owning_list == (anchor))
175230557Sjimharris
176230557Sjimharris//******************************************************************************
177230557Sjimharris//*
178230557Sjimharris//*     T Y P E S
179230557Sjimharris//*
180230557Sjimharris//******************************************************************************
181230557Sjimharris
182230557Sjimharris/**
183230557Sjimharris * @struct SCI_FAST_LIST
184230557Sjimharris *
185230557Sjimharris * @brief the list owner or list anchor for a set of SCI_FAST_LIST
186230557Sjimharris *        elements.
187230557Sjimharris */
188230557Sjimharristypedef struct SCI_FAST_LIST
189230557Sjimharris{
190230557Sjimharris   struct SCI_FAST_LIST_ELEMENT *list_head;
191230557Sjimharris   struct SCI_FAST_LIST_ELEMENT *list_tail;
192230557Sjimharris   int                           element_count;
193230557Sjimharris} SCI_FAST_LIST_T;
194230557Sjimharris
195230557Sjimharris/**
196230557Sjimharris * @struct SCI_FAST_LIST_ELEMENT
197230557Sjimharris *
198230557Sjimharris * @brief This structure defines what a doubly linked list element contains.
199230557Sjimharris */
200230557Sjimharristypedef struct SCI_FAST_LIST_ELEMENT
201230557Sjimharris{
202230557Sjimharris   struct SCI_FAST_LIST_ELEMENT *next;
203230557Sjimharris   struct SCI_FAST_LIST_ELEMENT *prev;
204230557Sjimharris   struct SCI_FAST_LIST         *owning_list;
205230557Sjimharris   void                         *object;
206230557Sjimharris} SCI_FAST_LIST_ELEMENT_T;
207230557Sjimharris
208230557Sjimharris
209230557Sjimharris/**
210230557Sjimharris * Insert an element to be the new head of the list hanging off of the list
211230557Sjimharris * anchor.  An empty list has the list anchor pointing to itself.
212230557Sjimharris * dListAnchor - The name of the SCI_FAST_LIST_T element that is the anchor
213230557Sjimharris *               of the queue.
214230557Sjimharris * dListFieldBeingInserted - The SCI_FAST_LIST_T field in the data structure
215230557Sjimharris *                           being queued.  This SCI_FAST_LIST will become
216230557Sjimharris *                           the new list head.
217230557Sjimharris */
218230557SjimharrisINLINE
219230557Sjimharrisstatic void sci_fast_list_insert_head(
220230557Sjimharris    SCI_FAST_LIST_T *anchor,
221230557Sjimharris    SCI_FAST_LIST_ELEMENT_T *element
222230557Sjimharris)
223230557Sjimharris{
224230557Sjimharris    element->owning_list = anchor;
225230557Sjimharris    element->prev = NULL;
226230557Sjimharris    if ( anchor->list_head == NULL )
227230557Sjimharris        anchor->list_tail = element;
228230557Sjimharris    else
229230557Sjimharris        anchor->list_head->prev = element;
230230557Sjimharris    element->next = anchor->list_head;
231230557Sjimharris    anchor->list_head = element;
232230557Sjimharris    anchor->element_count++;
233230557Sjimharris}
234230557Sjimharris
235230557Sjimharris/**
236230557Sjimharris * Insert an element at the tail of the list.  Since the list is circular we
237230557Sjimharris * can add the element at the tail through use the list anchors previous
238230557Sjimharris * pointer.
239230557Sjimharris * dListAnchor - The name of the SCI_FAST_LIST_T element that is the anchor
240230557Sjimharris *               of the queue.
241230557Sjimharris * dListFieldBeingInserted - The SCI_FAST_LIST_T field in the data structure
242230557Sjimharris *                           being queued.  This SCI_FAST_LIST will become
243230557Sjimharris *                           the new list head.
244230557Sjimharris */
245230557SjimharrisINLINE
246230557Sjimharrisstatic void sci_fast_list_insert_tail(
247230557Sjimharris    SCI_FAST_LIST_T *anchor,
248230557Sjimharris    SCI_FAST_LIST_ELEMENT_T *element
249230557Sjimharris)
250230557Sjimharris{
251230557Sjimharris    element->owning_list = anchor;
252230557Sjimharris    element->next = NULL;
253230557Sjimharris    if ( anchor->list_tail == NULL ) {
254230557Sjimharris        anchor->list_head = element;
255230557Sjimharris    } else {
256230557Sjimharris        anchor->list_tail->next = element;
257230557Sjimharris    }
258230557Sjimharris    element->prev = anchor->list_tail;
259230557Sjimharris    anchor->list_tail = element;
260230557Sjimharris    anchor->element_count++;
261230557Sjimharris}
262230557Sjimharris
263230557Sjimharris/**
264230557Sjimharris * This method will remove a dListFieldName from the head of the list.
265230557Sjimharris *
266230557Sjimharris * NOTE: This macro will always return a value, even if the list is empty.
267230557Sjimharris *       You must insure the list is not empty or use Dlist_safeRemoveHead.
268230557Sjimharris *
269230557Sjimharris * element - A pointer into which to save the address of the structure
270230557Sjimharris *           containing the SCI_FAST_LIST at the list head.
271230557Sjimharris */
272230557SjimharrisINLINE
273230557Sjimharrisstatic void *sci_fast_list_remove_head(
274230557Sjimharris    SCI_FAST_LIST_T *anchor
275230557Sjimharris)
276230557Sjimharris{
277230557Sjimharris    void *object = NULL;
278230557Sjimharris    SCI_FAST_LIST_ELEMENT_T *element;
279230557Sjimharris    if ( anchor->list_head != NULL )
280230557Sjimharris    {
281230557Sjimharris        element = anchor->list_head;
282230557Sjimharris        object = anchor->list_head->object;
283230557Sjimharris        anchor->list_head = anchor->list_head->next;
284230557Sjimharris        if ( anchor->list_head == NULL )
285230557Sjimharris        {
286230557Sjimharris            anchor->list_tail = NULL;
287230557Sjimharris        }
288230557Sjimharris        anchor->element_count--;
289230557Sjimharris        element->next = element->prev = NULL;
290230557Sjimharris        element->owning_list = NULL;
291230557Sjimharris    }
292230557Sjimharris    return object;
293230557Sjimharris}
294230557Sjimharris
295230557SjimharrisINLINE
296230557Sjimharrisstatic void *sci_fast_list_remove_tail(
297230557Sjimharris    SCI_FAST_LIST_T *anchor
298230557Sjimharris)
299230557Sjimharris{
300230557Sjimharris    void *object = NULL;
301230557Sjimharris    SCI_FAST_LIST_ELEMENT_T *element;
302230557Sjimharris    if ( anchor->list_tail != NULL )
303230557Sjimharris    {
304230557Sjimharris        element = anchor->list_tail;
305230557Sjimharris        object = element->object;
306230557Sjimharris        anchor->list_tail = element->prev;
307230557Sjimharris        if ( anchor->list_tail == NULL )
308230557Sjimharris            anchor->list_head = NULL;
309230557Sjimharris        anchor->element_count--;
310230557Sjimharris        element->next = element->prev = NULL;
311230557Sjimharris        element->owning_list = NULL;
312230557Sjimharris    }
313230557Sjimharris    return object;
314230557Sjimharris}
315230557Sjimharris
316230557Sjimharris/**
317230557Sjimharris * Remove an element from anywhere in the list referenced by name.
318230557Sjimharris */
319230557SjimharrisINLINE
320230557Sjimharrisstatic void sci_fast_list_remove_element(
321230557Sjimharris    SCI_FAST_LIST_ELEMENT_T *element
322230557Sjimharris)
323230557Sjimharris{
324230557Sjimharris    if ( element->next == NULL )
325230557Sjimharris        element->owning_list->list_tail = element->prev;
326230557Sjimharris    else
327230557Sjimharris        element->next->prev = element->prev;
328230557Sjimharris
329230557Sjimharris    if ( element->prev == NULL )
330230557Sjimharris        element->owning_list->list_head = element->next;
331230557Sjimharris    else
332230557Sjimharris        element->prev->next = element->next;
333230557Sjimharris
334230557Sjimharris    element->owning_list->element_count--;
335230557Sjimharris    element->next = element->prev = NULL;
336230557Sjimharris    element->owning_list = NULL;
337230557Sjimharris}
338230557Sjimharris
339230557Sjimharris#endif // _SCI_FAST_LIST_HEADER_
340