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.
55 #include <sys/cdefs.h>
56 __FBSDID("$FreeBSD$");
61 * @brief This file contains the implementation of an abstract list class.
62 * This class will allow for the same item to occur multiple times in
63 * the list. It will provide an interface that is similar to the
64 * C++ standard template list interface.
67 //******************************************************************************
71 //******************************************************************************
73 #include <dev/isci/scil/sci_abstract_list.h>
76 //******************************************************************************
78 //* P R I V A T E M E M B E R S
80 //******************************************************************************
82 //******************************************************************************
84 //* P R O T E C T E D M E T H O D S
86 //******************************************************************************
89 * @brief Initialize the abstract list
91 * @pre The supplied free pool should be constructed prior to utilization
92 * of this abstract list. It isn't mandatory for the free pool to be
93 * constructed before invoking this method, but suggested.
95 * @param[in] list This parameter specifies the abstract list to be
97 * @param[in] free_pool This parameter specifies the free pool to be
98 * utilized as the repository of free elements for list usage.
102 void sci_abstract_list_construct(
103 SCI_ABSTRACT_LIST_T * list,
104 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool
107 memset(list, 0, sizeof(SCI_ABSTRACT_LIST_T));
108 list->free_pool = free_pool;
112 * Initialize the abstract list with its free pool
115 * the free pool from which the elements will be extracted
116 * @param[in] list_elements
117 * the array of list elements to be added to the free list
118 * @param[in] element_count
119 * the count of the elements to be added to the free list these should be
120 * the same as the array size of list elements
124 void sci_abstract_element_pool_construct(
125 SCI_ABSTRACT_ELEMENT_POOL_T * pool,
126 SCI_ABSTRACT_ELEMENT_T * list_elements,
132 memset(pool, 0, sizeof(SCI_ABSTRACT_ELEMENT_POOL_T));
133 memset(list_elements, 0, sizeof(SCI_ABSTRACT_ELEMENT_T) * element_count);
135 pool->elements = list_elements;
136 pool->max_elements = element_count;
138 // Loop through all of the elements in the array and push them onto the
140 for (index = element_count - 1; index >= 0; index--)
142 private_pool_free(pool, &(list_elements[index]));
147 #ifdef USE_ABSTRACT_LIST_FUNCTIONS
149 //******************************************************************************
151 //* P U B L I C M E T H O D S
153 //******************************************************************************
156 * Simply return the front element pointer of the list. This returns an element
157 * element as opposed to what the element is pointing to.
159 SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_front(
160 SCI_ABSTRACT_LIST_T * list_p
163 return (list_p)->elements.front_p;
167 * This method simply returns the object pointed to by the head (front) of
170 void * sci_abstract_list_front(
171 SCI_ABSTRACT_LIST_T * list_p
175 ( ( (list_p)->elements.front_p ) ? ((list_p)->elements.front_p->object_p) : NULL );
179 * This method simply returns the object pointed to by the tail (back) of
182 void * sci_abstract_list_back(
183 SCI_ABSTRACT_LIST_T * list_p
187 ( ( (list_p)->elements.back_p ) ? ((list_p)->elements.back_p->object_p) : NULL );
191 * This method will return FALSE if the list is not empty.
193 BOOL sci_abstract_list_is_empty(
194 SCI_ABSTRACT_LIST_T * list_p
197 return ( (list_p)->elements.front_p == NULL );
202 * This method will return the number of elements queued in the list.
204 U32 sci_abstract_list_size(
205 SCI_ABSTRACT_LIST_T * list_p
208 return ( (list_p)->elements.size );
213 * This method simply returns the next list element in the list.
215 SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_next(
216 SCI_ABSTRACT_ELEMENT_T * alElement_p
219 return ( (alElement_p)->next_p );
223 #if defined(SCI_LOGGING)
225 * This method simply prints the contents of the list.
227 void sci_abstract_list_print(
228 SCI_ABSTRACT_LIST_T * list_p
231 SCI_ABSTRACT_ELEMENT_T * alElement_p = list_p->elements.front_p;
233 while (alElement_p != NULL)
235 #ifdef UNIT_TEST_DEBUG
236 /* Check to see if we found the object for which we are searching. */
237 printf("ITEM next_p 0x%x prev_p 0x%x obj_p 0x%x, 0x%x\n",
239 alElement_p->previous_p,
240 (U32*) (alElement_p->object_p));
242 alElement_p = alElement_p->next_p;
245 #endif // defined(SCI_LOGGING)
249 * This method will simply search the supplied list for the desired object.
250 * It will return a pointer to the object, if it is found. Otherwise
251 * it will return NULL.
253 void * sci_abstract_list_find(
254 SCI_ABSTRACT_LIST_T * list_p,
259 sci_abstract_list_get_object(private_find(&(list_p)->elements, (obj_p)));
264 * This method will simply remove the element at the back (tail) of the list.
265 * It will return a pointer to the object that was removed or NULL if not
268 void * sci_abstract_list_popback(
269 SCI_ABSTRACT_LIST_T * list_p
272 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements;
273 SCI_ABSTRACT_ELEMENT_T * alElement_p = elem_list->back_p;
276 if (alElement_p != NULL)
278 obj_p = alElement_p->object_p;
279 if (elem_list->back_p == elem_list->front_p)
281 elem_list->back_p = elem_list->front_p = NULL;
285 elem_list->back_p = elem_list->back_p->previous_p;
286 elem_list->back_p->next_p = NULL;
290 private_pool_free((list_p)->free_pool, alElement_p);
297 * This method simply removes the list element at the head of the list
298 * and returns the pointer to the object that was removed.
300 void * sci_abstract_list_popfront(
301 SCI_ABSTRACT_LIST_T * list_p
304 SCI_ABSTRACT_ELEMENT_T * alElement_p =
305 private_pop_front(&(list_p)->elements);
308 if (alElement_p != NULL)
310 obj_p = alElement_p->object_p;
311 private_pool_free((list_p)->free_pool, alElement_p);
320 * This method will erase (remove) all instances of the supplied object from
321 * anywhere in the list.
323 void sci_abstract_list_erase(
324 SCI_ABSTRACT_LIST_T * list_p,
328 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements;
329 SCI_ABSTRACT_ELEMENT_T * alElement_p;
331 while ((alElement_p = private_find(elem_list, (obj_p))) != NULL)
333 if (alElement_p == elem_list->front_p)
335 sci_abstract_list_popfront(list_p);
337 else if (alElement_p == elem_list->back_p)
339 sci_abstract_list_popback(list_p);
343 alElement_p->previous_p->next_p = alElement_p->next_p;
344 alElement_p->next_p->previous_p = alElement_p->previous_p;
346 private_pool_free((list_p)->free_pool, alElement_p);
353 * This method simply adds a LIST_ELEMENT for the supplied object to the back
354 * (tail) of the supplied list.
356 void sci_abstract_list_pushback(
357 SCI_ABSTRACT_LIST_T * list_p,
361 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements;
362 SCI_ABSTRACT_ELEMENT_T * alElement_p
363 = private_pool_allocate((list_p)->free_pool);
364 // assert(alElement_p != NULL);
366 alElement_p->object_p = (obj_p);
368 if (elem_list->front_p == NULL)
370 elem_list->front_p = elem_list->back_p = alElement_p;
374 elem_list->back_p->next_p = alElement_p;
375 alElement_p->previous_p = elem_list->back_p;
376 elem_list->back_p = alElement_p;
385 * This method simply adds a LIST_ELEMENT for the supplied object to the front
386 * (head) of the supplied list.
388 void sci_abstract_list_pushfront(
389 SCI_ABSTRACT_LIST_T * list_p,
393 SCI_ABSTRACT_ELEMENT_T * alElement_p =
394 private_pool_allocate((list_p)->free_pool);
395 alElement_p->object_p = (obj_p);
396 private_push_front(&(list_p)->elements, alElement_p);
401 * This method will add the objToAdd_p object to the list before the obj_p.
404 void sci_abstract_list_insert(
405 SCI_ABSTRACT_LIST_T * list_p,
410 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements;
412 SCI_ABSTRACT_ELEMENT_T * obj_element = private_find(elem_list, obj_p);
414 SCI_ABSTRACT_ELEMENT_T * objToAdd_element =
415 private_pool_allocate((list_p)->free_pool);
417 objToAdd_element->object_p = objToAdd_p;
419 ASSERT(obj_element != NULL);
420 ASSERT(objToAdd_element != NULL);
422 if (obj_element == elem_list->front_p)
424 objToAdd_element->object_p = (objToAdd_p);
425 private_push_front(&(list_p)->elements, objToAdd_element);
429 obj_element->previous_p->next_p = objToAdd_element;
430 objToAdd_element->previous_p = obj_element->previous_p;
432 obj_element->previous_p = objToAdd_element;
433 objToAdd_element->next_p = obj_element;
440 * This method simply frees all the items from the list.
442 void sci_abstract_list_clear(
443 SCI_ABSTRACT_LIST_T * list_p
446 while ((list_p)->elements.size > 0)
447 sci_abstract_list_popfront((list_p));
451 * This method simply returns the object being pointed to by the list element
452 * (The item being listed).
454 void * sci_abstract_list_get_object(
455 SCI_ABSTRACT_ELEMENT_T * alElement_p
459 if ((alElement_p) != NULL)
460 obj_p = (alElement_p)->object_p;
467 * This method is simply a wrapper to provide the number of elements in
470 U32 sci_abstract_list_freeList_size(
471 SCI_ABSTRACT_LIST_T * freeList
474 return (sci_abstract_list_size(freeList));
477 //******************************************************************************
479 //* P R I V A T E M E T H O D S
481 //******************************************************************************
484 * This method simply performs the common portion of pushing a list element
487 * WARNING: This is a private helper method that should not be called directly
490 void private_push_front(
491 SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p,
492 SCI_ABSTRACT_ELEMENT_T * alElement_p
495 if ((privateList_p)->front_p == NULL)
497 (privateList_p)->front_p = (privateList_p)->back_p = (alElement_p);
498 (alElement_p)->next_p = (alElement_p)->previous_p = NULL;
502 (alElement_p)->next_p = (privateList_p)->front_p;
503 (alElement_p)->previous_p = NULL;
504 (privateList_p)->front_p->previous_p = (alElement_p);
505 (privateList_p)->front_p = (alElement_p);
508 (privateList_p)->size++;
512 * This method simply performs the common portion of popping a list element
515 * WARNING: This is a private helper method that should not be called directly
518 SCI_ABSTRACT_ELEMENT_T * private_pop_front(
519 SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p
522 SCI_ABSTRACT_ELEMENT_T * alElement_p = (privateList_p)->front_p;
524 if (alElement_p != NULL)
526 if ((privateList_p)->front_p == (privateList_p)->back_p)
528 (privateList_p)->front_p = (privateList_p)->back_p = NULL;
532 (privateList_p)->front_p = (privateList_p)->front_p->next_p;
533 (privateList_p)->front_p->previous_p = NULL;
536 (privateList_p)->size--;
543 * This method will simply search the supplied list for the desired object.
544 * It will return a pointer to the abstract_list_element if found, otherwise
545 * it will return NULL.
547 SCI_ABSTRACT_ELEMENT_T * private_find(
548 SCI_ABSTRACT_ELEMENT_LIST_T * list_p,
552 SCI_ABSTRACT_ELEMENT_T * alElement_p = (list_p)->front_p;
554 while (alElement_p != NULL)
556 /* Check to see if we found the object for which we are searching. */
557 if (alElement_p->object_p == (void*) (obj_p))
562 alElement_p = alElement_p->next_p;
569 * This private method will free the supplied list element back to the pool
570 * of free list elements.
572 void private_pool_free(
573 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool,
574 SCI_ABSTRACT_ELEMENT_T * alElement_p
577 /* Push the list element back to the head to get better locality of */
578 /* reference with the cache. */
579 private_push_front(&(free_pool)->free_list, (alElement_p));
583 * This private method will allocate a list element from the pool of free
586 SCI_ABSTRACT_ELEMENT_T * private_pool_allocate(
587 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool
590 SCI_ABSTRACT_ELEMENT_T * alElement_p;
592 alElement_p = private_pop_front(&(free_pool)->free_list);
594 alElement_p->next_p = NULL;
595 alElement_p->previous_p = NULL;
596 alElement_p->object_p = NULL;
601 #endif // USE_ABSTRACT_LIST_FUNCTIONS