opensm/complib/cl_list.c

/*
 * Copyright (c) 2004, 2005 Voltaire, Inc. All rights reserved.
 * Copyright (c) 2002-2005 Mellanox Technologies LTD. All rights reserved.
 * Copyright (c) 1996-2003 Intel Corporation. All rights reserved.
 *
 * This software is available to you under a choice of one of two
 * licenses.  You may choose to be licensed under the terms of the GNU
 * General Public License (GPL) Version 2, available from the file
 * COPYING in the main directory of this source tree, or the
 * OpenIB.org BSD license below:
 *
 *     Redistribution and use in source and binary forms, with or
 *     without modification, are permitted provided that the following
 *     conditions are met:
 *
 *      - Redistributions of source code must retain the above
 *        copyright notice, this list of conditions and the following
 *        disclaimer.
 *
 *      - Redistributions in binary form must reproduce the above
 *        copyright notice, this list of conditions and the following
 *        disclaimer in the documentation and/or other materials
 *        provided with the distribution.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 *
 */

/*
 * Abstract:
 *	Implementation of quick list, and list.
 *
 */

#if HAVE_CONFIG_H
#  include <config.h>
#endif				/* HAVE_CONFIG_H */

#include <complib/cl_qlist.h>
#include <complib/cl_list.h>

#define FREE_ITEM_GROW_SIZE		10

/******************************************************************************
*******************************************************************************
**************													   ************
**************			 IMPLEMENTATION OF QUICK LIST			   ************
**************													   ************
*******************************************************************************
******************************************************************************/
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)
{
	cl_list_item_t *p_item;

	CL_ASSERT(p_list);
	CL_ASSERT(p_list->state == CL_INITIALIZED);
	CL_ASSERT(p_array);
	CL_ASSERT(item_size >= sizeof(cl_list_item_t));
	CL_ASSERT(item_count);

	/*
	 * To add items from the array to the list in the same order as
	 * the elements appear in the array, we add them starting with
	 * the last one first.  Locate the last item.
	 */
	p_item = (cl_list_item_t *) ((uint8_t *) p_array +
				     (item_size * (item_count - 1)));

	/* Continue to add all items to the list. */
	while (item_count--) {
		cl_qlist_insert_head(p_list, p_item);

		/* Get the next object to add to the list. */
		p_item = (cl_list_item_t *) ((uint8_t *) p_item - item_size);
	}
}

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)
{
	cl_list_item_t *p_item;

	CL_ASSERT(p_list);
	CL_ASSERT(p_list->state == CL_INITIALIZED);
	CL_ASSERT(p_array);
	CL_ASSERT(item_size >= sizeof(cl_list_item_t));
	CL_ASSERT(item_count);

	/* Set the first item to add to the list. */
	p_item = p_array;

	/* Continue to add all items to the list. */
	while (item_count--) {
		cl_qlist_insert_tail(p_list, p_item);

		/* Get the next object to add to the list. */
		p_item = (cl_list_item_t *) ((uint8_t *) p_item + item_size);
	}
}

void
cl_qlist_insert_list_head(IN cl_qlist_t * const p_dest_list,
			  IN cl_qlist_t * const p_src_list)
{
#if defined( _DEBUG_ )
	cl_list_item_t *p_item;
#endif

	CL_ASSERT(p_dest_list);
	CL_ASSERT(p_src_list);
	CL_ASSERT(p_dest_list->state == CL_INITIALIZED);
	CL_ASSERT(p_src_list->state == CL_INITIALIZED);

	/*
	 * Is the src list empty?
	 * We must have this check here for code below to work.
	 */
	if (cl_is_qlist_empty(p_src_list))
		return;

#if defined( _DEBUG_ )
	/* Check that all items in the source list belong there. */
	p_item = cl_qlist_head(p_src_list);
	while (p_item != cl_qlist_end(p_src_list)) {
		/* All list items in the source list must point to it. */
		CL_ASSERT(p_item->p_list == p_src_list);
		/* Point them all to the destination list. */
		p_item->p_list = p_dest_list;
		p_item = cl_qlist_next(p_item);
	}
#endif

	/* Chain the destination list to the tail of the source list. */
	cl_qlist_tail(p_src_list)->p_next = cl_qlist_head(p_dest_list);
	cl_qlist_head(p_dest_list)->p_prev = cl_qlist_tail(p_src_list);

	/*
	 * Update the head of the destination list to the head of
	 * the source list.
	 */
	p_dest_list->end.p_next = cl_qlist_head(p_src_list);
	cl_qlist_head(p_src_list)->p_prev = &p_dest_list->end;

	/*
	 * Update the count of the destination to reflect the source items having
	 * been added.
	 */
	p_dest_list->count += p_src_list->count;

	/* Update source list to reflect being empty. */
	__cl_qlist_reset(p_src_list);
}

