cl_vector.c revision 326169
12786Ssos/* 22786Ssos * Copyright (c) 2004-2006 Voltaire, Inc. All rights reserved. 32786Ssos * Copyright (c) 2002-2005 Mellanox Technologies LTD. All rights reserved. 42786Ssos * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. 52786Ssos * 632822Syokota * This software is available to you under a choice of one of two 72786Ssos * licenses. You may choose to be licensed under the terms of the GNU 82786Ssos * General Public License (GPL) Version 2, available from the file 92786Ssos * COPYING in the main directory of this source tree, or the 102786Ssos * OpenIB.org BSD license below: 112786Ssos * 122786Ssos * Redistribution and use in source and binary forms, with or 132786Ssos * without modification, are permitted provided that the following 142786Ssos * conditions are met: 152786Ssos * 162786Ssos * - Redistributions of source code must retain the above 172786Ssos * copyright notice, this list of conditions and the following 182786Ssos * disclaimer. 197420Ssos * 202786Ssos * - Redistributions in binary form must reproduce the above 212786Ssos * copyright notice, this list of conditions and the following 222786Ssos * disclaimer in the documentation and/or other materials 232786Ssos * provided with the distribution. 242786Ssos * 252786Ssos * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 262786Ssos * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 272786Ssos * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 282786Ssos * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 292786Ssos * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 302786Ssos * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 312786Ssos * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 322786Ssos * SOFTWARE. 332786Ssos * 342786Ssos */ 352786Ssos 362786Ssos/* 372786Ssos * Abstract: 382786Ssos * This file contains ivector and isvector implementations. 392786Ssos * 402786Ssos */ 412786Ssos 422786Ssos#if HAVE_CONFIG_H 432786Ssos# include <config.h> 442786Ssos#endif /* HAVE_CONFIG_H */ 452786Ssos 462786Ssos#include <stdlib.h> 472786Ssos#include <string.h> 482786Ssos#include <complib/cl_vector.h> 492786Ssos 502786Ssos/* 512786Ssos * Define the maximum size for array pages in an cl_vector_t. 522786Ssos * This size is in objects, not bytes. 532786Ssos */ 542786Ssos#define SVEC_MAX_PAGE_SIZE 0x1000 552786Ssos 562786Ssos/* 572786Ssos * cl_vector_copy_general 582786Ssos * 592786Ssos * Description: 602786Ssos * copy operator used when size of the user object doesn't fit one of the 612786Ssos * other optimized copy functions. 6232822Syokota * 632786Ssos * Inputs: 642786Ssos * p_src - source for copy 652786Ssos * 662786Ssos * Outputs: 672786Ssos * p_dest - destination for copy 682786Ssos * 692786Ssos * Returns: 702786Ssos * None 712786Ssos * 722786Ssos */ 732786Ssosstatic void cl_vector_copy_general(OUT void *const p_dest, 742786Ssos IN const void *const p_src, 752786Ssos IN const size_t size) 762786Ssos{ 772786Ssos memcpy(p_dest, p_src, size); 782786Ssos} 792786Ssos 802786Ssos/* 815994Ssos * cl_vector_copy8 822786Ssos * 832786Ssos * Description: 842786Ssos * copy operator used when the user structure is only 8 bits long. 852786Ssos * 862786Ssos * Inputs: 872786Ssos * p_src - source for copy 886045Ssos * 892786Ssos * Outputs: 902786Ssos * p_dest - destination for copy 912786Ssos * 922786Ssos * Returns: 932786Ssos * None 9418194Ssos * 952786Ssos */ 962786Ssosstatic void cl_vector_copy8(OUT void *const p_dest, 972786Ssos IN const void *const p_src, IN const size_t size) 982786Ssos{ 992786Ssos CL_ASSERT(size == sizeof(uint8_t)); 1002786Ssos UNUSED_PARAM(size); 1012786Ssos 1022786Ssos *(uint8_t *) p_dest = *(uint8_t *) p_src; 1032786Ssos} 1042786Ssos 1052786Ssos/* 1062786Ssos * cl_vector_copy16 1072786Ssos * 1086851Ssos * Description: 1092786Ssos * copy operator used when the user structure is only 16 bits long. 1106851Ssos * 1116851Ssos * Inputs: 1126851Ssos * p_src - source for copy 113 * 114 * Outputs: 115 * p_dest - destination for copy 116 * 117 * Returns: 118 * None 119 * 120 */ 121void 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 */ 146void 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 */ 171void 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 180void 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 189cl_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 254void 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 288cl_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 302cl_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 333cl_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 400cl_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 472cl_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 487void 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 504size_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 524size_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