contrib/ofed/opensm/complib/cl_list.c

   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 }