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