ospf_linked_list.c

vxworks下ospf协议栈

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

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

	if (((LINKED_LIST_ITERATOR*)p_first_iterator)->p_node == NULL)
		{
		return (false);
		}
	
	p_last_iterator = (LINKED_LIST_ITERATOR*) p_iterator_end;

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

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

	if (((LINKED_LIST_ITERATOR*)p_last_iterator)->p_node == NULL)
		{
		return (false);
		}
	

	if (p_first_iterator->p_linked_list != p_last_iterator->p_linked_list)
		{
		return (false);
		}
				
	p_node = p_first_iterator->p_node;
	p_last_node = p_last_iterator->p_node;

	item_found = false;

	while ((p_node != NULL) && (p_node != p_last_node->p_next))
		{
		item_found = fp_criteria_matcher (p_node->p_data, p_criteria);

		if (item_found == true)
			{
			break;
			}
		else
			{
			p_node = p_node->p_next;
			}			
		}

	if (item_found == true)
		{
		((LINKED_LIST_ITERATOR*)p_matched_item_iterator)->p_linked_list = p_first_iterator->p_linked_list;
		((LINKED_LIST_ITERATOR*)p_matched_item_iterator)->p_node = p_node;
		return (true);
		}
	else
		{
		/*((LINKED_LIST_ITERATOR*)p_matched_item_iterator)->p_linked_list = NULL;*/
		((LINKED_LIST_ITERATOR*)p_matched_item_iterator)->p_node = NULL;
		return (false);
		}
		
}


