1/*- 2 * SPDX-License-Identifier: BSD-2-Clause OR GPL-2.0 3 * 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. 6 * 7 * GPL LICENSE SUMMARY 8 * 9 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved. 10 * 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. 14 * 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. 19 * 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. 25 * 26 * BSD LICENSE 27 * 28 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved. 29 * All rights reserved. 30 * 31 * Redistribution and use in source and binary forms, with or without 32 * modification, are permitted provided that the following conditions 33 * are met: 34 * 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 40 * distribution. 41 * 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. 53 */ 54 55#include <sys/cdefs.h> 56__FBSDID("$FreeBSD$"); 57 58/** 59 * @file 60 * 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. 65 */ 66 67//****************************************************************************** 68//* 69//* I N C L U D E S 70//* 71//****************************************************************************** 72 73#include <dev/isci/scil/sci_abstract_list.h> 74 75 76//****************************************************************************** 77//* 78//* P R I V A T E M E M B E R S 79//* 80//****************************************************************************** 81 82//****************************************************************************** 83//* 84//* P R O T E C T E D M E T H O D S 85//* 86//****************************************************************************** 87 88/** 89 * @brief Initialize the abstract list 90 * 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. 94 * 95 * @param[in] list This parameter specifies the abstract list to be 96 * constructed. 97 * @param[in] free_pool This parameter specifies the free pool to be 98 * utilized as the repository of free elements for list usage. 99 * 100 * @return none 101 */ 102void sci_abstract_list_construct( 103 SCI_ABSTRACT_LIST_T * list, 104 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool 105) 106{ 107 memset(list, 0, sizeof(SCI_ABSTRACT_LIST_T)); 108 list->free_pool = free_pool; 109} 110 111/** 112 * Initialize the abstract list with its free pool 113 * 114 * @param[in] 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 121 * 122 * @return none 123 */ 124void sci_abstract_element_pool_construct( 125 SCI_ABSTRACT_ELEMENT_POOL_T * pool, 126 SCI_ABSTRACT_ELEMENT_T * list_elements, 127 int element_count 128) 129{ 130 int index; 131 132 memset(pool, 0, sizeof(SCI_ABSTRACT_ELEMENT_POOL_T)); 133 memset(list_elements, 0, sizeof(SCI_ABSTRACT_ELEMENT_T) * element_count); 134 135 pool->elements = list_elements; 136 pool->max_elements = element_count; 137 138 // Loop through all of the elements in the array and push them onto the 139 // pool's free list. 140 for (index = element_count - 1; index >= 0; index--) 141 { 142 private_pool_free(pool, &(list_elements[index])); 143 } 144} 145 146 147#ifdef USE_ABSTRACT_LIST_FUNCTIONS 148 149//****************************************************************************** 150//* 151//* P U B L I C M E T H O D S 152//* 153//****************************************************************************** 154 155/** 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. 158 */ 159SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_front( 160 SCI_ABSTRACT_LIST_T * list_p 161) 162{ 163 return (list_p)->elements.front_p; 164} 165 166/** 167 * This method simply returns the object pointed to by the head (front) of 168 * the list. 169 */ 170void * sci_abstract_list_front( 171 SCI_ABSTRACT_LIST_T * list_p 172) 173{ 174 return 175 ( ( (list_p)->elements.front_p ) ? ((list_p)->elements.front_p->object_p) : NULL ); 176} 177 178/** 179 * This method simply returns the object pointed to by the tail (back) of 180 * the list. 181 */ 182void * sci_abstract_list_back( 183 SCI_ABSTRACT_LIST_T * list_p 184) 185{ 186 return 187 ( ( (list_p)->elements.back_p ) ? ((list_p)->elements.back_p->object_p) : NULL ); 188} 189 190/** 191 * This method will return FALSE if the list is not empty. 192 */ 193BOOL sci_abstract_list_is_empty( 194 SCI_ABSTRACT_LIST_T * list_p 195) 196{ 197 return ( (list_p)->elements.front_p == NULL ); 198} 199 200 201/** 202 * This method will return the number of elements queued in the list. 203 */ 204U32 sci_abstract_list_size( 205 SCI_ABSTRACT_LIST_T * list_p 206) 207{ 208 return ( (list_p)->elements.size ); 209} 210 211 212/** 213 * This method simply returns the next list element in the list. 214 */ 215SCI_ABSTRACT_ELEMENT_T * sci_abstract_list_get_next( 216 SCI_ABSTRACT_ELEMENT_T * alElement_p 217) 218{ 219 return ( (alElement_p)->next_p ); 220} 221 222 223#if defined(SCI_LOGGING) 224/** 225 * This method simply prints the contents of the list. 226 */ 227void sci_abstract_list_print( 228 SCI_ABSTRACT_LIST_T * list_p 229) 230{ 231 SCI_ABSTRACT_ELEMENT_T * alElement_p = list_p->elements.front_p; 232 233 while (alElement_p != NULL) 234 { 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", 238 alElement_p->next_p, 239 alElement_p->previous_p, 240 (U32*) (alElement_p->object_p)); 241#endif 242 alElement_p = alElement_p->next_p; 243 } 244} 245#endif // defined(SCI_LOGGING) 246 247 248/** 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. 252 */ 253void * sci_abstract_list_find( 254 SCI_ABSTRACT_LIST_T * list_p, 255 void * obj_p 256) 257{ 258 return 259 sci_abstract_list_get_object(private_find(&(list_p)->elements, (obj_p))); 260} 261 262 263/** 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 266 * found. 267 */ 268void * sci_abstract_list_popback( 269 SCI_ABSTRACT_LIST_T * list_p 270) 271{ 272 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; 273 SCI_ABSTRACT_ELEMENT_T * alElement_p = elem_list->back_p; 274 void * obj_p = NULL; 275 276 if (alElement_p != NULL) 277 { 278 obj_p = alElement_p->object_p; 279 if (elem_list->back_p == elem_list->front_p) 280 { 281 elem_list->back_p = elem_list->front_p = NULL; 282 } 283 else 284 { 285 elem_list->back_p = elem_list->back_p->previous_p; 286 elem_list->back_p->next_p = NULL; 287 } 288 289 elem_list->size--; 290 private_pool_free((list_p)->free_pool, alElement_p); 291 } 292 293 return obj_p; 294} 295 296/** 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. 299 */ 300void * sci_abstract_list_popfront( 301 SCI_ABSTRACT_LIST_T * list_p 302) 303{ 304 SCI_ABSTRACT_ELEMENT_T * alElement_p = 305 private_pop_front(&(list_p)->elements); 306 void * obj_p = NULL; 307 308 if (alElement_p != NULL) 309 { 310 obj_p = alElement_p->object_p; 311 private_pool_free((list_p)->free_pool, alElement_p); 312 } 313 314 return obj_p; 315} 316 317 318 319/** 320 * This method will erase (remove) all instances of the supplied object from 321 * anywhere in the list. 322 */ 323void sci_abstract_list_erase( 324 SCI_ABSTRACT_LIST_T * list_p, 325 void * obj_p 326) 327{ 328 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; 329 SCI_ABSTRACT_ELEMENT_T * alElement_p; 330 331 while ((alElement_p = private_find(elem_list, (obj_p))) != NULL) 332 { 333 if (alElement_p == elem_list->front_p) 334 { 335 sci_abstract_list_popfront(list_p); 336 } 337 else if (alElement_p == elem_list->back_p) 338 { 339 sci_abstract_list_popback(list_p); 340 } 341 else 342 { 343 alElement_p->previous_p->next_p = alElement_p->next_p; 344 alElement_p->next_p->previous_p = alElement_p->previous_p; 345 elem_list->size--; 346 private_pool_free((list_p)->free_pool, alElement_p); 347 } 348 } 349 return; 350} 351 352/** 353 * This method simply adds a LIST_ELEMENT for the supplied object to the back 354 * (tail) of the supplied list. 355 */ 356void sci_abstract_list_pushback( 357 SCI_ABSTRACT_LIST_T * list_p, 358 void * obj_p 359) 360{ 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); 365 366 alElement_p->object_p = (obj_p); 367 368 if (elem_list->front_p == NULL) 369 { 370 elem_list->front_p = elem_list->back_p = alElement_p; 371 } 372 else 373 { 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; 377 } 378 379 elem_list->size++; 380} 381 382 383 384/** 385 * This method simply adds a LIST_ELEMENT for the supplied object to the front 386 * (head) of the supplied list. 387 */ 388void sci_abstract_list_pushfront( 389 SCI_ABSTRACT_LIST_T * list_p, 390 void * obj_p 391) 392{ 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); 397} 398 399 400/** 401 * This method will add the objToAdd_p object to the list before the obj_p. 402 * 403 */ 404void sci_abstract_list_insert( 405 SCI_ABSTRACT_LIST_T * list_p, 406 void * obj_p, 407 void * objToAdd_p 408) 409{ 410 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; 411 412 SCI_ABSTRACT_ELEMENT_T * obj_element = private_find(elem_list, obj_p); 413 414 SCI_ABSTRACT_ELEMENT_T * objToAdd_element = 415 private_pool_allocate((list_p)->free_pool); 416 417 objToAdd_element->object_p = objToAdd_p; 418 419 ASSERT(obj_element != NULL); 420 ASSERT(objToAdd_element != NULL); 421 422 if (obj_element == elem_list->front_p) 423 { 424 objToAdd_element->object_p = (objToAdd_p); 425 private_push_front(&(list_p)->elements, objToAdd_element); 426 } 427 else 428 { 429 obj_element->previous_p->next_p = objToAdd_element; 430 objToAdd_element->previous_p = obj_element->previous_p; 431 432 obj_element->previous_p = objToAdd_element; 433 objToAdd_element->next_p = obj_element; 434 435 elem_list->size++; 436 } 437} 438 439/** 440 * This method simply frees all the items from the list. 441 */ 442void sci_abstract_list_clear( 443 SCI_ABSTRACT_LIST_T * list_p 444) 445{ 446 while ((list_p)->elements.size > 0) 447 sci_abstract_list_popfront((list_p)); 448} 449 450/** 451 * This method simply returns the object being pointed to by the list element 452 * (The item being listed). 453 */ 454void * sci_abstract_list_get_object( 455 SCI_ABSTRACT_ELEMENT_T * alElement_p 456) 457{ 458 void * obj_p = NULL; 459 if ((alElement_p) != NULL) 460 obj_p = (alElement_p)->object_p; 461 462 return obj_p; 463} 464 465 466/** 467 * This method is simply a wrapper to provide the number of elements in 468 * the free list. 469 */ 470U32 sci_abstract_list_freeList_size( 471 SCI_ABSTRACT_LIST_T * freeList 472) 473{ 474 return (sci_abstract_list_size(freeList)); 475} 476 477//****************************************************************************** 478//* 479//* P R I V A T E M E T H O D S 480//* 481//****************************************************************************** 482 483/** 484 * This method simply performs the common portion of pushing a list element 485 * onto a list. 486 * 487 * WARNING: This is a private helper method that should not be called directly 488 * by any users. 489 */ 490void private_push_front( 491 SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p, 492 SCI_ABSTRACT_ELEMENT_T * alElement_p 493) 494{ 495 if ((privateList_p)->front_p == NULL) 496 { 497 (privateList_p)->front_p = (privateList_p)->back_p = (alElement_p); 498 (alElement_p)->next_p = (alElement_p)->previous_p = NULL; 499 } 500 else 501 { 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); 506 } 507 508 (privateList_p)->size++; 509} 510 511/** 512 * This method simply performs the common portion of popping a list element 513 * from a list. 514 * 515 * WARNING: This is a private helper method that should not be called directly 516 * by any users. 517 */ 518SCI_ABSTRACT_ELEMENT_T * private_pop_front( 519 SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p 520) 521{ 522 SCI_ABSTRACT_ELEMENT_T * alElement_p = (privateList_p)->front_p; 523 524 if (alElement_p != NULL) 525 { 526 if ((privateList_p)->front_p == (privateList_p)->back_p) 527 { 528 (privateList_p)->front_p = (privateList_p)->back_p = NULL; 529 } 530 else 531 { 532 (privateList_p)->front_p = (privateList_p)->front_p->next_p; 533 (privateList_p)->front_p->previous_p = NULL; 534 } 535 536 (privateList_p)->size--; 537 } 538 539 return alElement_p; 540} 541 542/** 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. 546 */ 547SCI_ABSTRACT_ELEMENT_T * private_find( 548 SCI_ABSTRACT_ELEMENT_LIST_T * list_p, 549 void * obj_p 550) 551{ 552 SCI_ABSTRACT_ELEMENT_T * alElement_p = (list_p)->front_p; 553 554 while (alElement_p != NULL) 555 { 556 /* Check to see if we found the object for which we are searching. */ 557 if (alElement_p->object_p == (void*) (obj_p)) 558 { 559 break; 560 } 561 562 alElement_p = alElement_p->next_p; 563 } 564 565 return alElement_p; 566} 567 568/** 569 * This private method will free the supplied list element back to the pool 570 * of free list elements. 571 */ 572void private_pool_free( 573 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool, 574 SCI_ABSTRACT_ELEMENT_T * alElement_p 575) 576{ 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)); 580} 581 582/** 583 * This private method will allocate a list element from the pool of free 584 * list elements. 585 */ 586SCI_ABSTRACT_ELEMENT_T * private_pool_allocate( 587 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool 588) 589{ 590 SCI_ABSTRACT_ELEMENT_T * alElement_p; 591 592 alElement_p = private_pop_front(&(free_pool)->free_list); 593 594 alElement_p->next_p = NULL; 595 alElement_p->previous_p = NULL; 596 alElement_p->object_p = NULL; 597 598 return alElement_p; 599} 600 601#endif // USE_ABSTRACT_LIST_FUNCTIONS 602