sys/dev/isci/scil/sci_abstract_list.c

   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
  53 #include <sys/cdefs.h>
  54 __FBSDID("$FreeBSD$");
  55
  56 /**
  57  * @file
  58  *
  59  * @brief This file contains the implementation of an abstract list class.
  60  *        This class will allow for the same item to occur multiple times in
  61  *        the list.  It will provide an interface that is similar to the
  62  *        C++ standard template list interface.
  63  */
  64
  65 //******************************************************************************
  66 //*
  67 //*     I N C L U D E S
  68 //*
  69 //******************************************************************************
  70
  71 #include <dev/isci/scil/sci_abstract_list.h>
  72
  73
  74 //******************************************************************************
  75 //*
  76 //*     P R I V A T E   M E M B E R S
  77 //*
  78 //******************************************************************************
  79
  80 //******************************************************************************
  81 //*
  82 //*     P R O T E C T E D   M E T H O D S
  83 //*
  84 //******************************************************************************
  85
  86 /**
  87  * @brief Initialize the abstract list
  88  *
  89  * @pre The supplied free pool should be constructed prior to utilization
  90  *      of this abstract list.  It isn't mandatory for the free pool to be
  91  *      constructed before invoking this method, but suggested.
  92  *
  93  * @param[in] list This parameter specifies the abstract list to be
  94  *            constructed.
  95  * @param[in] free_pool This parameter specifies the free pool to be
  96  *            utilized as the repository of free elements for list usage.
  97  *
  98  * @return none
  99  */
 100 void sci_abstract_list_construct(
 101    SCI_ABSTRACT_LIST_T         * list,
 102    SCI_ABSTRACT_ELEMENT_POOL_T * free_pool
 103 )
 104 {
 105    memset(list, 0, sizeof(SCI_ABSTRACT_LIST_T));
 106    list->free_pool = free_pool;
 107 }
 108
 109 /**
 110  * Initialize the abstract list with its free pool
 111  *
 112  * @param[in] pool
 113  *    the free pool from which the elements will be extracted
 114  * @param[in] list_elements
 115  *    the array of list elements to be added to the free list
 116  * @param[in] element_count
 117  *    the count of the elements to be added to the free list these should be
 118  *    the same as the array size of list elements
 119  *
 120  * @return none
 121  */
 122 void sci_abstract_element_pool_construct(
 123    SCI_ABSTRACT_ELEMENT_POOL_T * pool,
 124    SCI_ABSTRACT_ELEMENT_T      * list_elements,
 125    int                           element_count
 126 )
 127 {
 128    int index;
 129
 130    memset(pool, 0, sizeof(SCI_ABSTRACT_ELEMENT_POOL_T));
 131    memset(list_elements, 0, sizeof(SCI_ABSTRACT_ELEMENT_T) * element_count);
 132
 133    pool->elements     = list_elements;
 134    pool->max_elements = element_count;
 135
 136    // Loop through all of the elements in the array and push them onto the
 137    // pool's free list.
 138    for (index = element_count - 1; index >= 0; index--)
 139    {
 140       private_pool_free(pool, &(list_elements[index]));
 141    }
 142 }
 143
 144
 145 #ifdef USE_ABSTRACT_LIST_FUNCTIONS
 146
 147 //******************************************************************************
 148 //*
 149 //*     P U B L I C   M E T H O D S
 150 //*
 151 //******************************************************************************
 152
 153 /**
 154  * Simply return the front element pointer of the list.  This returns an element
 155  * element as opposed to what the element is pointing to.
 156  */
 157 SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_front(
 158    SCI_ABSTRACT_LIST_T * list_p
 159 )
 160 {
 161    return (list_p)->elements.front_p;
 162 }
 163
 164 /**
 165  * This method simply returns the object pointed to by the head (front) of
 166  * the list.
 167  */
 168 void * sci_abstract_list_front(
 169    SCI_ABSTRACT_LIST_T * list_p
 170 )
 171 {
 172    return
 173       ( ( (list_p)->elements.front_p ) ? ((list_p)->elements.front_p->object_p) : NULL );
 174 }
 175
 176 /**
 177  * This method simply returns the object pointed to by the tail (back) of
 178  * the list.
 179  */
 180 void * sci_abstract_list_back(
 181    SCI_ABSTRACT_LIST_T * list_p
 182 )
 183 {
 184    return
 185       ( ( (list_p)->elements.back_p ) ? ((list_p)->elements.back_p->object_p) : NULL );
 186 }
 187
 188 /**
 189  * This method will return FALSE if the list is not empty.
 190  */
 191 BOOL sci_abstract_list_is_empty(
 192    SCI_ABSTRACT_LIST_T * list_p
 193 )
 194 {
 195    return ( (list_p)->elements.front_p == NULL );
 196 }
 197
 198
 199 /**
 200  * This method will return the number of elements queued in the list.
 201  */
 202 U32 sci_abstract_list_size(
 203    SCI_ABSTRACT_LIST_T * list_p
 204 )
 205 {
 206    return ( (list_p)->elements.size );
 207 }
 208
 209
 210 /**
 211  * This method simply returns the next list element in the list.
 212  */
 213 SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_next(
 214    SCI_ABSTRACT_ELEMENT_T * alElement_p
 215 )
 216 {
 217    return ( (alElement_p)->next_p );
 218 }
 219
 220
 221 #if defined(SCI_LOGGING)
 222 /**
 223  * This method simply prints the contents of the list.
 224  */
 225 void  sci_abstract_list_print(
 226    SCI_ABSTRACT_LIST_T * list_p
 227 )
 228 {
 229    SCI_ABSTRACT_ELEMENT_T * alElement_p = list_p->elements.front_p;
 230
 231    while (alElement_p != NULL)
 232    {
 233 #ifdef UNIT_TEST_DEBUG
 234       /* Check to see if we found the object for which we are searching. */
 235       printf("ITEM next_p 0x%x prev_p 0x%x obj_p 0x%x, 0x%x\n",
 236              alElement_p->next_p,
 237              alElement_p->previous_p,
 238              (U32*) (alElement_p->object_p));
 239 #endif
 240       alElement_p = alElement_p->next_p;
 241    }
 242 }
 243 #endif // defined(SCI_LOGGING)
 244
 245
 246 /**
 247  * This method will simply search the supplied list for the desired object.
 248  * It will return a pointer to the object, if it is found.  Otherwise
 249  * it will return NULL.
 250  */
 251 void * sci_abstract_list_find(
 252    SCI_ABSTRACT_LIST_T * list_p,
 253    void * obj_p
 254 )
 255 {
 256    return
 257       sci_abstract_list_get_object(private_find(&(list_p)->elements, (obj_p)));
 258 }
 259
 260
 261 /**
 262  * This method will simply remove the element at the back (tail) of the list.
 263  * It will return a pointer to the object that was removed or NULL if not
 264  * found.
 265  */
 266 void * sci_abstract_list_popback(
 267    SCI_ABSTRACT_LIST_T * list_p
 268 )
 269 {
 270    SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements;
 271    SCI_ABSTRACT_ELEMENT_T      * alElement_p = elem_list->back_p;
 272    void * obj_p = NULL;
 273
 274    if (alElement_p != NULL)
 275    {
 276       obj_p = alElement_p->object_p;
 277       if (elem_list->back_p == elem_list->front_p)
 278       {
 279          elem_list->back_p = elem_list->front_p = NULL;
 280       }
 281       else
 282       {
 283          elem_list->back_p = elem_list->back_p->previous_p;
 284          elem_list->back_p->next_p = NULL;
 285       }
 286
 287       elem_list->size--;
 288       private_pool_free((list_p)->free_pool, alElement_p);
 289    }
 290
 291    return obj_p;
 292 }
 293
 294 /**
 295  * This method simply removes the list element at the head of the list
 296  * and returns the pointer to the object that was removed.
 297  */
 298 void * sci_abstract_list_popfront(
 299    SCI_ABSTRACT_LIST_T * list_p
 300 )
 301 {
 302    SCI_ABSTRACT_ELEMENT_T * alElement_p =
 303                               private_pop_front(&(list_p)->elements);
 304    void * obj_p = NULL;
 305
 306    if (alElement_p != NULL)
 307    {
 308       obj_p = alElement_p->object_p;
 309       private_pool_free((list_p)->free_pool, alElement_p);
 310    }
 311
 312    return obj_p;
 313 }
 314
 315
 316
 317 /**
 318  * This method will erase (remove) all instances of the supplied object from
 319  * anywhere in the list.
 320  */
 321 void sci_abstract_list_erase(
 322    SCI_ABSTRACT_LIST_T * list_p,
 323    void * obj_p
 324 )
 325 {
 326    SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements;
 327    SCI_ABSTRACT_ELEMENT_T      * alElement_p;
 328
 329    while ((alElement_p = private_find(elem_list, (obj_p))) != NULL)
 330    {
 331       if (alElement_p == elem_list->front_p)
 332       {
 333          sci_abstract_list_popfront(list_p);
 334       }
 335       else if (alElement_p == elem_list->back_p)
 336       {
 337          sci_abstract_list_popback(list_p);
 338       }
 339       else
 340       {
 341          alElement_p->previous_p->next_p = alElement_p->next_p;
 342          alElement_p->next_p->previous_p = alElement_p->previous_p;
 343          elem_list->size--;
 344          private_pool_free((list_p)->free_pool, alElement_p);
 345       }
 346    }
 347    return;
 348 }
 349
 350 /**
 351  * This method simply adds a LIST_ELEMENT for the supplied object to the back
 352  * (tail) of the supplied list.
 353  */
 354 void sci_abstract_list_pushback(
 355    SCI_ABSTRACT_LIST_T * list_p,
 356    void * obj_p
 357 )
 358 {
 359    SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements;
 360    SCI_ABSTRACT_ELEMENT_T      * alElement_p
 361       = private_pool_allocate((list_p)->free_pool);
 362 //   assert(alElement_p != NULL);
 363
 364    alElement_p->object_p = (obj_p);
 365
 366    if (elem_list->front_p == NULL)
 367    {
 368       elem_list->front_p = elem_list->back_p = alElement_p;
 369    }
 370    else
 371    {
 372       elem_list->back_p->next_p = alElement_p;
 373       alElement_p->previous_p   = elem_list->back_p;
 374       elem_list->back_p         = alElement_p;
 375    }
 376
 377    elem_list->size++;
 378 }
 379
 380
 381
 382 /**
 383  * This method simply adds a LIST_ELEMENT for the supplied object to the front
 384  * (head) of the supplied list.
 385  */
 386 void sci_abstract_list_pushfront(
 387    SCI_ABSTRACT_LIST_T * list_p,
 388    void * obj_p
 389 )
 390 {
 391    SCI_ABSTRACT_ELEMENT_T * alElement_p =
 392          private_pool_allocate((list_p)->free_pool);
 393    alElement_p->object_p = (obj_p);
 394    private_push_front(&(list_p)->elements, alElement_p);
 395 }
 396
 397
 398 /**
 399  * This method will add the objToAdd_p object to the list before the obj_p.
 400  *
 401  */
 402 void sci_abstract_list_insert(
 403    SCI_ABSTRACT_LIST_T * list_p,
 404    void * obj_p,
 405    void * objToAdd_p
 406 )
 407 {
 408    SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements;
 409
 410    SCI_ABSTRACT_ELEMENT_T * obj_element = private_find(elem_list, obj_p);
 411
 412    SCI_ABSTRACT_ELEMENT_T * objToAdd_element =
 413       private_pool_allocate((list_p)->free_pool);
 414
 415    objToAdd_element->object_p = objToAdd_p;
 416
 417    ASSERT(obj_element != NULL);
 418    ASSERT(objToAdd_element != NULL);
 419
 420    if (obj_element == elem_list->front_p)
 421    {
 422       objToAdd_element->object_p = (objToAdd_p);
 423       private_push_front(&(list_p)->elements, objToAdd_element);
 424    }
 425    else
 426    {
 427       obj_element->previous_p->next_p = objToAdd_element;
 428       objToAdd_element->previous_p = obj_element->previous_p;
 429
 430       obj_element->previous_p = objToAdd_element;
 431       objToAdd_element->next_p = obj_element;
 432
 433       elem_list->size++;
 434    }
 435 }
 436
 437 /**
 438  * This method simply frees all the items from the list.
 439  */
 440 void sci_abstract_list_clear(
 441    SCI_ABSTRACT_LIST_T * list_p
 442 )
 443 {
 444    while ((list_p)->elements.size > 0)
 445       sci_abstract_list_popfront((list_p));
 446 }
 447
 448 /**
 449  * This method simply returns the object being pointed to by the list element
 450  * (The item being listed).
 451  */
 452 void * sci_abstract_list_get_object(
 453    SCI_ABSTRACT_ELEMENT_T * alElement_p
 454 )
 455 {
 456    void * obj_p = NULL;
 457    if ((alElement_p) != NULL)
 458       obj_p = (alElement_p)->object_p;
 459
 460    return obj_p;
 461 }
 462
 463
 464 /**
 465  * This method is simply a wrapper to provide the number of elements in
 466  * the free list.
 467  */
 468 U32 sci_abstract_list_freeList_size(
 469    SCI_ABSTRACT_LIST_T * freeList
 470 )
 471 {
 472    return (sci_abstract_list_size(freeList));
 473 }
 474
 475 //******************************************************************************
 476 //*
 477 //*     P R I V A T E   M E T H O D S
 478 //*
 479 //******************************************************************************
 480
 481 /**
 482  * This method simply performs the common portion of pushing a list element
 483  * onto a list.
 484  *
 485  * WARNING: This is a private helper method that should not be called directly
 486  *          by any users.
 487  */
 488 void private_push_front(
 489    SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p,
 490    SCI_ABSTRACT_ELEMENT_T * alElement_p
 491 )
 492 {
 493    if ((privateList_p)->front_p == NULL)
 494    {
 495       (privateList_p)->front_p = (privateList_p)->back_p = (alElement_p);
 496       (alElement_p)->next_p = (alElement_p)->previous_p = NULL;
 497    }
 498    else
 499    {
 500       (alElement_p)->next_p                = (privateList_p)->front_p;
 501       (alElement_p)->previous_p            = NULL;
 502       (privateList_p)->front_p->previous_p = (alElement_p);
 503       (privateList_p)->front_p             = (alElement_p);
 504    }
 505
 506    (privateList_p)->size++;
 507 }
 508
 509 /**
 510  * This method simply performs the common portion of popping a list element
 511  * from a list.
 512  *
 513  * WARNING: This is a private helper method that should not be called directly
 514  *          by any users.
 515  */
 516 SCI_ABSTRACT_ELEMENT_T * private_pop_front(
 517    SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p
 518 )
 519 {
 520    SCI_ABSTRACT_ELEMENT_T * alElement_p = (privateList_p)->front_p;
 521
 522    if (alElement_p != NULL)
 523    {
 524       if ((privateList_p)->front_p == (privateList_p)->back_p)
 525       {
 526          (privateList_p)->front_p = (privateList_p)->back_p = NULL;
 527       }
 528       else
 529       {
 530          (privateList_p)->front_p = (privateList_p)->front_p->next_p;
 531          (privateList_p)->front_p->previous_p = NULL;
 532       }
 533
 534       (privateList_p)->size--;
 535    }
 536
 537    return alElement_p;
 538 }
 539
 540 /**
 541  * This method will simply search the supplied list for the desired object.
 542  * It will return a pointer to the abstract_list_element if found, otherwise
 543  * it will return NULL.
 544  */
 545 SCI_ABSTRACT_ELEMENT_T * private_find(
 546    SCI_ABSTRACT_ELEMENT_LIST_T * list_p,
 547    void * obj_p
 548 )
 549 {
 550    SCI_ABSTRACT_ELEMENT_T * alElement_p = (list_p)->front_p;
 551
 552    while (alElement_p != NULL)
 553    {
 554       /* Check to see if we found the object for which we are searching. */
 555       if (alElement_p->object_p == (void*) (obj_p))
 556       {
 557          break;
 558       }
 559
 560       alElement_p = alElement_p->next_p;
 561    }
 562
 563    return alElement_p;
 564 }
 565
 566 /**
 567  * This private method will free the supplied list element back to the pool
 568  * of free list elements.
 569  */
 570 void private_pool_free(
 571    SCI_ABSTRACT_ELEMENT_POOL_T * free_pool,
 572    SCI_ABSTRACT_ELEMENT_T * alElement_p
 573 )
 574 {
 575    /* Push the list element back to the head to get better locality of */
 576    /* reference with the cache.                                        */
 577    private_push_front(&(free_pool)->free_list, (alElement_p));
 578 }
 579
 580 /**
 581  * This private method will allocate a list element from the pool of free
 582  * list elements.
 583  */
 584 SCI_ABSTRACT_ELEMENT_T * private_pool_allocate(
 585    SCI_ABSTRACT_ELEMENT_POOL_T * free_pool
 586 )
 587 {
 588    SCI_ABSTRACT_ELEMENT_T * alElement_p;
 589
 590    alElement_p = private_pop_front(&(free_pool)->free_list);
 591
 592    alElement_p->next_p     = NULL;
 593    alElement_p->previous_p = NULL;
 594    alElement_p->object_p   = NULL;
 595
 596    return alElement_p;
 597 }
 598
 599 #endif // USE_ABSTRACT_LIST_FUNCTIONS