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 */ 73static void 74cl_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 */ 96static void 97cl_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 */ 122void 123cl_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 */ 148void 149cl_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 */ 174void 175cl_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 184void 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 193cl_status_t 194cl_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 260void 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 294cl_status_t 295cl_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 309cl_status_t 310cl_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 341cl_status_t 342cl_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 409cl_status_t 410cl_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 481cl_status_t 482cl_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 497void 498cl_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 515size_t 516cl_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 536size_t 537cl_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} 562