void
cl_qlist_insert_list_tail(IN cl_qlist_t * const p_dest_list,
			  IN cl_qlist_t * const p_src_list)
{
#if defined( _DEBUG_ )
	cl_list_item_t *p_item;
#endif

	CL_ASSERT(p_dest_list);
	CL_ASSERT(p_src_list);
	CL_ASSERT(p_dest_list->state == CL_INITIALIZED);
	CL_ASSERT(p_src_list->state == CL_INITIALIZED);

	/*
	 * Is the src list empty?
	 * We must have this check here for code below to work.
	 */
	if (cl_is_qlist_empty(p_src_list))
		return;

#if defined( _DEBUG_ )
	/* Check that all items in the source list belong there. */
	p_item = cl_qlist_head(p_src_list);
	while (p_item != cl_qlist_end(p_src_list)) {
		/* All list items in the source list must point to it. */
		CL_ASSERT(p_item->p_list == p_src_list);
		/* Point them all to the destination list. */
		p_item->p_list = p_dest_list;
		p_item = cl_qlist_next(p_item);
	}
#endif

	/* Chain the source list to the tail of the destination list. */
	cl_qlist_tail(p_dest_list)->p_next = cl_qlist_head(p_src_list);
	cl_qlist_head(p_src_list)->p_prev = cl_qlist_tail(p_dest_list);

	/*
	 * Update the tail of the destination list to the tail of
	 * the source list.
	 */
	p_dest_list->end.p_prev = cl_qlist_tail(p_src_list);
	cl_qlist_tail(p_src_list)->p_next = &p_dest_list->end;

	/*
	 * Update the count of the destination to reflect the source items having
	 * been added.
	 */
	p_dest_list->count += p_src_list->count;

	/* Update source list to reflect being empty. */
	__cl_qlist_reset(p_src_list);
}

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)
{
	const cl_list_item_t *p_temp;

	CL_ASSERT(p_list);
	CL_ASSERT(p_list_item);
	CL_ASSERT(p_list->state == CL_INITIALIZED);

	/* Traverse looking for a match */
	p_temp = cl_qlist_head(p_list);
	while (p_temp != cl_qlist_end(p_list)) {
		if (p_temp == p_list_item) {
			CL_ASSERT(p_list_item->p_list == p_list);
			return (TRUE);
		}

		p_temp = cl_qlist_next(p_temp);
	}

	return (FALSE);
}

cl_list_item_t *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)
{
	cl_list_item_t *p_found_item;

	CL_ASSERT(p_list);
	CL_ASSERT(p_list->state == CL_INITIALIZED);
	CL_ASSERT(p_list_item);
	CL_ASSERT(p_list_item->p_list == p_list);
	CL_ASSERT(pfn_func);

	p_found_item = cl_qlist_next(p_list_item);

	/* The user provided a compare function */
	while (p_found_item != cl_qlist_end(p_list)) {
		CL_ASSERT(p_found_item->p_list == p_list);

		if (pfn_func(p_found_item, (void *)context) == CL_SUCCESS)
			break;

		p_found_item = cl_qlist_next(p_found_item);
	}

	/* No match */
	return (p_found_item);
}

