2 * Copyright (c) 2004, 2005 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.
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:
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
16 * - Redistributions of source code must retain the above
17 * copyright notice, this list of conditions and the following
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.
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
38 * This file contains pointer vector definitions. Pointer Vector provides
39 * dynmically resizable array functionality.
42 #ifndef _CL_PTR_VECTOR_H_
43 #define _CL_PTR_VECTOR_H_
45 #include <complib/cl_types.h>
48 # define BEGIN_C_DECLS extern "C" {
49 # define END_C_DECLS }
50 #else /* !__cplusplus */
51 # define BEGIN_C_DECLS
53 #endif /* __cplusplus */
56 /****h* Component Library/Pointer Vector
61 * The Pointer Vector is a self-sizing array of pointers. Like a traditonal
62 * array, a pointer vector allows efficient constant time access to elements
63 * with a specified index. A pointer vector grows transparently as the
64 * user adds elements to the array.
66 * The cl_pointer vector_t structure should be treated as opaque and should be
67 * manipulated only through the provided functions.
74 * cl_pfn_ptr_vec_apply_t, cl_pfn_ptr_vec_find_t
77 * cl_ptr_vector_set, cl_ptr_vector_obj
80 * cl_ptr_vector_construct, cl_ptr_vector_init, cl_ptr_vector_destroy
83 * cl_ptr_vector_get_capacity, cl_ptr_vector_set_capacity,
84 * cl_ptr_vector_get_size, cl_ptr_vector_set_size, cl_ptr_vector_set_min_size
85 * cl_ptr_vector_get_ptr, cl_ptr_vector_get, cl_ptr_vector_at, cl_ptr_vector_set
88 * cl_ptr_vector_find_from_start, cl_ptr_vector_find_from_end
89 * cl_ptr_vector_apply_func
91 /****d* Component Library: Pointer Vector/cl_pfn_ptr_vec_apply_t
93 * cl_pfn_ptr_vec_apply_t
96 * The cl_pfn_ptr_vec_apply_t function type defines the prototype for
97 * functions used to iterate elements in a pointer vector.
102 (*cl_pfn_ptr_vec_apply_t) (IN const size_t index,
103 IN void *const element, IN void *context);
107 * [in] Index of the element.
110 * [in] Pointer to an element at the specified index in the pointer vector.
113 * [in] Context provided in a call to cl_ptr_vector_apply_func.
116 * This function does not return a value.
119 * This function type is provided as function prototype reference for
120 * the function passed by users as a parameter to the cl_ptr_vector_apply_func
124 * Pointer Vector, cl_ptr_vector_apply_func
127 /****d* Component Library: Pointer Vector/cl_pfn_ptr_vec_find_t
129 * cl_pfn_ptr_vec_find_t
132 * The cl_pfn_ptr_vec_find_t function type defines the prototype for
133 * functions used to find elements in a pointer vector.
138 (*cl_pfn_ptr_vec_find_t) (IN const size_t index,
139 IN const void *const element, IN void *context);
143 * [in] Index of the element.
146 * [in] Pointer to an element at the specified index in the
150 * [in] Context provided in a call to cl_ptr_vector_find_from_start or
151 * cl_ptr_vector_find_from_end.
154 * Return CL_SUCCESS if the element was found. This stops pointer vector
157 * CL_NOT_FOUND to continue the pointer vector iteration.
160 * This function type is provided as function prototype reference for the
161 * function provided by users as a parameter to the
162 * cl_ptr_vector_find_from_start and cl_ptr_vector_find_from_end functions.
165 * Pointer Vector, cl_ptr_vector_find_from_start, cl_ptr_vector_find_from_end
168 /****s* Component Library: Pointer Vector/cl_ptr_vector_t
173 * Pointer Vector structure.
175 * The cl_ptr_vector_t structure should be treated as opaque and should be
176 * manipulated only through the provided functions.
180 typedef struct _cl_ptr_vector {
184 const void **p_ptr_array;
190 * Number of elements successfully initialized in the pointer vector.
193 * Number of elements to allocate when growing.
196 * total # of elements allocated.
199 * List of allocations.
202 * Internal array of pointers to elements.
205 * State of the pointer vector.
211 /****f* Component Library: Pointer Vector/cl_ptr_vector_construct
213 * cl_ptr_vector_construct
216 * The cl_ptr_vector_construct function constructs a pointer vector.
220 void cl_ptr_vector_construct(IN cl_ptr_vector_t * const p_vector);
224 * [in] Pointer to a cl_ptr_vector_t structure to construct.
227 * This function does not return a value.
230 * Allows calling cl_ptr_vector_destroy without first calling
231 * cl_ptr_vector_init.
233 * Calling cl_ptr_vector_construct is a prerequisite to calling any other
234 * pointer vector function except cl_ptr_vector_init.
237 * Pointer Vector, cl_ptr_vector_init, cl_ptr_vector_destroy
240 /****f* Component Library: Pointer Vector/cl_ptr_vector_init
245 * The cl_ptr_vector_init function initializes a pointer vector for use.
250 cl_ptr_vector_init(IN cl_ptr_vector_t * const p_vector,
251 IN const size_t min_size, IN const size_t grow_size);
255 * [in] Pointer to a cl_ptr_vector_t structure to inititalize.
258 * [in] Initial number of elements.
261 * [in] Number of elements to allocate when incrementally growing
262 * the pointer vector. A value of zero disables automatic growth.
265 * CL_SUCCESS if the pointer vector was initialized successfully.
267 * CL_INSUFFICIENT_MEMORY if the initialization failed.
270 * Pointer Vector, cl_ptr_vector_construct, cl_ptr_vector_destroy,
271 * cl_ptr_vector_set, cl_ptr_vector_get, cl_ptr_vector_at
274 /****f* Component Library: Pointer Vector/cl_ptr_vector_destroy
276 * cl_ptr_vector_destroy
279 * The cl_ptr_vector_destroy function destroys a pointer vector.
283 void cl_ptr_vector_destroy(IN cl_ptr_vector_t * const p_vector);
287 * [in] Pointer to a cl_ptr_vector_t structure to destroy.
290 * This function does not return a value.
293 * cl_ptr_vector_destroy frees all memory allocated for the pointer vector.
295 * This function should only be called after a call to cl_ptr_vector_construct
296 * or cl_ptr_vector_init.
299 * Pointer Vector, cl_ptr_vector_construct, cl_ptr_vector_init
302 /****f* Component Library: Pointer Vector/cl_ptr_vector_get_capacity
304 * cl_ptr_vector_get_capacity
307 * The cl_ptr_vector_get_capacity function returns the capacity of
313 cl_ptr_vector_get_capacity(IN const cl_ptr_vector_t * const p_vector)
316 CL_ASSERT(p_vector->state == CL_INITIALIZED);
318 return (p_vector->capacity);
324 * [in] Pointer to a cl_ptr_vector_t structure whose capacity to return.
327 * Capacity, in elements, of the pointer vector.
330 * The capacity is the number of elements that the pointer vector can store,
331 * and can be greater than the number of elements stored. To get the number
332 * of elements stored in the pointer vector, use cl_ptr_vector_get_size.
335 * Pointer Vector, cl_ptr_vector_set_capacity, cl_ptr_vector_get_size
338 /****f* Component Library: Pointer Vector/cl_ptr_vector_get_size
340 * cl_ptr_vector_get_size
343 * The cl_ptr_vector_get_size function returns the size of a pointer vector.
347 static inline uint32_t
348 cl_ptr_vector_get_size(IN const cl_ptr_vector_t * const p_vector)
351 CL_ASSERT(p_vector->state == CL_INITIALIZED);
352 return ((uint32_t) p_vector->size);
359 * [in] Pointer to a cl_ptr_vector_t structure whose size to return.
362 * Size, in elements, of the pointer vector.
365 * Pointer Vector, cl_ptr_vector_set_size, cl_ptr_vector_get_capacity
368 /****f* Component Library: Pointer Vector/cl_ptr_vector_get
373 * The cl_ptr_vector_get function returns the pointer stored in a
374 * pointer vector at a specified index.
378 static inline void *cl_ptr_vector_get(IN const cl_ptr_vector_t * const p_vector,
379 IN const size_t index)
382 CL_ASSERT(p_vector->state == CL_INITIALIZED);
383 CL_ASSERT(p_vector->size > index);
385 return ((void *)p_vector->p_ptr_array[index]);
391 * [in] Pointer to a cl_ptr_vector_t structure from which to get an
395 * [in] Index of the element.
398 * Value of the pointer stored at the specified index.
401 * cl_ptr_vector_get provides constant access times regardless of the index.
403 * cl_ptr_vector_get does not perform boundary checking. Callers are
404 * responsible for providing an index that is within the range of the pointer
408 * Pointer Vector, cl_ptr_vector_at, cl_ptr_vector_set, cl_ptr_vector_get_size
411 /****f* Component Library: Pointer Vector/cl_ptr_vector_at
416 * The cl_ptr_vector_at function copies an element stored in a pointer
417 * vector at a specified index, performing boundary checks.
422 cl_ptr_vector_at(IN const cl_ptr_vector_t * const p_vector,
423 IN const size_t index, OUT void **const p_element);
427 * [in] Pointer to a cl_ptr_vector_t structure from which to get a copy of
431 * [in] Index of the element.
434 * [out] Pointer to storage for the pointer element. Contains a copy of
435 * the desired pointer upon successful completion of the call.
438 * CL_SUCCESS if an element was found at the specified index.
440 * CL_INVALID_SETTING if the index was out of range.
443 * cl_ptr_vector_at provides constant time access regardless of
444 * the index, and performs boundary checking on the pointer vector.
446 * Upon success, the p_element parameter contains a copy of the
450 * Pointer Vector, cl_ptr_vector_get
453 /****f* Component Library: Pointer Vector/cl_ptr_vector_set
458 * The cl_ptr_vector_set function sets the element at the specified index.
463 cl_ptr_vector_set(IN cl_ptr_vector_t * const p_vector,
464 IN const size_t index, IN const void *const element);
468 * [in] Pointer to a cl_ptr_vector_t structure into which to store
472 * [in] Index of the element.
475 * [in] Pointer to store in the pointer vector.
478 * CL_SUCCESS if the element was successfully set.
480 * CL_INSUFFICIENT_MEMORY if the pointer vector could not be resized to
481 * accommodate the new element.
484 * cl_ptr_vector_set grows the pointer vector as needed to accommodate
485 * the new element, unless the grow_size parameter passed into the
486 * cl_ptr_vector_init function was zero.
489 * Pointer Vector, cl_ptr_vector_get
492 /****f* Component Library: Pointer Vector/cl_ptr_vector_insert
494 * cl_ptr_vector_insert
497 * The cl_ptr_vector_insert function inserts an element into a pointer vector.
501 static inline cl_status_t
502 cl_ptr_vector_insert(IN cl_ptr_vector_t * const p_vector,
503 IN const void *const element,
504 OUT size_t * const p_index OPTIONAL)
509 CL_ASSERT(p_vector->state == CL_INITIALIZED);
511 status = cl_ptr_vector_set(p_vector, p_vector->size, element);
512 if (status == CL_SUCCESS && p_index)
513 *p_index = p_vector->size - 1;
521 * [in] Pointer to a cl_ptr_vector_t structure into which to store
525 * [in] Pointer to store in the pointer vector.
528 * [out] Pointer to the index of the element. Valid only if
529 * insertion was successful.
532 * CL_SUCCESS if the element was successfully inserted.
534 * CL_INSUFFICIENT_MEMORY if the pointer vector could not be resized to
535 * accommodate the new element.
538 * cl_ptr_vector_insert places the new element at the end of
539 * the pointer vector.
541 * cl_ptr_vector_insert grows the pointer vector as needed to accommodate
542 * the new element, unless the grow_size parameter passed into the
543 * cl_ptr_vector_init function was zero.
546 * Pointer Vector, cl_ptr_vector_remove, cl_ptr_vector_set
549 /****f* Component Library: Pointer Vector/cl_ptr_vector_remove
551 * cl_ptr_vector_remove
554 * The cl_ptr_vector_remove function removes and returns the pointer stored
555 * in a pointer vector at a specified index. Items beyond the removed item
556 * are shifted down and the size of the pointer vector is decremented.
560 void *cl_ptr_vector_remove(IN cl_ptr_vector_t * const p_vector,
561 IN const size_t index);
565 * [in] Pointer to a cl_ptr_vector_t structure from which to get an
569 * [in] Index of the element.
572 * Value of the pointer stored at the specified index.
575 * cl_ptr_vector_get does not perform boundary checking. Callers are
576 * responsible for providing an index that is within the range of the pointer
580 * Pointer Vector, cl_ptr_vector_insert, cl_ptr_vector_get_size
583 /****f* Component Library: Pointer Vector/cl_ptr_vector_set_capacity
585 * cl_ptr_vector_set_capacity
588 * The cl_ptr_vector_set_capacity function reserves memory in a
589 * pointer vector for a specified number of pointers.
594 cl_ptr_vector_set_capacity(IN cl_ptr_vector_t * const p_vector,
595 IN const size_t new_capacity);
599 * [in] Pointer to a cl_ptr_vector_t structure whose capacity to set.
602 * [in] Total number of elements for which the pointer vector should
606 * CL_SUCCESS if the capacity was successfully set.
608 * CL_INSUFFICIENT_MEMORY if there was not enough memory to satisfy the
609 * operation. The pointer vector is left unchanged.
612 * cl_ptr_vector_set_capacity increases the capacity of the pointer vector.
613 * It does not change the size of the pointer vector. If the requested
614 * capacity is less than the current capacity, the pointer vector is left
618 * Pointer Vector, cl_ptr_vector_get_capacity, cl_ptr_vector_set_size,
619 * cl_ptr_vector_set_min_size
622 /****f* Component Library: Pointer Vector/cl_ptr_vector_set_size
624 * cl_ptr_vector_set_size
627 * The cl_ptr_vector_set_size function resizes a pointer vector, either
628 * increasing or decreasing its size.
633 cl_ptr_vector_set_size(IN cl_ptr_vector_t * const p_vector,
634 IN const size_t size);
638 * [in] Pointer to a cl_ptr_vector_t structure whose size to set.
641 * [in] Number of elements desired in the pointer vector.
644 * CL_SUCCESS if the size of the pointer vector was set successfully.
646 * CL_INSUFFICIENT_MEMORY if there was not enough memory to complete the
647 * operation. The pointer vector is left unchanged.
650 * cl_ptr_vector_set_size sets the pointer vector to the specified size.
651 * If size is smaller than the current size of the pointer vector, the size
654 * This function can only fail if size is larger than the current capacity.
657 * Pointer Vector, cl_ptr_vector_get_size, cl_ptr_vector_set_min_size,
658 * cl_ptr_vector_set_capacity
661 /****f* Component Library: Pointer Vector/cl_ptr_vector_set_min_size
663 * cl_ptr_vector_set_min_size
666 * The cl_ptr_vector_set_min_size function resizes a pointer vector to a
667 * specified size if the pointer vector is smaller than the specified size.
672 cl_ptr_vector_set_min_size(IN cl_ptr_vector_t * const p_vector,
673 IN const size_t min_size);
677 * [in] Pointer to a cl_ptr_vector_t structure whose minimum size to set.
680 * [in] Minimum number of elements that the pointer vector should contain.
683 * CL_SUCCESS if the pointer vector size is greater than or equal to min_size.
684 * This could indicate that the pointer vector's capacity was increased to
685 * min_size or that the pointer vector was already of sufficient size.
687 * CL_INSUFFICIENT_MEMORY if there was not enough memory to resize the
688 * pointer vector. The pointer vector is left unchanged.
691 * If min_size is smaller than the current size of the pointer vector,
692 * the pointer vector is unchanged. The pointer vector is unchanged if the
693 * size could not be changed due to insufficient memory being available to
694 * perform the operation.
697 * Pointer Vector, cl_ptr_vector_get_size, cl_ptr_vector_set_size,
698 * cl_ptr_vector_set_capacity
701 /****f* Component Library: Pointer Vector/cl_ptr_vector_apply_func
703 * cl_ptr_vector_apply_func
706 * The cl_ptr_vector_apply_func function invokes a specified function for
707 * every element in a pointer vector.
712 cl_ptr_vector_apply_func(IN const cl_ptr_vector_t * const p_vector,
713 IN cl_pfn_ptr_vec_apply_t pfn_callback,
714 IN const void *const context);
718 * [in] Pointer to a cl_ptr_vector_t structure whose elements to iterate.
721 * [in] Function invoked for every element in the array.
722 * See the cl_pfn_ptr_vec_apply_t function type declaration for details
723 * about the callback function.
726 * [in] Value to pass to the callback function.
729 * This function does not return a value.
732 * cl_ptr_vector_apply_func invokes the specified function for every element
733 * in the pointer vector, starting from the beginning of the pointer vector.
736 * Pointer Vector, cl_ptr_vector_find_from_start, cl_ptr_vector_find_from_end,
737 * cl_pfn_ptr_vec_apply_t
740 /****f* Component Library: Pointer Vector/cl_ptr_vector_find_from_start
742 * cl_ptr_vector_find_from_start
745 * The cl_ptr_vector_find_from_start function uses a specified function to
746 * search for elements in a pointer vector starting from the lowest index.
751 cl_ptr_vector_find_from_start(IN const cl_ptr_vector_t * const p_vector,
752 IN cl_pfn_ptr_vec_find_t pfn_callback,
753 IN const void *const context);
757 * [in] Pointer to a cl_ptr_vector_t structure to inititalize.
760 * [in] Function invoked to determine if a match was found.
761 * See the cl_pfn_ptr_vec_find_t function type declaration for details
762 * about the callback function.
765 * [in] Value to pass to the callback function.
768 * Index of the element, if found.
770 * Size of the pointer vector if the element was not found.
773 * cl_ptr_vector_find_from_start does not remove the found element from
774 * the pointer vector. The index of the element is returned when the function
775 * provided by the pfn_callback parameter returns CL_SUCCESS.
778 * Pointer Vector, cl_ptr_vector_find_from_end, cl_ptr_vector_apply_func,
779 * cl_pfn_ptr_vec_find_t
782 /****f* Component Library: Pointer Vector/cl_ptr_vector_find_from_end
784 * cl_ptr_vector_find_from_end
787 * The cl_ptr_vector_find_from_end function uses a specified function to
788 * search for elements in a pointer vector starting from the highest index.
793 cl_ptr_vector_find_from_end(IN const cl_ptr_vector_t * const p_vector,
794 IN cl_pfn_ptr_vec_find_t pfn_callback,
795 IN const void *const context);
799 * [in] Pointer to a cl_ptr_vector_t structure to inititalize.
802 * [in] Function invoked to determine if a match was found.
803 * See the cl_pfn_ptr_vec_find_t function type declaration for details
804 * about the callback function.
807 * [in] Value to pass to the callback function.
810 * Index of the element, if found.
812 * Size of the pointer vector if the element was not found.
815 * cl_ptr_vector_find_from_end does not remove the found element from
816 * the pointer vector. The index of the element is returned when the function
817 * provided by the pfn_callback parameter returns CL_SUCCESS.
820 * Pointer Vector, cl_ptr_vector_find_from_start, cl_ptr_vector_apply_func,
821 * cl_pfn_ptr_vec_find_t
825 #endif /* _CL_PTR_VECTOR_H_ */