1/*- 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. 4 * 5 * GPL LICENSE SUMMARY 6 * 7 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved. 8 * 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. 12 * 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. 17 * 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. 23 * 24 * BSD LICENSE 25 * 26 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved. 27 * All rights reserved. 28 * 29 * Redistribution and use in source and binary forms, with or without 30 * modification, are permitted provided that the following conditions 31 * are met: 32 * 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 38 * distribution. 39 * 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. 51 */ 52 53#include <sys/cdefs.h> 54__FBSDID("$FreeBSD$"); 55 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 */ 100void 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 */ 122void 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 */ 157SCI_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 */ 168void * 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 */ 180void * 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 */ 191BOOL 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 */ 202U32 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 */ 213SCI_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 */ 225void 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#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", 236 alElement_p->next_p, 237 alElement_p->previous_p, 238 (U32*) (alElement_p->object_p)); 239#endif 240 alElement_p = alElement_p->next_p; 241 } 242} 243#endif // defined(SCI_LOGGING) 244 245 246/** 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. 250 */ 251void * sci_abstract_list_find( 252 SCI_ABSTRACT_LIST_T * list_p, 253 void * obj_p 254) 255{ 256 return 257 sci_abstract_list_get_object(private_find(&(list_p)->elements, (obj_p))); 258} 259 260 261/** 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 264 * found. 265 */ 266void * sci_abstract_list_popback( 267 SCI_ABSTRACT_LIST_T * list_p 268) 269{ 270 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; 271 SCI_ABSTRACT_ELEMENT_T * alElement_p = elem_list->back_p; 272 void * obj_p = NULL; 273 274 if (alElement_p != NULL) 275 { 276 obj_p = alElement_p->object_p; 277 if (elem_list->back_p == elem_list->front_p) 278 { 279 elem_list->back_p = elem_list->front_p = NULL; 280 } 281 else 282 { 283 elem_list->back_p = elem_list->back_p->previous_p; 284 elem_list->back_p->next_p = NULL; 285 } 286 287 elem_list->size--; 288 private_pool_free((list_p)->free_pool, alElement_p); 289 } 290 291 return obj_p; 292} 293 294/** 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. 297 */ 298void * sci_abstract_list_popfront( 299 SCI_ABSTRACT_LIST_T * list_p 300) 301{ 302 SCI_ABSTRACT_ELEMENT_T * alElement_p = 303 private_pop_front(&(list_p)->elements); 304 void * obj_p = NULL; 305 306 if (alElement_p != NULL) 307 { 308 obj_p = alElement_p->object_p; 309 private_pool_free((list_p)->free_pool, alElement_p); 310 } 311 312 return obj_p; 313} 314 315 316 317/** 318 * This method will erase (remove) all instances of the supplied object from 319 * anywhere in the list. 320 */ 321void sci_abstract_list_erase( 322 SCI_ABSTRACT_LIST_T * list_p, 323 void * obj_p 324) 325{ 326 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; 327 SCI_ABSTRACT_ELEMENT_T * alElement_p; 328 329 while ((alElement_p = private_find(elem_list, (obj_p))) != NULL) 330 { 331 if (alElement_p == elem_list->front_p) 332 { 333 sci_abstract_list_popfront(list_p); 334 } 335 else if (alElement_p == elem_list->back_p) 336 { 337 sci_abstract_list_popback(list_p); 338 } 339 else 340 { 341 alElement_p->previous_p->next_p = alElement_p->next_p; 342 alElement_p->next_p->previous_p = alElement_p->previous_p; 343 elem_list->size--; 344 private_pool_free((list_p)->free_pool, alElement_p); 345 } 346 } 347 return; 348} 349 350/** 351 * This method simply adds a LIST_ELEMENT for the supplied object to the back 352 * (tail) of the supplied list. 353 */ 354void sci_abstract_list_pushback( 355 SCI_ABSTRACT_LIST_T * list_p, 356 void * obj_p 357) 358{ 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); 363 364 alElement_p->object_p = (obj_p); 365 366 if (elem_list->front_p == NULL) 367 { 368 elem_list->front_p = elem_list->back_p = alElement_p; 369 } 370 else 371 { 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; 375 } 376 377 elem_list->size++; 378} 379 380 381 382/** 383 * This method simply adds a LIST_ELEMENT for the supplied object to the front 384 * (head) of the supplied list. 385 */ 386void sci_abstract_list_pushfront( 387 SCI_ABSTRACT_LIST_T * list_p, 388 void * obj_p 389) 390{ 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); 395} 396 397 398/** 399 * This method will add the objToAdd_p object to the list before the obj_p. 400 * 401 */ 402void sci_abstract_list_insert( 403 SCI_ABSTRACT_LIST_T * list_p, 404 void * obj_p, 405 void * objToAdd_p 406) 407{ 408 SCI_ABSTRACT_ELEMENT_LIST_T * elem_list = &(list_p)->elements; 409 410 SCI_ABSTRACT_ELEMENT_T * obj_element = private_find(elem_list, obj_p); 411 412 SCI_ABSTRACT_ELEMENT_T * objToAdd_element = 413 private_pool_allocate((list_p)->free_pool); 414 415 objToAdd_element->object_p = objToAdd_p; 416 417 ASSERT(obj_element != NULL); 418 ASSERT(objToAdd_element != NULL); 419 420 if (obj_element == elem_list->front_p) 421 { 422 objToAdd_element->object_p = (objToAdd_p); 423 private_push_front(&(list_p)->elements, objToAdd_element); 424 } 425 else 426 { 427 obj_element->previous_p->next_p = objToAdd_element; 428 objToAdd_element->previous_p = obj_element->previous_p; 429 430 obj_element->previous_p = objToAdd_element; 431 objToAdd_element->next_p = obj_element; 432 433 elem_list->size++; 434 } 435} 436 437/** 438 * This method simply frees all the items from the list. 439 */ 440void sci_abstract_list_clear( 441 SCI_ABSTRACT_LIST_T * list_p 442) 443{ 444 while ((list_p)->elements.size > 0) 445 sci_abstract_list_popfront((list_p)); 446} 447 448/** 449 * This method simply returns the object being pointed to by the list element 450 * (The item being listed). 451 */ 452void * sci_abstract_list_get_object( 453 SCI_ABSTRACT_ELEMENT_T * alElement_p 454) 455{ 456 void * obj_p = NULL; 457 if ((alElement_p) != NULL) 458 obj_p = (alElement_p)->object_p; 459 460 return obj_p; 461} 462 463 464/** 465 * This method is simply a wrapper to provide the number of elements in 466 * the free list. 467 */ 468U32 sci_abstract_list_freeList_size( 469 SCI_ABSTRACT_LIST_T * freeList 470) 471{ 472 return (sci_abstract_list_size(freeList)); 473} 474 475//****************************************************************************** 476//* 477//* P R I V A T E M E T H O D S 478//* 479//****************************************************************************** 480 481/** 482 * This method simply performs the common portion of pushing a list element 483 * onto a list. 484 * 485 * WARNING: This is a private helper method that should not be called directly 486 * by any users. 487 */ 488void private_push_front( 489 SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p, 490 SCI_ABSTRACT_ELEMENT_T * alElement_p 491) 492{ 493 if ((privateList_p)->front_p == NULL) 494 { 495 (privateList_p)->front_p = (privateList_p)->back_p = (alElement_p); 496 (alElement_p)->next_p = (alElement_p)->previous_p = NULL; 497 } 498 else 499 { 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); 504 } 505 506 (privateList_p)->size++; 507} 508 509/** 510 * This method simply performs the common portion of popping a list element 511 * from a list. 512 * 513 * WARNING: This is a private helper method that should not be called directly 514 * by any users. 515 */ 516SCI_ABSTRACT_ELEMENT_T * private_pop_front( 517 SCI_ABSTRACT_ELEMENT_LIST_T * privateList_p 518) 519{ 520 SCI_ABSTRACT_ELEMENT_T * alElement_p = (privateList_p)->front_p; 521 522 if (alElement_p != NULL) 523 { 524 if ((privateList_p)->front_p == (privateList_p)->back_p) 525 { 526 (privateList_p)->front_p = (privateList_p)->back_p = NULL; 527 } 528 else 529 { 530 (privateList_p)->front_p = (privateList_p)->front_p->next_p; 531 (privateList_p)->front_p->previous_p = NULL; 532 } 533 534 (privateList_p)->size--; 535 } 536 537 return alElement_p; 538} 539 540/** 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. 544 */ 545SCI_ABSTRACT_ELEMENT_T * private_find( 546 SCI_ABSTRACT_ELEMENT_LIST_T * list_p, 547 void * obj_p 548) 549{ 550 SCI_ABSTRACT_ELEMENT_T * alElement_p = (list_p)->front_p; 551 552 while (alElement_p != NULL) 553 { 554 /* Check to see if we found the object for which we are searching. */ 555 if (alElement_p->object_p == (void*) (obj_p)) 556 { 557 break; 558 } 559 560 alElement_p = alElement_p->next_p; 561 } 562 563 return alElement_p; 564} 565 566/** 567 * This private method will free the supplied list element back to the pool 568 * of free list elements. 569 */ 570void private_pool_free( 571 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool, 572 SCI_ABSTRACT_ELEMENT_T * alElement_p 573) 574{ 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)); 578} 579 580/** 581 * This private method will allocate a list element from the pool of free 582 * list elements. 583 */ 584SCI_ABSTRACT_ELEMENT_T * private_pool_allocate( 585 SCI_ABSTRACT_ELEMENT_POOL_T * free_pool 586) 587{ 588 SCI_ABSTRACT_ELEMENT_T * alElement_p; 589 590 alElement_p = private_pop_front(&(free_pool)->free_list); 591 592 alElement_p->next_p = NULL; 593 alElement_p->previous_p = NULL; 594 alElement_p->object_p = NULL; 595 596 return alElement_p; 597} 598 599#endif // USE_ABSTRACT_LIST_FUNCTIONS 600