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.
7 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved.
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.
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.
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.
26 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved.
27 * All rights reserved.
29 * Redistribution and use in source and binary forms, with or without
30 * modification, are permitted provided that the following conditions
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
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.
57 * @brief This file contains the interface to the abstract list class.
58 * This class will allow for the same item to occur multiple times in
59 * a list or multiple lists. It will provide an interface that is
60 * similar to the C++ standard template list interface.
62 * - sci_abstract_list_front()
63 * - sci_abstract_list_back()
64 * - sci_abstract_list_is_empty()
65 * - sci_abstract_list_size()
66 * - sci_abstract_list_print()
67 * - sci_abstract_list_find()
68 * - sci_abstract_list_popback()
69 * - sci_abstract_list_popfront()
70 * - sci_abstract_list_erase()
71 * - sci_abstract_list_pushback()
72 * - sci_abstract_list_pushfront()
73 * - sci_abstract_list_get_object()
74 * - sci_abstract_list_get_next()
75 * - sci_abstract_list_insert() UNIMPLEMENTED
76 * - sci_abstract_list_clear()
79 #ifndef _SCI_ABSTRACT_LIST_H_
80 #define _SCI_ABSTRACT_LIST_H_
82 //******************************************************************************
86 //******************************************************************************
88 #include <dev/isci/scil/sci_types.h>
90 //******************************************************************************
94 //******************************************************************************
96 //******************************************************************************
100 //******************************************************************************
103 * @struct SCI_ABSTRACT_ELEMENT
105 * @brief This object represents an element of a abstract list.
106 * NOTE: This structure does not evenly align on a cache line
107 * boundary. If SSP specific code ends up using this list,
108 * then it may be a good idea to force the alignment. Now
109 * it is more important to save the space.
111 typedef struct SCI_ABSTRACT_ELEMENT
114 * This field points to the next item in the abstract_list.
116 struct SCI_ABSTRACT_ELEMENT * next_p;
119 * This field points to the previous item in the abstract_list.
121 struct SCI_ABSTRACT_ELEMENT * previous_p;
124 * This field points to the object the list is managing (i.e. the thing
129 } SCI_ABSTRACT_ELEMENT_T;
132 * @struct SCI_ABSTRACT_ELEMENT_LIST
134 * @brief This object represents an element list object. It can have
135 * elements added and removed from it.
137 typedef struct SCI_ABSTRACT_ELEMENT_LIST
140 * Pointer to the front (head) of the list.
142 SCI_ABSTRACT_ELEMENT_T * front_p;
145 * Pointer to the back (tail) of the list.
147 SCI_ABSTRACT_ELEMENT_T * back_p;
150 * This field depicts the number of elements in this list.
151 * NOTE: It is possible to remove this field and replace it with a
152 * linear walking of the list to determine the size, but since
153 * there aren't many lists in the system we don't utilize much
158 } SCI_ABSTRACT_ELEMENT_LIST_T;
161 * @struct SCI_ABSTRACT_ELEMENT_POOL
163 * @brief This structure provides the pool of free abstract elements to be
164 * utilized by an SCI_ABSTRACT_LIST.
166 typedef struct SCI_ABSTRACT_ELEMENT_POOL
169 * Pointer to an array of elements to be managed by this pool. This
170 * array acts as the memory store for the elements in the free pool or
171 * allocated out of the pool into an SCI_ABSTRACT_LIST.
173 SCI_ABSTRACT_ELEMENT_T * elements;
176 * This field contains the maximum number of free elements for the pool.
177 * It is set at creation of the pool and should not be changed afterward.
182 * Pointer to the list of free elements that can be allocated from
185 struct SCI_ABSTRACT_ELEMENT_LIST free_list;
187 } SCI_ABSTRACT_ELEMENT_POOL_T;
190 * @struct SCI_ABSTRACT_LIST
192 * @brief This object provides the ability to queue any type of object or
193 * even the same object multiple times. The object must be provided
194 * an element pool from which to draw free elements.
196 typedef struct SCI_ABSTRACT_LIST
199 * This represents the elements currently managed by the list.
201 SCI_ABSTRACT_ELEMENT_LIST_T elements;
204 * This field contains elements that are currently available for
205 * allocation into the list of elements;
207 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool;
209 } SCI_ABSTRACT_LIST_T;
211 //******************************************************************************
213 //* P R O T E C T E D M E T H O D S
215 //******************************************************************************
217 void sci_abstract_element_pool_construct(
218 SCI_ABSTRACT_ELEMENT_POOL_T * pool,
219 SCI_ABSTRACT_ELEMENT_T * list_elements,
223 void sci_abstract_list_construct(
224 SCI_ABSTRACT_LIST_T * list,
225 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool
230 #ifdef USE_ABSTRACT_LIST_FUNCTIONS
231 //******************************************************************************
233 //* P U B L I C M E T H O D S
235 //******************************************************************************
238 * Simply return the front element pointer of the list. This returns an element
239 * element as opposed to what the element is pointing to.
241 SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_front(
242 SCI_ABSTRACT_LIST_T * list_p
247 * This method simply returns the object pointed to by the head (front) of
250 void * sci_abstract_list_front(
251 SCI_ABSTRACT_LIST_T * list_p
256 * This method simply returns the object pointed to by the tail (back) of
259 void * sci_abstract_list_back(
260 SCI_ABSTRACT_LIST_T * list_p
265 * This method will return FALSE if the list is not empty.
267 BOOL sci_abstract_list_is_empty(
268 SCI_ABSTRACT_LIST_T * list_p
273 * This method will return the number of elements queued in the list.
275 U32 sci_abstract_list_size(
276 SCI_ABSTRACT_LIST_T * list_p
281 * This method simply returns the next list element in the list.
283 SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_next(
284 SCI_ABSTRACT_ELEMENT_T * alElement_p
289 * This method simply prints the contents of the list.
291 void sci_abstract_list_print(
292 SCI_ABSTRACT_LIST_T * list_p
297 * This method will simply search the supplied list for the desired object.
298 * It will return a pointer to the object, if it is found. Otherwise
299 * it will return NULL.
301 void * sci_abstract_list_find(
302 SCI_ABSTRACT_LIST_T * list_p,
308 * This method will simply remove the element at the back (tail) of the list.
309 * It will return a pointer to the object that was removed or NULL if not
312 void * sci_abstract_list_popback(
313 SCI_ABSTRACT_LIST_T * list_p
318 * This method simply removes the list element at the head of the list
319 * and returns the pointer to the object that was removed.
321 void * sci_abstract_list_popfront(
322 SCI_ABSTRACT_LIST_T * list_p
328 * This method will erase (remove) all instances of the supplied object from
329 * anywhere in the list.
331 void sci_abstract_list_erase(
332 SCI_ABSTRACT_LIST_T * list_p,
338 * This method simply adds a LIST_ELEMENT for the supplied object to the back
339 * (tail) of the supplied list.
341 void sci_abstract_list_pushback(
342 SCI_ABSTRACT_LIST_T * list_p,
349 * This method simply adds a LIST_ELEMENT for the supplied object to the front
350 * (head) of the supplied list.
352 void sci_abstract_list_pushfront(
353 SCI_ABSTRACT_LIST_T * list_p,
359 * This method will add the objToAdd_p object to the list before the obj_p.
360 * NOTE: UNIMPLEMENTED
362 void sci_abstract_list_insert(
363 SCI_ABSTRACT_LIST_T * list_p,
370 * This method simply frees all the items from the list.
372 void sci_abstract_list_clear(
373 SCI_ABSTRACT_LIST_T * list_p
378 * This method simply returns the object being pointed to by the list element
379 * (The item being listed).
381 void * sci_abstract_list_get_object(
382 SCI_ABSTRACT_ELEMENT_T * alElement_p
387 * This method is simply a wrapper to provide the number of elements in
390 U32 sci_abstract_list_freeList_size(
391 SCI_ABSTRACT_LIST_T * freeList
395 //******************************************************************************
397 //* P R I V A T E M E T H O D S
399 //******************************************************************************
402 * This method simply performs the common portion of pushing a list element
405 * WARNING: This is a private helper method that should not be called directly
408 void private_push_front(
409 SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p,
410 SCI_ABSTRACT_ELEMENT_T * alElement_p
415 * This method simply performs the common portion of popping a list element
418 * WARNING: This is a private helper method that should not be called directly
421 SCI_ABSTRACT_ELEMENT_T * private_pop_front(
422 SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p
427 * This method will simply search the supplied list for the desired object.
428 * It will return a pointer to the abstract_list_element if found, otherwise
429 * it will return NULL.
431 SCI_ABSTRACT_ELEMENT_T * private_find(
432 SCI_ABSTRACT_ELEMENT_LIST_T * list_p,
438 * This private method will free the supplied list element back to the pool
439 * of free list elements.
441 void private_pool_free(
442 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool,
443 SCI_ABSTRACT_ELEMENT_T * alElement_p
448 * This private method will allocate a list element from the pool of free
451 SCI_ABSTRACT_ELEMENT_T * private_pool_allocate(
452 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool
458 //******************************************************************************
460 //* P U B L I C M E T H O D S
462 //******************************************************************************
465 * Simply return the front element pointer of the list. This returns an element
466 * element as opposed to what the element is pointing to.
468 #define sci_abstract_list_get_front( \
471 ((list_p)->elements.front_p)
474 * This method simply returns the object pointed to by the head (front) of
477 #define sci_abstract_list_front( \
480 ( ( (list_p)->elements.front_p ) ? ((list_p)->elements.front_p->object_p) : NULL )
483 * This method simply returns the object pointed to by the tail (back) of
486 #define sci_abstract_list_back( \
489 ( ( (list_p)->elements.back_p ) ? ((list_p)->elements.back_p->object_p) : NULL )
492 * This method will return FALSE if the list is not empty.
494 #define sci_abstract_list_is_empty( \
497 ( (list_p)->elements.front_p == NULL )
500 * This method will return the number of elements queued in the list.
502 #define sci_abstract_list_size( \
505 ( (list_p)->elements.size )
508 * This method simply returns the next list element in the list.
510 #define sci_abstract_list_get_next( \
513 ( (alElement_p)->next_p )
516 * This method simply prints the contents of the list.
518 #define sci_abstract_list_print( \
522 SCI_ABSTRACT_ELEMENT_T * alElement_p = list_p->elements.front_p; \
524 while (alElement_p != NULL) \
526 /* Check to see if we found the object for which we are searching. */ \
527 printf("ITEM next_p 0x%x prev_p 0x%x obj_p 0x%x, 0x%x\n", \
528 alElement_p->next_p, \
529 alElement_p->previous_p, \
530 (U32*) (alElement_p->object_p)); \
532 alElement_p = alElement_p->next_p; \
537 * This method will simply search the supplied list for the desired object.
538 * It will return a pointer to the object, if it is found. Otherwise
539 * it will return NULL.
541 #define sci_abstract_list_find( \
546 sci_abstract_list_get_object(private_find(&(list_p)->elements, (obj_p))); \
550 * This method will simply remove the element at the back (tail) of the list.
551 * It will return a pointer to the object that was removed or NULL if not
554 #define sci_abstract_list_popback( \
558 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; \
559 SCI_ABSTRACT_ELEMENT_T * alElement_p = elem_list->back_p; \
560 void * obj_p = NULL; \
562 if (alElement_p != NULL) \
564 obj_p = alElement_p->object_p; \
565 if (elem_list->back_p == elem_list->front_p) \
567 elem_list->back_p = elem_list->front_p = NULL; \
571 elem_list->back_p = elem_list->back_p->previous_p; \
572 elem_list->back_p->next_p = NULL; \
576 private_pool_free((list_p)->free_pool, alElement_p); \
583 * This method simply removes the list element at the head of the list
584 * and returns the pointer to the object that was removed.
586 #define sci_abstract_list_popfront( \
590 SCI_ABSTRACT_ELEMENT_T * alElement_p = \
591 private_pop_front(&(list_p)->elements); \
592 void * obj_p = NULL; \
594 if (alElement_p != NULL) \
596 obj_p = alElement_p->object_p; \
597 private_pool_free((list_p)->free_pool, alElement_p); \
604 * This method will erase (remove) all instances of the supplied object from
605 * anywhere in the list.
607 #define sci_abstract_list_erase( \
612 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; \
613 SCI_ABSTRACT_ELEMENT_T * alElement_p; \
615 while ((alElement_p = private_find(elem_list, (obj_p))) != NULL) \
617 if (alElement_p == elem_list->front_p) \
619 sci_abstract_list_popfront(list_p); \
621 else if (alElement_p == elem_list->back_p) \
623 sci_abstract_list_popback(list_p); \
627 alElement_p->previous_p->next_p = alElement_p->next_p; \
628 alElement_p->next_p->previous_p = alElement_p->previous_p; \
630 private_pool_free((list_p)->free_pool, alElement_p); \
636 * This method simply adds a LIST_ELEMENT for the supplied object to the back
637 * (tail) of the supplied list.
639 #define sci_abstract_list_pushback( \
644 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; \
645 SCI_ABSTRACT_ELEMENT_T * alElement_p \
646 = private_pool_allocate((list_p)->free_pool); \
647 assert(alElement_p != NULL); \
649 alElement_p->object_p = (obj_p); \
651 if (elem_list->front_p == NULL) \
653 elem_list->front_p = elem_list->back_p = alElement_p; \
657 elem_list->back_p->next_p = alElement_p; \
658 alElement_p->previous_p = elem_list->back_p; \
659 elem_list->back_p = alElement_p; \
666 * This method simply adds a LIST_ELEMENT for the supplied object to the front
667 * (head) of the supplied list.
669 #define sci_abstract_list_pushfront( \
674 SCI_ABSTRACT_ELEMENT_T * alElement_p = \
675 private_pool_allocate((list_p)->free_pool); \
676 alElement_p->object_p = (obj_p); \
677 private_push_front(&(list_p)->elements, alElement_p); \
681 * This method will add the objToAdd_p object to the list before the obj_p.
682 * NOTE: UNIMPLEMENTED
684 #define sci_abstract_list_insert( \
690 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; \
692 SCI_ABSTRACT_ELEMENT_T * obj_element = private_find(elem_list, obj_p); \
694 SCI_ABSTRACT_ELEMENT_T * objToAdd_element = \
695 private_pool_allocate((list_p)->free_pool); \
697 objToAdd_element->object_p = objToAdd_p; \
699 ASSERT(obj_element != NULL); \
700 ASSERT(objToAdd_element != NULL); \
702 if (obj_element == elem_list->front_p) \
704 objToAdd_element->object_p = (objToAdd_p); \
705 private_push_front(&(list_p)->elements, objToAdd_element); \
709 obj_element->previous_p->next_p = objToAdd_element; \
710 objToAdd_element->previous_p = obj_element->previous_p; \
712 obj_element->previous_p = objToAdd_element; \
713 objToAdd_element->next_p = obj_element; \
720 * This method simply frees all the items from the list.
722 #define sci_abstract_list_clear( \
726 while ((list_p)->elements.size > 0) \
727 sci_abstract_list_popfront((list_p)); \
731 * This method simply returns the object being pointed to by the list element
732 * (The item being listed).
734 #define sci_abstract_list_get_object( \
738 void * obj_p = NULL; \
739 if ((alElement_p) != NULL) \
740 obj_p = (alElement_p)->object_p; \
746 * This method is simply a wrapper to provide the number of elements in
749 #define sci_abstract_list_freeList_size(freeList) (sci_abstract_list_size(freeList))
751 //******************************************************************************
753 //* P R I V A T E M E T H O D S
755 //******************************************************************************
758 * This method simply performs the common portion of pushing a list element
761 * WARNING: This is a private helper method that should not be called directly
764 #define private_push_front( \
769 if ((privateList_p)->front_p == NULL) \
771 (privateList_p)->front_p = (privateList_p)->back_p = (alElement_p); \
772 (alElement_p)->next_p = (alElement_p)->previous_p = NULL; \
776 (alElement_p)->next_p = (privateList_p)->front_p; \
777 (alElement_p)->previous_p = NULL; \
778 (privateList_p)->front_p->previous_p = (alElement_p); \
779 (privateList_p)->front_p = (alElement_p); \
782 (privateList_p)->size++; \
786 * This method simply performs the common portion of popping a list element
789 * WARNING: This is a private helper method that should not be called directly
792 #define private_pop_front( \
796 SCI_ABSTRACT_ELEMENT_T * alElement_p = (privateList_p)->front_p; \
798 if (alElement_p != NULL) \
800 if ((privateList_p)->front_p == (privateList_p)->back_p) \
802 (privateList_p)->front_p = (privateList_p)->back_p = NULL; \
806 (privateList_p)->front_p = (privateList_p)->front_p->next_p; \
807 (privateList_p)->front_p->previous_p = NULL; \
810 (privateList_p)->size--; \
817 * This method will simply search the supplied list for the desired object.
818 * It will return a pointer to the abstract_list_element if found, otherwise
819 * it will return NULL.
821 #define private_find( \
826 SCI_ABSTRACT_ELEMENT_T * alElement_p = (list_p)->front_p; \
828 while (alElement_p != NULL) \
830 /* Check to see if we found the object for which we are searching. */ \
831 if (alElement_p->object_p == (void*) (obj_p)) \
836 alElement_p = alElement_p->next_p; \
843 * This private method will free the supplied list element back to the pool
844 * of free list elements.
846 #define private_pool_free( \
851 /* Push the list element back to the head to get better locality of */ \
852 /* reference with the cache. */ \
853 private_push_front(&(free_pool)->free_list, (alElement_p)); \
857 * This private method will allocate a list element from the pool of free
860 #define private_pool_allocate(free_pool) \
862 SCI_ABSTRACT_ELEMENT_T * alElement_p; \
864 alElement_p = private_pop_front(&(free_pool)->free_list); \
866 memset(alElement_p, 0, sizeof(SCI_ABSTRACT_ELEMENT_T)); \
871 #endif // _ABSTRACT_LIST_H_