winverbs: process connect and accept asynchronously
[mirror/winof/.git] / core / complib / cl_vector.c
1 /*\r
2  * Copyright (c) 2005 SilverStorm Technologies.  All rights reserved.\r
3  * Copyright (c) 1996-2003 Intel Corporation. All rights reserved.\r
4  * Copyright (c) 2005 Mellanox Technologies, Inc. All rights reserved.\r
5  *\r
6  * This software is available to you under the OpenIB.org BSD license\r
7  * below:\r
8  *\r
9  *     Redistribution and use in source and binary forms, with or\r
10  *     without modification, are permitted provided that the following\r
11  *     conditions are met:\r
12  *\r
13  *      - Redistributions of source code must retain the above\r
14  *        copyright notice, this list of conditions and the following\r
15  *        disclaimer.\r
16  *\r
17  *      - Redistributions in binary form must reproduce the above\r
18  *        copyright notice, this list of conditions and the following\r
19  *        disclaimer in the documentation and/or other materials\r
20  *        provided with the distribution.\r
21  *\r
22  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
23  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
24  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\r
25  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS\r
26  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN\r
27  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
28  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
29  * SOFTWARE.\r
30  *\r
31  * $Id$\r
32  */\r
33 \r
34 \r
35 /*\r
36  * Abstract:\r
37  *      This file contains ivector and isvector implementations.\r
38  *\r
39  * Environment:\r
40  *      All\r
41  */\r
42 \r
43 \r
44 #include <complib/cl_vector.h>\r
45 #include <complib/cl_memory.h>\r
46 \r
47 \r
48 /*\r
49  * Define the maximum size for array pages in an cl_vector_t.\r
50  * This size is in objects, not bytes.\r
51  */\r
52 #define SVEC_MAX_PAGE_SIZE 0x1000\r
53 \r
54 \r
55 \r
56 /*\r
57  * cl_vector_copy_general\r
58  *\r
59  * Description:\r
60  *      copy operator used when size of the user object doesn't fit one of the\r
61  *      other optimized copy functions.\r
62  *\r
63  * Inputs:\r
64  *      p_src - source for copy\r
65  *\r
66  * Outputs:\r
67  *      p_dest - destination for copy\r
68  *\r
69  * Returns:\r
70  *      None\r
71  *\r
72  */\r
73 static void\r
74 cl_vector_copy_general(\r
75         OUT     void* const                     p_dest,\r
76         IN      const void* const       p_src,\r
77         IN      const size_t            size )\r
78 {\r
79         cl_memcpy( p_dest, p_src, size );\r
80 }\r
81 \r
82 \r
83 /*\r
84  * cl_vector_copy8\r
85  *\r
86  * Description:\r
87  *      copy operator used when the user structure is only 8 bits long.\r
88  *\r
89  * Inputs:\r
90  *      p_src - source for copy\r
91  *\r
92  * Outputs:\r
93  *      p_dest - destination for copy\r
94  *\r
95  * Returns:\r
96  *      None\r
97  *\r
98  */\r
99 static void\r
100 cl_vector_copy8(\r
101         OUT     void* const                     p_dest,\r
102         IN      const void* const       p_src,\r
103         IN      const size_t            size )\r
104 {\r
105         CL_ASSERT( size == sizeof(uint8_t) );\r
106         UNUSED_PARAM( size );\r
107 \r
108         *(uint8_t*)p_dest = *(uint8_t*)p_src;\r
109 }\r
110 \r
111 \r
112 /*\r
113  * cl_vector_copy16\r
114  *\r
115  * Description:\r
116  *      copy operator used when the user structure is only 16 bits long.\r
117  *\r
118  * Inputs:\r
119  *      p_src - source for copy\r
120  *\r
121  * Outputs:\r
122  *      p_dest - destination for copy\r
123  *\r
124  * Returns:\r
125  *      None\r
126  *\r
127  */\r
128 void\r
129 cl_vector_copy16(\r
130         OUT     void* const                     p_dest,\r
131         IN      const void* const       p_src,\r
132         IN      const size_t            size )\r
133 {\r
134         CL_ASSERT( size == sizeof(uint16_t) );\r
135         UNUSED_PARAM( size );\r
136 \r
137         *(uint16_t*)p_dest = *(uint16_t*)p_src;\r
138 }\r
139 \r
140 \r
141 /*\r
142  * cl_vector_copy32\r
143  *\r
144  * Description:\r
145  *      copy operator used when the user structure is only 32 bits long.\r
146  *\r
147  * Inputs:\r
148  *      p_src - source for copy\r
149  *\r
150  * Outputs:\r
151  *      p_dest - destination for copy\r
152  *\r
153  * Returns:\r
154  *      None\r
155  *\r
156  */\r
157 void\r
158 cl_vector_copy32(\r
159         OUT     void* const                     p_dest,\r
160         IN      const void* const       p_src,\r
161         IN      const size_t            size )\r
162 {\r
163         CL_ASSERT( size == sizeof(uint32_t) );\r
164         UNUSED_PARAM( size );\r
165 \r
166         *(uint32_t*)p_dest = *(uint32_t*)p_src;\r
167 }\r
168 \r
169 \r
170 /*\r
171  * cl_vector_copy64\r
172  *\r
173  * Description:\r
174  *      copy operator used when the user structure is only 64 bits long.\r
175  *\r
176  * Inputs:\r
177  *      p_src - source for copy\r
178  *\r
179  * Outputs:\r
180  *      p_dest - destination for copy\r
181  *\r
182  * Returns:\r
183  *      None\r
184  *\r
185  */\r
186 void\r
187 cl_vector_copy64(\r
188         OUT     void* const                     p_dest,\r
189         IN      const void* const       p_src,\r
190         IN      const size_t            size )\r
191 {\r
192         CL_ASSERT( size == sizeof(uint64_t) );\r
193         UNUSED_PARAM( size );\r
194 \r
195         *(uint64_t*)p_dest = *(uint64_t*)p_src;\r
196 }\r
197 \r
198 \r
199 void\r
200 cl_vector_construct(\r
201         IN      cl_vector_t* const      p_vector )\r
202 {\r
203         CL_ASSERT( p_vector );\r
204 \r
205         cl_memclr( p_vector, sizeof(cl_vector_t) );\r
206 \r
207         p_vector->state = CL_UNINITIALIZED;\r
208 }\r
209 \r
210 \r
211 cl_status_t\r
212 cl_vector_init(\r
213         IN      cl_vector_t* const      p_vector,\r
214         IN      const size_t            min_size,\r
215         IN      const size_t            grow_size,\r
216         IN      const size_t            element_size,\r
217         IN      cl_pfn_vec_init_t       pfn_init OPTIONAL,\r
218         IN      cl_pfn_vec_dtor_t       pfn_dtor OPTIONAL,\r
219         IN      const void* const       context )\r
220 {\r
221         cl_status_t     status = CL_SUCCESS;\r
222 \r
223         CL_ASSERT( p_vector );\r
224         CL_ASSERT( element_size );\r
225 \r
226         cl_vector_construct( p_vector );\r
227 \r
228         p_vector->grow_size = grow_size;\r
229         p_vector->element_size = element_size;\r
230         p_vector->pfn_init = pfn_init;\r
231         p_vector->pfn_dtor = pfn_dtor;\r
232         p_vector->context = context;\r
233 \r
234         /*\r
235          * Try to choose a smart copy operator\r
236          * someday, we could simply let the users pass one in\r
237          */\r
238         switch( element_size )\r
239         {\r
240         case sizeof(uint8_t):\r
241                 p_vector->pfn_copy = cl_vector_copy8;\r
242                 break;\r
243 \r
244         case sizeof(uint16_t):\r
245                 p_vector->pfn_copy = cl_vector_copy16;\r
246                 break;\r
247 \r
248         case sizeof(uint32_t):\r
249                 p_vector->pfn_copy = cl_vector_copy32;\r
250                 break;\r
251 \r
252         case sizeof(uint64_t):\r
253                 p_vector->pfn_copy = cl_vector_copy64;\r
254                 break;\r
255 \r
256         default:\r
257                 p_vector->pfn_copy = cl_vector_copy_general;\r
258                 break;\r
259         }\r
260 \r
261         /*\r
262          * Set the state to initialized so that the call to set_size\r
263          * doesn't assert.\r
264          */\r
265         p_vector->state = CL_INITIALIZED;\r
266 \r
267         /* Initialize the allocation list */\r
268         cl_qlist_init( &p_vector->alloc_list );\r
269 \r
270         /* get the storage needed by the user */\r
271         if( min_size )\r
272         {\r
273                 status = cl_vector_set_size( p_vector, min_size );\r
274                 if( status != CL_SUCCESS )\r
275                         cl_vector_destroy( p_vector );\r
276         }\r
277 \r
278         return( status );\r
279 }\r
280 \r
281 \r
282 void\r
283 cl_vector_destroy(\r
284         IN      cl_vector_t* const      p_vector )\r
285 {\r
286         size_t          i;\r
287         void            *p_element;\r
288 \r
289         CL_ASSERT( p_vector );\r
290         CL_ASSERT( cl_is_state_valid( p_vector->state ) );\r
291 \r
292         /* Call the user's destructor for each element in the array. */\r
293         if( p_vector->state == CL_INITIALIZED )\r
294         {\r
295                 if( p_vector->pfn_dtor )\r
296                 {\r
297                         for( i = 0; i < p_vector->size; i++ )\r
298                         {\r
299                                 p_element = p_vector->p_ptr_array[i];\r
300                                 /* Sanity check! */\r
301                                 CL_ASSERT( p_element );\r
302                                 p_vector->pfn_dtor( p_element, (void*)p_vector->context );\r
303                         }\r
304                 }\r
305 \r
306                 /* Deallocate the pages */\r
307                 while( !cl_is_qlist_empty( &p_vector->alloc_list ) )\r
308                         cl_free( cl_qlist_remove_head( &p_vector->alloc_list ) );\r
309 \r
310                 /* Destroy the page vector. */\r
311                 if( p_vector->p_ptr_array )\r
312                 {\r
313                         cl_free( p_vector->p_ptr_array );\r
314                         p_vector->p_ptr_array = NULL;\r
315                 }\r
316         }\r
317 \r
318         p_vector->state = CL_UNINITIALIZED;\r
319 }\r
320 \r
321 \r
322 cl_status_t\r
323 cl_vector_at(\r
324         IN      const cl_vector_t* const        p_vector,\r
325         IN      const size_t                            index,\r
326         OUT     void* const                                     p_element )\r
327 {\r
328         CL_ASSERT( p_vector );\r
329         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
330 \r
331         /* Range check */\r
332         if( index >= p_vector->size )\r
333                 return( CL_INVALID_PARAMETER );\r
334 \r
335         cl_vector_get( p_vector, index, p_element );\r
336         return( CL_SUCCESS );\r
337 }\r
338 \r
339 \r
340 cl_status_t\r
341 cl_vector_set(\r
342         IN      cl_vector_t* const      p_vector,\r
343         IN      const size_t            index,\r
344         IN      void* const                     p_element )\r
345 {\r
346         cl_status_t     status;\r
347         void            *p_dest;\r
348 \r
349         CL_ASSERT( p_vector );\r
350         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
351         CL_ASSERT( p_element );\r
352 \r
353         /* Determine if the vector has room for this element. */\r
354         if( index >= p_vector->size )\r
355         {\r
356                 /* Resize to accomodate the given index. */\r
357                 status = cl_vector_set_size( p_vector, index + 1 );\r
358 \r
359                 /* Check for failure on or before the given index. */\r
360                 if( (status != CL_SUCCESS) && (p_vector->size < index) )\r
361                         return( status );\r
362         }\r
363 \r
364         /* At this point, the array is guaranteed to be big enough */\r
365         p_dest = cl_vector_get_ptr( p_vector, index );\r
366         /* Sanity check! */\r
367         CL_ASSERT( p_dest );\r
368 \r
369         /* Copy the data into the array */\r
370         p_vector->pfn_copy( p_dest, p_element, p_vector->element_size );\r
371 \r
372         return( CL_SUCCESS );\r
373 }\r
374 \r
375 \r
376 cl_status_t\r
377 cl_vector_set_capacity(\r
378         IN      cl_vector_t* const      p_vector,\r
379         IN      const size_t            new_capacity )\r
380 {\r
381         size_t                  new_elements;\r
382         size_t                  alloc_size;\r
383         size_t                  i;\r
384         cl_list_item_t  *p_buf;\r
385         void                    *p_new_ptr_array;\r
386 \r
387         CL_ASSERT( p_vector );\r
388         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
389 \r
390         /* Do we have to do anything here? */\r
391         if( new_capacity <= p_vector->capacity )\r
392         {\r
393                 /* Nope */\r
394                 return( CL_SUCCESS );\r
395         }\r
396 \r
397         /* Allocate our pointer array. */\r
398         p_new_ptr_array = cl_zalloc( new_capacity * sizeof(void*) );\r
399         if( !p_new_ptr_array )\r
400                 return( CL_INSUFFICIENT_MEMORY );\r
401 \r
402         if( p_vector->p_ptr_array )\r
403         {\r
404                 /* Copy the old pointer array into the new. */\r
405                 cl_memcpy( p_new_ptr_array, p_vector->p_ptr_array,\r
406                         p_vector->capacity * sizeof(void*) );\r
407 \r
408                 /* Free the old pointer array. */\r
409                 cl_free( p_vector->p_ptr_array );\r
410         }\r
411 \r
412         /* Set the new array. */\r
413         p_vector->p_ptr_array = p_new_ptr_array;\r
414 \r
415         /*\r
416          * We have to add capacity to the array.  Determine how many\r
417          * elements to add.\r
418          */\r
419         new_elements = new_capacity - p_vector->capacity;\r
420         /* Determine the allocation size for the new array elements. */\r
421         alloc_size = new_elements * p_vector->element_size;\r
422 \r
423         p_buf = (cl_list_item_t*)cl_zalloc( alloc_size + sizeof(cl_list_item_t) );\r
424         if( !p_buf )\r
425                 return( CL_INSUFFICIENT_MEMORY );\r
426 \r
427         cl_qlist_insert_tail( &p_vector->alloc_list, p_buf );\r
428         /* Advance the buffer pointer past the list item. */\r
429         p_buf++;\r
430 \r
431         for( i = p_vector->capacity; i < new_capacity; i++ )\r
432         {\r
433                 p_vector->p_ptr_array[i] = p_buf;\r
434                 /* Move the buffer pointer to the next element. */\r
435                 p_buf = (void*)(((uint8_t*)p_buf) + p_vector->element_size);\r
436         }\r
437 \r
438         /* Update the vector with the new capactity. */\r
439         p_vector->capacity = new_capacity;\r
440 \r
441         return( CL_SUCCESS );\r
442 }\r
443 \r
444 \r
445 cl_status_t\r
446 cl_vector_set_size(\r
447         IN      cl_vector_t* const      p_vector,\r
448         IN      const size_t            size )\r
449 {\r
450         cl_status_t     status;\r
451         size_t          new_capacity;\r
452         size_t          index;\r
453         void            *p_element;\r
454 \r
455         CL_ASSERT( p_vector );\r
456         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
457 \r
458         /* Check to see if the requested size is the same as the existing size. */\r
459         if( size == p_vector->size )\r
460                 return( CL_SUCCESS );\r
461 \r
462         /* Determine if the vector has room for this element. */\r
463         if( size > p_vector->capacity )\r
464         {\r
465                 if( !p_vector->grow_size )\r
466                         return( CL_INSUFFICIENT_MEMORY );\r
467 \r
468                 /* Calculate the new capacity, taking into account the grow size. */\r
469                 new_capacity = size;\r
470                 if( size % p_vector->grow_size )\r
471                 {\r
472                         /* Round up to nearest grow_size boundary. */\r
473                         new_capacity += p_vector->grow_size -\r
474                                 (size % p_vector->grow_size);\r
475                 }\r
476 \r
477                 status = cl_vector_set_capacity( p_vector, new_capacity );\r
478                 if( status != CL_SUCCESS )\r
479                         return( status );\r
480         }\r
481 \r
482         /* Are we growing the array and need to invoke an initializer callback? */\r
483         if( size > p_vector->size && p_vector->pfn_init )\r
484         {\r
485                 for( index = p_vector->size; index < size; index++ )\r
486                 {\r
487                         /* Get a pointer to this element */\r
488                         p_element = cl_vector_get_ptr( p_vector, index );\r
489 \r
490                         /* Call the user's initializer and trap failures. */\r
491                         status = p_vector->pfn_init( p_element, (void*)p_vector->context );\r
492                         if( status != CL_SUCCESS )\r
493                         {\r
494                                 /* Call the destructor for this object */\r
495                                 if( p_vector->pfn_dtor )\r
496                                         p_vector->pfn_dtor( p_element, (void*)p_vector->context );\r
497 \r
498                                 /* Return the failure status to the caller. */\r
499                                 return( status );\r
500                         }\r
501 \r
502                         /* The array just grew by one element */\r
503                         p_vector->size++;\r
504                 }\r
505         }\r
506         else if( p_vector->pfn_dtor )\r
507         {\r
508                 /* The array is shrinking and there is a destructor to invoke. */\r
509                 for( index = size; index < p_vector->size; index++ )\r
510                 {\r
511                         /* compute the address of the new elements */\r
512                         p_element = cl_vector_get_ptr( p_vector, index );\r
513                         /* call the user's destructor */\r
514                         p_vector->pfn_dtor( p_element, (void*)p_vector->context );\r
515                 }\r
516         }\r
517 \r
518         p_vector->size = size;\r
519         return( CL_SUCCESS );\r
520 }\r
521 \r
522 \r
523 cl_status_t\r
524 cl_vector_set_min_size(\r
525         IN      cl_vector_t* const      p_vector,\r
526         IN      const size_t            min_size )\r
527 {\r
528         CL_ASSERT( p_vector );\r
529         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
530 \r
531         if( min_size > p_vector->size )\r
532         {\r
533                 /* We have to resize the array */\r
534                 return( cl_vector_set_size( p_vector, min_size ) );\r
535         }\r
536 \r
537         /* We didn't have to do anything */\r
538         return( CL_SUCCESS );\r
539 }\r
540 \r
541 \r
542 void\r
543 cl_vector_apply_func(\r
544         IN      const cl_vector_t* const        p_vector,\r
545         IN      cl_pfn_vec_apply_t                      pfn_callback,\r
546         IN      const void* const                       context )\r
547 {\r
548         size_t          i;\r
549         void            *p_element;\r
550 \r
551         CL_ASSERT( p_vector );\r
552         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
553         CL_ASSERT( pfn_callback );\r
554 \r
555         for( i = 0; i < p_vector->size; i++ )\r
556         {\r
557                 p_element = cl_vector_get_ptr( p_vector, i );\r
558                 pfn_callback( i, p_element, (void*)context );\r
559         }\r
560 }\r
561 \r
562 \r
563 size_t\r
564 cl_vector_find_from_start(\r
565         IN      const cl_vector_t* const        p_vector,\r
566         IN      cl_pfn_vec_find_t                       pfn_callback,\r
567         IN      const void* const                       context )\r
568 {\r
569         size_t          i;\r
570         void            *p_element;\r
571 \r
572         CL_ASSERT( p_vector );\r
573         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
574         CL_ASSERT( pfn_callback );\r
575 \r
576         for( i = 0; i < p_vector->size; i++ )\r
577         {\r
578                 p_element = cl_vector_get_ptr( p_vector, i );\r
579                 /* Invoke the callback */\r
580                 if( pfn_callback( i, p_element, (void*)context ) == CL_SUCCESS )\r
581                         break;\r
582         }\r
583         return( i );\r
584 }\r
585 \r
586 \r
587 size_t\r
588 cl_vector_find_from_end(\r
589         IN      const cl_vector_t* const        p_vector,\r
590         IN      cl_pfn_vec_find_t                       pfn_callback,\r
591         IN      const void* const                       context )\r
592 {\r
593         size_t          i;\r
594         void            *p_element;\r
595 \r
596         CL_ASSERT( p_vector );\r
597         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
598         CL_ASSERT( pfn_callback );\r
599 \r
600         i = p_vector->size;\r
601 \r
602         while( i )\r
603         {\r
604                 /* Get a pointer to the element in the array. */\r
605                 p_element = cl_vector_get_ptr( p_vector, --i );\r
606                 CL_ASSERT( p_element );\r
607 \r
608                 /* Invoke the callback for the current element. */\r
609                 if( pfn_callback( i, p_element, (void*)context ) == CL_SUCCESS )\r
610                         return( i );\r
611         }\r
612 \r
613         return( p_vector->size );\r
614 }\r
615 \r
616 \r
617 \r