contrib/ofed/management/opensm/complib/cl_list.c

   1 /*
   2  * Copyright (c) 2004, 2005 Voltaire, Inc. All rights reserved.
   3  * Copyright (c) 2002-2005 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 *******************************************************************************
  53 **************                                                                                                     ************
  54 **************                   IMPLEMENTATION OF QUICK LIST                      ************
  55 **************                                                                                                     ************
  56 *******************************************************************************
  57 ******************************************************************************/
  58 void
  59 cl_qlist_insert_array_head(IN cl_qlist_t * const p_list,
  60                            IN cl_list_item_t * const p_array,
  61                            IN uint32_t item_count, IN const uint32_t item_size)
  62 {
  63         cl_list_item_t *p_item;
  64
  65         CL_ASSERT(p_list);
  66         CL_ASSERT(p_list->state == CL_INITIALIZED);
  67         CL_ASSERT(p_array);
  68         CL_ASSERT(item_size >= sizeof(cl_list_item_t));
  69         CL_ASSERT(item_count);
  70
  71         /*
  72          * To add items from the array to the list in the same order as
  73          * the elements appear in the array, we add them starting with
  74          * the last one first.  Locate the last item.
  75          */
  76         p_item = (cl_list_item_t *) ((uint8_t *) p_array +
  77                                      (item_size * (item_count - 1)));
  78
  79         /* Continue to add all items to the list. */
  80         while (item_count--) {
  81                 cl_qlist_insert_head(p_list, p_item);
  82
  83                 /* Get the next object to add to the list. */
  84                 p_item = (cl_list_item_t *) ((uint8_t *) p_item - item_size);
  85         }
  86 }
  87
  88 void
  89 cl_qlist_insert_array_tail(IN cl_qlist_t * const p_list,
  90                            IN cl_list_item_t * const p_array,
  91                            IN uint32_t item_count, IN const uint32_t item_size)
  92 {
  93         cl_list_item_t *p_item;
  94
  95         CL_ASSERT(p_list);
  96         CL_ASSERT(p_list->state == CL_INITIALIZED);
  97         CL_ASSERT(p_array);
  98         CL_ASSERT(item_size >= sizeof(cl_list_item_t));
  99         CL_ASSERT(item_count);
 100
 101         /* Set the first item to add to the list. */
 102         p_item = p_array;
 103
 104         /* Continue to add all items to the list. */
 105         while (item_count--) {
 106                 cl_qlist_insert_tail(p_list, p_item);
 107
 108                 /* Get the next object to add to the list. */
 109                 p_item = (cl_list_item_t *) ((uint8_t *) p_item + item_size);
 110         }
 111 }
 112
 113 void
 114 cl_qlist_insert_list_head(IN cl_qlist_t * const p_dest_list,
 115                           IN cl_qlist_t * const p_src_list)
 116 {
 117 #if defined( _DEBUG_ )
 118         cl_list_item_t *p_item;
 119 #endif
 120
 121         CL_ASSERT(p_dest_list);
 122         CL_ASSERT(p_src_list);
 123         CL_ASSERT(p_dest_list->state == CL_INITIALIZED);
 124         CL_ASSERT(p_src_list->state == CL_INITIALIZED);
 125
 126         /*
 127          * Is the src list empty?
 128          * We must have this check here for code below to work.
 129          */
 130         if (cl_is_qlist_empty(p_src_list))
 131                 return;
 132
 133 #if defined( _DEBUG_ )
 134         /* Check that all items in the source list belong there. */
 135         p_item = cl_qlist_head(p_src_list);
 136         while (p_item != cl_qlist_end(p_src_list)) {
 137                 /* All list items in the source list must point to it. */
 138                 CL_ASSERT(p_item->p_list == p_src_list);
 139                 /* Point them all to the destination list. */
 140                 p_item->p_list = p_dest_list;
 141                 p_item = cl_qlist_next(p_item);
 142         }
 143 #endif
 144
 145         /* Chain the destination list to the tail of the source list. */
 146         cl_qlist_tail(p_src_list)->p_next = cl_qlist_head(p_dest_list);
 147         cl_qlist_head(p_dest_list)->p_prev = cl_qlist_tail(p_src_list);
 148
 149         /*
 150          * Update the head of the destination list to the head of
 151          * the source list.
 152          */
 153         p_dest_list->end.p_next = cl_qlist_head(p_src_list);
 154         cl_qlist_head(p_src_list)->p_prev = &p_dest_list->end;
 155
 156         /*
 157          * Update the count of the destination to reflect the source items having
 158          * been added.
 159          */
 160         p_dest_list->count += p_src_list->count;
 161
 162         /* Update source list to reflect being empty. */
 163         __cl_qlist_reset(p_src_list);
 164 }
 165
 166 void
 167 cl_qlist_insert_list_tail(IN cl_qlist_t * const p_dest_list,
 168                           IN cl_qlist_t * const p_src_list)
 169 {
 170 #if defined( _DEBUG_ )
 171         cl_list_item_t *p_item;
 172 #endif
 173
 174         CL_ASSERT(p_dest_list);
 175         CL_ASSERT(p_src_list);
 176         CL_ASSERT(p_dest_list->state == CL_INITIALIZED);
 177         CL_ASSERT(p_src_list->state == CL_INITIALIZED);
 178
 179         /*
 180          * Is the src list empty?
 181          * We must have this check here for code below to work.
 182          */
 183         if (cl_is_qlist_empty(p_src_list))
 184                 return;
 185
 186 #if defined( _DEBUG_ )
 187         /* Check that all items in the source list belong there. */
 188         p_item = cl_qlist_head(p_src_list);
 189         while (p_item != cl_qlist_end(p_src_list)) {
 190                 /* All list items in the source list must point to it. */
 191                 CL_ASSERT(p_item->p_list == p_src_list);
 192                 /* Point them all to the destination list. */
 193                 p_item->p_list = p_dest_list;
 194                 p_item = cl_qlist_next(p_item);
 195         }
 196 #endif
 197
 198         /* Chain the source list to the tail of the destination list. */
 199         cl_qlist_tail(p_dest_list)->p_next = cl_qlist_head(p_src_list);
 200         cl_qlist_head(p_src_list)->p_prev = cl_qlist_tail(p_dest_list);
 201
 202         /*
 203          * Update the tail of the destination list to the tail of
 204          * the source list.
 205          */
 206         p_dest_list->end.p_prev = cl_qlist_tail(p_src_list);
 207         cl_qlist_tail(p_src_list)->p_next = &p_dest_list->end;
 208
 209         /*
 210          * Update the count of the destination to reflect the source items having
 211          * been added.
 212          */
 213         p_dest_list->count += p_src_list->count;
 214
 215         /* Update source list to reflect being empty. */
 216         __cl_qlist_reset(p_src_list);
 217 }
 218
 219 boolean_t
 220 cl_is_item_in_qlist(IN const cl_qlist_t * const p_list,
 221                     IN const cl_list_item_t * const p_list_item)
 222 {
 223         const cl_list_item_t *p_temp;
 224
 225         CL_ASSERT(p_list);
 226         CL_ASSERT(p_list_item);
 227         CL_ASSERT(p_list->state == CL_INITIALIZED);
 228
 229         /* Traverse looking for a match */
 230         p_temp = cl_qlist_head(p_list);
 231         while (p_temp != cl_qlist_end(p_list)) {
 232                 if (p_temp == p_list_item) {
 233                         CL_ASSERT(p_list_item->p_list == p_list);
 234                         return (TRUE);
 235                 }
 236
 237                 p_temp = cl_qlist_next(p_temp);
 238         }
 239
 240         return (FALSE);
 241 }
 242
 243 cl_list_item_t *cl_qlist_find_next(IN const cl_qlist_t * const p_list,
 244                                    IN const cl_list_item_t * const p_list_item,
 245                                    IN cl_pfn_qlist_find_t pfn_func,
 246                                    IN const void *const context)
 247 {
 248         cl_list_item_t *p_found_item;
 249
 250         CL_ASSERT(p_list);
 251         CL_ASSERT(p_list->state == CL_INITIALIZED);
 252         CL_ASSERT(p_list_item);
 253         CL_ASSERT(p_list_item->p_list == p_list);
 254         CL_ASSERT(pfn_func);
 255
 256         p_found_item = cl_qlist_next(p_list_item);
 257
 258         /* The user provided a compare function */
 259         while (p_found_item != cl_qlist_end(p_list)) {
 260                 CL_ASSERT(p_found_item->p_list == p_list);
 261
 262                 if (pfn_func(p_found_item, (void *)context) == CL_SUCCESS)
 263                         break;
 264
 265                 p_found_item = cl_qlist_next(p_found_item);
 266         }
 267
 268         /* No match */
 269         return (p_found_item);
 270 }
 271
 272 cl_list_item_t *cl_qlist_find_prev(IN const cl_qlist_t * const p_list,
 273                                    IN const cl_list_item_t * const p_list_item,
 274                                    IN cl_pfn_qlist_find_t pfn_func,
 275                                    IN const void *const context)
 276 {
 277         cl_list_item_t *p_found_item;
 278
 279         CL_ASSERT(p_list);
 280         CL_ASSERT(p_list->state == CL_INITIALIZED);
 281         CL_ASSERT(p_list_item);
 282         CL_ASSERT(p_list_item->p_list == p_list);
 283         CL_ASSERT(pfn_func);
 284
 285         p_found_item = cl_qlist_prev(p_list_item);
 286
 287         /* The user provided a compare function */
 288         while (p_found_item != cl_qlist_end(p_list)) {
 289                 CL_ASSERT(p_found_item->p_list == p_list);
 290
 291                 if (pfn_func(p_found_item, (void *)context) == CL_SUCCESS)
 292                         break;
 293
 294                 p_found_item = cl_qlist_prev(p_found_item);
 295         }
 296
 297         /* No match */
 298         return (p_found_item);
 299 }
 300
 301 void
 302 cl_qlist_apply_func(IN const cl_qlist_t * const p_list,
 303                     IN cl_pfn_qlist_apply_t pfn_func,
 304                     IN const void *const context)
 305 {
 306         cl_list_item_t *p_list_item;
 307
 308         /* Note that context can have any arbitrary value. */
 309         CL_ASSERT(p_list);
 310         CL_ASSERT(p_list->state == CL_INITIALIZED);
 311         CL_ASSERT(pfn_func);
 312
 313         p_list_item = cl_qlist_head(p_list);
 314         while (p_list_item != cl_qlist_end(p_list)) {
 315                 pfn_func(p_list_item, (void *)context);
 316                 p_list_item = cl_qlist_next(p_list_item);
 317         }
 318 }
 319
 320 void
 321 cl_qlist_move_items(IN cl_qlist_t * const p_src_list,
 322                     IN cl_qlist_t * const p_dest_list,
 323                     IN cl_pfn_qlist_find_t pfn_func,
 324                     IN const void *const context)
 325 {
 326         cl_list_item_t *p_current_item, *p_next;
 327
 328         CL_ASSERT(p_src_list);
 329         CL_ASSERT(p_dest_list);
 330         CL_ASSERT(p_src_list->state == CL_INITIALIZED);
 331         CL_ASSERT(p_dest_list->state == CL_INITIALIZED);
 332         CL_ASSERT(pfn_func);
 333
 334         p_current_item = cl_qlist_head(p_src_list);
 335
 336         while (p_current_item != cl_qlist_end(p_src_list)) {
 337                 /* Before we do anything, get a pointer to the next item. */
 338                 p_next = cl_qlist_next(p_current_item);
 339
 340                 if (pfn_func(p_current_item, (void *)context) == CL_SUCCESS) {
 341                         /* Move the item from one list to the other. */
 342                         cl_qlist_remove_item(p_src_list, p_current_item);
 343                         cl_qlist_insert_tail(p_dest_list, p_current_item);
 344                 }
 345                 p_current_item = p_next;
 346         }
 347 }
 348
 349 /******************************************************************************
 350 *******************************************************************************
 351 **************                                                                                                     ************
 352 **************                   IMPLEMENTATION OF LIST                                    ************
 353 **************                                                                                                     ************
 354 *******************************************************************************
 355 ******************************************************************************/
 356 void cl_list_construct(IN cl_list_t * const p_list)
 357 {
 358         CL_ASSERT(p_list);
 359
 360         cl_qpool_construct(&p_list->list_item_pool);
 361 }
 362
 363 cl_status_t cl_list_init(IN cl_list_t * const p_list, IN const size_t min_items)
 364 {
 365         uint32_t grow_size;
 366
 367         CL_ASSERT(p_list);
 368         cl_qlist_init(&p_list->list);
 369
 370         /*
 371          * We will grow by min_items/8 items at a time, with a minimum of
 372          * FREE_ITEM_GROW_SIZE.
 373          */
 374         grow_size = (uint32_t) min_items >> 3;
 375         if (grow_size < FREE_ITEM_GROW_SIZE)
 376                 grow_size = FREE_ITEM_GROW_SIZE;
 377
 378         /* Initialize the pool of list items. */
 379         return (cl_qpool_init(&p_list->list_item_pool, min_items, 0, grow_size,
 380                               sizeof(cl_pool_obj_t), NULL, NULL, NULL));
 381 }
 382
 383 void cl_list_destroy(IN cl_list_t * const p_list)
 384 {
 385         CL_ASSERT(p_list);
 386
 387         cl_qpool_destroy(&p_list->list_item_pool);
 388 }
 389
 390 static cl_status_t
 391 cl_list_find_cb(IN const cl_list_item_t * const p_list_item,
 392                 IN void *const context)
 393 {
 394         CL_ASSERT(p_list_item);
 395
 396         if (cl_list_obj(p_list_item) == context)
 397                 return (CL_SUCCESS);
 398
 399         return (CL_NOT_FOUND);
 400 }
 401
 402 cl_status_t
 403 cl_list_remove_object(IN cl_list_t * const p_list,
 404                       IN const void *const p_object)
 405 {
 406         cl_list_item_t *p_list_item;
 407
 408         CL_ASSERT(p_list);
 409         CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
 410
 411         /* find the item in question */
 412         p_list_item =
 413             cl_qlist_find_from_head(&p_list->list, cl_list_find_cb, p_object);
 414         if (p_list_item != cl_qlist_end(&p_list->list)) {
 415                 /* remove this item */
 416                 cl_qlist_remove_item(&p_list->list, p_list_item);
 417                 cl_qpool_put(&p_list->list_item_pool,
 418                              (cl_pool_item_t *) p_list_item);
 419                 return (CL_SUCCESS);
 420         }
 421         return (CL_NOT_FOUND);
 422 }
 423
 424 boolean_t
 425 cl_is_object_in_list(IN const cl_list_t * const p_list,
 426                      IN const void *const p_object)
 427 {
 428         CL_ASSERT(p_list);
 429         CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
 430
 431         return (cl_qlist_find_from_head
 432                 (&p_list->list, cl_list_find_cb, p_object)
 433                 != cl_qlist_end(&p_list->list));
 434 }
 435
 436 cl_status_t
 437 cl_list_insert_array_head(IN cl_list_t * const p_list,
 438                           IN const void *const p_array,
 439                           IN uint32_t item_count, IN const uint32_t item_size)
 440 {
 441         cl_status_t status;
 442         void *p_object;
 443
 444         CL_ASSERT(p_list);
 445         CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
 446         CL_ASSERT(p_array);
 447         CL_ASSERT(item_size);
 448         CL_ASSERT(item_count);
 449
 450         /*
 451          * To add items from the array to the list in the same order as
 452          * the elements appear in the array, we add them starting with
 453          * the last one first.  Locate the last item.
 454          */
 455         p_object = ((uint8_t *) p_array + (item_size * (item_count - 1)));
 456
 457         /* Continue to add all items to the list. */
 458         while (item_count--) {
 459                 status = cl_list_insert_head(p_list, p_object);
 460                 if (status != CL_SUCCESS) {
 461                         /* Remove all items that have been inserted. */
 462                         while (item_count++ < item_count)
 463                                 cl_list_remove_head(p_list);
 464                         return (status);
 465                 }
 466
 467                 /* Get the next object to add to the list. */
 468                 p_object = ((uint8_t *) p_object - item_size);
 469         }
 470
 471         return (CL_SUCCESS);
 472 }
 473
 474 cl_status_t
 475 cl_list_insert_array_tail(IN cl_list_t * const p_list,
 476                           IN const void *const p_array,
 477                           IN uint32_t item_count, IN const uint32_t item_size)
 478 {
 479         cl_status_t status;
 480         void *p_object;
 481
 482         CL_ASSERT(p_list);
 483         CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
 484         CL_ASSERT(p_array);
 485         CL_ASSERT(item_size);
 486         CL_ASSERT(item_count);
 487
 488         /* Set the first item to add to the list. */
 489         p_object = (void *)p_array;
 490
 491         /* Continue to add all items to the list. */
 492         while (item_count--) {
 493                 status = cl_list_insert_tail(p_list, p_object);
 494                 if (status != CL_SUCCESS) {
 495                         /* Remove all items that have been inserted. */
 496                         while (item_count++ < item_count)
 497                                 cl_list_remove_tail(p_list);
 498                         return (status);
 499                 }
 500
 501                 /* Get the next object to add to the list. */
 502                 p_object = ((uint8_t *) p_object + item_size);
 503         }
 504
 505         return (CL_SUCCESS);
 506 }
 507
 508 cl_list_iterator_t
 509 cl_list_find_from_head(IN const cl_list_t * const p_list,
 510                        IN cl_pfn_list_find_t pfn_func,
 511                        IN const void *const context)
 512 {
 513         cl_status_t status;
 514         cl_list_iterator_t itor;
 515
 516         /* Note that context can have any arbitrary value. */
 517         CL_ASSERT(p_list);
 518         CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
 519         CL_ASSERT(pfn_func);
 520
 521         itor = cl_list_head(p_list);
 522
 523         while (itor != cl_list_end(p_list)) {
 524                 status = pfn_func(cl_list_obj(itor), (void *)context);
 525                 if (status == CL_SUCCESS)
 526                         break;
 527
 528                 itor = cl_list_next(itor);
 529         }
 530
 531         /* no match */
 532         return (itor);
 533 }
 534
 535 cl_list_iterator_t
 536 cl_list_find_from_tail(IN const cl_list_t * const p_list,
 537                        IN cl_pfn_list_find_t pfn_func,
 538                        IN const void *const context)
 539 {
 540         cl_status_t status;
 541         cl_list_iterator_t itor;
 542
 543         /* Note that context can have any arbitrary value. */
 544         CL_ASSERT(p_list);
 545         CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
 546         CL_ASSERT(pfn_func);
 547
 548         itor = cl_list_tail(p_list);
 549
 550         while (itor != cl_list_end(p_list)) {
 551                 status = pfn_func(cl_list_obj(itor), (void *)context);
 552                 if (status == CL_SUCCESS)
 553                         break;
 554
 555                 itor = cl_list_prev(itor);
 556         }
 557
 558         /* no match */
 559         return (itor);
 560 }
 561
 562 void
 563 cl_list_apply_func(IN const cl_list_t * const p_list,
 564                    IN cl_pfn_list_apply_t pfn_func,
 565                    IN const void *const context)
 566 {
 567         cl_list_iterator_t itor;
 568
 569         /* Note that context can have any arbitrary value. */
 570         CL_ASSERT(p_list);
 571         CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
 572         CL_ASSERT(pfn_func);
 573
 574         itor = cl_list_head(p_list);
 575
 576         while (itor != cl_list_end(p_list)) {
 577                 pfn_func(cl_list_obj(itor), (void *)context);
 578
 579                 itor = cl_list_next(itor);
 580         }
 581 }