1f11c7f63SJim Harris /*- 2718cf2ccSPedro F. Giffuni * SPDX-License-Identifier: BSD-2-Clause OR GPL-2.0 3718cf2ccSPedro F. Giffuni * 4f11c7f63SJim Harris * This file is provided under a dual BSD/GPLv2 license. When using or 5f11c7f63SJim Harris * redistributing this file, you may do so under either license. 6f11c7f63SJim Harris * 7f11c7f63SJim Harris * GPL LICENSE SUMMARY 8f11c7f63SJim Harris * 9f11c7f63SJim Harris * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved. 10f11c7f63SJim Harris * 11f11c7f63SJim Harris * This program is free software; you can redistribute it and/or modify 12f11c7f63SJim Harris * it under the terms of version 2 of the GNU General Public License as 13f11c7f63SJim Harris * published by the Free Software Foundation. 14f11c7f63SJim Harris * 15f11c7f63SJim Harris * This program is distributed in the hope that it will be useful, but 16f11c7f63SJim Harris * WITHOUT ANY WARRANTY; without even the implied warranty of 17f11c7f63SJim Harris * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 18f11c7f63SJim Harris * General Public License for more details. 19f11c7f63SJim Harris * 20f11c7f63SJim Harris * You should have received a copy of the GNU General Public License 21f11c7f63SJim Harris * along with this program; if not, write to the Free Software 22f11c7f63SJim Harris * Foundation, Inc., 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA. 23f11c7f63SJim Harris * The full GNU General Public License is included in this distribution 24f11c7f63SJim Harris * in the file called LICENSE.GPL. 25f11c7f63SJim Harris * 26f11c7f63SJim Harris * BSD LICENSE 27f11c7f63SJim Harris * 28f11c7f63SJim Harris * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved. 29f11c7f63SJim Harris * All rights reserved. 30f11c7f63SJim Harris * 31f11c7f63SJim Harris * Redistribution and use in source and binary forms, with or without 32f11c7f63SJim Harris * modification, are permitted provided that the following conditions 33f11c7f63SJim Harris * are met: 34f11c7f63SJim Harris * 35f11c7f63SJim Harris * * Redistributions of source code must retain the above copyright 36f11c7f63SJim Harris * notice, this list of conditions and the following disclaimer. 37f11c7f63SJim Harris * * Redistributions in binary form must reproduce the above copyright 38f11c7f63SJim Harris * notice, this list of conditions and the following disclaimer in 39f11c7f63SJim Harris * the documentation and/or other materials provided with the 40f11c7f63SJim Harris * distribution. 41f11c7f63SJim Harris * 42f11c7f63SJim Harris * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 43f11c7f63SJim Harris * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 44f11c7f63SJim Harris * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 45f11c7f63SJim Harris * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 46f11c7f63SJim Harris * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 47f11c7f63SJim Harris * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 48f11c7f63SJim Harris * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 49f11c7f63SJim Harris * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 50f11c7f63SJim Harris * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 51f11c7f63SJim Harris * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 52f11c7f63SJim Harris * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 53f11c7f63SJim Harris * 54f11c7f63SJim Harris * $FreeBSD$ 55f11c7f63SJim Harris */ 56f11c7f63SJim Harris #ifndef _SCI_FAST_LIST_HEADER_ 57f11c7f63SJim Harris #define _SCI_FAST_LIST_HEADER_ 58f11c7f63SJim Harris 59f11c7f63SJim Harris /** 60f11c7f63SJim Harris * @file 61f11c7f63SJim Harris * 62f11c7f63SJim Harris * @brief Header file that contains basic Linked List manipulation macros. 63f11c7f63SJim Harris * These macros implement a double linked list (SCI_FAST_LIST_T) that is 64f11c7f63SJim Harris * circular in nature. This means that the next and prev pointers for 65f11c7f63SJim Harris * an empty queue head always the address of the queue head 66f11c7f63SJim Harris * SCI_FAST_LIST_T. Likewise an element that has been removed from 67f11c7f63SJim Harris * a queue will have its next and prev pointer set to the address of 68f11c7f63SJim Harris * the SCI_FAST_LIST_T found in the structure just removed from the 69f11c7f63SJim Harris * queue. Pointers in this implementation never == NULL. 70f11c7f63SJim Harris * 71f11c7f63SJim Harris * Definitions: 72453130d9SPedro F. Giffuni * - anchor : This is the list container and has a 73f11c7f63SJim Harris * pointer to both the head and tail of the 74f11c7f63SJim Harris * list elements 75f11c7f63SJim Harris * - element: This is the list element not the actual 76f11c7f63SJim Harris * object but the list element which has a 77f11c7f63SJim Harris * pointer to the object. 78f11c7f63SJim Harris */ 79f11c7f63SJim Harris 80f11c7f63SJim Harris //****************************************************************************** 81f11c7f63SJim Harris //* 82f11c7f63SJim Harris //* P U B L I C M E T H O D S 83f11c7f63SJim Harris //* 84f11c7f63SJim Harris //****************************************************************************** 85f11c7f63SJim Harris 86f11c7f63SJim Harris /** 87f11c7f63SJim Harris * Initialize the double linked list anchor. The other macros require the list 88f11c7f63SJim Harris * anchor to be set up using this macro. 89f11c7f63SJim Harris */ 90f11c7f63SJim Harris #define sci_fast_list_init(anchor) \ 91f11c7f63SJim Harris { \ 92f11c7f63SJim Harris (anchor)->list_head = NULL; \ 93f11c7f63SJim Harris (anchor)->list_tail = NULL; \ 94f11c7f63SJim Harris (anchor)->element_count = 0; \ 95f11c7f63SJim Harris } 96f11c7f63SJim Harris 97f11c7f63SJim Harris /** 98f11c7f63SJim Harris * Initialize the sci_fast_list_element to point to its owning object 99f11c7f63SJim Harris */ 100f11c7f63SJim Harris #define sci_fast_list_element_init(list_object, element) \ 101f11c7f63SJim Harris { \ 102f11c7f63SJim Harris (element)->object = (list_object); \ 103f11c7f63SJim Harris (element)->next = (element)->prev = NULL; \ 104f11c7f63SJim Harris (element)->owning_list = NULL; \ 105f11c7f63SJim Harris } 106f11c7f63SJim Harris 107f11c7f63SJim Harris /** 108f11c7f63SJim Harris * See if there is anything on the list by checking the list anchor. 109f11c7f63SJim Harris */ 110f11c7f63SJim Harris #define sci_fast_list_is_empty(anchor) ((anchor)->list_head == NULL) 111f11c7f63SJim Harris 112f11c7f63SJim Harris /** 113f11c7f63SJim Harris * Return a pointer to the element at the head of the sci_fast_list. The 114f11c7f63SJim Harris * item is NOT removed from the list. 115f11c7f63SJim Harris * 116f11c7f63SJim Harris * NOTE: This macro will always return a value, even if the list is empty. 117f11c7f63SJim Harris * You must insure the list is not empty or use Dlist_safeGetHead. 118f11c7f63SJim Harris * 119f11c7f63SJim Harris * element - A pointer into which to save the address of the structure 120f11c7f63SJim Harris * containing the SCI_FAST_LIST at the list head. 121f11c7f63SJim Harris */ 122f11c7f63SJim Harris #define sci_fast_list_get_head(anchor) \ 123f11c7f63SJim Harris ((anchor)->list_head == NULL ? NULL: (anchor)->list_head->object) 124f11c7f63SJim Harris 125f11c7f63SJim Harris /** 126f11c7f63SJim Harris * Return a pointer to the element at the tail of the sci_fast_list. The item 127f11c7f63SJim Harris * is NOT removed from the list. 128f11c7f63SJim Harris * 129f11c7f63SJim Harris * NOTE: This macro will always return a value, even if the list is empty. 130f11c7f63SJim Harris * You must insure the list is not empty or use Dlist_safeGetHead. 131f11c7f63SJim Harris * 132f11c7f63SJim Harris * element - A pointer into which to save the address of the structure 133f11c7f63SJim Harris * containing the SCI_FAST_LIST at the list head. 134f11c7f63SJim Harris */ 135f11c7f63SJim Harris #define sci_fast_list_get_tail(anchor) \ 136f11c7f63SJim Harris ((anchor)->list_tail == NULL ? NULL: (anchor)->list_head->object) 137f11c7f63SJim Harris 138f11c7f63SJim Harris /** 139f11c7f63SJim Harris * This method will get the next dListField in the SCI_FAST_LIST. This method 140f11c7f63SJim Harris * returns a pointer to a SCI_FAST_LIST object. 141f11c7f63SJim Harris */ 142f11c7f63SJim Harris #define sci_fast_list_get_next(element) ((element)->next) 143f11c7f63SJim Harris 144f11c7f63SJim Harris /** 145f11c7f63SJim Harris * This method will get the prev dListField in the SCI_FAST_LIST. This method 146f11c7f63SJim Harris * returns a pointer to a SCI_FAST_LIST object. 147f11c7f63SJim Harris */ 148f11c7f63SJim Harris #define sci_fast_list_get_prev(element) ((element)->prev) 149f11c7f63SJim Harris 150f11c7f63SJim Harris 151f11c7f63SJim Harris /** 152f11c7f63SJim Harris * This method returns the object that is represented by this 153f11c7f63SJim Harris * sci_fast_list_element 154f11c7f63SJim Harris */ 155f11c7f63SJim Harris #define sci_fast_list_get_object(element) ((element)->object) 156f11c7f63SJim Harris 157f11c7f63SJim Harris /** 158f11c7f63SJim Harris * This method will determine if the supplied dListField is on a SCI_FAST_LIST. 159f11c7f63SJim Harris * If the element has only one dListField but can be on more than one list, 160f11c7f63SJim Harris * this will only tell you that it is on one of them. If the element has 161f11c7f63SJim Harris * multiple dListFields and can exist on multiple lists at the same time, this 162f11c7f63SJim Harris * macro can tell you exactly which list it is on. 163f11c7f63SJim Harris */ 164f11c7f63SJim Harris #define sci_fast_list_is_on_a_list(element) ((element)->owning_list != NULL) 165f11c7f63SJim Harris 166f11c7f63SJim Harris /** 167f11c7f63SJim Harris * This method will determine if the supplied dListFieldName is on the given 168f11c7f63SJim Harris * specified list? If the element can be on more than one list, this 169f11c7f63SJim Harris * allows you to determine exactly which list it is on. Performs a linear 170f11c7f63SJim Harris * search through the list. 171f11c7f63SJim Harris * result - BOOL_T that will contain the result of the search. 172f11c7f63SJim Harris * TRUE - item is on the list described by head. 173f11c7f63SJim Harris * FALSE - item is not on the list. 174f11c7f63SJim Harris */ 175f11c7f63SJim Harris #define sci_fast_list_is_on_this_list(anchor, element) \ 176f11c7f63SJim Harris ((element)->owning_list == (anchor)) 177f11c7f63SJim Harris 178f11c7f63SJim Harris //****************************************************************************** 179f11c7f63SJim Harris //* 180f11c7f63SJim Harris //* T Y P E S 181f11c7f63SJim Harris //* 182f11c7f63SJim Harris //****************************************************************************** 183f11c7f63SJim Harris 184f11c7f63SJim Harris /** 185f11c7f63SJim Harris * @struct SCI_FAST_LIST 186f11c7f63SJim Harris * 187f11c7f63SJim Harris * @brief the list owner or list anchor for a set of SCI_FAST_LIST 188f11c7f63SJim Harris * elements. 189f11c7f63SJim Harris */ 190f11c7f63SJim Harris typedef struct SCI_FAST_LIST 191f11c7f63SJim Harris { 192f11c7f63SJim Harris struct SCI_FAST_LIST_ELEMENT *list_head; 193f11c7f63SJim Harris struct SCI_FAST_LIST_ELEMENT *list_tail; 194f11c7f63SJim Harris int element_count; 195f11c7f63SJim Harris } SCI_FAST_LIST_T; 196f11c7f63SJim Harris 197f11c7f63SJim Harris /** 198f11c7f63SJim Harris * @struct SCI_FAST_LIST_ELEMENT 199f11c7f63SJim Harris * 200f11c7f63SJim Harris * @brief This structure defines what a doubly linked list element contains. 201f11c7f63SJim Harris */ 202f11c7f63SJim Harris typedef struct SCI_FAST_LIST_ELEMENT 203f11c7f63SJim Harris { 204f11c7f63SJim Harris struct SCI_FAST_LIST_ELEMENT *next; 205f11c7f63SJim Harris struct SCI_FAST_LIST_ELEMENT *prev; 206f11c7f63SJim Harris struct SCI_FAST_LIST *owning_list; 207f11c7f63SJim Harris void *object; 208f11c7f63SJim Harris } SCI_FAST_LIST_ELEMENT_T; 209f11c7f63SJim Harris 210f11c7f63SJim Harris 211f11c7f63SJim Harris /** 212f11c7f63SJim Harris * Insert an element to be the new head of the list hanging off of the list 213f11c7f63SJim Harris * anchor. An empty list has the list anchor pointing to itself. 214f11c7f63SJim Harris * dListAnchor - The name of the SCI_FAST_LIST_T element that is the anchor 215f11c7f63SJim Harris * of the queue. 216f11c7f63SJim Harris * dListFieldBeingInserted - The SCI_FAST_LIST_T field in the data structure 217f11c7f63SJim Harris * being queued. This SCI_FAST_LIST will become 218f11c7f63SJim Harris * the new list head. 219f11c7f63SJim Harris */ 220f11c7f63SJim Harris INLINE 221f11c7f63SJim Harris static void sci_fast_list_insert_head( 222f11c7f63SJim Harris SCI_FAST_LIST_T *anchor, 223f11c7f63SJim Harris SCI_FAST_LIST_ELEMENT_T *element 224f11c7f63SJim Harris ) 225f11c7f63SJim Harris { 226f11c7f63SJim Harris element->owning_list = anchor; 227f11c7f63SJim Harris element->prev = NULL; 228f11c7f63SJim Harris if ( anchor->list_head == NULL ) 229f11c7f63SJim Harris anchor->list_tail = element; 230f11c7f63SJim Harris else 231f11c7f63SJim Harris anchor->list_head->prev = element; 232f11c7f63SJim Harris element->next = anchor->list_head; 233f11c7f63SJim Harris anchor->list_head = element; 234f11c7f63SJim Harris anchor->element_count++; 235f11c7f63SJim Harris } 236f11c7f63SJim Harris 237f11c7f63SJim Harris /** 238f11c7f63SJim Harris * Insert an element at the tail of the list. Since the list is circular we 239f11c7f63SJim Harris * can add the element at the tail through use the list anchors previous 240f11c7f63SJim Harris * pointer. 241f11c7f63SJim Harris * dListAnchor - The name of the SCI_FAST_LIST_T element that is the anchor 242f11c7f63SJim Harris * of the queue. 243f11c7f63SJim Harris * dListFieldBeingInserted - The SCI_FAST_LIST_T field in the data structure 244f11c7f63SJim Harris * being queued. This SCI_FAST_LIST will become 245f11c7f63SJim Harris * the new list head. 246f11c7f63SJim Harris */ 247f11c7f63SJim Harris INLINE 248f11c7f63SJim Harris static void sci_fast_list_insert_tail( 249f11c7f63SJim Harris SCI_FAST_LIST_T *anchor, 250f11c7f63SJim Harris SCI_FAST_LIST_ELEMENT_T *element 251f11c7f63SJim Harris ) 252f11c7f63SJim Harris { 253f11c7f63SJim Harris element->owning_list = anchor; 254f11c7f63SJim Harris element->next = NULL; 255f11c7f63SJim Harris if ( anchor->list_tail == NULL ) { 256f11c7f63SJim Harris anchor->list_head = element; 257f11c7f63SJim Harris } else { 258f11c7f63SJim Harris anchor->list_tail->next = element; 259f11c7f63SJim Harris } 260f11c7f63SJim Harris element->prev = anchor->list_tail; 261f11c7f63SJim Harris anchor->list_tail = element; 262f11c7f63SJim Harris anchor->element_count++; 263f11c7f63SJim Harris } 264f11c7f63SJim Harris 265f11c7f63SJim Harris /** 266f11c7f63SJim Harris * This method will remove a dListFieldName from the head of the list. 267f11c7f63SJim Harris * 268f11c7f63SJim Harris * NOTE: This macro will always return a value, even if the list is empty. 269f11c7f63SJim Harris * You must insure the list is not empty or use Dlist_safeRemoveHead. 270f11c7f63SJim Harris * 271f11c7f63SJim Harris * element - A pointer into which to save the address of the structure 272f11c7f63SJim Harris * containing the SCI_FAST_LIST at the list head. 273f11c7f63SJim Harris */ 274f11c7f63SJim Harris INLINE 275f11c7f63SJim Harris static void *sci_fast_list_remove_head( 276f11c7f63SJim Harris SCI_FAST_LIST_T *anchor 277f11c7f63SJim Harris ) 278f11c7f63SJim Harris { 279f11c7f63SJim Harris void *object = NULL; 280f11c7f63SJim Harris SCI_FAST_LIST_ELEMENT_T *element; 281f11c7f63SJim Harris if ( anchor->list_head != NULL ) 282f11c7f63SJim Harris { 283f11c7f63SJim Harris element = anchor->list_head; 284f11c7f63SJim Harris object = anchor->list_head->object; 285f11c7f63SJim Harris anchor->list_head = anchor->list_head->next; 286f11c7f63SJim Harris if ( anchor->list_head == NULL ) 287f11c7f63SJim Harris { 288f11c7f63SJim Harris anchor->list_tail = NULL; 289f11c7f63SJim Harris } 290f11c7f63SJim Harris anchor->element_count--; 291f11c7f63SJim Harris element->next = element->prev = NULL; 292f11c7f63SJim Harris element->owning_list = NULL; 293f11c7f63SJim Harris } 294f11c7f63SJim Harris return object; 295f11c7f63SJim Harris } 296f11c7f63SJim Harris 297f11c7f63SJim Harris INLINE 298f11c7f63SJim Harris static void *sci_fast_list_remove_tail( 299f11c7f63SJim Harris SCI_FAST_LIST_T *anchor 300f11c7f63SJim Harris ) 301f11c7f63SJim Harris { 302f11c7f63SJim Harris void *object = NULL; 303f11c7f63SJim Harris SCI_FAST_LIST_ELEMENT_T *element; 304f11c7f63SJim Harris if ( anchor->list_tail != NULL ) 305f11c7f63SJim Harris { 306f11c7f63SJim Harris element = anchor->list_tail; 307f11c7f63SJim Harris object = element->object; 308f11c7f63SJim Harris anchor->list_tail = element->prev; 309f11c7f63SJim Harris if ( anchor->list_tail == NULL ) 310f11c7f63SJim Harris anchor->list_head = NULL; 311f11c7f63SJim Harris anchor->element_count--; 312f11c7f63SJim Harris element->next = element->prev = NULL; 313f11c7f63SJim Harris element->owning_list = NULL; 314f11c7f63SJim Harris } 315f11c7f63SJim Harris return object; 316f11c7f63SJim Harris } 317f11c7f63SJim Harris 318f11c7f63SJim Harris /** 319f11c7f63SJim Harris * Remove an element from anywhere in the list referenced by name. 320f11c7f63SJim Harris */ 321f11c7f63SJim Harris INLINE 322f11c7f63SJim Harris static void sci_fast_list_remove_element( 323f11c7f63SJim Harris SCI_FAST_LIST_ELEMENT_T *element 324f11c7f63SJim Harris ) 325f11c7f63SJim Harris { 326f11c7f63SJim Harris if ( element->next == NULL ) 327f11c7f63SJim Harris element->owning_list->list_tail = element->prev; 328f11c7f63SJim Harris else 329f11c7f63SJim Harris element->next->prev = element->prev; 330f11c7f63SJim Harris 331f11c7f63SJim Harris if ( element->prev == NULL ) 332f11c7f63SJim Harris element->owning_list->list_head = element->next; 333f11c7f63SJim Harris else 334f11c7f63SJim Harris element->prev->next = element->next; 335f11c7f63SJim Harris 336f11c7f63SJim Harris element->owning_list->element_count--; 337f11c7f63SJim Harris element->next = element->prev = NULL; 338f11c7f63SJim Harris element->owning_list = NULL; 339f11c7f63SJim Harris } 340f11c7f63SJim Harris 341f11c7f63SJim Harris #endif // _SCI_FAST_LIST_HEADER_ 342