core/complib/cl_vector.c

   1 /*\r
   2  * Copyright (c) 2005 SilverStorm Technologies.  All rights reserved.\r
   3  * Copyright (c) 1996-2003 Intel Corporation. All rights reserved.\r
   4  * Copyright (c) 2005 Mellanox Technologies, Inc. All rights reserved.\r
   5  *\r
   6  * This software is available to you under the OpenIB.org BSD license\r
   7  * below:\r
   8  *\r
   9  *     Redistribution and use in source and binary forms, with or\r
  10  *     without modification, are permitted provided that the following\r
  11  *     conditions are met:\r
  12  *\r
  13  *      - Redistributions of source code must retain the above\r
  14  *        copyright notice, this list of conditions and the following\r
  15  *        disclaimer.\r
  16  *\r
  17  *      - Redistributions in binary form must reproduce the above\r
  18  *        copyright notice, this list of conditions and the following\r
  19  *        disclaimer in the documentation and/or other materials\r
  20  *        provided with the distribution.\r
  21  *\r
  22  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
  23  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
  24  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\r
  25  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS\r
  26  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN\r
  27  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
  28  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
  29  * SOFTWARE.\r
  30  *\r
  31  * $Id$\r
  32  */\r
  33 \r
  34 \r
  35 /*\r
  36  * Abstract:\r
  37  *      This file contains ivector and isvector implementations.\r
  38  *\r
  39  * Environment:\r
  40  *      All\r
  41  */\r
  42 \r
  43 \r
  44 #include <complib/cl_vector.h>\r
  45 #include <complib/cl_memory.h>\r
  46 \r
  47 \r
  48 /*\r
  49  * Define the maximum size for array pages in an cl_vector_t.\r
  50  * This size is in objects, not bytes.\r
  51  */\r
  52 #define SVEC_MAX_PAGE_SIZE 0x1000\r
  53 \r
  54 \r
  55 \r
  56 /*\r
  57  * cl_vector_copy_general\r
  58  *\r
  59  * Description:\r
  60  *      copy operator used when size of the user object doesn't fit one of the\r
  61  *      other optimized copy functions.\r
  62  *\r
  63  * Inputs:\r
  64  *      p_src - source for copy\r
  65  *\r
  66  * Outputs:\r
  67  *      p_dest - destination for copy\r
  68  *\r
  69  * Returns:\r
  70  *      None\r
  71  *\r
  72  */\r
  73 static void\r
  74 cl_vector_copy_general(\r
  75         OUT     void* const                     p_dest,\r
  76         IN      const void* const       p_src,\r
  77         IN      const size_t            size )\r
  78 {\r
  79         cl_memcpy( p_dest, p_src, size );\r
  80 }\r
  81 \r
  82 \r
  83 /*\r
  84  * cl_vector_copy8\r
  85  *\r
  86  * Description:\r
  87  *      copy operator used when the user structure is only 8 bits long.\r
  88  *\r
  89  * Inputs:\r
  90  *      p_src - source for copy\r
  91  *\r
  92  * Outputs:\r
  93  *      p_dest - destination for copy\r
  94  *\r
  95  * Returns:\r
  96  *      None\r
  97  *\r
  98  */\r
  99 static void\r
 100 cl_vector_copy8(\r
 101         OUT     void* const                     p_dest,\r
 102         IN      const void* const       p_src,\r
 103         IN      const size_t            size )\r
 104 {\r
 105         CL_ASSERT( size == sizeof(uint8_t) );\r
 106         UNUSED_PARAM( size );\r
 107 \r
 108         *(uint8_t*)p_dest = *(uint8_t*)p_src;\r
 109 }\r
 110 \r
 111 \r
 112 /*\r
 113  * cl_vector_copy16\r
 114  *\r
 115  * Description:\r
 116  *      copy operator used when the user structure is only 16 bits long.\r
 117  *\r
 118  * Inputs:\r
 119  *      p_src - source for copy\r
 120  *\r
 121  * Outputs:\r
 122  *      p_dest - destination for copy\r
 123  *\r
 124  * Returns:\r
 125  *      None\r
 126  *\r
 127  */\r
 128 void\r
 129 cl_vector_copy16(\r
 130         OUT     void* const                     p_dest,\r
 131         IN      const void* const       p_src,\r
 132         IN      const size_t            size )\r
 133 {\r
 134         CL_ASSERT( size == sizeof(uint16_t) );\r
 135         UNUSED_PARAM( size );\r
 136 \r
 137         *(uint16_t*)p_dest = *(uint16_t*)p_src;\r
 138 }\r
 139 \r
 140 \r
 141 /*\r
 142  * cl_vector_copy32\r
 143  *\r
 144  * Description:\r
 145  *      copy operator used when the user structure is only 32 bits long.\r
 146  *\r
 147  * Inputs:\r
 148  *      p_src - source for copy\r
 149  *\r
 150  * Outputs:\r
 151  *      p_dest - destination for copy\r
 152  *\r
 153  * Returns:\r
 154  *      None\r
 155  *\r
 156  */\r
 157 void\r
 158 cl_vector_copy32(\r
 159         OUT     void* const                     p_dest,\r
 160         IN      const void* const       p_src,\r
 161         IN      const size_t            size )\r
 162 {\r
 163         CL_ASSERT( size == sizeof(uint32_t) );\r
 164         UNUSED_PARAM( size );\r
 165 \r
 166         *(uint32_t*)p_dest = *(uint32_t*)p_src;\r
 167 }\r
 168 \r
 169 \r
 170 /*\r
 171  * cl_vector_copy64\r
 172  *\r
 173  * Description:\r
 174  *      copy operator used when the user structure is only 64 bits long.\r
 175  *\r
 176  * Inputs:\r
 177  *      p_src - source for copy\r
 178  *\r
 179  * Outputs:\r
 180  *      p_dest - destination for copy\r
 181  *\r
 182  * Returns:\r
 183  *      None\r
 184  *\r
 185  */\r
 186 void\r
 187 cl_vector_copy64(\r
 188         OUT     void* const                     p_dest,\r
 189         IN      const void* const       p_src,\r
 190         IN      const size_t            size )\r
 191 {\r
 192         CL_ASSERT( size == sizeof(uint64_t) );\r
 193         UNUSED_PARAM( size );\r
 194 \r
 195         *(uint64_t*)p_dest = *(uint64_t*)p_src;\r
 196 }\r
 197 \r
 198 \r
 199 void\r
 200 cl_vector_construct(\r
 201         IN      cl_vector_t* const      p_vector )\r
 202 {\r
 203         CL_ASSERT( p_vector );\r
 204 \r
 205         cl_memclr( p_vector, sizeof(cl_vector_t) );\r
 206 \r
 207         p_vector->state = CL_UNINITIALIZED;\r
 208 }\r
 209 \r
 210 \r
 211 cl_status_t\r
 212 cl_vector_init(\r
 213         IN      cl_vector_t* const      p_vector,\r
 214         IN      const size_t            min_size,\r
 215         IN      const size_t            grow_size,\r
 216         IN      const size_t            element_size,\r
 217         IN      cl_pfn_vec_init_t       pfn_init OPTIONAL,\r
 218         IN      cl_pfn_vec_dtor_t       pfn_dtor OPTIONAL,\r
 219         IN      const void* const       context )\r
 220 {\r
 221         cl_status_t     status = CL_SUCCESS;\r
 222 \r
 223         CL_ASSERT( p_vector );\r
 224         CL_ASSERT( element_size );\r
 225 \r
 226         cl_vector_construct( p_vector );\r
 227 \r
 228         p_vector->grow_size = grow_size;\r
 229         p_vector->element_size = element_size;\r
 230         p_vector->pfn_init = pfn_init;\r
 231         p_vector->pfn_dtor = pfn_dtor;\r
 232         p_vector->context = context;\r
 233 \r
 234         /*\r
 235          * Try to choose a smart copy operator\r
 236          * someday, we could simply let the users pass one in\r
 237          */\r
 238         switch( element_size )\r
 239         {\r
 240         case sizeof(uint8_t):\r
 241                 p_vector->pfn_copy = cl_vector_copy8;\r
 242                 break;\r
 243 \r
 244         case sizeof(uint16_t):\r
 245                 p_vector->pfn_copy = cl_vector_copy16;\r
 246                 break;\r
 247 \r
 248         case sizeof(uint32_t):\r
 249                 p_vector->pfn_copy = cl_vector_copy32;\r
 250                 break;\r
 251 \r
 252         case sizeof(uint64_t):\r
 253                 p_vector->pfn_copy = cl_vector_copy64;\r
 254                 break;\r
 255 \r
 256         default:\r
 257                 p_vector->pfn_copy = cl_vector_copy_general;\r
 258                 break;\r
 259         }\r
 260 \r
 261         /*\r
 262          * Set the state to initialized so that the call to set_size\r
 263          * doesn't assert.\r
 264          */\r
 265         p_vector->state = CL_INITIALIZED;\r
 266 \r
 267         /* Initialize the allocation list */\r
 268         cl_qlist_init( &p_vector->alloc_list );\r
 269 \r
 270         /* get the storage needed by the user */\r
 271         if( min_size )\r
 272         {\r
 273                 status = cl_vector_set_size( p_vector, min_size );\r
 274                 if( status != CL_SUCCESS )\r
 275                         cl_vector_destroy( p_vector );\r
 276         }\r
 277 \r
 278         return( status );\r
 279 }\r
 280 \r
 281 \r
 282 void\r
 283 cl_vector_destroy(\r
 284         IN      cl_vector_t* const      p_vector )\r
 285 {\r
 286         size_t          i;\r
 287         void            *p_element;\r
 288 \r
 289         CL_ASSERT( p_vector );\r
 290         CL_ASSERT( cl_is_state_valid( p_vector->state ) );\r
 291 \r
 292         /* Call the user's destructor for each element in the array. */\r
 293         if( p_vector->state == CL_INITIALIZED )\r
 294         {\r
 295                 if( p_vector->pfn_dtor )\r
 296                 {\r
 297                         for( i = 0; i < p_vector->size; i++ )\r
 298                         {\r
 299                                 p_element = p_vector->p_ptr_array[i];\r
 300                                 /* Sanity check! */\r
 301                                 CL_ASSERT( p_element );\r
 302                                 p_vector->pfn_dtor( p_element, (void*)p_vector->context );\r
 303                         }\r
 304                 }\r
 305 \r
 306                 /* Deallocate the pages */\r
 307                 while( !cl_is_qlist_empty( &p_vector->alloc_list ) )\r
 308                         cl_free( cl_qlist_remove_head( &p_vector->alloc_list ) );\r
 309 \r
 310                 /* Destroy the page vector. */\r
 311                 if( p_vector->p_ptr_array )\r
 312                 {\r
 313                         cl_free( p_vector->p_ptr_array );\r
 314                         p_vector->p_ptr_array = NULL;\r
 315                 }\r
 316         }\r
 317 \r
 318         p_vector->state = CL_UNINITIALIZED;\r
 319 }\r
 320 \r
 321 \r
 322 cl_status_t\r
 323 cl_vector_at(\r
 324         IN      const cl_vector_t* const        p_vector,\r
 325         IN      const size_t                            index,\r
 326         OUT     void* const                                     p_element )\r
 327 {\r
 328         CL_ASSERT( p_vector );\r
 329         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 330 \r
 331         /* Range check */\r
 332         if( index >= p_vector->size )\r
 333                 return( CL_INVALID_PARAMETER );\r
 334 \r
 335         cl_vector_get( p_vector, index, p_element );\r
 336         return( CL_SUCCESS );\r
 337 }\r
 338 \r
 339 \r
 340 cl_status_t\r
 341 cl_vector_set(\r
 342         IN      cl_vector_t* const      p_vector,\r
 343         IN      const size_t            index,\r
 344         IN      void* const                     p_element )\r
 345 {\r
 346         cl_status_t     status;\r
 347         void            *p_dest;\r
 348 \r
 349         CL_ASSERT( p_vector );\r
 350         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 351         CL_ASSERT( p_element );\r
 352 \r
 353         /* Determine if the vector has room for this element. */\r
 354         if( index >= p_vector->size )\r
 355         {\r
 356                 /* Resize to accomodate the given index. */\r
 357                 status = cl_vector_set_size( p_vector, index + 1 );\r
 358 \r
 359                 /* Check for failure on or before the given index. */\r
 360                 if( (status != CL_SUCCESS) && (p_vector->size < index) )\r
 361                         return( status );\r
 362         }\r
 363 \r
 364         /* At this point, the array is guaranteed to be big enough */\r
 365         p_dest = cl_vector_get_ptr( p_vector, index );\r
 366         /* Sanity check! */\r
 367         CL_ASSERT( p_dest );\r
 368 \r
 369         /* Copy the data into the array */\r
 370         p_vector->pfn_copy( p_dest, p_element, p_vector->element_size );\r
 371 \r
 372         return( CL_SUCCESS );\r
 373 }\r
 374 \r
 375 \r
 376 cl_status_t\r
 377 cl_vector_set_capacity(\r
 378         IN      cl_vector_t* const      p_vector,\r
 379         IN      const size_t            new_capacity )\r
 380 {\r
 381         size_t                  new_elements;\r
 382         size_t                  alloc_size;\r
 383         size_t                  i;\r
 384         cl_list_item_t  *p_buf;\r
 385         void                    *p_new_ptr_array;\r
 386 \r
 387         CL_ASSERT( p_vector );\r
 388         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 389 \r
 390         /* Do we have to do anything here? */\r
 391         if( new_capacity <= p_vector->capacity )\r
 392         {\r
 393                 /* Nope */\r
 394                 return( CL_SUCCESS );\r
 395         }\r
 396 \r
 397         /* Allocate our pointer array. */\r
 398         p_new_ptr_array = cl_zalloc( new_capacity * sizeof(void*) );\r
 399         if( !p_new_ptr_array )\r
 400                 return( CL_INSUFFICIENT_MEMORY );\r
 401 \r
 402         if( p_vector->p_ptr_array )\r
 403         {\r
 404                 /* Copy the old pointer array into the new. */\r
 405                 cl_memcpy( p_new_ptr_array, p_vector->p_ptr_array,\r
 406                         p_vector->capacity * sizeof(void*) );\r
 407 \r
 408                 /* Free the old pointer array. */\r
 409                 cl_free( p_vector->p_ptr_array );\r
 410         }\r
 411 \r
 412         /* Set the new array. */\r
 413         p_vector->p_ptr_array = p_new_ptr_array;\r
 414 \r
 415         /*\r
 416          * We have to add capacity to the array.  Determine how many\r
 417          * elements to add.\r
 418          */\r
 419         new_elements = new_capacity - p_vector->capacity;\r
 420         /* Determine the allocation size for the new array elements. */\r
 421         alloc_size = new_elements * p_vector->element_size;\r
 422 \r
 423         p_buf = (cl_list_item_t*)cl_zalloc( alloc_size + sizeof(cl_list_item_t) );\r
 424         if( !p_buf )\r
 425                 return( CL_INSUFFICIENT_MEMORY );\r
 426 \r
 427         cl_qlist_insert_tail( &p_vector->alloc_list, p_buf );\r
 428         /* Advance the buffer pointer past the list item. */\r
 429         p_buf++;\r
 430 \r
 431         for( i = p_vector->capacity; i < new_capacity; i++ )\r
 432         {\r
 433                 p_vector->p_ptr_array[i] = p_buf;\r
 434                 /* Move the buffer pointer to the next element. */\r
 435                 p_buf = (void*)(((uint8_t*)p_buf) + p_vector->element_size);\r
 436         }\r
 437 \r
 438         /* Update the vector with the new capactity. */\r
 439         p_vector->capacity = new_capacity;\r
 440 \r
 441         return( CL_SUCCESS );\r
 442 }\r
 443 \r
 444 \r
 445 cl_status_t\r
 446 cl_vector_set_size(\r
 447         IN      cl_vector_t* const      p_vector,\r
 448         IN      const size_t            size )\r
 449 {\r
 450         cl_status_t     status;\r
 451         size_t          new_capacity;\r
 452         size_t          index;\r
 453         void            *p_element;\r
 454 \r
 455         CL_ASSERT( p_vector );\r
 456         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 457 \r
 458         /* Check to see if the requested size is the same as the existing size. */\r
 459         if( size == p_vector->size )\r
 460                 return( CL_SUCCESS );\r
 461 \r
 462         /* Determine if the vector has room for this element. */\r
 463         if( size > p_vector->capacity )\r
 464         {\r
 465                 if( !p_vector->grow_size )\r
 466                         return( CL_INSUFFICIENT_MEMORY );\r
 467 \r
 468                 /* Calculate the new capacity, taking into account the grow size. */\r
 469                 new_capacity = size;\r
 470                 if( size % p_vector->grow_size )\r
 471                 {\r
 472                         /* Round up to nearest grow_size boundary. */\r
 473                         new_capacity += p_vector->grow_size -\r
 474                                 (size % p_vector->grow_size);\r
 475                 }\r
 476 \r
 477                 status = cl_vector_set_capacity( p_vector, new_capacity );\r
 478                 if( status != CL_SUCCESS )\r
 479                         return( status );\r
 480         }\r
 481 \r
 482         /* Are we growing the array and need to invoke an initializer callback? */\r
 483         if( size > p_vector->size && p_vector->pfn_init )\r
 484         {\r
 485                 for( index = p_vector->size; index < size; index++ )\r
 486                 {\r
 487                         /* Get a pointer to this element */\r
 488                         p_element = cl_vector_get_ptr( p_vector, index );\r
 489 \r
 490                         /* Call the user's initializer and trap failures. */\r
 491                         status = p_vector->pfn_init( p_element, (void*)p_vector->context );\r
 492                         if( status != CL_SUCCESS )\r
 493                         {\r
 494                                 /* Call the destructor for this object */\r
 495                                 if( p_vector->pfn_dtor )\r
 496                                         p_vector->pfn_dtor( p_element, (void*)p_vector->context );\r
 497 \r
 498                                 /* Return the failure status to the caller. */\r
 499                                 return( status );\r
 500                         }\r
 501 \r
 502                         /* The array just grew by one element */\r
 503                         p_vector->size++;\r
 504                 }\r
 505         }\r
 506         else if( p_vector->pfn_dtor )\r
 507         {\r
 508                 /* The array is shrinking and there is a destructor to invoke. */\r
 509                 for( index = size; index < p_vector->size; index++ )\r
 510                 {\r
 511                         /* compute the address of the new elements */\r
 512                         p_element = cl_vector_get_ptr( p_vector, index );\r
 513                         /* call the user's destructor */\r
 514                         p_vector->pfn_dtor( p_element, (void*)p_vector->context );\r
 515                 }\r
 516         }\r
 517 \r
 518         p_vector->size = size;\r
 519         return( CL_SUCCESS );\r
 520 }\r
 521 \r
 522 \r
 523 cl_status_t\r
 524 cl_vector_set_min_size(\r
 525         IN      cl_vector_t* const      p_vector,\r
 526         IN      const size_t            min_size )\r
 527 {\r
 528         CL_ASSERT( p_vector );\r
 529         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 530 \r
 531         if( min_size > p_vector->size )\r
 532         {\r
 533                 /* We have to resize the array */\r
 534                 return( cl_vector_set_size( p_vector, min_size ) );\r
 535         }\r
 536 \r
 537         /* We didn't have to do anything */\r
 538         return( CL_SUCCESS );\r
 539 }\r
 540 \r
 541 \r
 542 void\r
 543 cl_vector_apply_func(\r
 544         IN      const cl_vector_t* const        p_vector,\r
 545         IN      cl_pfn_vec_apply_t                      pfn_callback,\r
 546         IN      const void* const                       context )\r
 547 {\r
 548         size_t          i;\r
 549         void            *p_element;\r
 550 \r
 551         CL_ASSERT( p_vector );\r
 552         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 553         CL_ASSERT( pfn_callback );\r
 554 \r
 555         for( i = 0; i < p_vector->size; i++ )\r
 556         {\r
 557                 p_element = cl_vector_get_ptr( p_vector, i );\r
 558                 pfn_callback( i, p_element, (void*)context );\r
 559         }\r
 560 }\r
 561 \r
 562 \r
 563 size_t\r
 564 cl_vector_find_from_start(\r
 565         IN      const cl_vector_t* const        p_vector,\r
 566         IN      cl_pfn_vec_find_t                       pfn_callback,\r
 567         IN      const void* const                       context )\r
 568 {\r
 569         size_t          i;\r
 570         void            *p_element;\r
 571 \r
 572         CL_ASSERT( p_vector );\r
 573         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 574         CL_ASSERT( pfn_callback );\r
 575 \r
 576         for( i = 0; i < p_vector->size; i++ )\r
 577         {\r
 578                 p_element = cl_vector_get_ptr( p_vector, i );\r
 579                 /* Invoke the callback */\r
 580                 if( pfn_callback( i, p_element, (void*)context ) == CL_SUCCESS )\r
 581                         break;\r
 582         }\r
 583         return( i );\r
 584 }\r
 585 \r
 586 \r
 587 size_t\r
 588 cl_vector_find_from_end(\r
 589         IN      const cl_vector_t* const        p_vector,\r
 590         IN      cl_pfn_vec_find_t                       pfn_callback,\r
 591         IN      const void* const                       context )\r
 592 {\r
 593         size_t          i;\r
 594         void            *p_element;\r
 595 \r
 596         CL_ASSERT( p_vector );\r
 597         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 598         CL_ASSERT( pfn_callback );\r
 599 \r
 600         i = p_vector->size;\r
 601 \r
 602         while( i )\r
 603         {\r
 604                 /* Get a pointer to the element in the array. */\r
 605                 p_element = cl_vector_get_ptr( p_vector, --i );\r
 606                 CL_ASSERT( p_element );\r
 607 \r
 608                 /* Invoke the callback for the current element. */\r
 609                 if( pfn_callback( i, p_element, (void*)context ) == CL_SUCCESS )\r
 610                         return( i );\r
 611         }\r
 612 \r
 613         return( p_vector->size );\r
 614 }\r
 615 \r
 616 \r
 617 \r