1 /*
2 * Copyright (c) 2004-2009 Voltaire, Inc. All rights reserved.
3 * Copyright (c) 2002-2005,2009 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 * Implementation of quick list, and list.
39 *
40 */
41
42 #if HAVE_CONFIG_H
43 # include <config.h>
44 #endif /* HAVE_CONFIG_H */
45
46 #include <complib/cl_qlist.h>
47 #include <complib/cl_list.h>
48
49 #define FREE_ITEM_GROW_SIZE 10
50
51 /******************************************************************************
52 IMPLEMENTATION OF QUICK LIST
53 ******************************************************************************/
cl_qlist_insert_array_head(IN cl_qlist_t * const p_list,IN cl_list_item_t * const p_array,IN uint32_t item_count,IN const uint32_t item_size)54 void cl_qlist_insert_array_head(IN cl_qlist_t * const p_list,
55 IN cl_list_item_t * const p_array,
56 IN uint32_t item_count,
57 IN const uint32_t item_size)
58 {
59 cl_list_item_t *p_item;
60
61 CL_ASSERT(p_list);
62 CL_ASSERT(p_list->state == CL_INITIALIZED);
63 CL_ASSERT(p_array);
64 CL_ASSERT(item_size >= sizeof(cl_list_item_t));
65 CL_ASSERT(item_count);
66
67 /*
68 * To add items from the array to the list in the same order as
69 * the elements appear in the array, we add them starting with
70 * the last one first. Locate the last item.
71 */
72 p_item = (cl_list_item_t *) ((uint8_t *) p_array +
73 (item_size * (item_count - 1)));
74
75 /* Continue to add all items to the list. */
76 while (item_count--) {
77 cl_qlist_insert_head(p_list, p_item);
78
79 /* Get the next object to add to the list. */
80 p_item = (cl_list_item_t *) ((uint8_t *) p_item - item_size);
81 }
82 }
83
cl_qlist_insert_array_tail(IN cl_qlist_t * const p_list,IN cl_list_item_t * const p_array,IN uint32_t item_count,IN const uint32_t item_size)84 void cl_qlist_insert_array_tail(IN cl_qlist_t * const p_list,
85 IN cl_list_item_t * const p_array,
86 IN uint32_t item_count,
87 IN const uint32_t item_size)
88 {
89 cl_list_item_t *p_item;
90
91 CL_ASSERT(p_list);
92 CL_ASSERT(p_list->state == CL_INITIALIZED);
93 CL_ASSERT(p_array);
94 CL_ASSERT(item_size >= sizeof(cl_list_item_t));
95 CL_ASSERT(item_count);
96
97 /* Set the first item to add to the list. */
98 p_item = p_array;
99
100 /* Continue to add all items to the list. */
101 while (item_count--) {
102 cl_qlist_insert_tail(p_list, p_item);
103
104 /* Get the next object to add to the list. */
105 p_item = (cl_list_item_t *) ((uint8_t *) p_item + item_size);
106 }
107 }
108
cl_qlist_insert_list_head(IN cl_qlist_t * const p_dest_list,IN cl_qlist_t * const p_src_list)109 void cl_qlist_insert_list_head(IN cl_qlist_t * const p_dest_list,
110 IN cl_qlist_t * const p_src_list)
111 {
112 #if defined( _DEBUG_ )
113 cl_list_item_t *p_item;
114 #endif
115
116 CL_ASSERT(p_dest_list);
117 CL_ASSERT(p_src_list);
118 CL_ASSERT(p_dest_list->state == CL_INITIALIZED);
119 CL_ASSERT(p_src_list->state == CL_INITIALIZED);
120
121 /*
122 * Is the src list empty?
123 * We must have this check here for code below to work.
124 */
125 if (cl_is_qlist_empty(p_src_list))
126 return;
127
128 #if defined( _DEBUG_ )
129 /* Check that all items in the source list belong there. */
130 p_item = cl_qlist_head(p_src_list);
131 while (p_item != cl_qlist_end(p_src_list)) {
132 /* All list items in the source list must point to it. */
133 CL_ASSERT(p_item->p_list == p_src_list);
134 /* Point them all to the destination list. */
135 p_item->p_list = p_dest_list;
136 p_item = cl_qlist_next(p_item);
137 }
138 #endif
139
140 /* Chain the destination list to the tail of the source list. */
141 cl_qlist_tail(p_src_list)->p_next = cl_qlist_head(p_dest_list);
142 cl_qlist_head(p_dest_list)->p_prev = cl_qlist_tail(p_src_list);
143
144 /*
145 * Update the head of the destination list to the head of
146 * the source list.
147 */
148 p_dest_list->end.p_next = cl_qlist_head(p_src_list);
149 cl_qlist_head(p_src_list)->p_prev = &p_dest_list->end;
150
151 /*
152 * Update the count of the destination to reflect the source items having
153 * been added.
154 */
155 p_dest_list->count += p_src_list->count;
156
157 /* Update source list to reflect being empty. */
158 __cl_qlist_reset(p_src_list);
159 }
160
cl_qlist_insert_list_tail(IN cl_qlist_t * const p_dest_list,IN cl_qlist_t * const p_src_list)161 void cl_qlist_insert_list_tail(IN cl_qlist_t * const p_dest_list,
162 IN cl_qlist_t * const p_src_list)
163 {
164 #if defined( _DEBUG_ )
165 cl_list_item_t *p_item;
166 #endif
167
168 CL_ASSERT(p_dest_list);
169 CL_ASSERT(p_src_list);
170 CL_ASSERT(p_dest_list->state == CL_INITIALIZED);
171 CL_ASSERT(p_src_list->state == CL_INITIALIZED);
172
173 /*
174 * Is the src list empty?
175 * We must have this check here for code below to work.
176 */
177 if (cl_is_qlist_empty(p_src_list))
178 return;
179
180 #if defined( _DEBUG_ )
181 /* Check that all items in the source list belong there. */
182 p_item = cl_qlist_head(p_src_list);
183 while (p_item != cl_qlist_end(p_src_list)) {
184 /* All list items in the source list must point to it. */
185 CL_ASSERT(p_item->p_list == p_src_list);
186 /* Point them all to the destination list. */
187 p_item->p_list = p_dest_list;
188 p_item = cl_qlist_next(p_item);
189 }
190 #endif
191
192 /* Chain the source list to the tail of the destination list. */
193 cl_qlist_tail(p_dest_list)->p_next = cl_qlist_head(p_src_list);
194 cl_qlist_head(p_src_list)->p_prev = cl_qlist_tail(p_dest_list);
195
196 /*
197 * Update the tail of the destination list to the tail of
198 * the source list.
199 */
200 p_dest_list->end.p_prev = cl_qlist_tail(p_src_list);
201 cl_qlist_tail(p_src_list)->p_next = &p_dest_list->end;
202
203 /*
204 * Update the count of the destination to reflect the source items having
205 * been added.
206 */
207 p_dest_list->count += p_src_list->count;
208
209 /* Update source list to reflect being empty. */
210 __cl_qlist_reset(p_src_list);
211 }
212
cl_is_item_in_qlist(IN const cl_qlist_t * const p_list,IN const cl_list_item_t * const p_list_item)213 boolean_t cl_is_item_in_qlist(IN const cl_qlist_t * const p_list,
214 IN const cl_list_item_t * const p_list_item)
215 {
216 const cl_list_item_t *p_temp;
217
218 CL_ASSERT(p_list);
219 CL_ASSERT(p_list_item);
220 CL_ASSERT(p_list->state == CL_INITIALIZED);
221
222 /* Traverse looking for a match */
223 p_temp = cl_qlist_head(p_list);
224 while (p_temp != cl_qlist_end(p_list)) {
225 if (p_temp == p_list_item) {
226 CL_ASSERT(p_list_item->p_list == p_list);
227 return (TRUE);
228 }
229
230 p_temp = cl_qlist_next(p_temp);
231 }
232
233 return (FALSE);
234 }
235
cl_qlist_find_next(IN const cl_qlist_t * const p_list,IN const cl_list_item_t * const p_list_item,IN cl_pfn_qlist_find_t pfn_func,IN const void * const context)236 cl_list_item_t *cl_qlist_find_next(IN const cl_qlist_t * const p_list,
237 IN const cl_list_item_t * const p_list_item,
238 IN cl_pfn_qlist_find_t pfn_func,
239 IN const void *const context)
240 {
241 cl_list_item_t *p_found_item;
242
243 CL_ASSERT(p_list);
244 CL_ASSERT(p_list->state == CL_INITIALIZED);
245 CL_ASSERT(p_list_item);
246 CL_ASSERT(p_list_item->p_list == p_list);
247 CL_ASSERT(pfn_func);
248
249 p_found_item = cl_qlist_next(p_list_item);
250
251 /* The user provided a compare function */
252 while (p_found_item != cl_qlist_end(p_list)) {
253 CL_ASSERT(p_found_item->p_list == p_list);
254
255 if (pfn_func(p_found_item, (void *)context) == CL_SUCCESS)
256 break;
257
258 p_found_item = cl_qlist_next(p_found_item);
259 }
260
261 /* No match */
262 return (p_found_item);
263 }
264
cl_qlist_find_prev(IN const cl_qlist_t * const p_list,IN const cl_list_item_t * const p_list_item,IN cl_pfn_qlist_find_t pfn_func,IN const void * const context)265 cl_list_item_t *cl_qlist_find_prev(IN const cl_qlist_t * const p_list,
266 IN const cl_list_item_t * const p_list_item,
267 IN cl_pfn_qlist_find_t pfn_func,
268 IN const void *const context)
269 {
270 cl_list_item_t *p_found_item;
271
272 CL_ASSERT(p_list);
273 CL_ASSERT(p_list->state == CL_INITIALIZED);
274 CL_ASSERT(p_list_item);
275 CL_ASSERT(p_list_item->p_list == p_list);
276 CL_ASSERT(pfn_func);
277
278 p_found_item = cl_qlist_prev(p_list_item);
279
280 /* The user provided a compare function */
281 while (p_found_item != cl_qlist_end(p_list)) {
282 CL_ASSERT(p_found_item->p_list == p_list);
283
284 if (pfn_func(p_found_item, (void *)context) == CL_SUCCESS)
285 break;
286
287 p_found_item = cl_qlist_prev(p_found_item);
288 }
289
290 /* No match */
291 return (p_found_item);
292 }
293
cl_qlist_apply_func(IN const cl_qlist_t * const p_list,IN cl_pfn_qlist_apply_t pfn_func,IN const void * const context)294 void cl_qlist_apply_func(IN const cl_qlist_t * const p_list,
295 IN cl_pfn_qlist_apply_t pfn_func,
296 IN const void *const context)
297 {
298 cl_list_item_t *p_list_item;
299
300 /* Note that context can have any arbitrary value. */
301 CL_ASSERT(p_list);
302 CL_ASSERT(p_list->state == CL_INITIALIZED);
303 CL_ASSERT(pfn_func);
304
305 p_list_item = cl_qlist_head(p_list);
306 while (p_list_item != cl_qlist_end(p_list)) {
307 pfn_func(p_list_item, (void *)context);
308 p_list_item = cl_qlist_next(p_list_item);
309 }
310 }
311
cl_qlist_move_items(IN cl_qlist_t * const p_src_list,IN cl_qlist_t * const p_dest_list,IN cl_pfn_qlist_find_t pfn_func,IN const void * const context)312 void cl_qlist_move_items(IN cl_qlist_t * const p_src_list,
313 IN cl_qlist_t * const p_dest_list,
314 IN cl_pfn_qlist_find_t pfn_func,
315 IN const void *const context)
316 {
317 cl_list_item_t *p_current_item, *p_next;
318
319 CL_ASSERT(p_src_list);
320 CL_ASSERT(p_dest_list);
321 CL_ASSERT(p_src_list->state == CL_INITIALIZED);
322 CL_ASSERT(p_dest_list->state == CL_INITIALIZED);
323 CL_ASSERT(pfn_func);
324
325 p_current_item = cl_qlist_head(p_src_list);
326
327 while (p_current_item != cl_qlist_end(p_src_list)) {
328 /* Before we do anything, get a pointer to the next item. */
329 p_next = cl_qlist_next(p_current_item);
330
331 if (pfn_func(p_current_item, (void *)context) == CL_SUCCESS) {
332 /* Move the item from one list to the other. */
333 cl_qlist_remove_item(p_src_list, p_current_item);
334 cl_qlist_insert_tail(p_dest_list, p_current_item);
335 }
336 p_current_item = p_next;
337 }
338 }
339
340 /******************************************************************************
341 IMPLEMENTATION OF LIST
342 ******************************************************************************/
cl_list_construct(IN cl_list_t * const p_list)343 void cl_list_construct(IN cl_list_t * const p_list)
344 {
345 CL_ASSERT(p_list);
346
347 cl_qpool_construct(&p_list->list_item_pool);
348 }
349
cl_list_init(IN cl_list_t * const p_list,IN const size_t min_items)350 cl_status_t cl_list_init(IN cl_list_t * const p_list, IN const size_t min_items)
351 {
352 uint32_t grow_size;
353
354 CL_ASSERT(p_list);
355 cl_qlist_init(&p_list->list);
356
357 /*
358 * We will grow by min_items/8 items at a time, with a minimum of
359 * FREE_ITEM_GROW_SIZE.
360 */
361 grow_size = (uint32_t) min_items >> 3;
362 if (grow_size < FREE_ITEM_GROW_SIZE)
363 grow_size = FREE_ITEM_GROW_SIZE;
364
365 /* Initialize the pool of list items. */
366 return (cl_qpool_init(&p_list->list_item_pool, min_items, 0, grow_size,
367 sizeof(cl_pool_obj_t), NULL, NULL, NULL));
368 }
369
cl_list_destroy(IN cl_list_t * const p_list)370 void cl_list_destroy(IN cl_list_t * const p_list)
371 {
372 CL_ASSERT(p_list);
373
374 cl_qpool_destroy(&p_list->list_item_pool);
375 }
376
cl_list_find_cb(IN const cl_list_item_t * const p_list_item,IN void * const context)377 static cl_status_t cl_list_find_cb(IN const cl_list_item_t * const p_list_item,
378 IN void *const context)
379 {
380 CL_ASSERT(p_list_item);
381
382 if (cl_list_obj(p_list_item) == context)
383 return (CL_SUCCESS);
384
385 return (CL_NOT_FOUND);
386 }
387
cl_list_remove_object(IN cl_list_t * const p_list,IN const void * const p_object)388 cl_status_t cl_list_remove_object(IN cl_list_t * const p_list,
389 IN const void *const p_object)
390 {
391 cl_list_item_t *p_list_item;
392
393 CL_ASSERT(p_list);
394 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
395
396 /* find the item in question */
397 p_list_item =
398 cl_qlist_find_from_head(&p_list->list, cl_list_find_cb, p_object);
399 if (p_list_item != cl_qlist_end(&p_list->list)) {
400 /* remove this item */
401 cl_qlist_remove_item(&p_list->list, p_list_item);
402 cl_qpool_put(&p_list->list_item_pool,
403 (cl_pool_item_t *) p_list_item);
404 return (CL_SUCCESS);
405 }
406 return (CL_NOT_FOUND);
407 }
408
cl_is_object_in_list(IN const cl_list_t * const p_list,IN const void * const p_object)409 boolean_t cl_is_object_in_list(IN const cl_list_t * const p_list,
410 IN const void *const p_object)
411 {
412 CL_ASSERT(p_list);
413 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
414
415 return (cl_qlist_find_from_head
416 (&p_list->list, cl_list_find_cb, p_object)
417 != cl_qlist_end(&p_list->list));
418 }
419
cl_list_insert_array_head(IN cl_list_t * const p_list,IN const void * const p_array,IN uint32_t item_count,IN const uint32_t item_size)420 cl_status_t cl_list_insert_array_head(IN cl_list_t * const p_list,
421 IN const void *const p_array,
422 IN uint32_t item_count,
423 IN const uint32_t item_size)
424 {
425 cl_status_t status;
426 void *p_object;
427 uint32_t items_remain = item_count;
428
429 CL_ASSERT(p_list);
430 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
431 CL_ASSERT(p_array);
432 CL_ASSERT(item_size);
433 CL_ASSERT(item_count);
434
435 /*
436 * To add items from the array to the list in the same order as
437 * the elements appear in the array, we add them starting with
438 * the last one first. Locate the last item.
439 */
440 p_object = ((uint8_t *) p_array + (item_size * (item_count - 1)));
441
442 /* Continue to add all items to the list. */
443 while (items_remain--) {
444 status = cl_list_insert_head(p_list, p_object);
445 if (status != CL_SUCCESS) {
446 /* Remove all items that have been inserted. */
447 while (items_remain++ < (item_count - 1))
448 cl_list_remove_head(p_list);
449 return (status);
450 }
451
452 /* Get the next object to add to the list. */
453 p_object = ((uint8_t *) p_object - item_size);
454 }
455
456 return (CL_SUCCESS);
457 }
458
cl_list_insert_array_tail(IN cl_list_t * const p_list,IN const void * const p_array,IN uint32_t item_count,IN const uint32_t item_size)459 cl_status_t cl_list_insert_array_tail(IN cl_list_t * const p_list,
460 IN const void *const p_array,
461 IN uint32_t item_count,
462 IN const uint32_t item_size)
463 {
464 cl_status_t status;
465 void *p_object;
466 uint32_t items_remain = item_count;
467
468 CL_ASSERT(p_list);
469 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
470 CL_ASSERT(p_array);
471 CL_ASSERT(item_size);
472 CL_ASSERT(item_count);
473
474 /* Set the first item to add to the list. */
475 p_object = (void *)p_array;
476
477 /* Continue to add all items to the list. */
478 while (items_remain--) {
479 status = cl_list_insert_tail(p_list, p_object);
480 if (status != CL_SUCCESS) {
481 /* Remove all items that have been inserted. */
482 while (items_remain++ < (item_count - 1))
483 cl_list_remove_tail(p_list);
484 return (status);
485 }
486
487 /* Get the next object to add to the list. */
488 p_object = ((uint8_t *) p_object + item_size);
489 }
490
491 return (CL_SUCCESS);
492 }
493
cl_list_find_from_head(IN const cl_list_t * const p_list,IN cl_pfn_list_find_t pfn_func,IN const void * const context)494 cl_list_iterator_t cl_list_find_from_head(IN const cl_list_t * const p_list,
495 IN cl_pfn_list_find_t pfn_func,
496 IN const void *const context)
497 {
498 cl_status_t status;
499 cl_list_iterator_t itor;
500
501 /* Note that context can have any arbitrary value. */
502 CL_ASSERT(p_list);
503 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
504 CL_ASSERT(pfn_func);
505
506 itor = cl_list_head(p_list);
507
508 while (itor != cl_list_end(p_list)) {
509 status = pfn_func(cl_list_obj(itor), (void *)context);
510 if (status == CL_SUCCESS)
511 break;
512
513 itor = cl_list_next(itor);
514 }
515
516 /* no match */
517 return (itor);
518 }
519
cl_list_find_from_tail(IN const cl_list_t * const p_list,IN cl_pfn_list_find_t pfn_func,IN const void * const context)520 cl_list_iterator_t cl_list_find_from_tail(IN const cl_list_t * const p_list,
521 IN cl_pfn_list_find_t pfn_func,
522 IN const void *const context)
523 {
524 cl_status_t status;
525 cl_list_iterator_t itor;
526
527 /* Note that context can have any arbitrary value. */
528 CL_ASSERT(p_list);
529 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
530 CL_ASSERT(pfn_func);
531
532 itor = cl_list_tail(p_list);
533
534 while (itor != cl_list_end(p_list)) {
535 status = pfn_func(cl_list_obj(itor), (void *)context);
536 if (status == CL_SUCCESS)
537 break;
538
539 itor = cl_list_prev(itor);
540 }
541
542 /* no match */
543 return (itor);
544 }
545
cl_list_apply_func(IN const cl_list_t * const p_list,IN cl_pfn_list_apply_t pfn_func,IN const void * const context)546 void cl_list_apply_func(IN const cl_list_t * const p_list,
547 IN cl_pfn_list_apply_t pfn_func,
548 IN const void *const context)
549 {
550 cl_list_iterator_t itor;
551
552 /* Note that context can have any arbitrary value. */
553 CL_ASSERT(p_list);
554 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
555 CL_ASSERT(pfn_func);
556
557 itor = cl_list_head(p_list);
558
559 while (itor != cl_list_end(p_list)) {
560 pfn_func(cl_list_obj(itor), (void *)context);
561
562 itor = cl_list_next(itor);
563 }
564 }
565