summaryrefslogtreecommitdiffstats
path: root/sys/dev/isci/scil/sci_simple_list.h
diff options
context:
space:
mode:
Diffstat (limited to 'sys/dev/isci/scil/sci_simple_list.h')
-rw-r--r--sys/dev/isci/scil/sci_simple_list.h350
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_
OpenPOWER on IntegriCloud