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 */ 102 void 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 */ 124 void 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 */ 159 SCI_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 */ 170 void * 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 */ 182 void * 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 */ 193 BOOL 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 */ 204 U32 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 */ 215 SCI_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 */ 227 void 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 */ 253 void * 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 */ 268 void * 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 */ 300 void * 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 */ 323 void 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 */ 356 void 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 */ 388 void 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 */ 404 void 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 */ 442 void 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 */ 454 void * 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 */ 470 U32 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 */ 490 void 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 */ 518 SCI_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 */ 547 SCI_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 */ 572 void 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 */ 586 SCI_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