sys/dev/isci/scil/sci_fast_list.h

   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  */
 188 typedef 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  */
 200 typedef 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  */
 218 INLINE
 219 static 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  */
 245 INLINE
 246 static 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  */
 272 INLINE
 273 static 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
 295 INLINE
 296 static 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  */
 319 INLINE
 320 static 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_