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 } 549