/* 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 partition01b,02jun03,agi added static keyword in front of local functions01a,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;