sys/dev/isci/scil/sci_simple_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_SIMPLE_LIST_HEADER_
  55 #define _SCI_SIMPLE_LIST_HEADER_
  56
  57 /**
  58  * @file
  59  *
  60  * @brief This header file contains simple linked list manipulation macros.
  61  *        These macros differ from the SCI_FAST_LIST in that deletion of
  62  *        an element from the list is O(n).
  63  *        The reason for using this implementation over the SCI_FAST_LIST
  64  *        is
  65  *           1) space savings as there is only a single link element instead
  66  *              of the 2 link elements used in the SCI_FAST_LIST and
  67  *           2) it is possible to detach the entire list from its anchor
  68  *              element for processing.
  69  *
  70  * @note Do not use the SCI_SIMPLE_LIST if you need to remove elements from
  71  *       random locations within the list use instead the SCI_FAST_LIST.
  72  */
  73
  74
  75 //******************************************************************************
  76 //*
  77 //*     P U B L I C    M E T H O D S
  78 //*
  79 //******************************************************************************
  80
  81 /**
  82  * Initialize the singely linked list anchor.  The other macros require the
  83  * list anchor to be properly initialized.
  84  */
  85 #define sci_simple_list_init(anchor) \
  86 { \
  87    (anchor)->list_head = NULL; \
  88    (anchor)->list_tail = NULL; \
  89    (anchor)->list_count = 0; \
  90 }
  91
  92 /**
  93  * Initialze the singely linked list element. The other macros require the
  94  * list element to be properly initialized.
  95  */
  96 #define sci_simple_list_element_init(list_object, element) \
  97 { \
  98    (element)->next = NULL; \
  99    (element)->object = (list_object); \
 100 }
 101
 102 /**
 103  * See if there are any list elements on this list.
 104  */
 105 #define sci_simple_list_is_empty(anchor)  ((anchor)->list_head == NULL)
 106
 107 /**
 108  * Return a pointer to the list element at the head of the list.  The list
 109  * element is not removed from the list.
 110  */
 111 #define sci_simple_list_get_head(anchor) ((anchor)->list_head)
 112
 113 /**
 114  * Retuen a pointer to the lsit element at the tail of the list.  The list
 115  * element is not removed from the list.
 116  */
 117 #define sci_simple_list_get_tail(anchor) ((anchor)->list_tail)
 118
 119 /**
 120  * Return the count of the number of elements in this list.
 121  */
 122 #define sci_simple_list_get_count(anchor) ((anchor)->list_count)
 123
 124 /**
 125  * Return a pointer to the list element following this list element.
 126  * If this is the last element in the list then NULL is returned.
 127  */
 128 #define sci_simple_list_get_next(element) ((element)->next)
 129
 130 /**
 131  * Return the object represented by the list element.
 132  */
 133 #define sci_simple_list_get_object(element) ((element)->object)
 134
 135
 136 //******************************************************************************
 137 //*
 138 //*     T Y P E S
 139 //*
 140 //******************************************************************************
 141
 142 /**
 143  * @struct
 144  *
 145  * @brief This structure defines the list owner for singely linked list.
 146  */
 147 typedef struct SCI_SIMPLE_LIST
 148 {
 149    struct SCI_SIMPLE_LIST_ELEMENT *list_head;
 150    struct SCI_SIMPLE_LIST_ELEMENT *list_tail;
 151    U32                             list_count;
 152 } SCI_SIMPLE_LIST_T;
 153
 154 /**
 155  * @struct SCI_SIMPLE_LIST_ELEMENT
 156  *
 157  * @brief This structure defines what a singely linked list element contains.
 158  */
 159 typedef struct SCI_SIMPLE_LIST_ELEMENT
 160 {
 161    struct SCI_SIMPLE_LIST_ELEMENT *next;
 162    void                           *object;
 163 } SCI_SIMPLE_LIST_ELEMENT_T;
 164
 165 /**
 166  * This method will insert the list element to the head of the list contained
 167  * by the anchor.
 168  *
 169  * @note Pushing new elements onto a list is more efficient than inserting
 170  *       them to the tail of the list though both are O(1) operations.
 171  */
 172 INLINE
 173 static void sci_simple_list_insert_head(
 174    SCI_SIMPLE_LIST_T * anchor,
 175    SCI_SIMPLE_LIST_ELEMENT_T *element
 176 )
 177 {
 178    if (anchor->list_tail == NULL)
 179    {
 180       anchor->list_tail = element;
 181    }
 182
 183    element->next = anchor->list_head;
 184    anchor->list_head = element;
 185    anchor->list_count++;
 186 }
 187
 188 /**
 189  * This methos will insert the list element to the tail of the list contained
 190  * by the anchor.
 191  *
 192  * @param[in, out] anchor this is the list into which the element is to be
 193  *                 inserted
 194  * @param[in] element this is the element which to insert into the list.
 195  *
 196  * @note Pushing new elements onto a list is more efficient than inserting
 197  *       them to the tail of the list though both are O(1) operations.
 198  */
 199 INLINE
 200 static void sci_simple_list_insert_tail(
 201    SCI_SIMPLE_LIST_T * anchor,
 202    SCI_SIMPLE_LIST_ELEMENT_T *element
 203 )
 204 {
 205    if (anchor->list_tail == NULL)
 206    {
 207       anchor->list_head = element;
 208    }
 209    else
 210    {
 211       anchor->list_tail->next = element;
 212    }
 213
 214    anchor->list_tail = element;
 215    anchor->list_count++;
 216 }
 217
 218 /**
 219  * This method will remove the list element from the anchor and return the
 220  * object pointed to by that list element.
 221  *
 222  * @param[in, out] anchor this is the list into which the element is to be
 223  *                 inserted
 224  *
 225  * @return the list element at the head of the list.
 226  */
 227 INLINE
 228 static void * sci_simple_list_remove_head(
 229    SCI_SIMPLE_LIST_T * anchor
 230 )
 231 {
 232    void * object = NULL;
 233
 234    if (anchor->list_head != NULL)
 235    {
 236       object = anchor->list_head->object;
 237
 238       anchor->list_head = anchor->list_head->next;
 239
 240       if (anchor->list_head == NULL)
 241       {
 242          anchor->list_tail = NULL;
 243       }
 244
 245       anchor->list_count--;
 246    }
 247
 248    return object;
 249 }
 250
 251 /**
 252  * Move all the list elements from source anchor to the dest anchor.
 253  * The source anchor will have all of its elements removed making it
 254  * an empty list and the dest anchor will contain all of the source
 255  * and dest list elements.
 256  *
 257  * @param[in, out] dest_anchor this is the list into which all elements from
 258  *                 the source list are to be moved.
 259  * @param[in, out] source_anchor this is the list which is to be moved to the
 260  *                 destination list.  This list will be empty on return.
 261  *
 262  * @return the list element at the head of the list.
 263  * @note If the destination has list elements use the insert at head
 264  *       or tail routines instead.
 265  */
 266 INLINE
 267 static void sci_simple_list_move_list(
 268    SCI_SIMPLE_LIST_T * dest_anchor,
 269    SCI_SIMPLE_LIST_T * source_anchor
 270 )
 271 {
 272    *dest_anchor = *source_anchor;
 273
 274    sci_simple_list_init(source_anchor);
 275 }
 276
 277 /**
 278  * This method will insert the list elements from the source anchor to the
 279  * destination list before all previous elements on the destination list.
 280  *
 281  * @param[in, out] dest_anchor this is the list into which all elements from
 282  *                 the source list are to be moved. The destination list will
 283  *                 now contain both sets of list elements.
 284  * @param[in, out] source_anchor this is the list which is to be moved to the
 285  *                 destination list.  This list will be empty on return.
 286  */
 287 INLINE
 288 static void sci_simple_list_insert_list_at_head(
 289    SCI_SIMPLE_LIST_T * dest_anchor,
 290    SCI_SIMPLE_LIST_T * source_anchor
 291 )
 292 {
 293    if (!sci_simple_list_is_empty(source_anchor))
 294    {
 295       if (sci_simple_list_is_empty(dest_anchor))
 296       {
 297          // Destination is empty just copy the source on over
 298          *dest_anchor = *source_anchor;
 299       }
 300       else
 301       {
 302          source_anchor->list_tail->next = dest_anchor->list_head;
 303          dest_anchor->list_head = source_anchor->list_head;
 304          dest_anchor->list_count += source_anchor->list_count;
 305       }
 306
 307       // Wipe the source list to make sure the list elements can not be accessed
 308       // from two seperate lists at the same time.
 309       sci_simple_list_init(source_anchor);
 310    }
 311 }
 312
 313 /**
 314  * This method will insert the list elements from the source anchor to the
 315  * destination anchor after all list elements on the destination anchor.
 316  *
 317  * @param[in, out] dest_anchor this is the list into which all elements from
 318  *                 the source list are to be moved. The destination list will
 319  *                 contain both the source and destination list elements.
 320  * @param[in, out] source_anchor this is the list which is to be moved to the
 321  *                 destination list.  This list will be empty on return.
 322  */
 323 INLINE
 324 static void sci_simple_list_insert_list_at_tail(
 325    SCI_SIMPLE_LIST_T * dest_anchor,
 326    SCI_SIMPLE_LIST_T * source_anchor
 327 )
 328 {
 329    if (!sci_simple_list_is_empty(source_anchor))
 330    {
 331       if (sci_simple_list_is_empty(dest_anchor))
 332       {
 333          // Destination is empty just copy the source on over
 334          *dest_anchor = *source_anchor;
 335       }
 336       else
 337       {
 338          // If the source list is empty the desination list is the result.
 339          dest_anchor->list_tail->next = source_anchor->list_head;
 340          dest_anchor->list_tail = source_anchor->list_tail;
 341          dest_anchor->list_count += source_anchor->list_count;
 342       }
 343
 344       // Wipe the source list to make sure the list elements can not be accessed
 345       // from two seperate lists at the same time.
 346       sci_simple_list_init(source_anchor);
 347    }
 348 }
 349
 350 #endif // _SCI_SIMPLE_LIST_HEADER_