diff options
Diffstat (limited to 'sys/dev/isci/scil/sci_simple_list.h')
-rw-r--r-- | sys/dev/isci/scil/sci_simple_list.h | 350 |
1 files changed, 350 insertions, 0 deletions
diff --git a/sys/dev/isci/scil/sci_simple_list.h b/sys/dev/isci/scil/sci_simple_list.h new file mode 100644 index 0000000..98d29e1 --- /dev/null +++ b/sys/dev/isci/scil/sci_simple_list.h @@ -0,0 +1,350 @@ +/*- + * 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. + * + * $FreeBSD$ + */ +#ifndef _SCI_SIMPLE_LIST_HEADER_ +#define _SCI_SIMPLE_LIST_HEADER_ + +/** + * @file + * + * @brief This header file contains simple linked list manipulation macros. + * These macros differ from the SCI_FAST_LIST in that deletion of + * an element from the list is O(n). + * The reason for using this implementation over the SCI_FAST_LIST + * is + * 1) space savings as there is only a single link element instead + * of the 2 link elements used in the SCI_FAST_LIST and + * 2) it is possible to detach the entire list from its anchor + * element for processing. + * + * @note Do not use the SCI_SIMPLE_LIST if you need to remove elements from + * random locations within the list use instead the SCI_FAST_LIST. + */ + + +//****************************************************************************** +//* +//* P U B L I C M E T H O D S +//* +//****************************************************************************** + +/** + * Initialize the singely linked list anchor. The other macros require the + * list anchor to be properly initialized. + */ +#define sci_simple_list_init(anchor) \ +{ \ + (anchor)->list_head = NULL; \ + (anchor)->list_tail = NULL; \ + (anchor)->list_count = 0; \ +} + +/** + * Initialze the singely linked list element. The other macros require the + * list element to be properly initialized. + */ +#define sci_simple_list_element_init(list_object, element) \ +{ \ + (element)->next = NULL; \ + (element)->object = (list_object); \ +} + +/** + * See if there are any list elements on this list. + */ +#define sci_simple_list_is_empty(anchor) ((anchor)->list_head == NULL) + +/** + * Return a pointer to the list element at the head of the list. The list + * element is not removed from the list. + */ +#define sci_simple_list_get_head(anchor) ((anchor)->list_head) + +/** + * Retuen a pointer to the lsit element at the tail of the list. The list + * element is not removed from the list. + */ +#define sci_simple_list_get_tail(anchor) ((anchor)->list_tail) + +/** + * Return the count of the number of elements in this list. + */ +#define sci_simple_list_get_count(anchor) ((anchor)->list_count) + +/** + * Return a pointer to the list element following this list element. + * If this is the last element in the list then NULL is returned. + */ +#define sci_simple_list_get_next(element) ((element)->next) + +/** + * Return the object represented by the list element. + */ +#define sci_simple_list_get_object(element) ((element)->object) + + +//****************************************************************************** +//* +//* T Y P E S +//* +//****************************************************************************** + +/** + * @struct + * + * @brief This structure defines the list owner for singely linked list. + */ +typedef struct SCI_SIMPLE_LIST +{ + struct SCI_SIMPLE_LIST_ELEMENT *list_head; + struct SCI_SIMPLE_LIST_ELEMENT *list_tail; + U32 list_count; +} SCI_SIMPLE_LIST_T; + +/** + * @struct SCI_SIMPLE_LIST_ELEMENT + * + * @brief This structure defines what a singely linked list element contains. + */ +typedef struct SCI_SIMPLE_LIST_ELEMENT +{ + struct SCI_SIMPLE_LIST_ELEMENT *next; + void *object; +} SCI_SIMPLE_LIST_ELEMENT_T; + +/** + * This method will insert the list element to the head of the list contained + * by the anchor. + * + * @note Pushing new elements onto a list is more efficient than inserting + * them to the tail of the list though both are O(1) operations. + */ +INLINE +static void sci_simple_list_insert_head( + SCI_SIMPLE_LIST_T * anchor, + SCI_SIMPLE_LIST_ELEMENT_T *element +) +{ + if (anchor->list_tail == NULL) + { + anchor->list_tail = element; + } + + element->next = anchor->list_head; + anchor->list_head = element; + anchor->list_count++; +} + +/** + * This methos will insert the list element to the tail of the list contained + * by the anchor. + * + * @param[in, out] anchor this is the list into which the element is to be + * inserted + * @param[in] element this is the element which to insert into the list. + * + * @note Pushing new elements onto a list is more efficient than inserting + * them to the tail of the list though both are O(1) operations. + */ +INLINE +static void sci_simple_list_insert_tail( + SCI_SIMPLE_LIST_T * anchor, + SCI_SIMPLE_LIST_ELEMENT_T *element +) +{ + if (anchor->list_tail == NULL) + { + anchor->list_head = element; + } + else + { + anchor->list_tail->next = element; + } + + anchor->list_tail = element; + anchor->list_count++; +} + +/** + * This method will remove the list element from the anchor and return the + * object pointed to by that list element. + * + * @param[in, out] anchor this is the list into which the element is to be + * inserted + * + * @return the list element at the head of the list. + */ +INLINE +static void * sci_simple_list_remove_head( + SCI_SIMPLE_LIST_T * anchor +) +{ + void * object = NULL; + + if (anchor->list_head != NULL) + { + object = anchor->list_head->object; + + anchor->list_head = anchor->list_head->next; + + if (anchor->list_head == NULL) + { + anchor->list_tail = NULL; + } + + anchor->list_count--; + } + + return object; +} + +/** + * Move all the list elements from source anchor to the dest anchor. + * The source anchor will have all of its elements removed making it + * an empty list and the dest anchor will contain all of the source + * and dest list elements. + * + * @param[in, out] dest_anchor this is the list into which all elements from + * the source list are to be moved. + * @param[in, out] source_anchor this is the list which is to be moved to the + * destination list. This list will be empty on return. + * + * @return the list element at the head of the list. + * @note If the destination has list elements use the insert at head + * or tail routines instead. + */ +INLINE +static void sci_simple_list_move_list( + SCI_SIMPLE_LIST_T * dest_anchor, + SCI_SIMPLE_LIST_T * source_anchor +) +{ + *dest_anchor = *source_anchor; + + sci_simple_list_init(source_anchor); +} + +/** + * This method will insert the list elements from the source anchor to the + * destination list before all previous elements on the destination list. + * + * @param[in, out] dest_anchor this is the list into which all elements from + * the source list are to be moved. The destination list will + * now contain both sets of list elements. + * @param[in, out] source_anchor this is the list which is to be moved to the + * destination list. This list will be empty on return. + */ +INLINE +static void sci_simple_list_insert_list_at_head( + SCI_SIMPLE_LIST_T * dest_anchor, + SCI_SIMPLE_LIST_T * source_anchor +) +{ + if (!sci_simple_list_is_empty(source_anchor)) + { + if (sci_simple_list_is_empty(dest_anchor)) + { + // Destination is empty just copy the source on over + *dest_anchor = *source_anchor; + } + else + { + source_anchor->list_tail->next = dest_anchor->list_head; + dest_anchor->list_head = source_anchor->list_head; + dest_anchor->list_count += source_anchor->list_count; + } + + // Wipe the source list to make sure the list elements can not be accessed + // from two seperate lists at the same time. + sci_simple_list_init(source_anchor); + } +} + +/** + * This method will insert the list elements from the source anchor to the + * destination anchor after all list elements on the destination anchor. + * + * @param[in, out] dest_anchor this is the list into which all elements from + * the source list are to be moved. The destination list will + * contain both the source and destination list elements. + * @param[in, out] source_anchor this is the list which is to be moved to the + * destination list. This list will be empty on return. + */ +INLINE +static void sci_simple_list_insert_list_at_tail( + SCI_SIMPLE_LIST_T * dest_anchor, + SCI_SIMPLE_LIST_T * source_anchor +) +{ + if (!sci_simple_list_is_empty(source_anchor)) + { + if (sci_simple_list_is_empty(dest_anchor)) + { + // Destination is empty just copy the source on over + *dest_anchor = *source_anchor; + } + else + { + // If the source list is empty the desination list is the result. + dest_anchor->list_tail->next = source_anchor->list_head; + dest_anchor->list_tail = source_anchor->list_tail; + dest_anchor->list_count += source_anchor->list_count; + } + + // Wipe the source list to make sure the list elements can not be accessed + // from two seperate lists at the same time. + sci_simple_list_init(source_anchor); + } +} + +#endif // _SCI_SIMPLE_LIST_HEADER_ |