cl_list_item_t *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)
{
	cl_list_item_t *p_found_item;

	CL_ASSERT(p_list);
	CL_ASSERT(p_list->state == CL_INITIALIZED);
	CL_ASSERT(p_list_item);
	CL_ASSERT(p_list_item->p_list == p_list);
	CL_ASSERT(pfn_func);

	p_found_item = cl_qlist_prev(p_list_item);

	/* The user provided a compare function */
	while (p_found_item != cl_qlist_end(p_list)) {
		CL_ASSERT(p_found_item->p_list == p_list);

		if (pfn_func(p_found_item, (void *)context) == CL_SUCCESS)
			break;

		p_found_item = cl_qlist_prev(p_found_item);
	}

	/* No match */
	return (p_found_item);
}

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)
{
	cl_list_item_t *p_list_item;

	/* Note that context can have any arbitrary value. */
	CL_ASSERT(p_list);
	CL_ASSERT(p_list->state == CL_INITIALIZED);
	CL_ASSERT(pfn_func);

	p_list_item = cl_qlist_head(p_list);
	while (p_list_item != cl_qlist_end(p_list)) {
		pfn_func(p_list_item, (void *)context);
		p_list_item = cl_qlist_next(p_list_item);
	}
}

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)
{
	cl_list_item_t *p_current_item, *p_next;

	CL_ASSERT(p_src_list);
	CL_ASSERT(p_dest_list);
	CL_ASSERT(p_src_list->state == CL_INITIALIZED);
	CL_ASSERT(p_dest_list->state == CL_INITIALIZED);
	CL_ASSERT(pfn_func);

	p_current_item = cl_qlist_head(p_src_list);

	while (p_current_item != cl_qlist_end(p_src_list)) {
		/* Before we do anything, get a pointer to the next item. */
		p_next = cl_qlist_next(p_current_item);

		if (pfn_func(p_current_item, (void *)context) == CL_SUCCESS) {
			/* Move the item from one list to the other. */
			cl_qlist_remove_item(p_src_list, p_current_item);
			cl_qlist_insert_tail(p_dest_list, p_current_item);
		}
		p_current_item = p_next;
	}
}

/******************************************************************************
*******************************************************************************
**************													   ************
**************			 IMPLEMENTATION OF LIST					   ************
**************													   ************
*******************************************************************************
******************************************************************************/
void cl_list_construct(IN cl_list_t * const p_list)
{
	CL_ASSERT(p_list);

	cl_qpool_construct(&p_list->list_item_pool);
}

cl_status_t cl_list_init(IN cl_list_t * const p_list, IN const size_t min_items)
{
	uint32_t grow_size;

	CL_ASSERT(p_list);
	cl_qlist_init(&p_list->list);

	/*
	 * We will grow by min_items/8 items at a time, with a minimum of
	 * FREE_ITEM_GROW_SIZE.
	 */
	grow_size = (uint32_t) min_items >> 3;
	if (grow_size < FREE_ITEM_GROW_SIZE)
		grow_size = FREE_ITEM_GROW_SIZE;

	/* Initialize the pool of list items. */
	return (cl_qpool_init(&p_list->list_item_pool, min_items, 0, grow_size,
			      sizeof(cl_pool_obj_t), NULL, NULL, NULL));
}

void cl_list_destroy(IN cl_list_t * const p_list)
{
	CL_ASSERT(p_list);

	cl_qpool_destroy(&p_list->list_item_pool);
}

static cl_status_t
cl_list_find_cb(IN const cl_list_item_t * const p_list_item,
		IN void *const context)
{
	CL_ASSERT(p_list_item);

	if (cl_list_obj(p_list_item) == context)
		return (CL_SUCCESS);

	return (CL_NOT_FOUND);
}