/************************************************************************************/
static bool linked_list_is_at_front (OSPF_CONTAINER_ITERATOR* p_iterator)
{
	if (p_iterator == NULL)
		{
		return (false);
		}

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

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

	if (((LINKED_LIST_ITERATOR*)p_iterator)->p_node == ((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list->p_first_node)
		{
		return (true);
		}
	else
		{
		return (false);
		}
}


/************************************************************************************/
static bool linked_list_remove_from_iterator (OSPF_CONTAINER_ITERATOR* p_iterator)
{
	LINKED_LIST_NODE* p_previous_node;
	LINKED_LIST_NODE* p_next_node;
	LINKED_LIST_NODE* p_node;

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

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

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

	p_node = ((LINKED_LIST_ITERATOR*)p_iterator)->p_node;

	p_previous_node = ((LINKED_LIST_ITERATOR*)p_iterator)->p_node->p_previous;
	
	p_next_node = ((LINKED_LIST_ITERATOR*)p_iterator)->p_node->p_next;
	
	if (p_previous_node != NULL)
		{
		p_previous_node->p_next = p_next_node;
		}
	else
		{
		((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list->p_first_node = p_next_node;
		}

	if (p_next_node != NULL)
		{
		p_next_node->p_previous = p_previous_node;
		}
	else
		{
		((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list->p_last_node = p_previous_node;
		}

	((LINKED_LIST_ITERATOR*)p_iterator)->p_node = p_next_node;
		
	table_free (p_node);

	p_node = NULL;

	return (true);				
}


/************************************************************************************/
static OSPF_CONTAINER_ITERATOR linked_list_create_copy_of_iterator (OSPF_CONTAINER_ITERATOR* p_iterator)
{
	LINKED_LIST_ITERATOR* p_new_iterator;
	LINKED_LIST_ITERATOR* p_old_iterator;

	p_old_iterator = (LINKED_LIST_ITERATOR*) p_iterator;

	if (p_old_iterator != NULL)
		{
		p_new_iterator = (LINKED_LIST_ITERATOR*) linked_list_create_iterator_local (p_old_iterator->p_linked_list);

		if (p_new_iterator != NULL)
			{
			p_new_iterator->p_node = p_old_iterator->p_node;

			return ((OSPF_CONTAINER_ITERATOR) p_new_iterator);
			}
		}

	return ((OSPF_CONTAINER_ITERATOR) NULL);
}	
/************************************************************************************/
static bool linked_list_find (FP_OSPF_CONTAINER_ITEM_CRITERIA_MATCHER fp_criteria_matcher, OSPF_CONTAINER_CRITERIA* p_criteria,
						OSPF_CONTAINER_ITERATOR* p_matched_item_iterator)
{
	bool item_found;
	LINKED_LIST_ITERATOR* p_first_iterator;
	LINKED_LIST_ITERATOR* p_last_iterator;

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

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

	p_first_iterator = (LINKED_LIST_ITERATOR*) linked_list_create_copy_of_iterator (p_matched_item_iterator);

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

	p_last_iterator = (LINKED_LIST_ITERATOR*) linked_list_create_copy_of_iterator (p_matched_item_iterator);

	if (p_last_iterator == NULL)
		{
		linked_list_free_iterator_local ((OSPF_CONTAINER_ITERATOR* )p_first_iterator);

		return (false);
		}

	linked_list_goto_front ((OSPF_CONTAINER_ITERATOR*) p_first_iterator);

	linked_list_goto_end ((OSPF_CONTAINER_ITERATOR*) p_last_iterator);

	item_found = linked_list_find_item_in_range ((OSPF_CONTAINER_ITERATOR*) p_first_iterator,
		(OSPF_CONTAINER_ITERATOR*) p_last_iterator, fp_criteria_matcher, p_criteria,
		(OSPF_CONTAINER_ITERATOR*) p_matched_item_iterator);

	linked_list_free_iterator_local ((OSPF_CONTAINER_ITERATOR* )p_first_iterator);

	linked_list_free_iterator_local ((OSPF_CONTAINER_ITERATOR* )p_last_iterator);

	return (item_found);
}	


/************************************************************************************/
static bool linked_list_find_item (OSPF_CONTAINER_ITEM* p_item, OSPF_CONTAINER_ITERATOR* p_iterator)
{
	LINKED_LIST_NODE* p_node;
	bool return_value;

	return_value = false;

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

	p_node = ((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list->p_first_node;
	
	while (p_node != NULL)
		{
		if (p_item == p_node->p_data)
			{
			return_value = true;
			break;
			}

		p_node = p_node->p_next;
		}

	((LINKED_LIST_ITERATOR*)p_iterator)->p_node = p_node;

	return (return_value);
}	


/************************************************************************************/
static bool linked_list_previous (OSPF_CONTAINER_ITERATOR* p_iterator)
{
	if (p_iterator == NULL)
		{
		return (false);
		}

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

	if (((LINKED_LIST_ITERATOR*)p_iterator)->p_node == NULL)
		{
		if (((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list->p_last_node != NULL)
			{
			((LINKED_LIST_ITERATOR*)p_iterator)->p_node = ((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list->p_last_node;

			return (true);
			}

		return (false);
		}

	((LINKED_LIST_ITERATOR*)p_iterator)->p_node = ((LINKED_LIST_ITERATOR*)p_iterator)->p_node->p_previous;
	
	return (true);		
}


/************************************************************************************/
static bool linked_list_set_item_at_iterator (OSPF_CONTAINER_ITERATOR* p_iterator, const OSPF_CONTAINER_ITEM* p_item)
{
	if (p_iterator == NULL)
		{
		return (false);
		}

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

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

	((LINKED_LIST_ITERATOR*)p_iterator)->p_node->p_data = (void*) p_item;

	return (true);		
}


/************************************************************************************/
static bool linked_list_next (OSPF_CONTAINER_ITERATOR* p_iterator)
{
	if (p_iterator == NULL)
		{
		return (false);
		}

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

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

	((LINKED_LIST_ITERATOR*)p_iterator)->p_node = ((LINKED_LIST_ITERATOR*)p_iterator)->p_node->p_next;
	
	return (true);		
}


/************************************************************************************/
static void linked_list_free_iterator (OSPF_CONTAINER_ITERATOR* p_iterator)
{
#if defined (__LOCAL_ITERATOR__)

	LINKED_LIST_ITERATOR* p_linked_list_iterator;

	p_linked_list_iterator = (LINKED_LIST_ITERATOR*) p_iterator;

	if (p_linked_list_iterator == p_linked_list_iterator->p_linked_list->mp_linked_list_iterator)
		linked_list_goto_front ((OSPF_CONTAINER_ITERATOR*)p_iterator);
	else
		{
		linked_list_free_iterator_local (p_iterator);
		}
#else
	linked_list_free_iterator_local (p_iterator);
#endif

}


/************************************************************************************/
static bool linked_list_insert_at_iterator (OSPF_CONTAINER_ITERATOR* p_iterator, const OSPF_CONTAINER_ITEM* p_item)
{
	LINKED_LIST_NODE* p_node;
	LINKED_LIST_NODE* p_previous_node;
	LINKED_LIST_NODE* p_next_node;
	bool return_value;

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

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

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

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

	p_node->p_data = (void*) p_item;
	p_node->p_next = NULL;
	p_node->p_previous = NULL;

	if (((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list->fp_compare != NULL)
		{
		return_value = linked_list_add_node_to_sorted_list (((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list, p_node);

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

			p_node = NULL;
			}
		}
	else
		{
		if (((LINKED_LIST_ITERATOR*)p_iterator)->p_node == NULL)
			{
			p_previous_node = ((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list->p_last_node;

			p_next_node = NULL;
			}
		else
			{
			p_previous_node = ((LINKED_LIST_ITERATOR*)p_iterator)->p_node->p_previous;
			
			p_next_node = ((LINKED_LIST_ITERATOR*)p_iterator)->p_node;
			}

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

		if (p_previous_node == NULL)
			{
			((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list->p_first_node = p_node;
			}
		else
			{
			p_previous_node->p_next = p_node;
			}

		if (p_next_node == NULL)
			{
			((LINKED_LIST_ITERATOR*)p_iterator)->p_linked_list->p_last_node = p_node;
			}
		else
			{
			p_next_node->p_previous = p_node;
			}
		
		return_value = true;
		}
		
	((LINKED_LIST_ITERATOR*)p_iterator)->p_node = p_node;	

	return (return_value);
}
/************************************************************************************/
static void linked_list_set_iterator_function_pointers (LINKED_LIST_ITERATOR* p_linked_list_iterator)
{
	if (p_linked_list_iterator != NULL)
		{
		p_linked_list_iterator->function.free_iterator = linked_list_free_iterator;
		p_linked_list_iterator->function.create_copy_of_iterator = linked_list_create_copy_of_iterator;
		p_linked_list_iterator->function.insert_at_iterator = linked_list_insert_at_iterator;
		p_linked_list_iterator->function.remove_from_iterator = linked_list_remove_from_iterator;
		p_linked_list_iterator->function.iterator_is_at_front = linked_list_is_at_front;
		p_linked_list_iterator->function.iterator_is_at_end = linked_list_is_at_end;
		p_linked_list_iterator->function.iterator_set_at_front = linked_list_goto_front;
		p_linked_list_iterator->function.iterator_set_at_end = linked_list_goto_end;
		p_linked_list_iterator->function.iterator_find_by_content = linked_list_find_item;
		p_linked_list_iterator->function.iterator_find = linked_list_find;
		p_linked_list_iterator->function.iterator_find_in_range = linked_list_find_item_in_range;
		p_linked_list_iterator->function.set_iterator_to_next_item = linked_list_next;
		p_linked_list_iterator->function.set_iterator_to_previous_item = linked_list_previous;
		p_linked_list_iterator->function.get_item_at_iterator = linked_list_get_item_at_iterator;
		p_linked_list_iterator->function.set_item_at_iterator = linked_list_set_item_at_iterator;
		}
}
/************************************************************************************/
static void linked_list_free_iterator_local (OSPF_CONTAINER_ITERATOR* p_iterator)
{
	LINKED_LIST_ITERATOR* p_linked_list_iterator;

	p_linked_list_iterator = (LINKED_LIST_ITERATOR*) p_iterator;

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

		p_linked_list_iterator = NULL;

		return ;
		}
}


/************************************************************************************/
static bool linked_list_add_node_to_sorted_list (LINKED_LIST_CONTAINER* p_linked_list, LINKED_LIST_NODE* p_node)
{
	LINKED_LIST_NODE* p_previous_node;
	LINKED_LIST_NODE* p_next_node;

	linked_list_determine_position (p_linked_list, p_node, &p_previous_node, &p_next_node);

	if (p_previous_node != NULL)
		{
		p_node->p_next = p_previous_node->p_next;
		p_previous_node->p_next = p_node;
		}
	else
		{
		p_node->p_next = p_next_node;
		p_linked_list->p_first_node = p_node;
		}

	if (p_next_node != NULL)
		{
		p_node->p_previous = p_next_node->p_previous;
		p_next_node->p_previous = p_node;
		}
	else
		{
		p_node->p_previous = p_previous_node;
		p_linked_list->p_last_node = p_node;
		}

	return (true);

}
/************************************************************************************/
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)
{
	FP_OSPF_CONTAINER_ITEM_COMPARE node_compare;
	LINKED_LIST_NODE* p_list_node;

	node_compare = p_linked_list->fp_compare;
		
	/*
	   node_compare (x,y) should return:
	    < 0 if x is less than y.
		== 0 if x is equal to y.
		> 0 if x is greater than y.
	*/
	p_list_node = p_linked_list->p_first_node;

	if (p_list_node == NULL)
		{
		*pp_previous_node = NULL;
		*pp_next_node = NULL;
		}
		
	while (p_list_node != NULL)
		{
		if (node_compare (p_list_node->p_data, p_node->p_data) > 0)
			{
			break;
			}

		p_list_node = p_list_node->p_next;
		}

	if (p_list_node == NULL)
		{
		*pp_previous_node = p_linked_list->p_last_node;
		*pp_next_node = NULL;
		}
	else
		{
		*pp_previous_node = p_list_node->p_previous;
		*pp_next_node = p_list_node;
		}
		
}