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_ptr_vector.h>
49 
50 void cl_ptr_vector_construct(IN cl_ptr_vector_t * const p_vector)
51 {
52 	CL_ASSERT(p_vector);
53 
54 	memset(p_vector, 0, sizeof(cl_ptr_vector_t));
55 
56 	p_vector->state = CL_UNINITIALIZED;
57 }
58 
59 cl_status_t cl_ptr_vector_init(IN cl_ptr_vector_t * const p_vector,
60 			       IN const size_t min_size,
61 			       IN const size_t grow_size)
62 {
63 	cl_status_t status = CL_SUCCESS;
64 
65 	CL_ASSERT(p_vector);
66 
67 	cl_ptr_vector_construct(p_vector);
68 
69 	p_vector->grow_size = grow_size;
70 
71 	/*
72 	 * Set the state to initialized so that the call to set_size
73 	 * doesn't assert.
74 	 */
75 	p_vector->state = CL_INITIALIZED;
76 
77 	/* get the storage needed by the user */
78 	if (min_size) {
79 		status = cl_ptr_vector_set_size(p_vector, min_size);
80 		if (status != CL_SUCCESS)
81 			cl_ptr_vector_destroy(p_vector);
82 	}
83 
84 	return (status);
85 }
86 
87 void cl_ptr_vector_destroy(IN cl_ptr_vector_t * const p_vector)
88 {
89 	CL_ASSERT(p_vector);
90 	CL_ASSERT(cl_is_state_valid(p_vector->state));
91 
92 	/* Call the user's destructor for each element in the array. */
93 	if (p_vector->state == CL_INITIALIZED) {
94 		/* Destroy the page vector. */
95 		if (p_vector->p_ptr_array) {
96 			free((void *)p_vector->p_ptr_array);
97 			p_vector->p_ptr_array = NULL;
98 		}
99 	}
100 
101 	p_vector->state = CL_UNINITIALIZED;
102 }
103 
104 cl_status_t cl_ptr_vector_at(IN const cl_ptr_vector_t * const p_vector,
105 			     IN const size_t index, OUT void **const p_element)
106 {
107 	CL_ASSERT(p_vector);
108 	CL_ASSERT(p_vector->state == CL_INITIALIZED);
109 
110 	/* Range check */
111 	if (index >= p_vector->size)
112 		return (CL_INVALID_PARAMETER);
113 
114 	*p_element = cl_ptr_vector_get(p_vector, index);
115 	return (CL_SUCCESS);
116 }
117 
118 cl_status_t cl_ptr_vector_set(IN cl_ptr_vector_t * const p_vector,
119 			      IN const size_t index,
120 			      IN const void *const element)
121 {
122 	cl_status_t status;
123 
124 	CL_ASSERT(p_vector);
125 	CL_ASSERT(p_vector->state == CL_INITIALIZED);
126 
127 	/* Determine if the vector has room for this element. */
128 	if (index >= p_vector->size) {
129 		/* Resize to accomodate the given index. */
130 		status = cl_ptr_vector_set_size(p_vector, index + 1);
131 
132 		/* Check for failure on or before the given index. */
133 		if ((status != CL_SUCCESS) && (p_vector->size < index))
134 			return (status);
135 	}
136 
137 	/* At this point, the array is guaranteed to be big enough */
138 	p_vector->p_ptr_array[index] = element;
139 
140 	return (CL_SUCCESS);
141 }
142 
143 void *cl_ptr_vector_remove(IN cl_ptr_vector_t * const p_vector,
144 			   IN const size_t index)
145 {
146 	size_t src;
147 	const void *element;
148 
149 	CL_ASSERT(p_vector);
150 	CL_ASSERT(p_vector->state == CL_INITIALIZED);
151 	CL_ASSERT(p_vector->size > index);
152 
153 	/* Store a copy of the element to return. */
154 	element = p_vector->p_ptr_array[index];
155 	/* Shift all items above the removed item down. */
156 	if (index < --p_vector->size) {
157 		for (src = index; src < p_vector->size; src++)
158 			p_vector->p_ptr_array[src] =
159 			    p_vector->p_ptr_array[src + 1];
160 	}
161 	/* Clear the entry for the element just outside of the new upper bound. */
162 	p_vector->p_ptr_array[p_vector->size] = NULL;
163 
164 	return ((void *)element);
165 }
166 
167 cl_status_t cl_ptr_vector_set_capacity(IN cl_ptr_vector_t * const p_vector,
168 				       IN const size_t new_capacity)
169 {
170 	void *p_new_ptr_array;
171 
172 	CL_ASSERT(p_vector);
173 	CL_ASSERT(p_vector->state == CL_INITIALIZED);
174 
175 	/* Do we have to do anything here? */
176 	if (new_capacity <= p_vector->capacity) {
177 		/* Nope */
178 		return (CL_SUCCESS);
179 	}
180 
181 	/* Allocate our pointer array. */
182 	p_new_ptr_array = malloc(new_capacity * sizeof(void *));
183 	if (!p_new_ptr_array)
184 		return (CL_INSUFFICIENT_MEMORY);
185 	else
186 		memset(p_new_ptr_array, 0, new_capacity * sizeof(void *));
187 
188 	if (p_vector->p_ptr_array) {
189 		/* Copy the old pointer array into the new. */
190 		memcpy(p_new_ptr_array, p_vector->p_ptr_array,
191 		       p_vector->capacity * sizeof(void *));
192 
193 		/* Free the old pointer array. */
194 		free((void *)p_vector->p_ptr_array);
195 	}
196 
197 	/* Set the new array. */
198 	p_vector->p_ptr_array = p_new_ptr_array;
199 
200 	/* Update the vector with the new capactity. */
201 	p_vector->capacity = new_capacity;
202 
203 	return (CL_SUCCESS);
204 }
205 
206 cl_status_t cl_ptr_vector_set_size(IN cl_ptr_vector_t * const p_vector,
207 				   IN const size_t size)
208 {
209 	cl_status_t status;
210 	size_t new_capacity;
211 
212 	CL_ASSERT(p_vector);
213 	CL_ASSERT(p_vector->state == CL_INITIALIZED);
214 
215 	/* Check to see if the requested size is the same as the existing size. */
216 	if (size == p_vector->size)
217 		return (CL_SUCCESS);
218 
219 	/* Determine if the vector has room for this element. */
220 	if (size >= p_vector->capacity) {
221 		if (!p_vector->grow_size)
222 			return (CL_INSUFFICIENT_MEMORY);
223 
224 		/* Calculate the new capacity, taking into account the grow size. */
225 		new_capacity = size;
226 		if (size % p_vector->grow_size) {
227 			/* Round up to nearest grow_size boundary. */
228 			new_capacity += p_vector->grow_size -
229 			    (size % p_vector->grow_size);
230 		}
231 
232 		status = cl_ptr_vector_set_capacity(p_vector, new_capacity);
233 		if (status != CL_SUCCESS)
234 			return (status);
235 	}
236 
237 	p_vector->size = size;
238 	return (CL_SUCCESS);
239 }
240 
241 cl_status_t cl_ptr_vector_set_min_size(IN cl_ptr_vector_t * const p_vector,
242 				       IN const size_t min_size)
243 {
244 	CL_ASSERT(p_vector);
245 	CL_ASSERT(p_vector->state == CL_INITIALIZED);
246 
247 	if (min_size > p_vector->size) {
248 		/* We have to resize the array */
249 		return (cl_ptr_vector_set_size(p_vector, min_size));
250 	}
251 
252 	/* We didn't have to do anything */
253 	return (CL_SUCCESS);
254 }
255 
256 void cl_ptr_vector_apply_func(IN const cl_ptr_vector_t * const p_vector,
257 			      IN cl_pfn_ptr_vec_apply_t pfn_callback,
258 			      IN const void *const context)
259 {
260 	size_t i;
261 
262 	CL_ASSERT(p_vector);
263 	CL_ASSERT(p_vector->state == CL_INITIALIZED);
264 	CL_ASSERT(pfn_callback);
265 
266 	for (i = 0; i < p_vector->size; i++)
267 		pfn_callback(i, (void *)p_vector->p_ptr_array[i],
268 			     (void *)context);
269 }
270 
271 size_t cl_ptr_vector_find_from_start(IN const cl_ptr_vector_t * const p_vector,
272 				     IN cl_pfn_ptr_vec_find_t pfn_callback,
273 				     IN const void *const context)
274 {
275 	size_t i;
276 
277 	CL_ASSERT(p_vector);
278 	CL_ASSERT(p_vector->state == CL_INITIALIZED);
279 	CL_ASSERT(pfn_callback);
280 
281 	for (i = 0; i < p_vector->size; i++) {
282 		/* Invoke the callback */
283 		if (pfn_callback(i, (void *)p_vector->p_ptr_array[i],
284 				 (void *)context) == CL_SUCCESS) {
285 			break;
286 		}
287 	}
288 	return (i);
289 }
290 
291 size_t cl_ptr_vector_find_from_end(IN const cl_ptr_vector_t * const p_vector,
292 				   IN cl_pfn_ptr_vec_find_t pfn_callback,
293 				   IN const void *const context)
294 {
295 	size_t i;
296 
297 	CL_ASSERT(p_vector);
298 	CL_ASSERT(p_vector->state == CL_INITIALIZED);
299 	CL_ASSERT(pfn_callback);
300 
301 	i = p_vector->size;
302 
303 	while (i) {
304 		/* Invoke the callback for the current element. */
305 		i--;
306 		if (pfn_callback(i, (void *)p_vector->p_ptr_array[i],
307 				 (void *)context) == CL_SUCCESS) {
308 			return (i);
309 		}
310 	}
311 
312 	return (p_vector->size);
313 }
314