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