1 /* 2 * Copyright (c) 2004-2009 Voltaire, Inc. All rights reserved. 3 * Copyright (c) 2002-2005,2009 Mellanox Technologies LTD. All rights reserved. 4 * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. 5 * 6 * This software is available to you under a choice of one of two 7 * licenses. You may choose to be licensed under the terms of the GNU 8 * General Public License (GPL) Version 2, available from the file 9 * COPYING in the main directory of this source tree, or the 10 * OpenIB.org BSD license below: 11 * 12 * Redistribution and use in source and binary forms, with or 13 * without modification, are permitted provided that the following 14 * conditions are met: 15 * 16 * - Redistributions of source code must retain the above 17 * copyright notice, this list of conditions and the following 18 * disclaimer. 19 * 20 * - Redistributions in binary form must reproduce the above 21 * copyright notice, this list of conditions and the following 22 * disclaimer in the documentation and/or other materials 23 * provided with the distribution. 24 * 25 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 26 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 27 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 28 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 29 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 30 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 31 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 32 * SOFTWARE. 33 * 34 */ 35 36 /* 37 * Abstract: 38 * Implementation of quick list, and list. 39 * 40 */ 41 42 #if HAVE_CONFIG_H 43 # include <config.h> 44 #endif /* HAVE_CONFIG_H */ 45 46 #include <complib/cl_qlist.h> 47 #include <complib/cl_list.h> 48 49 #define FREE_ITEM_GROW_SIZE 10 50 51 /****************************************************************************** 52 IMPLEMENTATION OF QUICK LIST 53 ******************************************************************************/ 54 void cl_qlist_insert_array_head(IN cl_qlist_t * const p_list, 55 IN cl_list_item_t * const p_array, 56 IN uint32_t item_count, 57 IN const uint32_t item_size) 58 { 59 cl_list_item_t *p_item; 60 61 CL_ASSERT(p_list); 62 CL_ASSERT(p_list->state == CL_INITIALIZED); 63 CL_ASSERT(p_array); 64 CL_ASSERT(item_size >= sizeof(cl_list_item_t)); 65 CL_ASSERT(item_count); 66 67 /* 68 * To add items from the array to the list in the same order as 69 * the elements appear in the array, we add them starting with 70 * the last one first. Locate the last item. 71 */ 72 p_item = (cl_list_item_t *) ((uint8_t *) p_array + 73 (item_size * (item_count - 1))); 74 75 /* Continue to add all items to the list. */ 76 while (item_count--) { 77 cl_qlist_insert_head(p_list, p_item); 78 79 /* Get the next object to add to the list. */ 80 p_item = (cl_list_item_t *) ((uint8_t *) p_item - item_size); 81 } 82 } 83 84 void cl_qlist_insert_array_tail(IN cl_qlist_t * const p_list, 85 IN cl_list_item_t * const p_array, 86 IN uint32_t item_count, 87 IN const uint32_t item_size) 88 { 89 cl_list_item_t *p_item; 90 91 CL_ASSERT(p_list); 92 CL_ASSERT(p_list->state == CL_INITIALIZED); 93 CL_ASSERT(p_array); 94 CL_ASSERT(item_size >= sizeof(cl_list_item_t)); 95 CL_ASSERT(item_count); 96 97 /* Set the first item to add to the list. */ 98 p_item = p_array; 99 100 /* Continue to add all items to the list. */ 101 while (item_count--) { 102 cl_qlist_insert_tail(p_list, p_item); 103 104 /* Get the next object to add to the list. */ 105 p_item = (cl_list_item_t *) ((uint8_t *) p_item + item_size); 106 } 107 } 108 109 void cl_qlist_insert_list_head(IN cl_qlist_t * const p_dest_list, 110 IN cl_qlist_t * const p_src_list) 111 { 112 #if defined( _DEBUG_ ) 113 cl_list_item_t *p_item; 114 #endif 115 116 CL_ASSERT(p_dest_list); 117 CL_ASSERT(p_src_list); 118 CL_ASSERT(p_dest_list->state == CL_INITIALIZED); 119 CL_ASSERT(p_src_list->state == CL_INITIALIZED); 120 121 /* 122 * Is the src list empty? 123 * We must have this check here for code below to work. 124 */ 125 if (cl_is_qlist_empty(p_src_list)) 126 return; 127 128 #if defined( _DEBUG_ ) 129 /* Check that all items in the source list belong there. */ 130 p_item = cl_qlist_head(p_src_list); 131 while (p_item != cl_qlist_end(p_src_list)) { 132 /* All list items in the source list must point to it. */ 133 CL_ASSERT(p_item->p_list == p_src_list); 134 /* Point them all to the destination list. */ 135 p_item->p_list = p_dest_list; 136 p_item = cl_qlist_next(p_item); 137 } 138 #endif 139 140 /* Chain the destination list to the tail of the source list. */ 141 cl_qlist_tail(p_src_list)->p_next = cl_qlist_head(p_dest_list); 142 cl_qlist_head(p_dest_list)->p_prev = cl_qlist_tail(p_src_list); 143 144 /* 145 * Update the head of the destination list to the head of 146 * the source list. 147 */ 148 p_dest_list->end.p_next = cl_qlist_head(p_src_list); 149 cl_qlist_head(p_src_list)->p_prev = &p_dest_list->end; 150 151 /* 152 * Update the count of the destination to reflect the source items having 153 * been added. 154 */ 155 p_dest_list->count += p_src_list->count; 156 157 /* Update source list to reflect being empty. */ 158 __cl_qlist_reset(p_src_list); 159 } 160 161 void cl_qlist_insert_list_tail(IN cl_qlist_t * const p_dest_list, 162 IN cl_qlist_t * const p_src_list) 163 { 164 #if defined( _DEBUG_ ) 165 cl_list_item_t *p_item; 166 #endif 167 168 CL_ASSERT(p_dest_list); 169 CL_ASSERT(p_src_list); 170 CL_ASSERT(p_dest_list->state == CL_INITIALIZED); 171 CL_ASSERT(p_src_list->state == CL_INITIALIZED); 172 173 /* 174 * Is the src list empty? 175 * We must have this check here for code below to work. 176 */ 177 if (cl_is_qlist_empty(p_src_list)) 178 return; 179 180 #if defined( _DEBUG_ ) 181 /* Check that all items in the source list belong there. */ 182 p_item = cl_qlist_head(p_src_list); 183 while (p_item != cl_qlist_end(p_src_list)) { 184 /* All list items in the source list must point to it. */ 185 CL_ASSERT(p_item->p_list == p_src_list); 186 /* Point them all to the destination list. */ 187 p_item->p_list = p_dest_list; 188 p_item = cl_qlist_next(p_item); 189 } 190 #endif 191 192 /* Chain the source list to the tail of the destination list. */ 193 cl_qlist_tail(p_dest_list)->p_next = cl_qlist_head(p_src_list); 194 cl_qlist_head(p_src_list)->p_prev = cl_qlist_tail(p_dest_list); 195 196 /* 197 * Update the tail of the destination list to the tail of 198 * the source list. 199 */ 200 p_dest_list->end.p_prev = cl_qlist_tail(p_src_list); 201 cl_qlist_tail(p_src_list)->p_next = &p_dest_list->end; 202 203 /* 204 * Update the count of the destination to reflect the source items having 205 * been added. 206 */ 207 p_dest_list->count += p_src_list->count; 208 209 /* Update source list to reflect being empty. */ 210 __cl_qlist_reset(p_src_list); 211 } 212 213 boolean_t cl_is_item_in_qlist(IN const cl_qlist_t * const p_list, 214 IN const cl_list_item_t * const p_list_item) 215 { 216 const cl_list_item_t *p_temp; 217 218 CL_ASSERT(p_list); 219 CL_ASSERT(p_list_item); 220 CL_ASSERT(p_list->state == CL_INITIALIZED); 221 222 /* Traverse looking for a match */ 223 p_temp = cl_qlist_head(p_list); 224 while (p_temp != cl_qlist_end(p_list)) { 225 if (p_temp == p_list_item) { 226 CL_ASSERT(p_list_item->p_list == p_list); 227 return (TRUE); 228 } 229 230 p_temp = cl_qlist_next(p_temp); 231 } 232 233 return (FALSE); 234 } 235 236 cl_list_item_t *cl_qlist_find_next(IN const cl_qlist_t * const p_list, 237 IN const cl_list_item_t * const p_list_item, 238 IN cl_pfn_qlist_find_t pfn_func, 239 IN const void *const context) 240 { 241 cl_list_item_t *p_found_item; 242 243 CL_ASSERT(p_list); 244 CL_ASSERT(p_list->state == CL_INITIALIZED); 245 CL_ASSERT(p_list_item); 246 CL_ASSERT(p_list_item->p_list == p_list); 247 CL_ASSERT(pfn_func); 248 249 p_found_item = cl_qlist_next(p_list_item); 250 251 /* The user provided a compare function */ 252 while (p_found_item != cl_qlist_end(p_list)) { 253 CL_ASSERT(p_found_item->p_list == p_list); 254 255 if (pfn_func(p_found_item, (void *)context) == CL_SUCCESS) 256 break; 257 258 p_found_item = cl_qlist_next(p_found_item); 259 } 260 261 /* No match */ 262 return (p_found_item); 263 } 264 265 cl_list_item_t *cl_qlist_find_prev(IN const cl_qlist_t * const p_list, 266 IN const cl_list_item_t * const p_list_item, 267 IN cl_pfn_qlist_find_t pfn_func, 268 IN const void *const context) 269 { 270 cl_list_item_t *p_found_item; 271 272 CL_ASSERT(p_list); 273 CL_ASSERT(p_list->state == CL_INITIALIZED); 274 CL_ASSERT(p_list_item); 275 CL_ASSERT(p_list_item->p_list == p_list); 276 CL_ASSERT(pfn_func); 277 278 p_found_item = cl_qlist_prev(p_list_item); 279 280 /* The user provided a compare function */ 281 while (p_found_item != cl_qlist_end(p_list)) { 282 CL_ASSERT(p_found_item->p_list == p_list); 283 284 if (pfn_func(p_found_item, (void *)context) == CL_SUCCESS) 285 break; 286 287 p_found_item = cl_qlist_prev(p_found_item); 288 } 289 290 /* No match */ 291 return (p_found_item); 292 } 293 294 void cl_qlist_apply_func(IN const cl_qlist_t * const p_list, 295 IN cl_pfn_qlist_apply_t pfn_func, 296 IN const void *const context) 297 { 298 cl_list_item_t *p_list_item; 299 300 /* Note that context can have any arbitrary value. */ 301 CL_ASSERT(p_list); 302 CL_ASSERT(p_list->state == CL_INITIALIZED); 303 CL_ASSERT(pfn_func); 304 305 p_list_item = cl_qlist_head(p_list); 306 while (p_list_item != cl_qlist_end(p_list)) { 307 pfn_func(p_list_item, (void *)context); 308 p_list_item = cl_qlist_next(p_list_item); 309 } 310 } 311 312 void cl_qlist_move_items(IN cl_qlist_t * const p_src_list, 313 IN cl_qlist_t * const p_dest_list, 314 IN cl_pfn_qlist_find_t pfn_func, 315 IN const void *const context) 316 { 317 cl_list_item_t *p_current_item, *p_next; 318 319 CL_ASSERT(p_src_list); 320 CL_ASSERT(p_dest_list); 321 CL_ASSERT(p_src_list->state == CL_INITIALIZED); 322 CL_ASSERT(p_dest_list->state == CL_INITIALIZED); 323 CL_ASSERT(pfn_func); 324 325 p_current_item = cl_qlist_head(p_src_list); 326 327 while (p_current_item != cl_qlist_end(p_src_list)) { 328 /* Before we do anything, get a pointer to the next item. */ 329 p_next = cl_qlist_next(p_current_item); 330 331 if (pfn_func(p_current_item, (void *)context) == CL_SUCCESS) { 332 /* Move the item from one list to the other. */ 333 cl_qlist_remove_item(p_src_list, p_current_item); 334 cl_qlist_insert_tail(p_dest_list, p_current_item); 335 } 336 p_current_item = p_next; 337 } 338 } 339 340 /****************************************************************************** 341 IMPLEMENTATION OF LIST 342 ******************************************************************************/ 343 void cl_list_construct(IN cl_list_t * const p_list) 344 { 345 CL_ASSERT(p_list); 346 347 cl_qpool_construct(&p_list->list_item_pool); 348 } 349 350 cl_status_t cl_list_init(IN cl_list_t * const p_list, IN const size_t min_items) 351 { 352 uint32_t grow_size; 353 354 CL_ASSERT(p_list); 355 cl_qlist_init(&p_list->list); 356 357 /* 358 * We will grow by min_items/8 items at a time, with a minimum of 359 * FREE_ITEM_GROW_SIZE. 360 */ 361 grow_size = (uint32_t) min_items >> 3; 362 if (grow_size < FREE_ITEM_GROW_SIZE) 363 grow_size = FREE_ITEM_GROW_SIZE; 364 365 /* Initialize the pool of list items. */ 366 return (cl_qpool_init(&p_list->list_item_pool, min_items, 0, grow_size, 367 sizeof(cl_pool_obj_t), NULL, NULL, NULL)); 368 } 369 370 void cl_list_destroy(IN cl_list_t * const p_list) 371 { 372 CL_ASSERT(p_list); 373 374 cl_qpool_destroy(&p_list->list_item_pool); 375 } 376 377 static cl_status_t cl_list_find_cb(IN const cl_list_item_t * const p_list_item, 378 IN void *const context) 379 { 380 CL_ASSERT(p_list_item); 381 382 if (cl_list_obj(p_list_item) == context) 383 return (CL_SUCCESS); 384 385 return (CL_NOT_FOUND); 386 } 387 388 cl_status_t cl_list_remove_object(IN cl_list_t * const p_list, 389 IN const void *const p_object) 390 { 391 cl_list_item_t *p_list_item; 392 393 CL_ASSERT(p_list); 394 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool)); 395 396 /* find the item in question */ 397 p_list_item = 398 cl_qlist_find_from_head(&p_list->list, cl_list_find_cb, p_object); 399 if (p_list_item != cl_qlist_end(&p_list->list)) { 400 /* remove this item */ 401 cl_qlist_remove_item(&p_list->list, p_list_item); 402 cl_qpool_put(&p_list->list_item_pool, 403 (cl_pool_item_t *) p_list_item); 404 return (CL_SUCCESS); 405 } 406 return (CL_NOT_FOUND); 407 } 408 409 boolean_t cl_is_object_in_list(IN const cl_list_t * const p_list, 410 IN const void *const p_object) 411 { 412 CL_ASSERT(p_list); 413 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool)); 414 415 return (cl_qlist_find_from_head 416 (&p_list->list, cl_list_find_cb, p_object) 417 != cl_qlist_end(&p_list->list)); 418 } 419 420 cl_status_t cl_list_insert_array_head(IN cl_list_t * const p_list, 421 IN const void *const p_array, 422 IN uint32_t item_count, 423 IN const uint32_t item_size) 424 { 425 cl_status_t status; 426 void *p_object; 427 uint32_t items_remain = item_count; 428 429 CL_ASSERT(p_list); 430 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool)); 431 CL_ASSERT(p_array); 432 CL_ASSERT(item_size); 433 CL_ASSERT(item_count); 434 435 /* 436 * To add items from the array to the list in the same order as 437 * the elements appear in the array, we add them starting with 438 * the last one first. Locate the last item. 439 */ 440 p_object = ((uint8_t *) p_array + (item_size * (item_count - 1))); 441 442 /* Continue to add all items to the list. */ 443 while (items_remain--) { 444 status = cl_list_insert_head(p_list, p_object); 445 if (status != CL_SUCCESS) { 446 /* Remove all items that have been inserted. */ 447 while (items_remain++ < (item_count - 1)) 448 cl_list_remove_head(p_list); 449 return (status); 450 } 451 452 /* Get the next object to add to the list. */ 453 p_object = ((uint8_t *) p_object - item_size); 454 } 455 456 return (CL_SUCCESS); 457 } 458 459 cl_status_t cl_list_insert_array_tail(IN cl_list_t * const p_list, 460 IN const void *const p_array, 461 IN uint32_t item_count, 462 IN const uint32_t item_size) 463 { 464 cl_status_t status; 465 void *p_object; 466 uint32_t items_remain = item_count; 467 468 CL_ASSERT(p_list); 469 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool)); 470 CL_ASSERT(p_array); 471 CL_ASSERT(item_size); 472 CL_ASSERT(item_count); 473 474 /* Set the first item to add to the list. */ 475 p_object = (void *)p_array; 476 477 /* Continue to add all items to the list. */ 478 while (items_remain--) { 479 status = cl_list_insert_tail(p_list, p_object); 480 if (status != CL_SUCCESS) { 481 /* Remove all items that have been inserted. */ 482 while (items_remain++ < (item_count - 1)) 483 cl_list_remove_tail(p_list); 484 return (status); 485 } 486 487 /* Get the next object to add to the list. */ 488 p_object = ((uint8_t *) p_object + item_size); 489 } 490 491 return (CL_SUCCESS); 492 } 493 494 cl_list_iterator_t cl_list_find_from_head(IN const cl_list_t * const p_list, 495 IN cl_pfn_list_find_t pfn_func, 496 IN const void *const context) 497 { 498 cl_status_t status; 499 cl_list_iterator_t itor; 500 501 /* Note that context can have any arbitrary value. */ 502 CL_ASSERT(p_list); 503 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool)); 504 CL_ASSERT(pfn_func); 505 506 itor = cl_list_head(p_list); 507 508 while (itor != cl_list_end(p_list)) { 509 status = pfn_func(cl_list_obj(itor), (void *)context); 510 if (status == CL_SUCCESS) 511 break; 512 513 itor = cl_list_next(itor); 514 } 515 516 /* no match */ 517 return (itor); 518 } 519 520 cl_list_iterator_t cl_list_find_from_tail(IN const cl_list_t * const p_list, 521 IN cl_pfn_list_find_t pfn_func, 522 IN const void *const context) 523 { 524 cl_status_t status; 525 cl_list_iterator_t itor; 526 527 /* Note that context can have any arbitrary value. */ 528 CL_ASSERT(p_list); 529 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool)); 530 CL_ASSERT(pfn_func); 531 532 itor = cl_list_tail(p_list); 533 534 while (itor != cl_list_end(p_list)) { 535 status = pfn_func(cl_list_obj(itor), (void *)context); 536 if (status == CL_SUCCESS) 537 break; 538 539 itor = cl_list_prev(itor); 540 } 541 542 /* no match */ 543 return (itor); 544 } 545 546 void cl_list_apply_func(IN const cl_list_t * const p_list, 547 IN cl_pfn_list_apply_t pfn_func, 548 IN const void *const context) 549 { 550 cl_list_iterator_t itor; 551 552 /* Note that context can have any arbitrary value. */ 553 CL_ASSERT(p_list); 554 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool)); 555 CL_ASSERT(pfn_func); 556 557 itor = cl_list_head(p_list); 558 559 while (itor != cl_list_end(p_list)) { 560 pfn_func(cl_list_obj(itor), (void *)context); 561 562 itor = cl_list_next(itor); 563 } 564 } 565