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 vector definitions. Vector provides dynmically
39 * resizable array functionality. Objects in a Vector are not relocated
40 * when the array is resized.
46 #include <complib/cl_qlist.h>
49 # define BEGIN_C_DECLS extern "C" {
50 # define END_C_DECLS }
51 #else /* !__cplusplus */
52 # define BEGIN_C_DECLS
54 #endif /* __cplusplus */
57 /****h* Component Library/Vector
62 * The Vector is a self-sizing array. Like a traditonal array, a vector
63 * allows efficient constant time access to elements with a specified index.
64 * A vector grows transparently as the user adds elements to the array.
66 * As the vector grows in size, it does not relocate existing elements in
67 * memory. This allows using pointers to elements stored in a Vector.
69 * Users can supply an initializer functions that allow a vector to ensure
70 * that new items added to the vector are properly initialized. A vector
71 * calls the initializer function on a per object basis when growing the
72 * array. The initializer is optional.
74 * The initializer function can fail, and returns a cl_status_t. The vector
75 * will call the destructor function, if provided, for an element that
76 * failed initialization. If an initializer fails, a vector does not call
77 * the initializer for objects in the remainder of the new memory allocation.
79 * The cl_vector_t structure should be treated as opaque and should be
80 * manipulated only through the provided functions.
87 * cl_pfn_vec_init_t, cl_pfn_vec_dtor_t, cl_pfn_vec_apply_t,
91 * cl_vector_set_obj, cl_vector_obj
94 * cl_vector_construct, cl_vector_init, cl_vector_destroy
97 * cl_vector_get_capacity, cl_vector_set_capacity,
98 * cl_vector_get_size, cl_vector_set_size, cl_vector_set_min_size
99 * cl_vector_get_ptr, cl_vector_get, cl_vector_at, cl_vector_set
102 * cl_vector_find_from_start, cl_vector_find_from_end
103 * cl_vector_apply_func
105 /****d* Component Library: Vector/cl_pfn_vec_init_t
110 * The cl_pfn_vec_init_t function type defines the prototype for functions
111 * used as initializer for elements being allocated by a vector.
116 (*cl_pfn_vec_init_t) (IN void *const p_element, IN void *context);
120 * [in] Pointer to an element being added to a vector.
123 * [in] Context provided in a call to cl_vector_init.
126 * Return CL_SUCCESS to indicate that the element was initialized successfully.
128 * Other cl_status_t values will be returned by the cl_vector_init,
129 * cl_vector_set_size, and cl_vector_set_min_size functions.
131 * In situations where the vector's size needs to grows in order to satisfy
132 * a call to cl_vector_set, a non-successful status returned by the
133 * initializer callback causes the growth to stop.
136 * This function type is provided as function prototype reference for
137 * the initializer function provided by users as an optional parameter to
138 * the cl_vector_init function.
141 * Vector, cl_vector_init
144 /****d* Component Library: Vector/cl_pfn_vec_dtor_t
149 * The cl_pfn_vec_dtor_t function type defines the prototype for functions
150 * used as destructor for elements being deallocated from a vector.
155 (*cl_pfn_vec_dtor_t) (IN void *const p_element, IN void *context);
159 * [in] Pointer to an element being deallocated from a vector.
162 * [in] Context provided in a call to cl_vector_init.
165 * This function does not return a value.
168 * This function type is provided as function prototype reference for
169 * the destructor function provided by users as an optional parameter to
170 * the cl_vector_init function.
173 * Vector, cl_vector_init
176 /****d* Component Library: Vector/cl_pfn_vec_apply_t
181 * The cl_pfn_vec_apply_t function type defines the prototype for functions
182 * used to iterate elements in a vector.
187 (*cl_pfn_vec_apply_t) (IN const size_t index,
188 IN void *const p_element, IN void *context);
192 * [in] Index of the element.
195 * [in] Pointer to an element at the specified index in the vector.
198 * [in] Context provided in a call to cl_vector_apply_func.
201 * This function does not return a value.
204 * This function type is provided as function prototype reference for
205 * the function passed by users as a parameter to the cl_vector_apply_func
209 * Vector, cl_vector_apply_func
212 /****d* Component Library: Vector/cl_pfn_vec_find_t
217 * The cl_pfn_vec_find_t function type defines the prototype for functions
218 * used to find elements in a vector.
223 (*cl_pfn_vec_find_t) (IN const size_t index,
224 IN const void *const p_element, IN void *context);
228 * [in] Index of the element.
231 * [in] Pointer to an element at the specified index in the vector.
234 * [in] Context provided in a call to cl_vector_find_from_start or
235 * cl_vector_find_from_end.
238 * Return CL_SUCCESS if the element was found. This stops vector iteration.
240 * CL_NOT_FOUND to continue the vector iteration.
243 * This function type is provided as function prototype reference for the
244 * function provided by users as a parameter to the cl_vector_find_from_start
245 * and cl_vector_find_from_end functions.
248 * Vector, cl_vector_find_from_start, cl_vector_find_from_end
251 /****i* Component Library: Vector/cl_pfn_vec_copy_t
256 * The cl_pfn_vec_copy_t function type defines the prototype for functions
257 * used to copy elements in a vector.
262 (*cl_pfn_vec_copy_t) (IN void *const p_dest,
263 IN const void *const p_src, IN const size_t size);
267 * [in] Pointer to the destination buffer into which to copy p_src.
270 * [in] Pointer to the destination buffer from which to copy.
273 * [in] Number of bytes to copy.
276 * This function does not return a value.
282 /****s* Component Library: Vector/cl_vector_t
289 * The cl_vector_t structure should be treated as opaque and should be
290 * manipulated only through the provided functions.
294 typedef struct _cl_vector {
299 cl_pfn_vec_init_t pfn_init;
300 cl_pfn_vec_dtor_t pfn_dtor;
301 cl_pfn_vec_copy_t pfn_copy;
303 cl_qlist_t alloc_list;
310 * Number of elements successfully initialized in the vector.
313 * Number of elements to allocate when growing.
316 * total # of elements allocated.
319 * Size of each element.
322 * User supplied element initializer.
325 * User supplied element destructor.
331 * User context for callbacks.
334 * List of allocations.
337 * Internal array of pointers to elements.
340 * State of the vector.
346 /****f* Component Library: Vector/cl_vector_construct
348 * cl_vector_construct
351 * The cl_vector_construct function constructs a vector.
355 void cl_vector_construct(IN cl_vector_t * const p_vector);
359 * [in] Pointer to a cl_vector_t structure to construct.
362 * This function does not return a value.
365 * Allows calling cl_vector_destroy without first calling cl_vector_init.
367 * Calling cl_vector_construct is a prerequisite to calling any other
368 * vector function except cl_vector_init.
371 * Vector, cl_vector_init, cl_vector_destroy
374 /****f* Component Library: Vector/cl_vector_init
379 * The cl_vector_init function initializes a vector for use.
384 cl_vector_init(IN cl_vector_t * const p_vector,
385 IN const size_t min_size,
386 IN const size_t grow_size,
387 IN const size_t element_size,
388 IN cl_pfn_vec_init_t pfn_init OPTIONAL,
389 IN cl_pfn_vec_dtor_t pfn_dtor OPTIONAL,
390 IN const void *const context);
394 * [in] Pointer to a cl_vector_t structure to inititalize.
397 * [in] Initial number of elements.
400 * [in] Number of elements to allocate when incrementally growing
401 * the vector. A value of zero disables automatic growth.
404 * [in] Size of each element.
407 * [in] Initializer callback to invoke for every new element.
408 * See the cl_pfn_vec_init_t function type declaration for details about
409 * the callback function.
412 * [in] Destructor callback to invoke for elements being deallocated.
413 * See the cl_pfn_vec_dtor_t function type declaration for details about
414 * the callback function.
417 * [in] Value to pass to the callback functions to provide context.
420 * CL_SUCCESS if the vector was initialized successfully.
422 * CL_INSUFFICIENT_MEMORY if the initialization failed.
424 * cl_status_t value returned by optional initializer function specified by
425 * the pfn_init parameter.
428 * The constructor and initializer functions, if any, are invoked for every
429 * new element in the array.
432 * Vector, cl_vector_construct, cl_vector_destroy, cl_vector_set,
433 * cl_vector_get, cl_vector_get_ptr, cl_vector_at
436 /****f* Component Library: Vector/cl_vector_destroy
441 * The cl_vector_destroy function destroys a vector.
445 void cl_vector_destroy(IN cl_vector_t * const p_vector);
449 * [in] Pointer to a cl_vector_t structure to destroy.
452 * This function does not return a value.
455 * cl_vector_destroy frees all memory allocated for the vector. The vector
456 * is left initialized to a zero capacity and size.
458 * This function should only be called after a call to cl_vector_construct
462 * Vector, cl_vector_construct, cl_vector_init
465 /****f* Component Library: Vector/cl_vector_get_capacity
467 * cl_vector_get_capacity
470 * The cl_vector_get_capacity function returns the capacity of a vector.
475 cl_vector_get_capacity(IN const cl_vector_t * const p_vector)
478 CL_ASSERT(p_vector->state == CL_INITIALIZED);
480 return (p_vector->capacity);
486 * [in] Pointer to a cl_vector_t structure whose capacity to return.
489 * Capacity, in elements, of the vector.
492 * The capacity is the number of elements that the vector can store, and
493 * can be greater than the number of elements stored. To get the number of
494 * elements stored in the vector, use cl_vector_get_size.
497 * Vector, cl_vector_set_capacity, cl_vector_get_size
500 /****f* Component Library: Vector/cl_vector_get_size
505 * The cl_vector_get_size function returns the size of a vector.
509 static inline size_t cl_vector_get_size(IN const cl_vector_t * const p_vector)
512 CL_ASSERT(p_vector->state == CL_INITIALIZED);
514 return (p_vector->size);
520 * [in] Pointer to a cl_vector_t structure whose size to return.
523 * Size, in elements, of the vector.
526 * Vector, cl_vector_set_size, cl_vector_get_capacity
529 /****f* Component Library: Vector/cl_vector_get_ptr
534 * The cl_vector_get_ptr function returns a pointer to an element
535 * stored in a vector at a specified index.
539 static inline void *cl_vector_get_ptr(IN const cl_vector_t * const p_vector,
540 IN const size_t index)
543 CL_ASSERT(p_vector->state == CL_INITIALIZED);
545 return (p_vector->p_ptr_array[index]);
551 * [in] Pointer to a cl_vector_t structure from which to get a
552 * pointer to an element.
555 * [in] Index of the element.
558 * Pointer to the element stored at specified index.
561 * cl_vector_get_ptr provides constant access times regardless of the index.
563 * cl_vector_get_ptr does not perform boundary checking. Callers are
564 * responsible for providing an index that is within the range of the vector.
567 * Vector, cl_vector_get, cl_vector_at, cl_vector_set, cl_vector_get_size
570 /****f* Component Library: Vector/cl_vector_get
575 * The cl_vector_get function copies an element stored in a vector at a
581 cl_vector_get(IN const cl_vector_t * const p_vector,
582 IN const size_t index, OUT void *const p_element)
587 CL_ASSERT(p_vector->state == CL_INITIALIZED);
588 CL_ASSERT(p_element);
590 /* Get a pointer to the element. */
591 p_src = cl_vector_get_ptr(p_vector, index);
592 p_vector->pfn_copy(p_src, p_element, p_vector->element_size);
598 * [in] Pointer to a cl_vector_t structure from which to get a copy of
602 * [in] Index of the element.
605 * [out] Pointer to storage for the element. Contains a copy of the
606 * desired element upon successful completion of the call.
609 * This function does not return a value.
612 * cl_vector_get provides constant time access regardless of the index.
614 * cl_vector_get does not perform boundary checking on the vector, and
615 * callers are responsible for providing an index that is within the range
616 * of the vector. To access elements after performing boundary checks,
619 * The p_element parameter contains a copy of the desired element upon
620 * return from this function.
623 * Vector, cl_vector_get_ptr, cl_vector_at
626 /****f* Component Library: Vector/cl_vector_at
631 * The cl_vector_at function copies an element stored in a vector at a
632 * specified index, performing boundary checks.
637 cl_vector_at(IN const cl_vector_t * const p_vector,
638 IN const size_t index, OUT void *const p_element);
642 * [in] Pointer to a cl_vector_t structure from which to get a copy of
646 * [in] Index of the element.
649 * [out] Pointer to storage for the element. Contains a copy of the
650 * desired element upon successful completion of the call.
653 * CL_SUCCESS if an element was found at the specified index.
655 * CL_INVALID_SETTING if the index was out of range.
658 * cl_vector_at provides constant time access regardless of the index, and
659 * performs boundary checking on the vector.
661 * Upon success, the p_element parameter contains a copy of the desired element.
664 * Vector, cl_vector_get, cl_vector_get_ptr
667 /****f* Component Library: Vector/cl_vector_set
672 * The cl_vector_set function sets the element at the specified index.
677 cl_vector_set(IN cl_vector_t * const p_vector,
678 IN const size_t index, IN void *const p_element);
682 * [in] Pointer to a cl_vector_t structure into which to store
686 * [in] Index of the element.
689 * [in] Pointer to an element to store in the vector.
692 * CL_SUCCESS if the element was successfully set.
694 * CL_INSUFFICIENT_MEMORY if the vector could not be resized to accommodate
698 * cl_vector_set grows the vector as needed to accommodate the new element,
699 * unless the grow_size parameter passed into the cl_vector_init function
703 * Vector, cl_vector_get
706 /****f* Component Library: Vector/cl_vector_set_capacity
708 * cl_vector_set_capacity
711 * The cl_vector_set_capacity function reserves memory in a vector for a
712 * specified number of elements.
717 cl_vector_set_capacity(IN cl_vector_t * const p_vector,
718 IN const size_t new_capacity);
722 * [in] Pointer to a cl_vector_t structure whose capacity to set.
725 * [in] Total number of elements for which the vector should
729 * CL_SUCCESS if the capacity was successfully set.
731 * CL_INSUFFICIENT_MEMORY if there was not enough memory to satisfy the
732 * operation. The vector is left unchanged.
735 * cl_vector_set_capacity increases the capacity of the vector. It does
736 * not change the size of the vector. If the requested capacity is less
737 * than the current capacity, the vector is left unchanged.
740 * Vector, cl_vector_get_capacity, cl_vector_set_size,
741 * cl_vector_set_min_size
744 /****f* Component Library: Vector/cl_vector_set_size
749 * The cl_vector_set_size function resizes a vector, either increasing or
750 * decreasing its size.
755 cl_vector_set_size(IN cl_vector_t * const p_vector, IN const size_t size);
759 * [in] Pointer to a cl_vector_t structure whose size to set.
762 * [in] Number of elements desired in the vector.
765 * CL_SUCCESS if the size of the vector was set successfully.
767 * CL_INSUFFICIENT_MEMORY if there was not enough memory to complete the
768 * operation. The vector is left unchanged.
771 * cl_vector_set_size sets the vector to the specified size. If size is
772 * smaller than the current size of the vector, the size is reduced.
773 * The destructor function, if any, will be invoked for all elements that
774 * are above size. Likewise, the constructor and initializer, if any, will
775 * be invoked for all new elements.
777 * This function can only fail if size is larger than the current capacity.
780 * Vector, cl_vector_get_size, cl_vector_set_min_size,
781 * cl_vector_set_capacity
784 /****f* Component Library: Vector/cl_vector_set_min_size
786 * cl_vector_set_min_size
789 * The cl_vector_set_min_size function resizes a vector to a specified size
790 * if the vector is smaller than the specified size.
795 cl_vector_set_min_size(IN cl_vector_t * const p_vector,
796 IN const size_t min_size);
800 * [in] Pointer to a cl_vector_t structure whose minimum size to set.
803 * [in] Minimum number of elements that the vector should contain.
806 * CL_SUCCESS if the vector size is greater than or equal to min_size. This
807 * could indicate that the vector's capacity was increased to min_size or
808 * that the vector was already of sufficient size.
810 * CL_INSUFFICIENT_MEMORY if there was not enough memory to resize the vector.
811 * The vector is left unchanged.
814 * If min_size is smaller than the current size of the vector, the vector is
815 * unchanged. The vector is unchanged if the size could not be changed due
816 * to insufficient memory being available to perform the operation.
819 * Vector, cl_vector_get_size, cl_vector_set_size, cl_vector_set_capacity
822 /****f* Component Library: Vector/cl_vector_apply_func
824 * cl_vector_apply_func
827 * The cl_vector_apply_func function invokes a specified function for every
828 * element in a vector.
833 cl_vector_apply_func(IN const cl_vector_t * const p_vector,
834 IN cl_pfn_vec_apply_t pfn_callback,
835 IN const void *const context);
839 * [in] Pointer to a cl_vector_t structure whose elements to iterate.
842 * [in] Function invoked for every element in the array.
843 * See the cl_pfn_vec_apply_t function type declaration for details
844 * about the callback function.
847 * [in] Value to pass to the callback function.
850 * This function does not return a value.
853 * cl_vector_apply_func invokes the specified function for every element
854 * in the vector, starting from the beginning of the vector.
857 * Vector, cl_vector_find_from_start, cl_vector_find_from_end,
861 /****f* Component Library: Vector/cl_vector_find_from_start
863 * cl_vector_find_from_start
866 * The cl_vector_find_from_start function uses a specified function to
867 * search for elements in a vector starting from the lowest index.
872 cl_vector_find_from_start(IN const cl_vector_t * const p_vector,
873 IN cl_pfn_vec_find_t pfn_callback,
874 IN const void *const context);
878 * [in] Pointer to a cl_vector_t structure to inititalize.
881 * [in] Function invoked to determine if a match was found.
882 * See the cl_pfn_vec_find_t function type declaration for details
883 * about the callback function.
886 * [in] Value to pass to the callback function.
889 * Index of the element, if found.
891 * Size of the vector if the element was not found.
894 * cl_vector_find_from_start does not remove the found element from
895 * the vector. The index of the element is returned when the function
896 * provided by the pfn_callback parameter returns CL_SUCCESS.
899 * Vector, cl_vector_find_from_end, cl_vector_apply_func, cl_pfn_vec_find_t
902 /****f* Component Library: Vector/cl_vector_find_from_end
904 * cl_vector_find_from_end
907 * The cl_vector_find_from_end function uses a specified function to search
908 * for elements in a vector starting from the highest index.
913 cl_vector_find_from_end(IN const cl_vector_t * const p_vector,
914 IN cl_pfn_vec_find_t pfn_callback,
915 IN const void *const context);
919 * [in] Pointer to a cl_vector_t structure to inititalize.
922 * [in] Function invoked to determine if a match was found.
923 * See the cl_pfn_vec_find_t function type declaration for details
924 * about the callback function.
927 * [in] Value to pass to the callback function.
930 * Index of the element, if found.
932 * Size of the vector if the element was not found.
935 * cl_vector_find_from_end does not remove the found element from
936 * the vector. The index of the element is returned when the function
937 * provided by the pfn_callback parameter returns CL_SUCCESS.
940 * Vector, cl_vector_find_from_start, cl_vector_apply_func,
945 #endif /* _CL_VECTOR_H_ */