2 * SPDX-License-Identifier: BSD-2-Clause OR GPL-2.0
4 * This file is provided under a dual BSD/GPLv2 license. When using or
5 * redistributing this file, you may do so under either license.
9 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved.
11 * This program is free software; you can redistribute it and/or modify
12 * it under the terms of version 2 of the GNU General Public License as
13 * published by the Free Software Foundation.
15 * This program is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * General Public License for more details.
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software
22 * Foundation, Inc., 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
23 * The full GNU General Public License is included in this distribution
24 * in the file called LICENSE.GPL.
28 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved.
29 * All rights reserved.
31 * Redistribution and use in source and binary forms, with or without
32 * modification, are permitted provided that the following conditions
35 * * Redistributions of source code must retain the above copyright
36 * notice, this list of conditions and the following disclaimer.
37 * * Redistributions in binary form must reproduce the above copyright
38 * notice, this list of conditions and the following disclaimer in
39 * the documentation and/or other materials provided with the
42 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
43 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
44 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
45 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
46 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
47 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
48 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
49 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
50 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
51 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
52 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
59 * @brief This file contains the interface to the abstract list class.
60 * This class will allow for the same item to occur multiple times in
61 * a list or multiple lists. It will provide an interface that is
62 * similar to the C++ standard template list interface.
64 * - sci_abstract_list_front()
65 * - sci_abstract_list_back()
66 * - sci_abstract_list_is_empty()
67 * - sci_abstract_list_size()
68 * - sci_abstract_list_print()
69 * - sci_abstract_list_find()
70 * - sci_abstract_list_popback()
71 * - sci_abstract_list_popfront()
72 * - sci_abstract_list_erase()
73 * - sci_abstract_list_pushback()
74 * - sci_abstract_list_pushfront()
75 * - sci_abstract_list_get_object()
76 * - sci_abstract_list_get_next()
77 * - sci_abstract_list_insert() UNIMPLEMENTED
78 * - sci_abstract_list_clear()
81 #ifndef _SCI_ABSTRACT_LIST_H_
82 #define _SCI_ABSTRACT_LIST_H_
84 //******************************************************************************
88 //******************************************************************************
90 #include <dev/isci/scil/sci_types.h>
92 //******************************************************************************
96 //******************************************************************************
98 //******************************************************************************
102 //******************************************************************************
105 * @struct SCI_ABSTRACT_ELEMENT
107 * @brief This object represents an element of a abstract list.
108 * NOTE: This structure does not evenly align on a cache line
109 * boundary. If SSP specific code ends up using this list,
110 * then it may be a good idea to force the alignment. Now
111 * it is more important to save the space.
113 typedef struct SCI_ABSTRACT_ELEMENT
116 * This field points to the next item in the abstract_list.
118 struct SCI_ABSTRACT_ELEMENT * next_p;
121 * This field points to the previous item in the abstract_list.
123 struct SCI_ABSTRACT_ELEMENT * previous_p;
126 * This field points to the object the list is managing (i.e. the thing
131 } SCI_ABSTRACT_ELEMENT_T;
134 * @struct SCI_ABSTRACT_ELEMENT_LIST
136 * @brief This object represents an element list object. It can have
137 * elements added and removed from it.
139 typedef struct SCI_ABSTRACT_ELEMENT_LIST
142 * Pointer to the front (head) of the list.
144 SCI_ABSTRACT_ELEMENT_T * front_p;
147 * Pointer to the back (tail) of the list.
149 SCI_ABSTRACT_ELEMENT_T * back_p;
152 * This field depicts the number of elements in this list.
153 * NOTE: It is possible to remove this field and replace it with a
154 * linear walking of the list to determine the size, but since
155 * there aren't many lists in the system we don't utilize much
160 } SCI_ABSTRACT_ELEMENT_LIST_T;
163 * @struct SCI_ABSTRACT_ELEMENT_POOL
165 * @brief This structure provides the pool of free abstract elements to be
166 * utilized by an SCI_ABSTRACT_LIST.
168 typedef struct SCI_ABSTRACT_ELEMENT_POOL
171 * Pointer to an array of elements to be managed by this pool. This
172 * array acts as the memory store for the elements in the free pool or
173 * allocated out of the pool into an SCI_ABSTRACT_LIST.
175 SCI_ABSTRACT_ELEMENT_T * elements;
178 * This field contains the maximum number of free elements for the pool.
179 * It is set at creation of the pool and should not be changed afterward.
184 * Pointer to the list of free elements that can be allocated from
187 struct SCI_ABSTRACT_ELEMENT_LIST free_list;
189 } SCI_ABSTRACT_ELEMENT_POOL_T;
192 * @struct SCI_ABSTRACT_LIST
194 * @brief This object provides the ability to queue any type of object or
195 * even the same object multiple times. The object must be provided
196 * an element pool from which to draw free elements.
198 typedef struct SCI_ABSTRACT_LIST
201 * This represents the elements currently managed by the list.
203 SCI_ABSTRACT_ELEMENT_LIST_T elements;
206 * This field contains elements that are currently available for
207 * allocation into the list of elements;
209 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool;
211 } SCI_ABSTRACT_LIST_T;
213 //******************************************************************************
215 //* P R O T E C T E D M E T H O D S
217 //******************************************************************************
219 void sci_abstract_element_pool_construct(
220 SCI_ABSTRACT_ELEMENT_POOL_T * pool,
221 SCI_ABSTRACT_ELEMENT_T * list_elements,
225 void sci_abstract_list_construct(
226 SCI_ABSTRACT_LIST_T * list,
227 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool
232 #ifdef USE_ABSTRACT_LIST_FUNCTIONS
233 //******************************************************************************
235 //* P U B L I C M E T H O D S
237 //******************************************************************************
240 * Simply return the front element pointer of the list. This returns an element
241 * element as opposed to what the element is pointing to.
243 SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_front(
244 SCI_ABSTRACT_LIST_T * list_p
249 * This method simply returns the object pointed to by the head (front) of
252 void * sci_abstract_list_front(
253 SCI_ABSTRACT_LIST_T * list_p
258 * This method simply returns the object pointed to by the tail (back) of
261 void * sci_abstract_list_back(
262 SCI_ABSTRACT_LIST_T * list_p
267 * This method will return FALSE if the list is not empty.
269 BOOL sci_abstract_list_is_empty(
270 SCI_ABSTRACT_LIST_T * list_p
275 * This method will return the number of elements queued in the list.
277 U32 sci_abstract_list_size(
278 SCI_ABSTRACT_LIST_T * list_p
283 * This method simply returns the next list element in the list.
285 SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_next(
286 SCI_ABSTRACT_ELEMENT_T * alElement_p
291 * This method simply prints the contents of the list.
293 void sci_abstract_list_print(
294 SCI_ABSTRACT_LIST_T * list_p
299 * This method will simply search the supplied list for the desired object.
300 * It will return a pointer to the object, if it is found. Otherwise
301 * it will return NULL.
303 void * sci_abstract_list_find(
304 SCI_ABSTRACT_LIST_T * list_p,
310 * This method will simply remove the element at the back (tail) of the list.
311 * It will return a pointer to the object that was removed or NULL if not
314 void * sci_abstract_list_popback(
315 SCI_ABSTRACT_LIST_T * list_p
320 * This method simply removes the list element at the head of the list
321 * and returns the pointer to the object that was removed.
323 void * sci_abstract_list_popfront(
324 SCI_ABSTRACT_LIST_T * list_p
330 * This method will erase (remove) all instances of the supplied object from
331 * anywhere in the list.
333 void sci_abstract_list_erase(
334 SCI_ABSTRACT_LIST_T * list_p,
340 * This method simply adds a LIST_ELEMENT for the supplied object to the back
341 * (tail) of the supplied list.
343 void sci_abstract_list_pushback(
344 SCI_ABSTRACT_LIST_T * list_p,
351 * This method simply adds a LIST_ELEMENT for the supplied object to the front
352 * (head) of the supplied list.
354 void sci_abstract_list_pushfront(
355 SCI_ABSTRACT_LIST_T * list_p,
361 * This method will add the objToAdd_p object to the list before the obj_p.
362 * NOTE: UNIMPLEMENTED
364 void sci_abstract_list_insert(
365 SCI_ABSTRACT_LIST_T * list_p,
372 * This method simply frees all the items from the list.
374 void sci_abstract_list_clear(
375 SCI_ABSTRACT_LIST_T * list_p
380 * This method simply returns the object being pointed to by the list element
381 * (The item being listed).
383 void * sci_abstract_list_get_object(
384 SCI_ABSTRACT_ELEMENT_T * alElement_p
389 * This method is simply a wrapper to provide the number of elements in
392 U32 sci_abstract_list_freeList_size(
393 SCI_ABSTRACT_LIST_T * freeList
397 //******************************************************************************
399 //* P R I V A T E M E T H O D S
401 //******************************************************************************
404 * This method simply performs the common portion of pushing a list element
407 * WARNING: This is a private helper method that should not be called directly
410 void private_push_front(
411 SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p,
412 SCI_ABSTRACT_ELEMENT_T * alElement_p
417 * This method simply performs the common portion of popping a list element
420 * WARNING: This is a private helper method that should not be called directly
423 SCI_ABSTRACT_ELEMENT_T * private_pop_front(
424 SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p
429 * This method will simply search the supplied list for the desired object.
430 * It will return a pointer to the abstract_list_element if found, otherwise
431 * it will return NULL.
433 SCI_ABSTRACT_ELEMENT_T * private_find(
434 SCI_ABSTRACT_ELEMENT_LIST_T * list_p,
440 * This private method will free the supplied list element back to the pool
441 * of free list elements.
443 void private_pool_free(
444 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool,
445 SCI_ABSTRACT_ELEMENT_T * alElement_p
450 * This private method will allocate a list element from the pool of free
453 SCI_ABSTRACT_ELEMENT_T * private_pool_allocate(
454 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool
460 //******************************************************************************
462 //* P U B L I C M E T H O D S
464 //******************************************************************************
467 * Simply return the front element pointer of the list. This returns an element
468 * element as opposed to what the element is pointing to.
470 #define sci_abstract_list_get_front( \
473 ((list_p)->elements.front_p)
476 * This method simply returns the object pointed to by the head (front) of
479 #define sci_abstract_list_front( \
482 ( ( (list_p)->elements.front_p ) ? ((list_p)->elements.front_p->object_p) : NULL )
485 * This method simply returns the object pointed to by the tail (back) of
488 #define sci_abstract_list_back( \
491 ( ( (list_p)->elements.back_p ) ? ((list_p)->elements.back_p->object_p) : NULL )
494 * This method will return FALSE if the list is not empty.
496 #define sci_abstract_list_is_empty( \
499 ( (list_p)->elements.front_p == NULL )
502 * This method will return the number of elements queued in the list.
504 #define sci_abstract_list_size( \
507 ( (list_p)->elements.size )
510 * This method simply returns the next list element in the list.
512 #define sci_abstract_list_get_next( \
515 ( (alElement_p)->next_p )
518 * This method simply prints the contents of the list.
520 #define sci_abstract_list_print( \
524 SCI_ABSTRACT_ELEMENT_T * alElement_p = list_p->elements.front_p; \
526 while (alElement_p != NULL) \
528 /* Check to see if we found the object for which we are searching. */ \
529 printf("ITEM next_p 0x%x prev_p 0x%x obj_p 0x%x, 0x%x\n", \
530 alElement_p->next_p, \
531 alElement_p->previous_p, \
532 (U32*) (alElement_p->object_p)); \
534 alElement_p = alElement_p->next_p; \
539 * This method will simply search the supplied list for the desired object.
540 * It will return a pointer to the object, if it is found. Otherwise
541 * it will return NULL.
543 #define sci_abstract_list_find( \
548 sci_abstract_list_get_object(private_find(&(list_p)->elements, (obj_p))); \
552 * This method will simply remove the element at the back (tail) of the list.
553 * It will return a pointer to the object that was removed or NULL if not
556 #define sci_abstract_list_popback( \
560 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; \
561 SCI_ABSTRACT_ELEMENT_T * alElement_p = elem_list->back_p; \
562 void * obj_p = NULL; \
564 if (alElement_p != NULL) \
566 obj_p = alElement_p->object_p; \
567 if (elem_list->back_p == elem_list->front_p) \
569 elem_list->back_p = elem_list->front_p = NULL; \
573 elem_list->back_p = elem_list->back_p->previous_p; \
574 elem_list->back_p->next_p = NULL; \
578 private_pool_free((list_p)->free_pool, alElement_p); \
585 * This method simply removes the list element at the head of the list
586 * and returns the pointer to the object that was removed.
588 #define sci_abstract_list_popfront( \
592 SCI_ABSTRACT_ELEMENT_T * alElement_p = \
593 private_pop_front(&(list_p)->elements); \
594 void * obj_p = NULL; \
596 if (alElement_p != NULL) \
598 obj_p = alElement_p->object_p; \
599 private_pool_free((list_p)->free_pool, alElement_p); \
606 * This method will erase (remove) all instances of the supplied object from
607 * anywhere in the list.
609 #define sci_abstract_list_erase( \
614 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; \
615 SCI_ABSTRACT_ELEMENT_T * alElement_p; \
617 while ((alElement_p = private_find(elem_list, (obj_p))) != NULL) \
619 if (alElement_p == elem_list->front_p) \
621 sci_abstract_list_popfront(list_p); \
623 else if (alElement_p == elem_list->back_p) \
625 sci_abstract_list_popback(list_p); \
629 alElement_p->previous_p->next_p = alElement_p->next_p; \
630 alElement_p->next_p->previous_p = alElement_p->previous_p; \
632 private_pool_free((list_p)->free_pool, alElement_p); \
638 * This method simply adds a LIST_ELEMENT for the supplied object to the back
639 * (tail) of the supplied list.
641 #define sci_abstract_list_pushback( \
646 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; \
647 SCI_ABSTRACT_ELEMENT_T * alElement_p \
648 = private_pool_allocate((list_p)->free_pool); \
649 assert(alElement_p != NULL); \
651 alElement_p->object_p = (obj_p); \
653 if (elem_list->front_p == NULL) \
655 elem_list->front_p = elem_list->back_p = alElement_p; \
659 elem_list->back_p->next_p = alElement_p; \
660 alElement_p->previous_p = elem_list->back_p; \
661 elem_list->back_p = alElement_p; \
668 * This method simply adds a LIST_ELEMENT for the supplied object to the front
669 * (head) of the supplied list.
671 #define sci_abstract_list_pushfront( \
676 SCI_ABSTRACT_ELEMENT_T * alElement_p = \
677 private_pool_allocate((list_p)->free_pool); \
678 alElement_p->object_p = (obj_p); \
679 private_push_front(&(list_p)->elements, alElement_p); \
683 * This method will add the objToAdd_p object to the list before the obj_p.
684 * NOTE: UNIMPLEMENTED
686 #define sci_abstract_list_insert( \
692 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; \
694 SCI_ABSTRACT_ELEMENT_T * obj_element = private_find(elem_list, obj_p); \
696 SCI_ABSTRACT_ELEMENT_T * objToAdd_element = \
697 private_pool_allocate((list_p)->free_pool); \
699 objToAdd_element->object_p = objToAdd_p; \
701 ASSERT(obj_element != NULL); \
702 ASSERT(objToAdd_element != NULL); \
704 if (obj_element == elem_list->front_p) \
706 objToAdd_element->object_p = (objToAdd_p); \
707 private_push_front(&(list_p)->elements, objToAdd_element); \
711 obj_element->previous_p->next_p = objToAdd_element; \
712 objToAdd_element->previous_p = obj_element->previous_p; \
714 obj_element->previous_p = objToAdd_element; \
715 objToAdd_element->next_p = obj_element; \
722 * This method simply frees all the items from the list.
724 #define sci_abstract_list_clear( \
728 while ((list_p)->elements.size > 0) \
729 sci_abstract_list_popfront((list_p)); \
733 * This method simply returns the object being pointed to by the list element
734 * (The item being listed).
736 #define sci_abstract_list_get_object( \
740 void * obj_p = NULL; \
741 if ((alElement_p) != NULL) \
742 obj_p = (alElement_p)->object_p; \
748 * This method is simply a wrapper to provide the number of elements in
751 #define sci_abstract_list_freeList_size(freeList) (sci_abstract_list_size(freeList))
753 //******************************************************************************
755 //* P R I V A T E M E T H O D S
757 //******************************************************************************
760 * This method simply performs the common portion of pushing a list element
763 * WARNING: This is a private helper method that should not be called directly
766 #define private_push_front( \
771 if ((privateList_p)->front_p == NULL) \
773 (privateList_p)->front_p = (privateList_p)->back_p = (alElement_p); \
774 (alElement_p)->next_p = (alElement_p)->previous_p = NULL; \
778 (alElement_p)->next_p = (privateList_p)->front_p; \
779 (alElement_p)->previous_p = NULL; \
780 (privateList_p)->front_p->previous_p = (alElement_p); \
781 (privateList_p)->front_p = (alElement_p); \
784 (privateList_p)->size++; \
788 * This method simply performs the common portion of popping a list element
791 * WARNING: This is a private helper method that should not be called directly
794 #define private_pop_front( \
798 SCI_ABSTRACT_ELEMENT_T * alElement_p = (privateList_p)->front_p; \
800 if (alElement_p != NULL) \
802 if ((privateList_p)->front_p == (privateList_p)->back_p) \
804 (privateList_p)->front_p = (privateList_p)->back_p = NULL; \
808 (privateList_p)->front_p = (privateList_p)->front_p->next_p; \
809 (privateList_p)->front_p->previous_p = NULL; \
812 (privateList_p)->size--; \
819 * This method will simply search the supplied list for the desired object.
820 * It will return a pointer to the abstract_list_element if found, otherwise
821 * it will return NULL.
823 #define private_find( \
828 SCI_ABSTRACT_ELEMENT_T * alElement_p = (list_p)->front_p; \
830 while (alElement_p != NULL) \
832 /* Check to see if we found the object for which we are searching. */ \
833 if (alElement_p->object_p == (void*) (obj_p)) \
838 alElement_p = alElement_p->next_p; \
845 * This private method will free the supplied list element back to the pool
846 * of free list elements.
848 #define private_pool_free( \
853 /* Push the list element back to the head to get better locality of */ \
854 /* reference with the cache. */ \
855 private_push_front(&(free_pool)->free_list, (alElement_p)); \
859 * This private method will allocate a list element from the pool of free
862 #define private_pool_allocate(free_pool) \
864 SCI_ABSTRACT_ELEMENT_T * alElement_p; \
866 alElement_p = private_pop_front(&(free_pool)->free_list); \
868 memset(alElement_p, 0, sizeof(SCI_ABSTRACT_ELEMENT_T)); \
873 #endif // _ABSTRACT_LIST_H_