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.
53 #include <sys/cdefs.h>
54 __FBSDID("$FreeBSD$");
59 * @brief This file contains the implementation of an abstract list class.
60 * This class will allow for the same item to occur multiple times in
61 * the list. It will provide an interface that is similar to the
62 * C++ standard template list interface.
65 //******************************************************************************
69 //******************************************************************************
71 #include <dev/isci/scil/sci_abstract_list.h>
74 //******************************************************************************
76 //* P R I V A T E M E M B E R S
78 //******************************************************************************
80 //******************************************************************************
82 //* P R O T E C T E D M E T H O D S
84 //******************************************************************************
87 * @brief Initialize the abstract list
89 * @pre The supplied free pool should be constructed prior to utilization
90 * of this abstract list. It isn't mandatory for the free pool to be
91 * constructed before invoking this method, but suggested.
93 * @param[in] list This parameter specifies the abstract list to be
95 * @param[in] free_pool This parameter specifies the free pool to be
96 * utilized as the repository of free elements for list usage.
100 void sci_abstract_list_construct(
101 SCI_ABSTRACT_LIST_T * list,
102 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool
105 memset(list, 0, sizeof(SCI_ABSTRACT_LIST_T));
106 list->free_pool = free_pool;
110 * Initialize the abstract list with its free pool
113 * the free pool from which the elements will be extracted
114 * @param[in] list_elements
115 * the array of list elements to be added to the free list
116 * @param[in] element_count
117 * the count of the elements to be added to the free list these should be
118 * the same as the array size of list elements
122 void sci_abstract_element_pool_construct(
123 SCI_ABSTRACT_ELEMENT_POOL_T * pool,
124 SCI_ABSTRACT_ELEMENT_T * list_elements,
130 memset(pool, 0, sizeof(SCI_ABSTRACT_ELEMENT_POOL_T));
131 memset(list_elements, 0, sizeof(SCI_ABSTRACT_ELEMENT_T) * element_count);
133 pool->elements = list_elements;
134 pool->max_elements = element_count;
136 // Loop through all of the elements in the array and push them onto the
138 for (index = element_count - 1; index >= 0; index--)
140 private_pool_free(pool, &(list_elements[index]));
145 #ifdef USE_ABSTRACT_LIST_FUNCTIONS
147 //******************************************************************************
149 //* P U B L I C M E T H O D S
151 //******************************************************************************
154 * Simply return the front element pointer of the list. This returns an element
155 * element as opposed to what the element is pointing to.
157 SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_front(
158 SCI_ABSTRACT_LIST_T * list_p
161 return (list_p)->elements.front_p;
165 * This method simply returns the object pointed to by the head (front) of
168 void * sci_abstract_list_front(
169 SCI_ABSTRACT_LIST_T * list_p
173 ( ( (list_p)->elements.front_p ) ? ((list_p)->elements.front_p->object_p) : NULL );
177 * This method simply returns the object pointed to by the tail (back) of
180 void * sci_abstract_list_back(
181 SCI_ABSTRACT_LIST_T * list_p
185 ( ( (list_p)->elements.back_p ) ? ((list_p)->elements.back_p->object_p) : NULL );
189 * This method will return FALSE if the list is not empty.
191 BOOL sci_abstract_list_is_empty(
192 SCI_ABSTRACT_LIST_T * list_p
195 return ( (list_p)->elements.front_p == NULL );
200 * This method will return the number of elements queued in the list.
202 U32 sci_abstract_list_size(
203 SCI_ABSTRACT_LIST_T * list_p
206 return ( (list_p)->elements.size );
211 * This method simply returns the next list element in the list.
213 SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_next(
214 SCI_ABSTRACT_ELEMENT_T * alElement_p
217 return ( (alElement_p)->next_p );
221 #if defined(SCI_LOGGING)
223 * This method simply prints the contents of the list.
225 void sci_abstract_list_print(
226 SCI_ABSTRACT_LIST_T * list_p
229 SCI_ABSTRACT_ELEMENT_T * alElement_p = list_p->elements.front_p;
231 while (alElement_p != NULL)
233 #ifdef UNIT_TEST_DEBUG
234 /* Check to see if we found the object for which we are searching. */
235 printf("ITEM next_p 0x%x prev_p 0x%x obj_p 0x%x, 0x%x\n",
237 alElement_p->previous_p,
238 (U32*) (alElement_p->object_p));
240 alElement_p = alElement_p->next_p;
243 #endif // defined(SCI_LOGGING)
247 * This method will simply search the supplied list for the desired object.
248 * It will return a pointer to the object, if it is found. Otherwise
249 * it will return NULL.
251 void * sci_abstract_list_find(
252 SCI_ABSTRACT_LIST_T * list_p,
257 sci_abstract_list_get_object(private_find(&(list_p)->elements, (obj_p)));
262 * This method will simply remove the element at the back (tail) of the list.
263 * It will return a pointer to the object that was removed or NULL if not
266 void * sci_abstract_list_popback(
267 SCI_ABSTRACT_LIST_T * list_p
270 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements;
271 SCI_ABSTRACT_ELEMENT_T * alElement_p = elem_list->back_p;
274 if (alElement_p != NULL)
276 obj_p = alElement_p->object_p;
277 if (elem_list->back_p == elem_list->front_p)
279 elem_list->back_p = elem_list->front_p = NULL;
283 elem_list->back_p = elem_list->back_p->previous_p;
284 elem_list->back_p->next_p = NULL;
288 private_pool_free((list_p)->free_pool, alElement_p);
295 * This method simply removes the list element at the head of the list
296 * and returns the pointer to the object that was removed.
298 void * sci_abstract_list_popfront(
299 SCI_ABSTRACT_LIST_T * list_p
302 SCI_ABSTRACT_ELEMENT_T * alElement_p =
303 private_pop_front(&(list_p)->elements);
306 if (alElement_p != NULL)
308 obj_p = alElement_p->object_p;
309 private_pool_free((list_p)->free_pool, alElement_p);
318 * This method will erase (remove) all instances of the supplied object from
319 * anywhere in the list.
321 void sci_abstract_list_erase(
322 SCI_ABSTRACT_LIST_T * list_p,
326 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements;
327 SCI_ABSTRACT_ELEMENT_T * alElement_p;
329 while ((alElement_p = private_find(elem_list, (obj_p))) != NULL)
331 if (alElement_p == elem_list->front_p)
333 sci_abstract_list_popfront(list_p);
335 else if (alElement_p == elem_list->back_p)
337 sci_abstract_list_popback(list_p);
341 alElement_p->previous_p->next_p = alElement_p->next_p;
342 alElement_p->next_p->previous_p = alElement_p->previous_p;
344 private_pool_free((list_p)->free_pool, alElement_p);
351 * This method simply adds a LIST_ELEMENT for the supplied object to the back
352 * (tail) of the supplied list.
354 void sci_abstract_list_pushback(
355 SCI_ABSTRACT_LIST_T * list_p,
359 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements;
360 SCI_ABSTRACT_ELEMENT_T * alElement_p
361 = private_pool_allocate((list_p)->free_pool);
362 // assert(alElement_p != NULL);
364 alElement_p->object_p = (obj_p);
366 if (elem_list->front_p == NULL)
368 elem_list->front_p = elem_list->back_p = alElement_p;
372 elem_list->back_p->next_p = alElement_p;
373 alElement_p->previous_p = elem_list->back_p;
374 elem_list->back_p = alElement_p;
383 * This method simply adds a LIST_ELEMENT for the supplied object to the front
384 * (head) of the supplied list.
386 void sci_abstract_list_pushfront(
387 SCI_ABSTRACT_LIST_T * list_p,
391 SCI_ABSTRACT_ELEMENT_T * alElement_p =
392 private_pool_allocate((list_p)->free_pool);
393 alElement_p->object_p = (obj_p);
394 private_push_front(&(list_p)->elements, alElement_p);
399 * This method will add the objToAdd_p object to the list before the obj_p.
402 void sci_abstract_list_insert(
403 SCI_ABSTRACT_LIST_T * list_p,
408 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements;
410 SCI_ABSTRACT_ELEMENT_T * obj_element = private_find(elem_list, obj_p);
412 SCI_ABSTRACT_ELEMENT_T * objToAdd_element =
413 private_pool_allocate((list_p)->free_pool);
415 objToAdd_element->object_p = objToAdd_p;
417 ASSERT(obj_element != NULL);
418 ASSERT(objToAdd_element != NULL);
420 if (obj_element == elem_list->front_p)
422 objToAdd_element->object_p = (objToAdd_p);
423 private_push_front(&(list_p)->elements, objToAdd_element);
427 obj_element->previous_p->next_p = objToAdd_element;
428 objToAdd_element->previous_p = obj_element->previous_p;
430 obj_element->previous_p = objToAdd_element;
431 objToAdd_element->next_p = obj_element;
438 * This method simply frees all the items from the list.
440 void sci_abstract_list_clear(
441 SCI_ABSTRACT_LIST_T * list_p
444 while ((list_p)->elements.size > 0)
445 sci_abstract_list_popfront((list_p));
449 * This method simply returns the object being pointed to by the list element
450 * (The item being listed).
452 void * sci_abstract_list_get_object(
453 SCI_ABSTRACT_ELEMENT_T * alElement_p
457 if ((alElement_p) != NULL)
458 obj_p = (alElement_p)->object_p;
465 * This method is simply a wrapper to provide the number of elements in
468 U32 sci_abstract_list_freeList_size(
469 SCI_ABSTRACT_LIST_T * freeList
472 return (sci_abstract_list_size(freeList));
475 //******************************************************************************
477 //* P R I V A T E M E T H O D S
479 //******************************************************************************
482 * This method simply performs the common portion of pushing a list element
485 * WARNING: This is a private helper method that should not be called directly
488 void private_push_front(
489 SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p,
490 SCI_ABSTRACT_ELEMENT_T * alElement_p
493 if ((privateList_p)->front_p == NULL)
495 (privateList_p)->front_p = (privateList_p)->back_p = (alElement_p);
496 (alElement_p)->next_p = (alElement_p)->previous_p = NULL;
500 (alElement_p)->next_p = (privateList_p)->front_p;
501 (alElement_p)->previous_p = NULL;
502 (privateList_p)->front_p->previous_p = (alElement_p);
503 (privateList_p)->front_p = (alElement_p);
506 (privateList_p)->size++;
510 * This method simply performs the common portion of popping a list element
513 * WARNING: This is a private helper method that should not be called directly
516 SCI_ABSTRACT_ELEMENT_T * private_pop_front(
517 SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p
520 SCI_ABSTRACT_ELEMENT_T * alElement_p = (privateList_p)->front_p;
522 if (alElement_p != NULL)
524 if ((privateList_p)->front_p == (privateList_p)->back_p)
526 (privateList_p)->front_p = (privateList_p)->back_p = NULL;
530 (privateList_p)->front_p = (privateList_p)->front_p->next_p;
531 (privateList_p)->front_p->previous_p = NULL;
534 (privateList_p)->size--;
541 * This method will simply search the supplied list for the desired object.
542 * It will return a pointer to the abstract_list_element if found, otherwise
543 * it will return NULL.
545 SCI_ABSTRACT_ELEMENT_T * private_find(
546 SCI_ABSTRACT_ELEMENT_LIST_T * list_p,
550 SCI_ABSTRACT_ELEMENT_T * alElement_p = (list_p)->front_p;
552 while (alElement_p != NULL)
554 /* Check to see if we found the object for which we are searching. */
555 if (alElement_p->object_p == (void*) (obj_p))
560 alElement_p = alElement_p->next_p;
567 * This private method will free the supplied list element back to the pool
568 * of free list elements.
570 void private_pool_free(
571 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool,
572 SCI_ABSTRACT_ELEMENT_T * alElement_p
575 /* Push the list element back to the head to get better locality of */
576 /* reference with the cache. */
577 private_push_front(&(free_pool)->free_list, (alElement_p));
581 * This private method will allocate a list element from the pool of free
584 SCI_ABSTRACT_ELEMENT_T * private_pool_allocate(
585 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool
588 SCI_ABSTRACT_ELEMENT_T * alElement_p;
590 alElement_p = private_pop_front(&(free_pool)->free_list);
592 alElement_p->next_p = NULL;
593 alElement_p->previous_p = NULL;
594 alElement_p->object_p = NULL;
599 #endif // USE_ABSTRACT_LIST_FUNCTIONS