winverbs: process connect and accept asynchronously
[mirror/winof/.git] / core / complib / cl_list.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  *\r
5  * This software is available to you under the OpenIB.org BSD license\r
6  * below:\r
7  *\r
8  *     Redistribution and use in source and binary forms, with or\r
9  *     without modification, are permitted provided that the following\r
10  *     conditions are met:\r
11  *\r
12  *      - Redistributions of source code must retain the above\r
13  *        copyright notice, this list of conditions and the following\r
14  *        disclaimer.\r
15  *\r
16  *      - Redistributions in binary form must reproduce the above\r
17  *        copyright notice, this list of conditions and the following\r
18  *        disclaimer in the documentation and/or other materials\r
19  *        provided with the distribution.\r
20  *\r
21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
22  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
23  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\r
24  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS\r
25  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN\r
26  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
27  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
28  * SOFTWARE.\r
29  *\r
30  * $Id$\r
31  */\r
32 \r
33 \r
34 \r
35 /*\r
36  * Abstract:\r
37  *      Implementation of quick list, and list.\r
38  *\r
39  * Environment:\r
40  *      All\r
41  */\r
42 \r
43 \r
44 #include <complib/cl_qlist.h>\r
45 #include <complib/cl_list.h>\r
46 \r
47 \r
48 #define FREE_ITEM_GROW_SIZE             10\r
49 \r
50 \r
51 /******************************************************************************\r
52 *******************************************************************************\r
53 **************                                                                                                     ************\r
54 **************                   IMPLEMENTATION OF QUICK LIST                      ************\r
55 **************                                                                                                     ************\r
56 *******************************************************************************\r
57 ******************************************************************************/\r
58 \r
59 void\r
60 cl_qlist_insert_array_head(\r
61         IN      cl_qlist_t* const               p_list,\r
62         IN      cl_list_item_t* const   p_array,\r
63         IN      size_t                                  item_count,\r
64         IN      const size_t                    item_size )\r
65 {\r
66         cl_list_item_t  *p_item;\r
67 \r
68         CL_ASSERT( p_list );\r
69         CL_ASSERT( p_list->state == CL_INITIALIZED );\r
70         CL_ASSERT( p_array );\r
71         CL_ASSERT( item_size >= sizeof(cl_list_item_t) );\r
72         CL_ASSERT( item_count );\r
73 \r
74         /*\r
75          * To add items from the array to the list in the same order as\r
76          * the elements appear in the array, we add them starting with\r
77          * the last one first.  Locate the last item.\r
78          */\r
79         p_item = (cl_list_item_t*)(\r
80                 (uint8_t*)p_array + (item_size * (item_count - 1)));\r
81 \r
82         /* Continue to add all items to the list. */\r
83         while( item_count-- )\r
84         {\r
85                 cl_qlist_insert_head( p_list, p_item );\r
86 \r
87                 /* Get the next object to add to the list. */\r
88                 p_item = (cl_list_item_t*)((uint8_t*)p_item - item_size);\r
89         }\r
90 }\r
91 \r
92 \r
93 void\r
94 cl_qlist_insert_array_tail(\r
95         IN      cl_qlist_t* const               p_list,\r
96         IN      cl_list_item_t* const   p_array,\r
97         IN      size_t                                  item_count,\r
98         IN      const size_t                    item_size )\r
99 {\r
100         cl_list_item_t  *p_item;\r
101 \r
102         CL_ASSERT( p_list );\r
103         CL_ASSERT( p_list->state == CL_INITIALIZED );\r
104         CL_ASSERT( p_array );\r
105         CL_ASSERT( item_size >= sizeof(cl_list_item_t) );\r
106         CL_ASSERT( item_count );\r
107 \r
108         /* Set the first item to add to the list. */\r
109         p_item = p_array;\r
110 \r
111         /* Continue to add all items to the list. */\r
112         while( item_count-- )\r
113         {\r
114                 cl_qlist_insert_tail( p_list, p_item );\r
115 \r
116                 /* Get the next object to add to the list. */\r
117                 p_item = (cl_list_item_t*)((uint8_t*)p_item + item_size);\r
118         }\r
119 }\r
120 \r
121 \r
122 void\r
123 cl_qlist_insert_list_head(\r
124         IN      cl_qlist_t* const       p_dest_list,\r
125         IN      cl_qlist_t* const       p_src_list )\r
126 {\r
127 #if defined( _DEBUG_ )\r
128         cl_list_item_t  *p_item;\r
129 #endif\r
130 \r
131         CL_ASSERT( p_dest_list );\r
132         CL_ASSERT( p_src_list );\r
133         CL_ASSERT( p_dest_list->state == CL_INITIALIZED );\r
134         CL_ASSERT( p_src_list->state == CL_INITIALIZED );\r
135 \r
136         /*\r
137          * Is the src list empty?\r
138          * We must have this check here for code below to work.\r
139          */\r
140         if( cl_is_qlist_empty( p_src_list ) )\r
141                 return;\r
142 \r
143 #if defined( _DEBUG_ )\r
144         /* Check that all items in the source list belong there. */\r
145         p_item = cl_qlist_head( p_src_list );\r
146         while( p_item != cl_qlist_end( p_src_list ) )\r
147         {\r
148                 /* All list items in the source list must point to it. */\r
149                 CL_ASSERT( p_item->p_list == p_src_list );\r
150                 /* Point them all to the destination list. */\r
151                 p_item->p_list = p_dest_list;\r
152                 p_item = cl_qlist_next( p_item );\r
153         }\r
154 #endif\r
155 \r
156         /* Chain the destination list to the tail of the source list. */\r
157         cl_qlist_tail( p_src_list )->p_next = cl_qlist_head( p_dest_list );\r
158         cl_qlist_head( p_dest_list )->p_prev = cl_qlist_tail( p_src_list );\r
159 \r
160         /*\r
161          * Update the head of the destination list to the head of\r
162          * the source list.\r
163          */\r
164         p_dest_list->end.p_next = cl_qlist_head( p_src_list );\r
165         cl_qlist_head( p_src_list )->p_prev = &p_dest_list->end;\r
166 \r
167         /*\r
168          * Update the count of the destination to reflect the source items having\r
169          * been added.\r
170          */\r
171         p_dest_list->count += p_src_list->count;\r
172 \r
173         /* Update source list to reflect being empty. */\r
174         __cl_qlist_reset( p_src_list );\r
175 }\r
176 \r
177 \r
178 void\r
179 cl_qlist_insert_list_tail(\r
180         IN      cl_qlist_t* const       p_dest_list,\r
181         IN      cl_qlist_t* const       p_src_list )\r
182 {\r
183 #if defined( _DEBUG_ )\r
184         cl_list_item_t  *p_item;\r
185 #endif\r
186 \r
187         CL_ASSERT( p_dest_list );\r
188         CL_ASSERT( p_src_list );\r
189         CL_ASSERT( p_dest_list->state == CL_INITIALIZED );\r
190         CL_ASSERT( p_src_list->state == CL_INITIALIZED );\r
191 \r
192         /*\r
193          * Is the src list empty?\r
194          * We must have this check here for code below to work.\r
195          */\r
196         if( cl_is_qlist_empty( p_src_list ) )\r
197                 return;\r
198 \r
199 #if defined( _DEBUG_ )\r
200         /* Check that all items in the source list belong there. */\r
201         p_item = cl_qlist_head( p_src_list );\r
202         while( p_item != cl_qlist_end( p_src_list ) )\r
203         {\r
204                 /* All list items in the source list must point to it. */\r
205                 CL_ASSERT( p_item->p_list == p_src_list );\r
206                 /* Point them all to the destination list. */\r
207                 p_item->p_list = p_dest_list;\r
208                 p_item = cl_qlist_next( p_item );\r
209         }\r
210 #endif\r
211 \r
212         /* Chain the source list to the tail of the destination list. */\r
213         cl_qlist_tail( p_dest_list )->p_next = cl_qlist_head( p_src_list );\r
214         cl_qlist_head( p_src_list )->p_prev = cl_qlist_tail( p_dest_list );\r
215 \r
216         /*\r
217          * Update the tail of the destination list to the tail of\r
218          * the source list.\r
219          */\r
220         p_dest_list->end.p_prev = cl_qlist_tail( p_src_list );\r
221         cl_qlist_tail( p_src_list )->p_next = &p_dest_list->end;\r
222 \r
223         /*\r
224          * Update the count of the destination to reflect the source items having\r
225          * been added.\r
226          */\r
227         p_dest_list->count += p_src_list->count;\r
228 \r
229         /* Update source list to reflect being empty. */\r
230         __cl_qlist_reset( p_src_list );\r
231 }\r
232 \r
233 \r
234 boolean_t\r
235 cl_is_item_in_qlist(\r
236         IN      const cl_qlist_t* const         p_list,\r
237         IN      const cl_list_item_t* const     p_list_item )\r
238 {\r
239         const cl_list_item_t*   p_temp;\r
240 \r
241         CL_ASSERT( p_list );\r
242         CL_ASSERT( p_list_item );\r
243         CL_ASSERT( p_list->state == CL_INITIALIZED );\r
244 \r
245         /* Traverse looking for a match */\r
246         p_temp = cl_qlist_head( p_list );\r
247         while( p_temp != cl_qlist_end( p_list ) )\r
248         {\r
249                 if( p_temp == p_list_item )\r
250                 {\r
251                         CL_ASSERT( p_list_item->p_list == p_list );\r
252                         return( TRUE );\r
253                 }\r
254 \r
255                 p_temp = cl_qlist_next( p_temp );\r
256         }\r
257 \r
258         return( FALSE );\r
259 }\r
260 \r
261 \r
262 cl_list_item_t*\r
263 cl_qlist_find_next(\r
264         IN      const cl_qlist_t* const         p_list,\r
265         IN      const cl_list_item_t* const     p_list_item,\r
266         IN      cl_pfn_qlist_find_t                     pfn_func,\r
267         IN      const void* const                       context )\r
268 {\r
269         cl_list_item_t  *p_found_item;\r
270 \r
271         CL_ASSERT( p_list );\r
272         CL_ASSERT( p_list->state == CL_INITIALIZED );\r
273         CL_ASSERT( p_list_item );\r
274         CL_ASSERT( p_list_item->p_list == p_list );\r
275         CL_ASSERT( pfn_func );\r
276 \r
277         p_found_item = cl_qlist_next( p_list_item );\r
278 \r
279         /* The user provided a compare function */\r
280         while( p_found_item != cl_qlist_end( p_list ) )\r
281         {\r
282                 CL_ASSERT( p_found_item->p_list == p_list );\r
283 \r
284                 if( pfn_func( p_found_item, (void*)context ) == CL_SUCCESS )\r
285                         break;\r
286 \r
287                 p_found_item = cl_qlist_next( p_found_item );\r
288         }\r
289 \r
290         /* No match */\r
291         return( p_found_item );\r
292 }\r
293 \r
294 \r
295 cl_list_item_t*\r
296 cl_qlist_find_prev(\r
297         IN      const cl_qlist_t* const         p_list,\r
298         IN      const cl_list_item_t* const     p_list_item,\r
299         IN      cl_pfn_qlist_find_t                     pfn_func,\r
300         IN      const void* const                       context )\r
301 {\r
302         cl_list_item_t  *p_found_item;\r
303 \r
304         CL_ASSERT( p_list );\r
305         CL_ASSERT( p_list->state == CL_INITIALIZED );\r
306         CL_ASSERT( p_list_item );\r
307         CL_ASSERT( p_list_item->p_list == p_list );\r
308         CL_ASSERT( pfn_func );\r
309 \r
310         p_found_item = cl_qlist_prev( p_list_item );\r
311 \r
312         /* The user provided a compare function */\r
313         while( p_found_item != cl_qlist_end( p_list ) )\r
314         {\r
315                 CL_ASSERT( p_found_item->p_list == p_list );\r
316 \r
317                 if( pfn_func( p_found_item, (void*)context ) == CL_SUCCESS )\r
318                         break;\r
319 \r
320                 p_found_item = cl_qlist_prev( p_found_item );\r
321         }\r
322 \r
323         /* No match */\r
324         return( p_found_item );\r
325 }\r
326 \r
327 \r
328 void\r
329 cl_qlist_apply_func(\r
330         IN      const cl_qlist_t* const p_list,\r
331         IN      cl_pfn_qlist_apply_t    pfn_func,\r
332         IN      const void* const               context )\r
333 {\r
334         cl_list_item_t* p_list_item;\r
335 \r
336         /* Note that context can have any arbitrary value. */\r
337         CL_ASSERT( p_list );\r
338         CL_ASSERT( p_list->state == CL_INITIALIZED );\r
339         CL_ASSERT( pfn_func );\r
340 \r
341         p_list_item = cl_qlist_head( p_list );\r
342         while( p_list_item != cl_qlist_end( p_list ) )\r
343         {\r
344                 pfn_func( p_list_item, (void*)context );\r
345                 p_list_item = cl_qlist_next( p_list_item );\r
346         }\r
347 }\r
348 \r
349 \r
350 void\r
351 cl_qlist_move_items(\r
352         IN      cl_qlist_t* const       p_src_list,\r
353         IN      cl_qlist_t* const       p_dest_list,\r
354         IN      cl_pfn_qlist_find_t     pfn_func,\r
355         IN      const void* const       context )\r
356 {\r
357         cl_list_item_t  *p_current_item, *p_next;\r
358 \r
359         CL_ASSERT( p_src_list );\r
360         CL_ASSERT( p_dest_list );\r
361         CL_ASSERT( p_src_list->state == CL_INITIALIZED );\r
362         CL_ASSERT( p_dest_list->state == CL_INITIALIZED );\r
363         CL_ASSERT( pfn_func );\r
364 \r
365         p_current_item = cl_qlist_head( p_src_list );\r
366 \r
367         while( p_current_item != cl_qlist_end( p_src_list ) )\r
368         {\r
369                 /* Before we do anything, get a pointer to the next item. */\r
370                 p_next = cl_qlist_next( p_current_item );\r
371 \r
372                 if( pfn_func( p_current_item, (void*)context ) == CL_SUCCESS )\r
373                 {\r
374                         /* Move the item from one list to the other. */\r
375                         cl_qlist_remove_item( p_src_list, p_current_item );\r
376                         cl_qlist_insert_tail( p_dest_list, p_current_item );\r
377                 }\r
378                 p_current_item = p_next;\r
379         }\r
380 }\r
381 \r
382 \r
383 /******************************************************************************\r
384 *******************************************************************************\r
385 **************                                                                                                     ************\r
386 **************                   IMPLEMENTATION OF LIST                                    ************\r
387 **************                                                                                                     ************\r
388 *******************************************************************************\r
389 ******************************************************************************/\r
390 \r
391 \r
392 void\r
393 cl_list_construct(\r
394         IN      cl_list_t* const        p_list )\r
395 {\r
396         CL_ASSERT( p_list );\r
397 \r
398         cl_qpool_construct( &p_list->list_item_pool );\r
399 }\r
400 \r
401 \r
402 cl_status_t\r
403 cl_list_init(\r
404         IN      cl_list_t* const        p_list,\r
405         IN      const size_t            min_items )\r
406 {\r
407         size_t  grow_size;\r
408 \r
409         CL_ASSERT( p_list );\r
410         cl_qlist_init( &p_list->list );\r
411 \r
412         /*\r
413          * We will grow by min_items/8 items at a time, with a minimum of\r
414          * FREE_ITEM_GROW_SIZE.\r
415          */\r
416         grow_size = min_items >> 3;\r
417         if( grow_size < FREE_ITEM_GROW_SIZE )\r
418                 grow_size = FREE_ITEM_GROW_SIZE;\r
419 \r
420         /* Initialize the pool of list items. */\r
421         return( cl_qpool_init( &p_list->list_item_pool, min_items, 0, grow_size,\r
422                 sizeof(cl_pool_obj_t), NULL, NULL, NULL ) );\r
423 }\r
424 \r
425 \r
426 void\r
427 cl_list_destroy(\r
428         IN      cl_list_t* const        p_list )\r
429 {\r
430         CL_ASSERT( p_list );\r
431 \r
432         cl_qpool_destroy( &p_list->list_item_pool );\r
433 }\r
434 \r
435 \r
436 static cl_status_t\r
437 cl_list_find_cb(\r
438         IN      const cl_list_item_t* const     p_list_item,\r
439         IN      void* const                                     context )\r
440 {\r
441         CL_ASSERT( p_list_item );\r
442 \r
443         if( cl_list_obj( p_list_item ) == context )\r
444                 return( CL_SUCCESS );\r
445 \r
446         return( CL_NOT_FOUND );\r
447 }\r
448 \r
449 \r
450 cl_status_t\r
451 cl_list_remove_object(\r
452         IN      cl_list_t* const        p_list,\r
453         IN      const void* const       p_object )\r
454 {\r
455         cl_list_item_t  *p_list_item;\r
456 \r
457         CL_ASSERT( p_list );\r
458         CL_ASSERT( cl_is_qpool_inited( &p_list->list_item_pool ) );\r
459 \r
460         /* find the item in question */\r
461         p_list_item =\r
462                 cl_qlist_find_from_head( &p_list->list, cl_list_find_cb, p_object );\r
463         if( p_list_item != cl_qlist_end( &p_list->list ) )\r
464         {\r
465                 /* remove this item */\r
466                 cl_qlist_remove_item( &p_list->list, p_list_item );\r
467                 cl_qpool_put( &p_list->list_item_pool, (cl_pool_item_t*)p_list_item );\r
468                 return( CL_SUCCESS );\r
469         }\r
470         return( CL_NOT_FOUND );\r
471 }\r
472 \r
473 \r
474 boolean_t\r
475 cl_is_object_in_list(\r
476         IN      const cl_list_t* const  p_list,\r
477         IN      const void* const               p_object )\r
478 {\r
479         CL_ASSERT( p_list );\r
480         CL_ASSERT( cl_is_qpool_inited( &p_list->list_item_pool ) );\r
481 \r
482         return( cl_qlist_find_from_head( &p_list->list, cl_list_find_cb, p_object )\r
483                 != cl_qlist_end( &p_list->list ) );\r
484 }\r
485 \r
486 \r
487 cl_status_t\r
488 cl_list_insert_array_head(\r
489         IN      cl_list_t* const        p_list,\r
490         IN      const void* const       p_array,\r
491         IN      uint32_t                        item_count,\r
492         IN      const uint32_t          item_size )\r
493 {\r
494         cl_status_t     status;\r
495         void            *p_object;\r
496 \r
497         CL_ASSERT( p_list );\r
498         CL_ASSERT( cl_is_qpool_inited( &p_list->list_item_pool ) );\r
499         CL_ASSERT( p_array );\r
500         CL_ASSERT( item_size );\r
501         CL_ASSERT( item_count );\r
502 \r
503         /*\r
504          * To add items from the array to the list in the same order as\r
505          * the elements appear in the array, we add them starting with\r
506          * the last one first.  Locate the last item.\r
507          */\r
508         p_object = ((uint8_t*)p_array + (item_size * (item_count - 1)));\r
509 \r
510         /* Continue to add all items to the list. */\r
511         while( item_count-- )\r
512         {\r
513                 status = cl_list_insert_head( p_list, p_object );\r
514                 if( status != CL_SUCCESS )\r
515                 {\r
516                         /* Remove all items that have been inserted. */\r
517                         while( item_count++ < item_count )\r
518                                 cl_list_remove_head( p_list );\r
519                         return( status );\r
520                 }\r
521 \r
522                 /* Get the next object to add to the list. */\r
523                 p_object = ((uint8_t*)p_object - item_size);\r
524         }\r
525 \r
526         return( CL_SUCCESS );\r
527 }\r
528 \r
529 \r
530 cl_status_t\r
531 cl_list_insert_array_tail(\r
532         IN      cl_list_t* const        p_list,\r
533         IN      const void* const       p_array,\r
534         IN      uint32_t                        item_count,\r
535         IN      const uint32_t          item_size )\r
536 {\r
537         cl_status_t     status;\r
538         void            *p_object;\r
539 \r
540         CL_ASSERT( p_list );\r
541         CL_ASSERT( cl_is_qpool_inited( &p_list->list_item_pool ) );\r
542         CL_ASSERT( p_array );\r
543         CL_ASSERT( item_size );\r
544         CL_ASSERT( item_count );\r
545 \r
546         /* Set the first item to add to the list. */\r
547         p_object = (void*)p_array;\r
548 \r
549         /* Continue to add all items to the list. */\r
550         while( item_count-- )\r
551         {\r
552                 status = cl_list_insert_tail( p_list, p_object );\r
553                 if( status != CL_SUCCESS )\r
554                 {\r
555                         /* Remove all items that have been inserted. */\r
556                         while( item_count++ < item_count )\r
557                                 cl_list_remove_tail( p_list );\r
558                         return( status );\r
559                 }\r
560 \r
561                 /* Get the next object to add to the list. */\r
562                 p_object = ((uint8_t*)p_object + item_size);\r
563         }\r
564 \r
565         return( CL_SUCCESS );\r
566 }\r
567 \r
568 \r
569 const cl_list_iterator_t\r
570 cl_list_find_from_head(\r
571         IN      const cl_list_t* const  p_list,\r
572         IN      cl_pfn_list_find_t              pfn_func,\r
573         IN      const void* const               context )\r
574 {\r
575         cl_status_t                     status;\r
576         cl_list_iterator_t      itor;\r
577 \r
578         /* Note that context can have any arbitrary value. */\r
579         CL_ASSERT( p_list );\r
580         CL_ASSERT( cl_is_qpool_inited( &p_list->list_item_pool ) );\r
581         CL_ASSERT( pfn_func );\r
582 \r
583         itor = cl_list_head( p_list );\r
584 \r
585         while( itor != cl_list_end( p_list ) )\r
586         {\r
587                 status = pfn_func( cl_list_obj( itor ), (void*)context );\r
588                 if( status == CL_SUCCESS )\r
589                         break;\r
590 \r
591                 itor = cl_list_next( itor );\r
592         }\r
593 \r
594         /* no match */\r
595         return( itor );\r
596 }\r
597 \r
598 \r
599 const cl_list_iterator_t\r
600 cl_list_find_from_tail(\r
601         IN      const cl_list_t* const  p_list,\r
602         IN      cl_pfn_list_find_t              pfn_func,\r
603         IN      const void* const               context )\r
604 {\r
605         cl_status_t                     status;\r
606         cl_list_iterator_t      itor;\r
607 \r
608         /* Note that context can have any arbitrary value. */\r
609         CL_ASSERT( p_list );\r
610         CL_ASSERT( cl_is_qpool_inited( &p_list->list_item_pool ) );\r
611         CL_ASSERT( pfn_func );\r
612 \r
613         itor = cl_list_tail( p_list );\r
614 \r
615         while( itor != cl_list_end( p_list ) )\r
616         {\r
617                 status = pfn_func( cl_list_obj( itor ), (void*)context );\r
618                 if( status == CL_SUCCESS )\r
619                         break;\r
620 \r
621                 itor = cl_list_prev( itor );\r
622         }\r
623 \r
624         /* no match */\r
625         return( itor );\r
626 }\r
627 \r
628 \r
629 void\r
630 cl_list_apply_func(\r
631         IN      const cl_list_t* const  p_list,\r
632         IN      cl_pfn_list_apply_t             pfn_func,\r
633         IN      const void* const               context )\r
634 {\r
635         cl_list_iterator_t      itor;\r
636 \r
637         /* Note that context can have any arbitrary value. */\r
638         CL_ASSERT( p_list );\r
639         CL_ASSERT( cl_is_qpool_inited( &p_list->list_item_pool ) );\r
640         CL_ASSERT( pfn_func );\r
641 \r
642         itor = cl_list_head( p_list );\r
643 \r
644         while( itor != cl_list_end( p_list ) )\r
645         {\r
646                 pfn_func( cl_list_obj( itor ), (void*)context );\r
647 \r
648                 itor = cl_list_next( itor );\r
649         }\r
650 }\r