cl_status_t
cl_list_remove_object(IN cl_list_t * const p_list,
		      IN const void *const p_object)
{
	cl_list_item_t *p_list_item;

	CL_ASSERT(p_list);
	CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));

	/* find the item in question */
	p_list_item =
	    cl_qlist_find_from_head(&p_list->list, cl_list_find_cb, p_object);
	if (p_list_item != cl_qlist_end(&p_list->list)) {
		/* remove this item */
		cl_qlist_remove_item(&p_list->list, p_list_item);
		cl_qpool_put(&p_list->list_item_pool,
			     (cl_pool_item_t *) p_list_item);
		return (CL_SUCCESS);
	}
	return (CL_NOT_FOUND);
}

boolean_t
cl_is_object_in_list(IN const cl_list_t * const p_list,
		     IN const void *const p_object)
{
	CL_ASSERT(p_list);
	CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));

	return (cl_qlist_find_from_head
		(&p_list->list, cl_list_find_cb, p_object)
		!= cl_qlist_end(&p_list->list));
}

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)
{
	cl_status_t status;
	void *p_object;

	CL_ASSERT(p_list);
	CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
	CL_ASSERT(p_array);
	CL_ASSERT(item_size);
	CL_ASSERT(item_count);

	/*
	 * To add items from the array to the list in the same order as
	 * the elements appear in the array, we add them starting with
	 * the last one first.  Locate the last item.
	 */
	p_object = ((uint8_t *) p_array + (item_size * (item_count - 1)));

	/* Continue to add all items to the list. */
	while (item_count--) {
		status = cl_list_insert_head(p_list, p_object);
		if (status != CL_SUCCESS) {
			/* Remove all items that have been inserted. */
			while (item_count++ < item_count)
				cl_list_remove_head(p_list);
			return (status);
		}

		/* Get the next object to add to the list. */
		p_object = ((uint8_t *) p_object - item_size);
	}

	return (CL_SUCCESS);
}

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)
{
	cl_status_t status;
	void *p_object;

	CL_ASSERT(p_list);
	CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
	CL_ASSERT(p_array);
	CL_ASSERT(item_size);
	CL_ASSERT(item_count);

	/* Set the first item to add to the list. */
	p_object = (void *)p_array;

	/* Continue to add all items to the list. */
	while (item_count--) {
		status = cl_list_insert_tail(p_list, p_object);
		if (status != CL_SUCCESS) {
			/* Remove all items that have been inserted. */
			while (item_count++ < item_count)
				cl_list_remove_tail(p_list);
			return (status);
		}

		/* Get the next object to add to the list. */
		p_object = ((uint8_t *) p_object + item_size);
	}

	return (CL_SUCCESS);
}

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)
{
	cl_status_t status;
	cl_list_iterator_t itor;

	/* Note that context can have any arbitrary value. */
	CL_ASSERT(p_list);
	CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
	CL_ASSERT(pfn_func);

	itor = cl_list_head(p_list);

	while (itor != cl_list_end(p_list)) {
		status = pfn_func(cl_list_obj(itor), (void *)context);
		if (status == CL_SUCCESS)
			break;

		itor = cl_list_next(itor);
	}

	/* no match */
	return (itor);
}

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)
{
	cl_status_t status;
	cl_list_iterator_t itor;

	/* Note that context can have any arbitrary value. */
	CL_ASSERT(p_list);
	CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
	CL_ASSERT(pfn_func);

	itor = cl_list_tail(p_list);

	while (itor != cl_list_end(p_list)) {
		status = pfn_func(cl_list_obj(itor), (void *)context);
		if (status == CL_SUCCESS)
			break;

		itor = cl_list_prev(itor);
	}

	/* no match */
	return (itor);
}

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)
{
	cl_list_iterator_t itor;

	/* Note that context can have any arbitrary value. */
	CL_ASSERT(p_list);
	CL_ASSERT(cl_is_qpool_inited(&p_list->list_item_pool));
	CL_ASSERT(pfn_func);

	itor = cl_list_head(p_list);

	while (itor != cl_list_end(p_list)) {
		pfn_func(cl_list_obj(itor), (void *)context);

		itor = cl_list_next(itor);
	}
}