/* ospf_dijkstra.c - Executes the dijkstra algorithm for the shortest path *//* Copyright 1998 - 2003 Wind River Systems, Inc. *//*modification history--------------------02w,20jun03,htm SPR# 87386 - Added ospf_check_if_net_link_exists() to check if a link                exists to a transit network in the router LSA of the attached router   02v,26may03,agi Changed rwos_get_system_elapsed_time_second() to                ospf_get_system_elapsed_time_second()02u,15may03,htm	SPR#86907 Vitual link is not included in router-LSA for the                 backbone02t,22apr03,ram	SPR#76812 Modifications for OSPF performance enhancements02s,11feb03,kkz SPR 86188 - fix ospf_examine_router_link_advertisement_for_vertex_V to                correctly increment router links to avoid page fault02r,03feb03,dsk SPR 86030 - avoid reading from null pointer02q,27jan03,mwv SPR 85572 - initialize Vertex W in ospf_set_intervening_router ()                            02p,07jan03,agi Fixed SPR#8471902o,07jan03,agi Fixed compilation error02n,03dec02,ram SPR 84312 - Change elapsed time to return seconds02m,01dec02,dsk	Fix for ANVL 5.3 SPR# 8333302l,19nov02,mwv Merge TMS code SPR 8428402k,15nov02,dsk SPR 84180 - Fixed Dijkstra computation of the routing                table for unnumbered links.02j,07oct02,agi Fixed compiler warnings02i,05aug02,jkw	Fix for TSR 288030.02h,10jul02,jkw	Fix UNH 5.3 test.02g,24apr02,jkw	Fix UNH 4.4 test.02f,30jan02,jkw	Fix routes not being propagated.02e,20dec01,jkw	Removed sptr_area->sptr_interfaces structure.02d,09nov01,jkw	Null pointer check.02c,11oct01,jkw	Set pointer to NULL after table_free.02b,03Sep01,jkw	Added Mistral updates for next hop calculation.02a,01jun01,jkw	Added updates for multiple path destination for inter area01z,26jun01,jkw	Added updates for multiple path destination01y,20jun01,jkw	Added unnumbered link support01x,03may01,jkw	Added checks for NULL pointers and alarm messages01w,26sep00,reshma	Added WindRiver CopyRight01v,25sep00,reshma	RFC-1587 implementation for OSPF NSSA Option, also 			tested against ANVL.01u,07jul00,reshma	Unix compatibility related changes.01t,04apr00,reshma	Added some MIB support (Read only).Passed all important			ANVL OSPF tests.01s,23dec99,reshma	Compatibility with VxWorks-IP and VxWorks RTM-interface01r,12may99,jack		Changes related to equal cost multi path and			ospf_set_patricia_route_change_status_on_ospf_rt_node01q,12may99,jack		Fixes for equal cost multipath01p,10may99,jack		Changes in prototypes and call and declaration of			ospf_get_new_next_hop_blocks01o,06jan99,jack	Added a new function ospf_check_and_mark_area_address_			range01n,05jan99,jack	Fixed the mask settings here01m,05jan99,jack	Fixed the mask setting on ASBR and ABR routes01l,28dec98,jack	Compiled and added some comments01k,11nov98,jack	Config changes, linted and big endian changes01j,30oct98,jack	Incorporate changes for compilation on Vxworks01i,23aug98,jack	ANVL tested OSPF with PATRICIA tree route table and no 			recursion01h,10aug98,jack	PATRICIA Route Table Based OSPF Code Base01g,19jun98,jack	Listroutine changes. OSPF add and delete list routines,			eventually call the rwutils list routines.01f,04jun98,jack	Integration with RTM and BGP01e,24apr98,jack	RTM changes01d,10jul97,cindy	Pre-release v1.52b01c,02oct97,cindy	Release Version 1.5201b,22oct96,cindy	Release Version 1.5001a,05jun96,cindy	First Beta Release*//*DESCRIPTIONospf_dijkstra.c is used for calculating the shortest path first algorithm for anintra area path.This file is used whenever OSPF needs to recalculate the routing table for anarea.*/#include "ospf.h"#if defined (__OSPF_VIRTUAL_STACK__)#include "ospf_vs_lib.h"#endif /* __OSPF_VIRTUAL_STACK__ *//******************************************************************************//* SPR 86907  -- Begin */extern OSPF_ROUTING_TABLE_ENTRY* ospf_find_routing_table_entry_for_ABR(ULONG destination_id_to_look, ULONG area_id);/* SPR 86907  -- End *//* SPR 87386 - Begin */enum TEST ospf_check_if_net_link_exists (OSPF_NETWORK_LINK_ADVERTISEMENT_HEADER *sptr_network,                                          OSPF_ROUTER_LINK_ADVERTISEMENT_HEADER *sptr_router);/* SPR 87386 - End */static void ospf_examine_advertisements_associated_with_vertex_V (OSPF_AREA_ENTRY *sptr_area,OSPF_SHORTEST_PATH_NODE *sptr_shortest_path_node);static void ospf_examine_router_link_advertisement_for_vertex_V (OSPF_ROUTER_LINK_ADVERTISEMENT_HEADER *sptr_router_link_advertisement,	OSPF_AREA_ENTRY *sptr_area,OSPF_SHORTEST_PATH_NODE *sptr_vertex_V);static void ospf_examine_network_link_advertisement_for_vertex_V (OSPF_NETWORK_LINK_ADVERTISEMENT_HEADER *sptr_network_link_advertisement,	OSPF_AREA_ENTRY *sptr_area,OSPF_SHORTEST_PATH_NODE *sptr_vertex_V);static enum TEST ospf_check_if_vertex_W_is_already_on_the_shortest_path_tree (OSPF_AREA_ENTRY *sptr_area,ULONG vertex_W, BYTE_ENUM (OSPF_LS_TYPE)	ls_type);static OSPF_SHORTEST_PATH_NODE *ospf_find_vertex_W_on_candidate_list (OSPF_SHORTEST_PATH_NODE *sptr_candidate,ULONG vertex_W, BYTE_ENUM (OSPF_LS_TYPE)	link_type);static OSPF_SHORTEST_PATH_NODE *ospf_choose_closest_vertex_to_root (OSPF_SHORTEST_PATH_NODE *sptr_candidate);static void ospf_add_closest_vertex_to_shortest_path_tree (OSPF_SHORTEST_PATH_NODE *sptr_vertex_to_add,OSPF_AREA_ENTRY *sptr_area);static void ospf_add_routing_table_entry_for_area_border_router (OSPF_SHORTEST_PATH_NODE *sptr_vertex_V,OSPF_AREA_ENTRY *sptr_area);static void ospf_add_routing_table_entry_for_autonomous_system_boundary_router (OSPF_SHORTEST_PATH_NODE *sptr_vertex_V,OSPF_AREA_ENTRY *sptr_area);static void ospf_add_routing_table_entry_for_transit_network (OSPF_SHORTEST_PATH_NODE *sptr_vertex_V,OSPF_AREA_ENTRY *sptr_area);static OSPF_LS_DATABASE_NODE *ospf_find_only_the_router_or_network_LSAs_advertised_by_vertex_V (ULONG vertex_V,OSPF_AREA_ENTRY *sptr_area, BYTE_ENUM (OSPF_LS_TYPE) link_type_of_vertex);static enum TEST ospf_set_next_hop_for_abr_or_asbr (OSPF_ROUTING_TABLE_ENTRY	*sptr_routing_table_entry, OSPF_AREA_ENTRY *sptr_area, OSPF_SHORTEST_PATH_NODE *sptr_vertex_V);static void ospf_add_non_stub_intra_area_entry_to_ospf_routing_table (OSPF_SHORTEST_PATH_NODE *sptr_vertex_V, OSPF_AREA_ENTRY *sptr_area);static OSPF_ROUTING_TABLE_NODE* ospf_add_fields_to_ospf_route_entry (ULONG destination_id_for_vertex_V, ULONG address_mask_for_vertex_V, OSPF_SHORTEST_PATH_NODE *sptr_vertex_V,	OSPF_AREA_ENTRY *sptr_area, enum OSPF_ROUTE_DESTINATION_TYPE ospf_route_destination_type);static void ospf_check_and_mark_area_address_range (ULONG destination_id_for_vertex_V, OSPF_AREA_ENTRY *sptr_area);/******************************************************************************//* section 16.1, first stage (page 151-154) *//********************************************************************************* ospf_run_dijkstra - calculates the shortest path tree for a particular area** This routine will run the dijkstra algorithm for a particular area.** <sptr_area> OSPF area** RETURNS: 	N/A** ERRNO: N/A** NOMANUAL*/void ospf_run_dijkstra (OSPF_AREA_ENTRY *sptr_area){	OSPF_SHORTEST_PATH_NODE *sptr_vertex_V =NULL;	OSPF_SHORTEST_PATH_NODE *sptr_vertex_P =NULL;	OSPF_SHORTEST_PATH_NODE *sptr_vertex_to_add =NULL;	enum BOOLEAN done;	OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_run_dijkstra\r\n");	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Running dijkstra\r\n");	    sptr_vertex_V = &sptr_area->shortest_path_first_tree;				/* start at the root */	sptr_area->number_of_area_border_routers = 0;	sptr_area->number_of_autonomous_system_boundary_routers = 0;	sptr_area->nssa_abr_to_convert_type_7_to_type_5 = 0;	done = FALSE;	do		{		ospf_examine_advertisements_associated_with_vertex_V (sptr_area, sptr_vertex_V);		if (sptr_area->sptr_candidate == NULL)			{			done = TRUE;			}		else			{			sptr_vertex_to_add = ospf_choose_closest_vertex_to_root (sptr_area->sptr_candidate);			ospf_add_closest_vertex_to_shortest_path_tree (sptr_vertex_to_add, sptr_area);			sptr_vertex_P = sptr_vertex_V;			sptr_vertex_V = sptr_vertex_to_add;			OSPF_PRINTF_ROUTING_TABLE (OSPF_ROUTING_TABLE_PRINTF, "==========++++++++++>>>>>PARENT VERTEX:%lx, Parent vertex_type:%x, Parent vertex cost:%d ADDING FOLLOWING VERTEX TO THE SPT: vertex:%lx, vertex_type:%x, vertex_cost:%d  \r\n",				sptr_vertex_P->vertex, sptr_vertex_P->vertex_type, sptr_vertex_P->cost, sptr_vertex_V->vertex, sptr_vertex_V->vertex_type, sptr_vertex_V->cost);			ospf_add_non_stub_intra_area_entry_to_ospf_routing_table (sptr_vertex_V, sptr_area);    /* It can be an entry for ABR, ASBR or transit network or combination of any of these */			}		}	while (done == FALSE);	return;}/**************************************************************************************** ospf_examine_advertisements_associated_with_vertex_V - examines advertisements associated with vertex** This routine will call the functions to find all network and router lsas associated with the vertex* and call the functions to examine the router and network lsas to build the shortest path tree.** <sptr_area> OSPF area** <sptr_shortest_path_node> Shortest path node for building the routing table** RETURNS: 	N/A** ERRNO: N/A** NOMANUAL*//*******************************************************************************************//* section 16.1, item (2) (page 151) */static void ospf_examine_advertisements_associated_with_vertex_V (OSPF_AREA_ENTRY *sptr_area,OSPF_SHORTEST_PATH_NODE *sptr_shortest_path_node){	OSPF_LS_DATABASE_NODE *sptr_vertex_V_advertisements =NULL;	OSPF_LS_DATABASE_NODE *sptr_database_node= NULL;	OSPF_LS_DATABASE_ENTRY *sptr_database_entry =NULL;	OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_examine_advertisements_associated_with_vertex_V\r\n");	OSPF_PRINTF_ROUTING_TABLE (OSPF_ROUTING_TABLE_PRINTF, "|||||----->>>>>OSPF:   Finding all LSAs by vertex which is added to SPT (in HEX): %lx for dijkestra   and vertex type:%x<<<<<-----\r\n",		sptr_shortest_path_node->vertex, sptr_shortest_path_node->vertex_type);	sptr_vertex_V_advertisements = ospf_find_only_the_router_or_network_LSAs_advertised_by_vertex_V  (sptr_shortest_path_node->vertex, sptr_area, sptr_shortest_path_node->vertex_type);	for (sptr_database_node = sptr_vertex_V_advertisements; sptr_database_node != NULL;		sptr_database_node = sptr_database_node->sptr_forward_link)		{		sptr_database_entry = sptr_database_node->sptr_ls_database_entry;        if ( sptr_database_entry == NULL )            continue;		switch (sptr_database_entry->advertisement.sptr_router->ls_header.type)			{			case OSPF_LS_ROUTER:				{				ospf_examine_router_link_advertisement_for_vertex_V (sptr_database_entry->advertisement.sptr_router, sptr_area,					sptr_shortest_path_node);				break;				}			case OSPF_LS_NETWORK:				{				ospf_examine_network_link_advertisement_for_vertex_V (sptr_database_entry->advertisement.sptr_network, sptr_area,					sptr_shortest_path_node);				break;				}			default:				{				break;				}			}		}	    if ( sptr_vertex_V_advertisements != NULL )		   {			(void) ospf_free_entire_list ((OSPF_GENERIC_NODE *) sptr_vertex_V_advertisements);			}	return;}/********************************************************************************* ospf_find_only_the_router_or_network_LSAs_advertised_by_vertex_V - finds link state advertisements associated with vertex** This routine will find all network and router lsas associated with the vertex** <vertex_V> Vertex on router OSPF is examining** <sptr_area> OSPF area** <link_type_of_vertex> Type of vertex we are examining** RETURNS: 	OSPF_LS_DATABASE_NODE * or NULL** ERRNO: N/A** NOMANUAL*/static OSPF_LS_DATABASE_NODE *ospf_find_only_the_router_or_network_LSAs_advertised_by_vertex_V    (    ULONG vertex_V,    OSPF_AREA_ENTRY *sptr_area,    BYTE_ENUM (OSPF_LS_TYPE) link_type_of_vertex    ){	OSPF_LS_DATABASE_NODE *sptr_first_database_node =NULL;	enum OSPF_LS_TYPE ls_type;	ULONG index =0;	OSPF_LS_DATABASE_HEAD *sptr_ls_database_head =NULL;	OSPF_LS_DATABASE_ENTRY *sptr_database_entry =NULL;	OSPF_LS_DATABASE_ENTRY *sptr_next_database_entry =NULL;	ULONG database_entry_advertising_router =0;	OSPF_LS_DATABASE_NODE *sptr_database_node =NULL;	OSPF_INTERFACE *sptr_interface =NULL;	OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_find_only_the_router_or_network_LSAs_advertised_by_vertex_V\r\n");	sptr_interface = NULL;	PARAMETER_NOT_USED (sptr_interface);	sptr_first_database_node = NULL;	for (ls_type = OSPF_LS_ROUTER; ls_type <= OSPF_LS_NETWORK; ++ls_type)		{		for (index = 0x00000000L, sptr_ls_database_head = &(sptr_area->ls_database_hash_table[ls_type][index]);			index < OSPF_HASH_TABLE_SIZE; ++index, sptr_ls_database_head = &(sptr_area->ls_database_hash_table[ls_type][index]))			{	        /* SPR#76812 */	       	for (sptr_database_entry = sptr_ls_database_head->sptr_linear_database_entry;	       		sptr_database_entry != NULL;	       	    sptr_database_entry = sptr_next_database_entry)                {				sptr_next_database_entry = sptr_database_entry->sptr_forward_link;				database_entry_advertising_router = sptr_database_entry->advertisement.sptr_router->ls_header.advertising_router;				database_entry_advertising_router = net_to_host_long (database_entry_advertising_router);				if ( (vertex_V == database_entry_advertising_router) && (sptr_database_entry->advertisement.sptr_router->ls_header.type == OSPF_LS_ROUTER)					 && (link_type_of_vertex == sptr_database_entry->advertisement.sptr_router->ls_header.type))					{					OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF:   ADDING THIS NODE and ***************VERTEX: (HEX) %lx ************************\r\n", vertex_V);					sptr_database_node = (OSPF_LS_DATABASE_NODE *) table_malloc (1, sizeof (OSPF_LS_DATABASE_NODE));					if (sptr_database_node != NULL)						{						memset (sptr_database_node, 0x00, sizeof (OSPF_LS_DATABASE_NODE));						sptr_database_node->sptr_ls_database_entry = sptr_database_entry;						if (sptr_first_database_node == NULL)							{							sptr_first_database_node = sptr_database_node;							}						else							{							ospf_add_node_to_end_of_list ((OSPF_GENERIC_NODE *) sptr_database_node, (OSPF_GENERIC_NODE *) sptr_first_database_node);							}						}					else						{						ospf_print_memory_error_message_and_free_buffer_if_necessary ((void *)NULL , "OSPF_LS_DATABASE_NODE");						}					}					/* For this vertex, process network links and other stubs : This was missing before  */				else if ( (vertex_V == net_to_host_long (sptr_database_entry->advertisement.sptr_router->ls_header.id)) && (sptr_database_entry->advertisement.sptr_router->ls_header.type == OSPF_LS_NETWORK)					&& (link_type_of_vertex == sptr_database_entry->advertisement.sptr_router->ls_header.type) )					{