diff options
Diffstat (limited to 'sys/dev/isci/scil/sci_abstract_list.c')
-rw-r--r-- | sys/dev/isci/scil/sci_abstract_list.c | 599 |
1 files changed, 599 insertions, 0 deletions
diff --git a/sys/dev/isci/scil/sci_abstract_list.c b/sys/dev/isci/scil/sci_abstract_list.c new file mode 100644 index 0000000..641eb4a --- /dev/null +++ b/sys/dev/isci/scil/sci_abstract_list.c @@ -0,0 +1,599 @@ +/*- + * This file is provided under a dual BSD/GPLv2 license. When using or + * redistributing this file, you may do so under either license. + * + * GPL LICENSE SUMMARY + * + * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of version 2 of the GNU General Public License as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA. + * The full GNU General Public License is included in this distribution + * in the file called LICENSE.GPL. + * + * BSD LICENSE + * + * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +/** + * @file + * + * @brief This file contains the implementation of an abstract list class. + * This class will allow for the same item to occur multiple times in + * the list. It will provide an interface that is similar to the + * C++ standard template list interface. + */ + +//****************************************************************************** +//* +//* I N C L U D E S +//* +//****************************************************************************** + +#include <dev/isci/scil/sci_abstract_list.h> + + +//****************************************************************************** +//* +//* P R I V A T E M E M B E R S +//* +//****************************************************************************** + +//****************************************************************************** +//* +//* P R O T E C T E D M E T H O D S +//* +//****************************************************************************** + +/** + * @brief Initialize the abstract list + * + * @pre The supplied free pool should be constructed prior to utilization + * of this abstract list. It isn't mandatory for the free pool to be + * constructed before invoking this method, but suggested. + * + * @param[in] list This parameter specifies the abstract list to be + * constructed. + * @param[in] free_pool This parameter specifies the free pool to be + * utilized as the repository of free elements for list usage. + * + * @return none + */ +void sci_abstract_list_construct( + SCI_ABSTRACT_LIST_T * list, + SCI_ABSTRACT_ELEMENT_POOL_T * free_pool +) +{ + memset(list, 0, sizeof(SCI_ABSTRACT_LIST_T)); + list->free_pool = free_pool; +} + +/** + * Initialize the abstract list with its free pool + * + * @param[in] pool + * the free pool from which the elements will be extracted + * @param[in] list_elements + * the array of list elements to be added to the free list + * @param[in] element_count + * the count of the elements to be added to the free list these should be + * the same as the array size of list elements + * + * @return none + */ +void sci_abstract_element_pool_construct( + SCI_ABSTRACT_ELEMENT_POOL_T * pool, + SCI_ABSTRACT_ELEMENT_T * list_elements, + int element_count +) +{ + int index; + + memset(pool, 0, sizeof(SCI_ABSTRACT_ELEMENT_POOL_T)); + memset(list_elements, 0, sizeof(SCI_ABSTRACT_ELEMENT_T) * element_count); + + pool->elements = list_elements; + pool->max_elements = element_count; + + // Loop through all of the elements in the array and push them onto the + // pool's free list. + for (index = element_count - 1; index >= 0; index--) + { + private_pool_free(pool, &(list_elements[index])); + } +} + + +#ifdef USE_ABSTRACT_LIST_FUNCTIONS + +//****************************************************************************** +//* +//* P U B L I C M E T H O D S +//* +//****************************************************************************** + +/** + * Simply return the front element pointer of the list. This returns an element + * element as opposed to what the element is pointing to. + */ +SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_front( + SCI_ABSTRACT_LIST_T * list_p +) +{ + return (list_p)->elements.front_p; +} + +/** + * This method simply returns the object pointed to by the head (front) of + * the list. + */ +void * sci_abstract_list_front( + SCI_ABSTRACT_LIST_T * list_p +) +{ + return + ( ( (list_p)->elements.front_p ) ? ((list_p)->elements.front_p->object_p) : NULL ); +} + +/** + * This method simply returns the object pointed to by the tail (back) of + * the list. + */ +void * sci_abstract_list_back( + SCI_ABSTRACT_LIST_T * list_p +) +{ + return + ( ( (list_p)->elements.back_p ) ? ((list_p)->elements.back_p->object_p) : NULL ); +} + +/** + * This method will return FALSE if the list is not empty. + */ +BOOL sci_abstract_list_is_empty( + SCI_ABSTRACT_LIST_T * list_p +) +{ + return ( (list_p)->elements.front_p == NULL ); +} + + +/** + * This method will return the number of elements queued in the list. + */ +U32 sci_abstract_list_size( + SCI_ABSTRACT_LIST_T * list_p +) +{ + return ( (list_p)->elements.size ); +} + + +/** + * This method simply returns the next list element in the list. + */ +SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_next( + SCI_ABSTRACT_ELEMENT_T * alElement_p +) +{ + return ( (alElement_p)->next_p ); +} + + +#if defined(SCI_LOGGING) +/** + * This method simply prints the contents of the list. + */ +void sci_abstract_list_print( + SCI_ABSTRACT_LIST_T * list_p +) +{ + SCI_ABSTRACT_ELEMENT_T * alElement_p = list_p->elements.front_p; + + while (alElement_p != NULL) + { +#ifdef UNIT_TEST_DEBUG + /* Check to see if we found the object for which we are searching. */ + printf("ITEM next_p 0x%x prev_p 0x%x obj_p 0x%x, 0x%x\n", + alElement_p->next_p, + alElement_p->previous_p, + (U32*) (alElement_p->object_p)); +#endif + alElement_p = alElement_p->next_p; + } +} +#endif // defined(SCI_LOGGING) + + +/** + * This method will simply search the supplied list for the desired object. + * It will return a pointer to the object, if it is found. Otherwise + * it will return NULL. + */ +void * sci_abstract_list_find( + SCI_ABSTRACT_LIST_T * list_p, + void * obj_p +) +{ + return + sci_abstract_list_get_object(private_find(&(list_p)->elements, (obj_p))); +} + + +/** + * This method will simply remove the element at the back (tail) of the list. + * It will return a pointer to the object that was removed or NULL if not + * found. + */ +void * sci_abstract_list_popback( + SCI_ABSTRACT_LIST_T * list_p +) +{ + SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; + SCI_ABSTRACT_ELEMENT_T * alElement_p = elem_list->back_p; + void * obj_p = NULL; + + if (alElement_p != NULL) + { + obj_p = alElement_p->object_p; + if (elem_list->back_p == elem_list->front_p) + { + elem_list->back_p = elem_list->front_p = NULL; + } + else + { + elem_list->back_p = elem_list->back_p->previous_p; + elem_list->back_p->next_p = NULL; + } + + elem_list->size--; + private_pool_free((list_p)->free_pool, alElement_p); + } + + return obj_p; +} + +/** + * This method simply removes the list element at the head of the list + * and returns the pointer to the object that was removed. + */ +void * sci_abstract_list_popfront( + SCI_ABSTRACT_LIST_T * list_p +) +{ + SCI_ABSTRACT_ELEMENT_T * alElement_p = + private_pop_front(&(list_p)->elements); + void * obj_p = NULL; + + if (alElement_p != NULL) + { + obj_p = alElement_p->object_p; + private_pool_free((list_p)->free_pool, alElement_p); + } + + return obj_p; +} + + + +/** + * This method will erase (remove) all instances of the supplied object from + * anywhere in the list. + */ +void sci_abstract_list_erase( + SCI_ABSTRACT_LIST_T * list_p, + void * obj_p +) +{ + SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; + SCI_ABSTRACT_ELEMENT_T * alElement_p; + + while ((alElement_p = private_find(elem_list, (obj_p))) != NULL) + { + if (alElement_p == elem_list->front_p) + { + sci_abstract_list_popfront(list_p); + } + else if (alElement_p == elem_list->back_p) + { + sci_abstract_list_popback(list_p); + } + else + { + alElement_p->previous_p->next_p = alElement_p->next_p; + alElement_p->next_p->previous_p = alElement_p->previous_p; + elem_list->size--; + private_pool_free((list_p)->free_pool, alElement_p); + } + } + return; +} + +/** + * This method simply adds a LIST_ELEMENT for the supplied object to the back + * (tail) of the supplied list. + */ +void sci_abstract_list_pushback( + SCI_ABSTRACT_LIST_T * list_p, + void * obj_p +) +{ + SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; + SCI_ABSTRACT_ELEMENT_T * alElement_p + = private_pool_allocate((list_p)->free_pool); +// assert(alElement_p != NULL); + + alElement_p->object_p = (obj_p); + + if (elem_list->front_p == NULL) + { + elem_list->front_p = elem_list->back_p = alElement_p; + } + else + { + elem_list->back_p->next_p = alElement_p; + alElement_p->previous_p = elem_list->back_p; + elem_list->back_p = alElement_p; + } + + elem_list->size++; +} + + + +/** + * This method simply adds a LIST_ELEMENT for the supplied object to the front + * (head) of the supplied list. + */ +void sci_abstract_list_pushfront( + SCI_ABSTRACT_LIST_T * list_p, + void * obj_p +) +{ + SCI_ABSTRACT_ELEMENT_T * alElement_p = + private_pool_allocate((list_p)->free_pool); + alElement_p->object_p = (obj_p); + private_push_front(&(list_p)->elements, alElement_p); +} + + +/** + * This method will add the objToAdd_p object to the list before the obj_p. + * + */ +void sci_abstract_list_insert( + SCI_ABSTRACT_LIST_T * list_p, + void * obj_p, + void * objToAdd_p +) +{ + SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; + + SCI_ABSTRACT_ELEMENT_T * obj_element = private_find(elem_list, obj_p); + + SCI_ABSTRACT_ELEMENT_T * objToAdd_element = + private_pool_allocate((list_p)->free_pool); + + objToAdd_element->object_p = objToAdd_p; + + ASSERT(obj_element != NULL); + ASSERT(objToAdd_element != NULL); + + if (obj_element == elem_list->front_p) + { + objToAdd_element->object_p = (objToAdd_p); + private_push_front(&(list_p)->elements, objToAdd_element); + } + else + { + obj_element->previous_p->next_p = objToAdd_element; + objToAdd_element->previous_p = obj_element->previous_p; + + obj_element->previous_p = objToAdd_element; + objToAdd_element->next_p = obj_element; + + elem_list->size++; + } +} + +/** + * This method simply frees all the items from the list. + */ +void sci_abstract_list_clear( + SCI_ABSTRACT_LIST_T * list_p +) +{ + while ((list_p)->elements.size > 0) + sci_abstract_list_popfront((list_p)); +} + +/** + * This method simply returns the object being pointed to by the list element + * (The item being listed). + */ +void * sci_abstract_list_get_object( + SCI_ABSTRACT_ELEMENT_T * alElement_p +) +{ + void * obj_p = NULL; + if ((alElement_p) != NULL) + obj_p = (alElement_p)->object_p; + + return obj_p; +} + + +/** + * This method is simply a wrapper to provide the number of elements in + * the free list. + */ +U32 sci_abstract_list_freeList_size( + SCI_ABSTRACT_LIST_T * freeList +) +{ + return (sci_abstract_list_size(freeList)); +} + +//****************************************************************************** +//* +//* P R I V A T E M E T H O D S +//* +//****************************************************************************** + +/** + * This method simply performs the common portion of pushing a list element + * onto a list. + * + * WARNING: This is a private helper method that should not be called directly + * by any users. + */ +void private_push_front( + SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p, + SCI_ABSTRACT_ELEMENT_T * alElement_p +) +{ + if ((privateList_p)->front_p == NULL) + { + (privateList_p)->front_p = (privateList_p)->back_p = (alElement_p); + (alElement_p)->next_p = (alElement_p)->previous_p = NULL; + } + else + { + (alElement_p)->next_p = (privateList_p)->front_p; + (alElement_p)->previous_p = NULL; + (privateList_p)->front_p->previous_p = (alElement_p); + (privateList_p)->front_p = (alElement_p); + } + + (privateList_p)->size++; +} + +/** + * This method simply performs the common portion of popping a list element + * from a list. + * + * WARNING: This is a private helper method that should not be called directly + * by any users. + */ +SCI_ABSTRACT_ELEMENT_T * private_pop_front( + SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p +) +{ + SCI_ABSTRACT_ELEMENT_T * alElement_p = (privateList_p)->front_p; + + if (alElement_p != NULL) + { + if ((privateList_p)->front_p == (privateList_p)->back_p) + { + (privateList_p)->front_p = (privateList_p)->back_p = NULL; + } + else + { + (privateList_p)->front_p = (privateList_p)->front_p->next_p; + (privateList_p)->front_p->previous_p = NULL; + } + + (privateList_p)->size--; + } + + return alElement_p; +} + +/** + * This method will simply search the supplied list for the desired object. + * It will return a pointer to the abstract_list_element if found, otherwise + * it will return NULL. + */ +SCI_ABSTRACT_ELEMENT_T * private_find( + SCI_ABSTRACT_ELEMENT_LIST_T * list_p, + void * obj_p +) +{ + SCI_ABSTRACT_ELEMENT_T * alElement_p = (list_p)->front_p; + + while (alElement_p != NULL) + { + /* Check to see if we found the object for which we are searching. */ + if (alElement_p->object_p == (void*) (obj_p)) + { + break; + } + + alElement_p = alElement_p->next_p; + } + + return alElement_p; +} + +/** + * This private method will free the supplied list element back to the pool + * of free list elements. + */ +void private_pool_free( + SCI_ABSTRACT_ELEMENT_POOL_T * free_pool, + SCI_ABSTRACT_ELEMENT_T * alElement_p +) +{ + /* Push the list element back to the head to get better locality of */ + /* reference with the cache. */ + private_push_front(&(free_pool)->free_list, (alElement_p)); +} + +/** + * This private method will allocate a list element from the pool of free + * list elements. + */ +SCI_ABSTRACT_ELEMENT_T * private_pool_allocate( + SCI_ABSTRACT_ELEMENT_POOL_T * free_pool +) +{ + SCI_ABSTRACT_ELEMENT_T * alElement_p; + + alElement_p = private_pop_front(&(free_pool)->free_list); + + alElement_p->next_p = NULL; + alElement_p->previous_p = NULL; + alElement_p->object_p = NULL; + + return alElement_p; +} + +#endif // USE_ABSTRACT_LIST_FUNCTIONS |