ospf_linked_list.c

vxworks下ospf协议栈

/* ospf_linked_list.c - OSPF linked list */

/* Copyright 2003 Wind River Systems, Inc. */
#include "copyright_wrs.h"

/*
modification history
--------------------
01c,02jun03,ram Changed native memory usage to OSPF memory partition
01b,02jun03,agi added static keyword in front of local functions
01a,30may03,agi create (ported from RWOS)
*/

/* includes */
#include "stdio.h"
#include "stdlib.h"
#include <vxWorks.h>
#include "ospf.h"
#include "ospf_container_functions.h"
#include "ospf_linked_list_structures.h"

/******************************************************************************/
static void linked_list_set_container_function_pointers (LINKED_LIST_CONTAINER* p_linked_list);
static void linked_list_set_iterator_function_pointers (LINKED_LIST_ITERATOR* p_linked_list_iterator);
static bool linked_list_add_node_to_sorted_list (LINKED_LIST_CONTAINER* p_linked_list, LINKED_LIST_NODE* p_node);
static void linked_list_determine_position (LINKED_LIST_CONTAINER* p_linked_list, LINKED_LIST_NODE* p_node,
	LINKED_LIST_NODE** pp_previous_node, LINKED_LIST_NODE** pp_next_node);
static void linked_list_free_iterator_local (OSPF_CONTAINER_ITERATOR* p_iterator);
static OSPF_CONTAINER_ITERATOR linked_list_create_iterator_local (OSPF_CONTAINER* p_rw_container);


/******************************************************************************/
OSPF_CONTAINER* ospf_list_create (FP_OSPF_CONTAINER_ITEM_COMPARE fp_compare)
{
    LINKED_LIST_CONTAINER* p_linked_list;

    p_linked_list = (LINKED_LIST_CONTAINER*) buffer_malloc (
        sizeof (LINKED_LIST_CONTAINER));

	if (p_linked_list == NULL)
		{
		return ((OSPF_CONTAINER*) NULL);
		}
		
	p_linked_list->p_first_node = NULL;
	p_linked_list->p_last_node = NULL;

	if (fp_compare != NULL)
		{
		p_linked_list->fp_compare = fp_compare;
		}
	else
		{
		p_linked_list->fp_compare = NULL;
		}

	linked_list_set_container_function_pointers (p_linked_list);


#if defined (__LOCAL_ITERATOR__)

    p_linked_list->mp_linked_list_iterator = buffer_malloc (
        sizeof (LINKED_LIST_ITERATOR));

	if (p_linked_list->mp_linked_list_iterator == NULL)
		{

		table_free ((void *)p_linked_list);

		return (NULL);
		}

	p_linked_list->mp_linked_list_iterator->p_linked_list = p_linked_list;

	p_linked_list->mp_linked_list_iterator->p_node = NULL;

	linked_list_set_iterator_function_pointers (p_linked_list->mp_linked_list_iterator);

#endif /*__LOCAL_ITERATOR__*/

	return ((OSPF_CONTAINER*)p_linked_list);		
}


