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.
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:
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
16 * - Redistributions of source code must retain the above
17 * copyright notice, this list of conditions and the following
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.
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
38 * Implementation of quick list, and list.
44 #endif /* HAVE_CONFIG_H */
46 #include <complib/cl_qlist.h>
47 #include <complib/cl_list.h>
49 #define FREE_ITEM_GROW_SIZE 10
51 /******************************************************************************
52 *******************************************************************************
53 ************** ************
54 ************** IMPLEMENTATION OF QUICK LIST ************
55 ************** ************
56 *******************************************************************************
57 ******************************************************************************/
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)
63 cl_list_item_t *p_item;
66 CL_ASSERT(p_list->state == CL_INITIALIZED);
68 CL_ASSERT(item_size >= sizeof(cl_list_item_t));
69 CL_ASSERT(item_count);
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.
76 p_item = (cl_list_item_t *) ((uint8_t *) p_array +
77 (item_size * (item_count - 1)));
79 /* Continue to add all items to the list. */
80 while (item_count--) {
81 cl_qlist_insert_head(p_list, p_item);
83 /* Get the next object to add to the list. */
84 p_item = (cl_list_item_t *) ((uint8_t *) p_item - 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)
93 cl_list_item_t *p_item;
96 CL_ASSERT(p_list->state == CL_INITIALIZED);
98 CL_ASSERT(item_size >= sizeof(cl_list_item_t));
99 CL_ASSERT(item_count);
101 /* Set the first item to add to the list. */
104 /* Continue to add all items to the list. */
105 while (item_count--) {
106 cl_qlist_insert_tail(p_list, p_item);
108 /* Get the next object to add to the list. */
109 p_item = (cl_list_item_t *) ((uint8_t *) p_item + item_size);
114 cl_qlist_insert_list_head(IN cl_qlist_t * const p_dest_list,
115 IN cl_qlist_t * const p_src_list)
117 #if defined( _DEBUG_ )
118 cl_list_item_t *p_item;
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);
127 * Is the src list empty?
128 * We must have this check here for code below to work.
130 if (cl_is_qlist_empty(p_src_list))
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);
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);
150 * Update the head of the destination list to the head of
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;
157 * Update the count of the destination to reflect the source items having
160 p_dest_list->count += p_src_list->count;
162 /* Update source list to reflect being empty. */
163 __cl_qlist_reset(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)
170 #if defined( _DEBUG_ )
171 cl_list_item_t *p_item;
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);
180 * Is the src list empty?
181 * We must have this check here for code below to work.
183 if (cl_is_qlist_empty(p_src_list))
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);
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);
203 * Update the tail of the destination list to the tail of
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;
210 * Update the count of the destination to reflect the source items having
213 p_dest_list->count += p_src_list->count;
215 /* Update source list to reflect being empty. */
216 __cl_qlist_reset(p_src_list);
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)
223 const cl_list_item_t *p_temp;
226 CL_ASSERT(p_list_item);
227 CL_ASSERT(p_list->state == CL_INITIALIZED);
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);
237 p_temp = cl_qlist_next(p_temp);
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)
248 cl_list_item_t *p_found_item;
251 CL_ASSERT(p_list->state == CL_INITIALIZED);
252 CL_ASSERT(p_list_item);
253 CL_ASSERT(p_list_item->p_list == p_list);
256 p_found_item = cl_qlist_next(p_list_item);
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);
262 if (pfn_func(p_found_item, (void *)context) == CL_SUCCESS)
265 p_found_item = cl_qlist_next(p_found_item);
269 return (p_found_item);
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)
277 cl_list_item_t *p_found_item;
280 CL_ASSERT(p_list->state == CL_INITIALIZED);
281 CL_ASSERT(p_list_item);
282 CL_ASSERT(p_list_item->p_list == p_list);
285 p_found_item = cl_qlist_prev(p_list_item);
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);
291 if (pfn_func(p_found_item, (void *)context) == CL_SUCCESS)
294 p_found_item = cl_qlist_prev(p_found_item);
298 return (p_found_item);
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)
306 cl_list_item_t *p_list_item;
308 /* Note that context can have any arbitrary value. */
310 CL_ASSERT(p_list->state == CL_INITIALIZED);
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);
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)
326 cl_list_item_t *p_current_item, *p_next;
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);
334 p_current_item = cl_qlist_head(p_src_list);
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);
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);
345 p_current_item = p_next;
349 /******************************************************************************
350 *******************************************************************************
351 ************** ************
352 ************** IMPLEMENTATION OF LIST ************
353 ************** ************
354 *******************************************************************************
355 ******************************************************************************/
356 void cl_list_construct(IN cl_list_t * const p_list)
360 cl_qpool_construct(&p_list->list_item_pool);
363 cl_status_t cl_list_init(IN cl_list_t * const p_list, IN const size_t min_items)
368 cl_qlist_init(&p_list->list);
371 * We will grow by min_items/8 items at a time, with a minimum of
372 * FREE_ITEM_GROW_SIZE.
374 grow_size = (uint32_t) min_items >> 3;
375 if (grow_size < FREE_ITEM_GROW_SIZE)
376 grow_size = FREE_ITEM_GROW_SIZE;
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));
383 void cl_list_destroy(IN cl_list_t * const p_list)
387 cl_qpool_destroy(&p_list->list_item_pool);
391 cl_list_find_cb(IN const cl_list_item_t * const p_list_item,
392 IN void *const context)
394 CL_ASSERT(p_list_item);
396 if (cl_list_obj(p_list_item) == context)
399 return (CL_NOT_FOUND);
403 cl_list_remove_object(IN cl_list_t * const p_list,
404 IN const void *const p_object)
406 cl_list_item_t *p_list_item;
409 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
411 /* find the item in question */
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);
421 return (CL_NOT_FOUND);
425 cl_is_object_in_list(IN const cl_list_t * const p_list,
426 IN const void *const p_object)
429 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
431 return (cl_qlist_find_from_head
432 (&p_list->list, cl_list_find_cb, p_object)
433 != cl_qlist_end(&p_list->list));
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)
445 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
447 CL_ASSERT(item_size);
448 CL_ASSERT(item_count);
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.
455 p_object = ((uint8_t *) p_array + (item_size * (item_count - 1)));
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);
467 /* Get the next object to add to the list. */
468 p_object = ((uint8_t *) p_object - 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)
483 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
485 CL_ASSERT(item_size);
486 CL_ASSERT(item_count);
488 /* Set the first item to add to the list. */
489 p_object = (void *)p_array;
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);
501 /* Get the next object to add to the list. */
502 p_object = ((uint8_t *) p_object + item_size);
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)
514 cl_list_iterator_t itor;
516 /* Note that context can have any arbitrary value. */
518 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
521 itor = cl_list_head(p_list);
523 while (itor != cl_list_end(p_list)) {
524 status = pfn_func(cl_list_obj(itor), (void *)context);
525 if (status == CL_SUCCESS)
528 itor = cl_list_next(itor);
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)
541 cl_list_iterator_t itor;
543 /* Note that context can have any arbitrary value. */
545 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
548 itor = cl_list_tail(p_list);
550 while (itor != cl_list_end(p_list)) {
551 status = pfn_func(cl_list_obj(itor), (void *)context);
552 if (status == CL_SUCCESS)
555 itor = cl_list_prev(itor);
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)
567 cl_list_iterator_t itor;
569 /* Note that context can have any arbitrary value. */
571 CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
574 itor = cl_list_head(p_list);
576 while (itor != cl_list_end(p_list)) {
577 pfn_func(cl_list_obj(itor), (void *)context);
579 itor = cl_list_next(itor);