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

   1 /*
   2  * Copyright (c) 2004-2006 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  *      This file contains ivector and isvector implementations.
  39  *
  40  */
  41
  42 #if HAVE_CONFIG_H
  43 #  include <config.h>
  44 #endif                          /* HAVE_CONFIG_H */
  45
  46 #include <stdlib.h>
  47 #include <string.h>
  48 #include <complib/cl_vector.h>
  49
  50 /*
  51  * Define the maximum size for array pages in an cl_vector_t.
  52  * This size is in objects, not bytes.
  53  */
  54 #define SVEC_MAX_PAGE_SIZE 0x1000
  55
  56 /*
  57  * cl_vector_copy_general
  58  *
  59  * Description:
  60  *      copy operator used when size of the user object doesn't fit one of the
  61  *      other optimized copy functions.
  62  *
  63  * Inputs:
  64  *      p_src - source for copy
  65  *
  66  * Outputs:
  67  *      p_dest - destination for copy
  68  *
  69  * Returns:
  70  *      None
  71  *
  72  */
  73 static void
  74 cl_vector_copy_general(OUT void *const p_dest,
  75                        IN const void *const p_src, IN const size_t size)
  76 {
  77         memcpy(p_dest, p_src, size);
  78 }
  79
  80 /*
  81  * cl_vector_copy8
  82  *
  83  * Description:
  84  *      copy operator used when the user structure is only 8 bits long.
  85  *
  86  * Inputs:
  87  *      p_src - source for copy
  88  *
  89  * Outputs:
  90  *      p_dest - destination for copy
  91  *
  92  * Returns:
  93  *      None
  94  *
  95  */
  96 static void
  97 cl_vector_copy8(OUT void *const p_dest,
  98                 IN const void *const p_src, IN const size_t size)
  99 {
 100         CL_ASSERT(size == sizeof(uint8_t));
 101         UNUSED_PARAM(size);
 102
 103         *(uint8_t *) p_dest = *(uint8_t *) p_src;
 104 }
 105
 106 /*
 107  * cl_vector_copy16
 108  *
 109  * Description:
 110  *      copy operator used when the user structure is only 16 bits long.
 111  *
 112  * Inputs:
 113  *      p_src - source for copy
 114  *
 115  * Outputs:
 116  *      p_dest - destination for copy
 117  *
 118  * Returns:
 119  *      None
 120  *
 121  */
 122 void
 123 cl_vector_copy16(OUT void *const p_dest,
 124                  IN const void *const p_src, IN const size_t size)
 125 {
 126         CL_ASSERT(size == sizeof(uint16_t));
 127         UNUSED_PARAM(size);
 128
 129         *(uint16_t *) p_dest = *(uint16_t *) p_src;
 130 }
 131
 132 /*
 133  * cl_vector_copy32
 134  *
 135  * Description:
 136  *      copy operator used when the user structure is only 32 bits long.
 137  *
 138  * Inputs:
 139  *      p_src - source for copy
 140  *
 141  * Outputs:
 142  *      p_dest - destination for copy
 143  *
 144  * Returns:
 145  *      None
 146  *
 147  */
 148 void
 149 cl_vector_copy32(OUT void *const p_dest,
 150                  IN const void *const p_src, IN const size_t size)
 151 {
 152         CL_ASSERT(size == sizeof(uint32_t));
 153         UNUSED_PARAM(size);
 154
 155         *(uint32_t *) p_dest = *(uint32_t *) p_src;
 156 }
 157
 158 /*
 159  * cl_vector_copy64
 160  *
 161  * Description:
 162  *      copy operator used when the user structure is only 64 bits long.
 163  *
 164  * Inputs:
 165  *      p_src - source for copy
 166  *
 167  * Outputs:
 168  *      p_dest - destination for copy
 169  *
 170  * Returns:
 171  *      None
 172  *
 173  */
 174 void
 175 cl_vector_copy64(OUT void *const p_dest,
 176                  IN const void *const p_src, IN const size_t size)
 177 {
 178         CL_ASSERT(size == sizeof(uint64_t));
 179         UNUSED_PARAM(size);
 180
 181         *(uint64_t *) p_dest = *(uint64_t *) p_src;
 182 }
 183
 184 void cl_vector_construct(IN cl_vector_t * const p_vector)
 185 {
 186         CL_ASSERT(p_vector);
 187
 188         memset(p_vector, 0, sizeof(cl_vector_t));
 189
 190         p_vector->state = CL_UNINITIALIZED;
 191 }
 192
 193 cl_status_t
 194 cl_vector_init(IN cl_vector_t * const p_vector,
 195                IN const size_t min_size,
 196                IN const size_t grow_size,
 197                IN const size_t element_size,
 198                IN cl_pfn_vec_init_t pfn_init OPTIONAL,
 199                IN cl_pfn_vec_dtor_t pfn_dtor OPTIONAL,
 200                IN const void *const context)
 201 {
 202         cl_status_t status = CL_SUCCESS;
 203
 204         CL_ASSERT(p_vector);
 205         CL_ASSERT(element_size);
 206
 207         cl_vector_construct(p_vector);
 208
 209         p_vector->grow_size = grow_size;
 210         p_vector->element_size = element_size;
 211         p_vector->pfn_init = pfn_init;
 212         p_vector->pfn_dtor = pfn_dtor;
 213         p_vector->context = context;
 214
 215         /*
 216          * Try to choose a smart copy operator
 217          * someday, we could simply let the users pass one in
 218          */
 219         switch (element_size) {
 220         case sizeof(uint8_t):
 221                 p_vector->pfn_copy = cl_vector_copy8;
 222                 break;
 223
 224         case sizeof(uint16_t):
 225                 p_vector->pfn_copy = cl_vector_copy16;
 226                 break;
 227
 228         case sizeof(uint32_t):
 229                 p_vector->pfn_copy = cl_vector_copy32;
 230                 break;
 231
 232         case sizeof(uint64_t):
 233                 p_vector->pfn_copy = cl_vector_copy64;
 234                 break;
 235
 236         default:
 237                 p_vector->pfn_copy = cl_vector_copy_general;
 238                 break;
 239         }
 240
 241         /*
 242          * Set the state to initialized so that the call to set_size
 243          * doesn't assert.
 244          */
 245         p_vector->state = CL_INITIALIZED;
 246
 247         /* Initialize the allocation list */
 248         cl_qlist_init(&p_vector->alloc_list);
 249
 250         /* get the storage needed by the user */
 251         if (min_size) {
 252                 status = cl_vector_set_size(p_vector, min_size);
 253                 if (status != CL_SUCCESS)
 254                         cl_vector_destroy(p_vector);
 255         }
 256
 257         return (status);
 258 }
 259
 260 void cl_vector_destroy(IN cl_vector_t * const p_vector)
 261 {
 262         size_t i;
 263         void *p_element;
 264
 265         CL_ASSERT(p_vector);
 266         CL_ASSERT(cl_is_state_valid(p_vector->state));
 267
 268         /* Call the user's destructor for each element in the array. */
 269         if (p_vector->state == CL_INITIALIZED) {
 270                 if (p_vector->pfn_dtor) {
 271                         for (i = 0; i < p_vector->size; i++) {
 272                                 p_element = p_vector->p_ptr_array[i];
 273                                 /* Sanity check! */
 274                                 CL_ASSERT(p_element);
 275                                 p_vector->pfn_dtor(p_element,
 276                                                    (void *)p_vector->context);
 277                         }
 278                 }
 279
 280                 /* Deallocate the pages */
 281                 while (!cl_is_qlist_empty(&p_vector->alloc_list))
 282                         free(cl_qlist_remove_head(&p_vector->alloc_list));
 283
 284                 /* Destroy the page vector. */
 285                 if (p_vector->p_ptr_array) {
 286                         free(p_vector->p_ptr_array);
 287                         p_vector->p_ptr_array = NULL;
 288                 }
 289         }
 290
 291         p_vector->state = CL_UNINITIALIZED;
 292 }
 293
 294 cl_status_t
 295 cl_vector_at(IN const cl_vector_t * const p_vector,
 296              IN const size_t index, OUT void *const p_element)
 297 {
 298         CL_ASSERT(p_vector);
 299         CL_ASSERT(p_vector->state == CL_INITIALIZED);
 300
 301         /* Range check */
 302         if (index >= p_vector->size)
 303                 return (CL_INVALID_PARAMETER);
 304
 305         cl_vector_get(p_vector, index, p_element);
 306         return (CL_SUCCESS);
 307 }
 308
 309 cl_status_t
 310 cl_vector_set(IN cl_vector_t * const p_vector,
 311               IN const size_t index, IN void *const p_element)
 312 {
 313         cl_status_t status;
 314         void *p_dest;
 315
 316         CL_ASSERT(p_vector);
 317         CL_ASSERT(p_vector->state == CL_INITIALIZED);
 318         CL_ASSERT(p_element);
 319
 320         /* Determine if the vector has room for this element. */
 321         if (index >= p_vector->size) {
 322                 /* Resize to accomodate the given index. */
 323                 status = cl_vector_set_size(p_vector, index + 1);
 324
 325                 /* Check for failure on or before the given index. */
 326                 if ((status != CL_SUCCESS) && (p_vector->size < index))
 327                         return (status);
 328         }
 329
 330         /* At this point, the array is guaranteed to be big enough */
 331         p_dest = cl_vector_get_ptr(p_vector, index);
 332         /* Sanity check! */
 333         CL_ASSERT(p_dest);
 334
 335         /* Copy the data into the array */
 336         p_vector->pfn_copy(p_dest, p_element, p_vector->element_size);
 337
 338         return (CL_SUCCESS);
 339 }
 340
 341 cl_status_t
 342 cl_vector_set_capacity(IN cl_vector_t * const p_vector,
 343                        IN const size_t new_capacity)
 344 {
 345         size_t new_elements;
 346         size_t alloc_size;
 347         size_t i;
 348         cl_list_item_t *p_buf;
 349         void *p_new_ptr_array;
 350
 351         CL_ASSERT(p_vector);
 352         CL_ASSERT(p_vector->state == CL_INITIALIZED);
 353
 354         /* Do we have to do anything here? */
 355         if (new_capacity <= p_vector->capacity) {
 356                 /* Nope */
 357                 return (CL_SUCCESS);
 358         }
 359
 360         /* Allocate our pointer array. */
 361         p_new_ptr_array = malloc(new_capacity * sizeof(void *));
 362         if (!p_new_ptr_array)
 363                 return (CL_INSUFFICIENT_MEMORY);
 364         else
 365                 memset(p_new_ptr_array, 0, new_capacity * sizeof(void *));
 366
 367         if (p_vector->p_ptr_array) {
 368                 /* Copy the old pointer array into the new. */
 369                 memcpy(p_new_ptr_array, p_vector->p_ptr_array,
 370                        p_vector->capacity * sizeof(void *));
 371
 372                 /* Free the old pointer array. */
 373                 free(p_vector->p_ptr_array);
 374         }
 375
 376         /* Set the new array. */
 377         p_vector->p_ptr_array = p_new_ptr_array;
 378
 379         /*
 380          * We have to add capacity to the array.  Determine how many
 381          * elements to add.
 382          */
 383         new_elements = new_capacity - p_vector->capacity;
 384         /* Determine the allocation size for the new array elements. */
 385         alloc_size = new_elements * p_vector->element_size;
 386
 387         p_buf = (cl_list_item_t *) malloc(alloc_size + sizeof(cl_list_item_t));
 388         if (!p_buf)
 389                 return (CL_INSUFFICIENT_MEMORY);
 390         else
 391                 memset(p_buf, 0, alloc_size + sizeof(cl_list_item_t));
 392
 393         cl_qlist_insert_tail(&p_vector->alloc_list, p_buf);
 394         /* Advance the buffer pointer past the list item. */
 395         p_buf++;
 396
 397         for (i = p_vector->capacity; i < new_capacity; i++) {
 398                 p_vector->p_ptr_array[i] = p_buf;
 399                 /* Move the buffer pointer to the next element. */
 400                 p_buf = (void *)(((uint8_t *) p_buf) + p_vector->element_size);
 401         }
 402
 403         /* Update the vector with the new capactity. */
 404         p_vector->capacity = new_capacity;
 405
 406         return (CL_SUCCESS);
 407 }
 408
 409 cl_status_t
 410 cl_vector_set_size(IN cl_vector_t * const p_vector, IN const size_t size)
 411 {
 412         cl_status_t status;
 413         size_t new_capacity;
 414         size_t index;
 415         void *p_element;
 416
 417         CL_ASSERT(p_vector);
 418         CL_ASSERT(p_vector->state == CL_INITIALIZED);
 419
 420         /* Check to see if the requested size is the same as the existing size. */
 421         if (size == p_vector->size)
 422                 return (CL_SUCCESS);
 423
 424         /* Determine if the vector has room for this element. */
 425         if (size >= p_vector->capacity) {
 426                 if (!p_vector->grow_size)
 427                         return (CL_INSUFFICIENT_MEMORY);
 428
 429                 /* Calculate the new capacity, taking into account the grow size. */
 430                 new_capacity = size;
 431                 if (size % p_vector->grow_size) {
 432                         /* Round up to nearest grow_size boundary. */
 433                         new_capacity += p_vector->grow_size -
 434                             (size % p_vector->grow_size);
 435                 }
 436
 437                 status = cl_vector_set_capacity(p_vector, new_capacity);
 438                 if (status != CL_SUCCESS)
 439                         return (status);
 440         }
 441
 442         /* Are we growing the array and need to invoke an initializer callback? */
 443         if (size > p_vector->size && p_vector->pfn_init) {
 444                 for (index = p_vector->size; index < size; index++) {
 445                         /* Get a pointer to this element */
 446                         p_element = cl_vector_get_ptr(p_vector, index);
 447
 448                         /* Call the user's initializer and trap failures. */
 449                         status =
 450                             p_vector->pfn_init(p_element,
 451                                                (void *)p_vector->context);
 452                         if (status != CL_SUCCESS) {
 453                                 /* Call the destructor for this object */
 454                                 if (p_vector->pfn_dtor)
 455                                         p_vector->pfn_dtor(p_element,
 456                                                            (void *)p_vector->
 457                                                            context);
 458
 459                                 /* Return the failure status to the caller. */
 460                                 return (status);
 461                         }
 462
 463                         /* The array just grew by one element */
 464                         p_vector->size++;
 465                 }
 466         } else if (p_vector->pfn_dtor) {
 467                 /* The array is shrinking and there is a destructor to invoke. */
 468                 for (index = size; index < p_vector->size; index++) {
 469                         /* compute the address of the new elements */
 470                         p_element = cl_vector_get_ptr(p_vector, index);
 471                         /* call the user's destructor */
 472                         p_vector->pfn_dtor(p_element,
 473                                            (void *)p_vector->context);
 474                 }
 475         }
 476
 477         p_vector->size = size;
 478         return (CL_SUCCESS);
 479 }
 480
 481 cl_status_t
 482 cl_vector_set_min_size(IN cl_vector_t * const p_vector,
 483                        IN const size_t min_size)
 484 {
 485         CL_ASSERT(p_vector);
 486         CL_ASSERT(p_vector->state == CL_INITIALIZED);
 487
 488         if (min_size > p_vector->size) {
 489                 /* We have to resize the array */
 490                 return (cl_vector_set_size(p_vector, min_size));
 491         }
 492
 493         /* We didn't have to do anything */
 494         return (CL_SUCCESS);
 495 }
 496
 497 void
 498 cl_vector_apply_func(IN const cl_vector_t * const p_vector,
 499                      IN cl_pfn_vec_apply_t pfn_callback,
 500                      IN const void *const context)
 501 {
 502         size_t i;
 503         void *p_element;
 504
 505         CL_ASSERT(p_vector);
 506         CL_ASSERT(p_vector->state == CL_INITIALIZED);
 507         CL_ASSERT(pfn_callback);
 508
 509         for (i = 0; i < p_vector->size; i++) {
 510                 p_element = cl_vector_get_ptr(p_vector, i);
 511                 pfn_callback(i, p_element, (void *)context);
 512         }
 513 }
 514
 515 size_t
 516 cl_vector_find_from_start(IN const cl_vector_t * const p_vector,
 517                           IN cl_pfn_vec_find_t pfn_callback,
 518                           IN const void *const context)
 519 {
 520         size_t i;
 521         void *p_element;
 522
 523         CL_ASSERT(p_vector);
 524         CL_ASSERT(p_vector->state == CL_INITIALIZED);
 525         CL_ASSERT(pfn_callback);
 526
 527         for (i = 0; i < p_vector->size; i++) {
 528                 p_element = cl_vector_get_ptr(p_vector, i);
 529                 /* Invoke the callback */
 530                 if (pfn_callback(i, p_element, (void *)context) == CL_SUCCESS)
 531                         break;
 532         }
 533         return (i);
 534 }
 535
 536 size_t
 537 cl_vector_find_from_end(IN const cl_vector_t * const p_vector,
 538                         IN cl_pfn_vec_find_t pfn_callback,
 539                         IN const void *const context)
 540 {
 541         size_t i;
 542         void *p_element;
 543
 544         CL_ASSERT(p_vector);
 545         CL_ASSERT(p_vector->state == CL_INITIALIZED);
 546         CL_ASSERT(pfn_callback);
 547
 548         i = p_vector->size;
 549
 550         while (i) {
 551                 /* Get a pointer to the element in the array. */
 552                 p_element = cl_vector_get_ptr(p_vector, --i);
 553                 CL_ASSERT(p_element);
 554
 555                 /* Invoke the callback for the current element. */
 556                 if (pfn_callback(i, p_element, (void *)context) == CL_SUCCESS)
 557                         return (i);
 558         }
 559
 560         return (p_vector->size);
 561 }