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