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