/************************************************************************************/
static bool linked_list_is_at_end (OSPF_CONTAINER_ITERATOR* p_iterator)
{
	if (p_iterator == NULL)
		{
		return (true);
		}

	if (((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list == NULL)
		{
		return (true);
		}

	if (((LINKED_LIST_ITERATOR*)p_iterator)->p_node == NULL)
		{
		return (true);
		}
	else
		{
		return (false);
		}
}
/************************************************************************************/
static void linked_list_goto_front (OSPF_CONTAINER_ITERATOR* p_iterator)
{
	if (p_iterator == NULL)
		{
		return;
		}

	if (((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list == NULL)
		{
		return;
		}

	((LINKED_LIST_ITERATOR*)p_iterator)->p_node = ((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list->p_first_node;
}
/************************************************************************************/
static void linked_list_goto_end (OSPF_CONTAINER_ITERATOR* p_iterator)
{
	if (p_iterator == NULL)
		{
		return;
		}

	if (((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list == NULL)
		{
		return;
		}

	((LINKED_LIST_ITERATOR*)p_iterator)->p_node = ((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list->p_last_node;
}
/************************************************************************************/
static OSPF_CONTAINER_ITERATOR linked_list_create_iterator (OSPF_CONTAINER* p_rw_container)
{
	LINKED_LIST_ITERATOR* p_linked_list_iterator;

#if defined (__LOCAL_ITERATOR__)
	p_linked_list_iterator = NULL;

	p_linked_list_iterator = ((LINKED_LIST_CONTAINER*) p_rw_container)->mp_linked_list_iterator;

	linked_list_goto_front ((OSPF_CONTAINER_ITERATOR*) p_linked_list_iterator);

#else 
	p_linked_list_iterator = buffer_malloc (sizeof (LINKED_LIST_ITERATOR));

	if (p_linked_list_iterator == NULL)
		{
		return ((OSPF_CONTAINER_ITERATOR) NULL);
		}

	p_linked_list_iterator->p_linked_list = (LINKED_LIST_CONTAINER*) p_rw_container;

	p_linked_list_iterator->p_node = NULL;

	linked_list_set_iterator_function_pointers (p_linked_list_iterator);

#endif

	return ((OSPF_CONTAINER_ITERATOR) p_linked_list_iterator);


}


/************************************************************************************/
static void linked_list_free_container (OSPF_CONTAINER* p_linked_list)
{
	LINKED_LIST_NODE* p_node;
	LINKED_LIST_NODE* p_next_node;
#if defined (__LOCAL_ITERATOR__)
	LINKED_LIST_ITERATOR* p_linked_list_iterator;
#endif

	if (p_linked_list == NULL)
		{
		return;
		}

	p_node = ((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node;

	while (p_node != NULL) 
		{
		p_next_node = p_node->p_next;

		table_free (p_node);

		p_node = p_next_node;		
		}

#if defined (__LOCAL_ITERATOR__)
	
	p_linked_list_iterator = NULL;

	p_linked_list_iterator = (LINKED_LIST_ITERATOR*)((LINKED_LIST_CONTAINER*)p_linked_list)->mp_linked_list_iterator;

	if (p_linked_list_iterator != NULL)
		{
		table_free (p_linked_list_iterator);

		p_linked_list_iterator = NULL;
		}
#endif
	table_free ((LINKED_LIST_CONTAINER*)p_linked_list);

	p_linked_list = NULL;
}


/************************************************************************************/
static bool linked_list_add_at_front (OSPF_CONTAINER* p_linked_list, const OSPF_CONTAINER_ITEM* p_item)
{
	LINKED_LIST_NODE* p_node;
	LINKED_LIST_NODE* p_next_node;
	bool return_value;

	if (p_linked_list == NULL)
		{
		return (false);
		}

	if (p_item == NULL)
		{
		return (false);
		}
		
	p_node = (LINKED_LIST_NODE*) buffer_malloc (sizeof (LINKED_LIST_NODE));

	if (p_node == NULL)
		{
		return (false);
		}
		
	p_node->p_next = NULL;
	p_node->p_previous = NULL;
	p_node->p_data = (void*) p_item;

	if (((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node == NULL)
		{
		((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node = p_node;
		((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node = p_node;

		p_node->p_previous = NULL;
		p_node->p_next = NULL;

		return (true);
		}
	else
		{
		if (((LINKED_LIST_CONTAINER*)p_linked_list)->fp_compare != NULL)
			{
			return_value = linked_list_add_node_to_sorted_list (p_linked_list, p_node);

			if (return_value == false)
				{
				table_free (p_node);

				p_node = NULL;
				}
			}
		else
			{
			p_next_node = ((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node;

			p_node->p_next = p_next_node;
			p_node->p_previous = NULL;

			p_next_node->p_previous = p_node;

			((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node = p_node;

			return_value = true;
			}

		return (return_value);
		}
}


/************************************************************************************/
static void linked_list_remove_from_front (OSPF_CONTAINER* p_linked_list)
{
	LINKED_LIST_NODE* p_node_to_remove;

	if (p_linked_list == NULL)
		{
		return;
		}
		
	if (((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node == NULL)
		{
		return;
		}

	if (((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node == ((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node)
		{
		p_node_to_remove = ((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node;

		((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node = NULL;
		((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node = NULL;

		table_free (p_node_to_remove);
		
		p_node_to_remove = NULL;

		return;
		}
		
	p_node_to_remove = ((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node;

	((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node = p_node_to_remove->p_next;

	((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node->p_previous = NULL;

	table_free (p_node_to_remove);

	p_node_to_remove = NULL;
}


/************************************************************************************/
static bool linked_list_add_at_back (OSPF_CONTAINER* p_linked_list, const OSPF_CONTAINER_ITEM* p_item)
{
	LINKED_LIST_NODE* p_node;
	LINKED_LIST_NODE* p_previous_node;
	bool return_value;

	if (p_linked_list == NULL)
		{
		return (false);
		}
		
	if (p_item == NULL)
		{
		return (false);
		}
		
	p_node = (LINKED_LIST_NODE*) buffer_malloc (sizeof (LINKED_LIST_NODE));

	if (p_node == NULL)
		{
		return (false);
		}
		
	p_node->p_next = NULL;
	p_node->p_previous = NULL;
	p_node->p_data = (void*) p_item;

	if (((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node == NULL)
		{
		((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node = p_node;
		((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node = p_node;
	
		p_node->p_next = NULL;
		p_node->p_previous = NULL;

		return (true);
		}
	else
		{
		if (((LINKED_LIST_CONTAINER*)p_linked_list)->fp_compare != NULL)
			{
			return_value = linked_list_add_node_to_sorted_list (p_linked_list, p_node);

			if (return_value == false)
				{
				table_free (p_node);
				
				p_node = NULL;
				}
			}
		else
			{
			p_previous_node = ((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node;

			p_node->p_next = NULL;
			p_node->p_previous = p_previous_node;

			p_previous_node->p_next = p_node;

			((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node = p_node;

			return_value = true;
			}

		return (return_value);
		}
}


/************************************************************************************/
static void linked_list_remove_from_back (OSPF_CONTAINER* p_linked_list)
{
	LINKED_LIST_NODE* p_node_to_remove;

	p_linked_list = (LINKED_LIST_CONTAINER*) p_linked_list;

	if (p_linked_list == NULL)
		{
		return;
		}

	if (((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node == NULL)
		{
		return;
		}
		
	if (((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node == ((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node)
		{
		p_node_to_remove = ((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node;

		((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node = NULL;
		((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node = NULL;

		table_free (p_node_to_remove);

		p_node_to_remove = NULL;

		return;
		}
		
	p_node_to_remove = ((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node;
	
	((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node = p_node_to_remove->p_previous;

	((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node->p_next = NULL;
	
	table_free (p_node_to_remove);

	p_node_to_remove = NULL;
}


/************************************************************************************/
static UINT linked_list_get_number_of_nodes (const OSPF_CONTAINER* p_linked_list)
{
	UINT number_of_nodes;
	LINKED_LIST_NODE* p_node;

	p_node = ((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node;

	number_of_nodes = 0;
	while (p_node !=  NULL)
		{
		++ number_of_nodes;
		p_node = p_node->p_next;
		}

	return (number_of_nodes);
}


/************************************************************************************/
static OSPF_CONTAINER_ITEM* linked_list_get_item_at_front (const OSPF_CONTAINER* p_linked_list)
{
	if (p_linked_list == NULL)
		{
		return (NULL);
		}

	if (((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node == NULL)
		{
		return (NULL);
		}

	return (((LINKED_LIST_CONTAINER*)p_linked_list)->p_first_node->p_data);
}


/************************************************************************************/
static OSPF_CONTAINER_ITEM* linked_list_get_item_at_back (const OSPF_CONTAINER* p_linked_list)
{
	if (p_linked_list == NULL)
		{
		return (NULL);
		}

	if (((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node == NULL)
		{
		return (NULL);
		}

	return (((LINKED_LIST_CONTAINER*)p_linked_list)->p_last_node->p_data);
}
/************************************************************************************/
static void linked_list_set_container_function_pointers (LINKED_LIST_CONTAINER* p_linked_list)
{
	if (p_linked_list != NULL)
		{
		p_linked_list->function.create_iterator = linked_list_create_iterator;
		p_linked_list->function.free_container = linked_list_free_container;
		p_linked_list->function.add_at_front = linked_list_add_at_front;
		p_linked_list->function.remove_from_front = linked_list_remove_from_front;
		p_linked_list->function.add_at_back = linked_list_add_at_back;
		p_linked_list->function.remove_from_back = linked_list_remove_from_back;
		p_linked_list->function.get_container_size = linked_list_get_number_of_nodes;
		p_linked_list->function.get_item_at_front = linked_list_get_item_at_front;
		p_linked_list->function.get_item_at_back = linked_list_get_item_at_back;
		}
}

/************************************************************************************/
static OSPF_CONTAINER_ITERATOR linked_list_create_iterator_local (OSPF_CONTAINER* p_rw_container)
{
	LINKED_LIST_ITERATOR* p_linked_list_iterator;

	p_linked_list_iterator = buffer_malloc (sizeof (LINKED_LIST_ITERATOR));

	if (p_linked_list_iterator == NULL)
		{
		return ((OSPF_CONTAINER_ITERATOR) NULL);
		}

	p_linked_list_iterator->p_linked_list = (LINKED_LIST_CONTAINER*) p_rw_container;

	p_linked_list_iterator->p_node = NULL;

	linked_list_set_iterator_function_pointers (p_linked_list_iterator);

	return ((OSPF_CONTAINER_ITERATOR) p_linked_list_iterator);
}


/************************************************************************************/
static OSPF_CONTAINER_ITEM* linked_list_get_item_at_iterator (OSPF_CONTAINER_ITERATOR* p_iterator)
{
	if (p_iterator == NULL)
		{
		return ((OSPF_CONTAINER_ITEM*)NULL);
		}

	if (((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list == NULL)
		{
		return ((OSPF_CONTAINER_ITEM*)NULL);
		}

	if (((LINKED_LIST_ITERATOR*)p_iterator)->p_node == NULL)
		{
		return ((OSPF_CONTAINER_ITEM*)NULL);
		}

	return ((OSPF_CONTAINER_ITEM*)(((LINKED_LIST_ITERATOR*)p_iterator)->p_node->p_data));		
}


/************************************************************************************/
static bool linked_list_find_item_in_range (OSPF_CONTAINER_ITERATOR* p_iterator_start, OSPF_CONTAINER_ITERATOR* p_iterator_end,
	FP_OSPF_CONTAINER_ITEM_CRITERIA_MATCHER fp_criteria_matcher, OSPF_CONTAINER_CRITERIA* p_criteria,
	OSPF_CONTAINER_ITERATOR* p_matched_item_iterator)
{
	LINKED_LIST_ITERATOR* p_first_iterator;
	LINKED_LIST_ITERATOR* p_last_iterator;
	LINKED_LIST_NODE* p_node;
	LINKED_LIST_NODE* p_last_node;
	bool item_found;

	if (fp_criteria_matcher == NULL)
		{
		return (false);
		}

	if (p_criteria == NULL)
		{
		return (false);
		}

	if (p_matched_item_iterator == NULL)
		{
		return (false);
		}
		
	p_first_iterator = (LINKED_LIST_ITERATOR*) p_iterator_start;