/* Procedures for dealing with OSPF link state advertisements. */

#include <opnet.h>

/* OMS specific headers */
#include "oms_pr.h"

/* IP specific headers */
#include "ip3_addr.h"
#include "ip3_rte.h"

/* Dijkstra package. */
#include "djk.h"

/* OSPF specific header files */
#include "ospf_defs.h"
#include "ospf_const.h"
#include "ospf_lsa.h"
#include "ospf_interface.h"
#include "ospf_neighbor.h"
#include "ospf_area.h"
#include "ospf_msg.h"

/***** Globals *****/
int					OspfI_Lsa_Seq_Num = 0;
extern IpT_Address	IpI_Default_Addr;

OspfT_Lsa_Type
ospf_lsa_type_get (OspfT_Lsa *lsa_ptr)
	{
	/** Return the type of a link state advertisement. **/
	FIN (ospf_lsa_type_get (lsa_ptr));
	FRET (lsa_ptr->lsa_header_ptr->type);
	}

OspfT_Lsa *
ospf_lsa_area_lookup (OspfT_Area *area_ptr, IpT_Address link_state_id, IpT_Address adv_router_id,
	OspfT_Lsa_Type lsa_type)
	{
	OspfT_Lsa *				lsa_ptr;
	char					err_msg [128];

	/** Return a link state advertisement within the area that matches **/
	/** the link state ID, advertising router, and LSA type.  Return   **/
	/** OPC_NIL if none is found.                                      **/
	FIN (ospf_lsa_area_lookup (area_ptr, link_state_id, adv_router_id, lsa_type));

	switch (lsa_type)
		{
		case OspfC_Lsa_Router_Links:
			{
			lsa_ptr = ospf_lsa_lookup (area_ptr->router_lsa_list_ptr, link_state_id, adv_router_id,
				lsa_type);
			break;
			}

		case OspfC_Lsa_Network_Links:
			{
			lsa_ptr = ospf_lsa_lookup (area_ptr->network_lsa_list_ptr, link_state_id, adv_router_id,
				lsa_type);
			break;
			}

		case OspfC_Lsa_Summary_Links:
			{
			lsa_ptr = ospf_lsa_lookup (area_ptr->summary_lsa_list_ptr, link_state_id, adv_router_id,
				lsa_type);
			break;
			}

		default:
			{
			/* Give a warning and return OPC_NIL. */
			sprintf (err_msg, "Area LSA Lookup: LSA type %d not supported\n", lsa_type);
			ospf_warn_error (err_msg);
			}
		}

	FRET (lsa_ptr);
	}

OspfT_Lsa *
ospf_lsa_lookup (List *lsa_list_ptr, IpT_Address link_state_id, IpT_Address adv_router_id, 
	OspfT_Lsa_Type lsa_type)
	{
	OspfT_Lsa *					cur_lsa_ptr;
	OspfT_Lsa_Header *			lsa_header_ptr;
	int							lsa_index, num_lsa;

	/** Return a link state advertisement within the list that matches **/
	/** the link state ID, advertising router, and LSA type.  Return   **/
	/** OPC_NIL if none is found.                                      **/
	FIN (ospf_lsa_lookup (lsa_list_ptr, link_state_id, adv_router_id, lsa_type));

	/* Determine the number of LSAs in the list. */
	num_lsa = op_prg_list_size (lsa_list_ptr);

	/* Loop through the LSAs and try to find a match. */	
	for (lsa_index = 0; lsa_index < num_lsa; lsa_index++)
		{
		/* Get current LSA. */
		cur_lsa_ptr = (OspfT_Lsa *) op_prg_list_access (lsa_list_ptr, lsa_index);

		/* Does it match? */
		lsa_header_ptr = cur_lsa_ptr->lsa_header_ptr;
		if ((lsa_header_ptr->type == lsa_type) &&
			ip_address_equal (lsa_header_ptr->link_state_id, link_state_id) &&
			ip_address_equal (lsa_header_ptr->router_id, adv_router_id))
			{
			/* Found a match, return the found LSA. */
			FRET (cur_lsa_ptr);
			}
		}

	FRET (OPC_NIL);
	}

OspfT_Lsa_Header *
ospf_lsa_header_lookup (List *lsa_header_list_ptr, IpT_Address link_state_id, IpT_Address adv_router_id, 
	OspfT_Lsa_Type lsa_type)
	{
	OspfT_Lsa_Header *			lsa_header_ptr;
	int							num_headers, header_index;

	/** Return a link state advertisement header within the list that matches **/
	/** the link state ID, advertising router, and LSA type.  Return OPC_NIL  **/
	/** if none is found.                                                     **/
	FIN (ospf_lsa_header_lookup (lsa_header_list_ptr, link_state_id, adv_router_id, lsa_type));

	/* Determine the number of headers in the list. */
	num_headers = op_prg_list_size (lsa_header_list_ptr);

	/* Loop through the headers and try to find a match. */	
	for (header_index = 0; header_index < num_headers; header_index++)
		{
		/* Get current header. */
		lsa_header_ptr = (OspfT_Lsa_Header *) op_prg_list_access (lsa_header_list_ptr, 
			header_index);

		/* Does it match? */
		if ((lsa_header_ptr->type == lsa_type) &&
			ip_address_equal (lsa_header_ptr->link_state_id, link_state_id) &&
			ip_address_equal (lsa_header_ptr->router_id, adv_router_id))
			{
			/* Found a match, return the found LSA. */
			FRET (lsa_header_ptr);
			}
		}

	FRET (OPC_NIL);
	}

void
ospf_lsa_remove (List *lsa_list_ptr, OspfT_Lsa *lsa_ptr)
	{
	int						num_lsas, lsa_index;
	OspfT_Lsa *				cur_lsa_ptr;

	/** Scan through a list of LSAs, and remove the LSA that matches the incoming **/
	/** LSA.  The criteria for matching is the pointers are equal.  This is a     **/
	/** useful operation if you need to remove something that was returned by     **/
	/** ospf_lsa_lookup ().                                                       **/
	FIN (ospf_lsa_remove (lsa_list_ptr, lsa_ptr));

	num_lsas = op_prg_list_size (lsa_list_ptr);
	
	for (lsa_index = 0; lsa_index < num_lsas; lsa_index++)
		{
		cur_lsa_ptr = op_prg_list_access (lsa_list_ptr, lsa_index);
		if (lsa_ptr == cur_lsa_ptr)
			{
			op_prg_list_remove (lsa_list_ptr, lsa_index);
			FOUT;
			}
		}

	FOUT;
	}

void
ospf_lsa_header_remove (List *lsa_header_list_ptr, OspfT_Lsa_Header *lsa_header_ptr)
	{
	OspfT_Lsa_Header *	cur_lsa_header_ptr;
	int					num_headers, header_index;

	/** Similar to above, except for headers. **/
	FIN (ospf_lsa_header_remove (lsa_header_list_ptr, lsa_header_ptr));

	num_headers = op_prg_list_size (lsa_header_list_ptr);
	
	for (header_index = 0; header_index < num_headers; header_index++)
		{
		cur_lsa_header_ptr = op_prg_list_access (lsa_header_list_ptr, header_index);
		if (lsa_header_ptr == cur_lsa_header_ptr)
			{
			op_prg_list_remove (lsa_header_list_ptr, header_index);
			FOUT;
			}
		}

	FOUT;
	}

void
ospf_lsa_dbase_remove (OspfT_Router *router_ptr, OspfT_Lsa *lsa_ptr)
	{
	List *			area_list_ptr;
	OspfT_Area *	area_ptr;
	int				num_areas, area_index;

	/** Remove an LSA (via ospf_lsa_remove ()) from the link state database of **/
	/** the router.  This involves checking each area database.                **/
	FIN (ospf_lsa_dbase_remove (router_ptr, lsa_ptr));

	area_list_ptr = ospf_area_list_get (router_ptr);
	num_areas = op_prg_list_size (area_list_ptr);
	for (area_index = 0; area_index < num_areas; area_index++)
		{
		area_ptr = op_prg_list_access (area_list_ptr, area_index);

		/* Only check the lists that match the LSA type. */
		switch (lsa_ptr->lsa_header_ptr->type)
			{
			case OspfC_Lsa_Router_Links:
				{
				ospf_lsa_remove (area_ptr->router_lsa_list_ptr, lsa_ptr);
				break;
				}

			case OspfC_Lsa_Network_Links:
				{
				ospf_lsa_remove (area_ptr->network_lsa_list_ptr, lsa_ptr);
				break;
				}

			case OspfC_Lsa_Summary_Links:
				{
				ospf_lsa_remove (area_ptr->summary_lsa_list_ptr, lsa_ptr);
				break;
				}

			default:
				{
				/* Issue fatal error. */
				ospf_fatal_error ("Trying to remove LSA of unknown type from link state database");
				break;
				}
			}
		}

	/* Destroy the advertisement. */
	ospf_lsa_destroy (lsa_ptr);

	/* This action may cause some alternative routes to be explored.  Schedule */
	/* a routing table calculation.                                            */
	router_ptr->rte_table_ptr->dirty_flag = OPC_TRUE;

	FOUT;
	}

int
ospf_lsa_compare (OspfT_Lsa_Header *lsa1_header_ptr, OspfT_Lsa_Header *lsa2_header_ptr)
	{
	/** Compares two link state advertisement headers according to its 'newness' **/
	/** as defined by section 13.1 of RFC 1583.  Returns 1 if the first LSA is   **/
	/** more recent, -1 if the second LSA is more recent, and 0 if they are      **/
	/** considered to be identical.                                              **/
	FIN (ospf_lsa_compare (lsa1_header_ptr, lsa2_header_ptr));

	/* First check seequence numbers; higher (more recent) sequence numbers are */
	/* preferred over lower (older) sequence numbers.                           */
	if (lsa1_header_ptr->sequence_num > lsa2_header_ptr->sequence_num)
		{
		FRET (1);
		}
	else if (lsa1_header_ptr->sequence_num < lsa2_header_ptr->sequence_num)
		{
		FRET (-1);
		}

	/* If the sequence numbers match, then check the age.  If the ages */
	/* are the same, then the LSAs are equal.                          */
	if (lsa1_header_ptr->age == lsa2_header_ptr->age)
		FRET (0);

	/* For different ages, the LSA whose age is MaxAge is preferred. */
	if (lsa1_header_ptr->age == OSPFC_MAX_AGE)
		FRET (1);

	if (lsa2_header_ptr->age == OSPFC_MAX_AGE)
		FRET (-1);

	/* If neither LSA's age is MaxAge, then prefer the LSA with the */
	/* smaller (younger) age, but only if the age difference is     */
	/* larger than MaxAgeDiff.                                      */
	if ((lsa1_header_ptr->age - lsa2_header_ptr->age) > OSPFC_MAX_AGE_DIFF)
		FRET (-1);

	if ((lsa2_header_ptr->age - lsa1_header_ptr->age) > OSPFC_MAX_AGE_DIFF)
		FRET (1);

	FRET (0);
	}

void
ospf_lsa_rxmt_list_purge (List *lsa_list_ptr, OspfT_Lsa *lsa_ptr)
	{
	OspfT_Lsa *					cur_lsa_ptr;
	int							lsa_index;
	char						router_id_str [IPC_ADDR_STR_LEN];
	char						trace_msg [128];

	/** Remove any equal or previous instances of the given LSA from the **/
	/** retransmission list.  Assume that the element in the list is a   **/
	/** pointer copy, so do not deallocate element from the list.        **/
	FIN (ospf_lsa_rxmt_list_purge (lsa_list_ptr, lsa_ptr));

	for (lsa_index = 0; lsa_index < op_prg_list_size (lsa_list_ptr); lsa_index++)
		{
		cur_lsa_ptr = op_prg_list_access (lsa_list_ptr, lsa_index);

		/* Is this an instance? */
		if ((lsa_ptr->lsa_header_ptr->type != cur_lsa_ptr->lsa_header_ptr->type) ||
			(!ip_address_equal (lsa_ptr->lsa_header_ptr->link_state_id,
				cur_lsa_ptr->lsa_header_ptr->link_state_id)) ||
			(!ip_address_equal (lsa_ptr->lsa_header_ptr->router_id,
				cur_lsa_ptr->lsa_header_ptr->router_id)))
			continue;
		
		/* Compare the headers.  If we found an equal or previous */
		/* instance, remove it from the list.                     */
		if ((ospf_lsa_compare (lsa_ptr->lsa_header_ptr, cur_lsa_ptr->lsa_header_ptr) == 1) ||
			(ospf_lsa_compare (lsa_ptr->lsa_header_ptr, cur_lsa_ptr->lsa_header_ptr) == 0))
			{
			op_prg_list_remove (lsa_list_ptr, lsa_index);

			/* Decrement reference count. */
			cur_lsa_ptr->rxmt_count--;

			/* Decrement index, since elements slide back. */
			lsa_index--;
			}
		}

	FOUT;
	}

void
ospf_lsa_header_list_purge (List *lsa_header_list_ptr, OspfT_Lsa_Header *lsa_header_ptr)
	{
	OspfT_Lsa_Header *			cur_lsa_header_ptr;
	int							header_index;

	/** Similar to above, except for headers. **/
	FIN (ospf_lsa_header_list_purge (lsa_header_list_ptr, lsa_header_ptr));

	for (header_index = 0; header_index < op_prg_list_size (lsa_header_list_ptr); header_index++)
		{
		cur_lsa_header_ptr = op_prg_list_access (lsa_header_list_ptr, header_index);

		/* Is this an instance? */
		if ((lsa_header_ptr->type != cur_lsa_header_ptr->type) ||
			(!ip_address_equal (lsa_header_ptr->link_state_id, cur_lsa_header_ptr->link_state_id)))
			continue;
		
		/* Compare the headers.  If we found and equal or previous */
		/* instance, remove it from the list.                      */
		if ((ospf_lsa_compare (lsa_header_ptr, cur_lsa_header_ptr) == 1) ||
			(ospf_lsa_compare (lsa_header_ptr, cur_lsa_header_ptr) == 0))
			{
			op_prg_list_remove (lsa_header_list_ptr, header_index);

			/* Decrement index, since elements slide back. */
			header_index--;
			}
		}

	FOUT;
	}

void
ospf_lsa_max_age_purge (OspfT_Router *router_ptr)
	{
	List *					area_list_ptr;
	OspfT_Area *			area_ptr;
	int						num_areas, area_index;
	int						lsa_index;
	OspfT_Lsa *				lsa_ptr;

	/** Purge a router's link state database of MaxAge advertisements that **/
	/** don't appear on any retransmission lists.                          **/
	FIN (ospf_lsa_max_age_purge (router_ptr));

	area_list_ptr = ospf_area_list_get (router_ptr);
	num_areas = op_prg_list_size (area_list_ptr);
	for (area_index = 0; area_index < num_areas; area_index++)
		{
		area_ptr = op_prg_list_access (area_list_ptr, area_index);
		
		/* Loop through router links advertisements. */
		for (lsa_index = 0; lsa_index < op_prg_list_size (area_ptr->router_lsa_list_ptr); lsa_index++)
			{
			lsa_ptr = op_prg_list_access (area_ptr->router_lsa_list_ptr, lsa_index);
			if ((lsa_ptr->lsa_header_ptr->age == OSPFC_MAX_AGE) &&
				(lsa_ptr->rxmt_count == 0))
				{
				op_prg_list_remove (area_ptr->router_lsa_list_ptr, lsa_index);
				ospf_lsa_destroy (lsa_ptr);
				lsa_index--;
				}
			}

		/* Loop through network links advertisements. */
		for (lsa_index = 0; lsa_index < op_prg_list_size (area_ptr->network_lsa_list_ptr); lsa_index++)
			{
			lsa_ptr = op_prg_list_access (area_ptr->network_lsa_list_ptr, lsa_index);
			if ((lsa_ptr->lsa_header_ptr->age == OSPFC_MAX_AGE) &&
				(lsa_ptr->rxmt_count == 0))
				{
				op_prg_list_remove (area_ptr->network_lsa_list_ptr, lsa_index);
				ospf_lsa_destroy (lsa_ptr);
				lsa_index--;
				}
			}

		/* Loop through summary links advertisements. */
		for (lsa_index = 0; lsa_index < op_prg_list_size (area_ptr->summary_lsa_list_ptr); lsa_index++)
			{
			lsa_ptr = op_prg_list_access (area_ptr->summary_lsa_list_ptr, lsa_index);
			if ((lsa_ptr->lsa_header_ptr->age == OSPFC_MAX_AGE) &&
				(lsa_ptr->rxmt_count == 0))
				{
				op_prg_list_remove (area_ptr->summary_lsa_list_ptr, lsa_index);
				ospf_lsa_destroy (lsa_ptr);
				lsa_index--;
				}
			}
		}

	/* This action may cause some alternative routes to be explored.  Schedule */
	/* a routing table calculation.                                            */
	router_ptr->rte_table_ptr->dirty_flag = OPC_TRUE;

	FOUT;
	}

void
ospf_lsa_flush (OspfT_Lsa *lsa_ptr, OspfT_Area *area_ptr)
	{
	char			msg_str [128];
	char			area_id_str [IPC_ADDR_STR_LEN];

	/** Flush an LSA from a particular area.  Do this by setting the advertisement's **/
	/** age to MaxAge and reflooding (as described in section 14.1 in RFC 1583).     **/
	FIN (ospf_lsa_flush (lsa_ptr, area_ptr));

	if (op_prg_odb_ltrace_active ("ospf_flush"))
		{
		ip_address_print (area_id_str, area_ptr->area_id);
		sprintf (msg_str, "Flushing LSA (%d) out of area (%s)", lsa_ptr->lsa_header_ptr->sequence_num,
			area_id_str);
		op_prg_odb_print_minor (msg_str, OPC_NIL);
		}

	lsa_ptr->lsa_header_ptr->age = OSPFC_MAX_AGE;
	ospf_area_flood (area_ptr, lsa_ptr, OPC_NIL, OPC_TRUE);

	FOUT;
	}

void
ospf_lsa_list_process (List *lsa_list_ptr, OspfT_Area *area_ptr, OspfT_Neighbor *rcvd_nbr_ptr)
	{
	int						num_lsas, lsa_index;
	OspfT_Lsa *				lsa_ptr;
	OspfT_Lsa_Header *		lsa_header_ptr;
	List *					lsr_list_ptr;
	List *					ls_rxmt_list_ptr;
	OspfT_Neighbor_State	nbr_state;
	OspfT_Lsa *				dbase_lsa_ptr;
	OspfT_Lsa *				rxmt_lsa_ptr;
	char					err_str [128];	
	int						num_neighbors, neighbor_index;
	int						num_interfaces, interface_index;
	OspfT_Interface *		interface_ptr;
	List *					neighbor_list_ptr;
	OspfT_Neighbor *		neighbor_ptr;
	List *					neighbor_ls_rxmt_list_ptr;
	Boolean					received_from_dr, hold_ack;
	List *					area_list_ptr;
	char					intf_addr_str [IPC_ADDR_STR_LEN];
	char					nbr_addr_str [IPC_ADDR_STR_LEN];
	char					router_id_str [IPC_ADDR_STR_LEN];
	char					trace_msg [128];

	/** Process a list of LSAs received from a Link State Update **/
	/** message.  This corresponds to section 13 of RFC 1583.    **/
	FIN (ospf_lsa_list_process (lsa_list_ptr, area_ptr, rcvd_nbr_ptr));

	/* Get neighbor state. */
	nbr_state = ospf_neighbor_state_get (rcvd_nbr_ptr, OPC_NIL);

	/* Note whether this was sent by the DR. */
	received_from_dr = ip_address_equal (ospf_interface_dr_get (rcvd_nbr_ptr->parent_interface_ptr),
		ospf_neighbor_router_id_get (rcvd_nbr_ptr));

	num_lsas = op_prg_list_size (lsa_list_ptr);
	
	for (lsa_index = 0; lsa_index < num_lsas; lsa_index++)
		{
		lsa_ptr = op_prg_list_access (lsa_list_ptr, lsa_index);

		/* Create a reference to the header. */
		lsa_header_ptr = lsa_ptr->lsa_header_ptr;

		/* Issue trace message. */
		if (op_prg_odb_ltrace_active ("ospf_lsa"))
			{
			ip_address_print (intf_addr_str, rcvd_nbr_ptr->parent_interface_ptr->interface_address);
			ip_address_print (nbr_addr_str, rcvd_nbr_ptr->ip_address);
			ip_address_print (router_id_str, lsa_header_ptr->router_id);
			sprintf (trace_msg, "LSA (%d) received on interface %s from neighbor %s originated by router %s",
				lsa_header_ptr->sequence_num, intf_addr_str, nbr_addr_str, router_id_str);
			op_prg_odb_print_minor (trace_msg, OPC_NIL);
			}

		/* Create references to the Link State Request list, */
		/* and Link State Retransmission list.               */
		lsr_list_ptr = ospf_neighbor_ls_request_list_get (rcvd_nbr_ptr);
		ls_rxmt_list_ptr = ospf_neighbor_ls_transmit_list_get (rcvd_nbr_ptr);

		/* Check the LSA type first. */
		if ((lsa_header_ptr->type < OspfC_Lsa_Router_Links) ||
			(lsa_header_ptr->type > OspfC_Lsa_Summary_Links))
			{
			/* Give warning. */
			ospf_warn_error ("Invalid LSA type found.");
			continue;
			}

		/* Check to see if this advertisement is in the database. */
		dbase_lsa_ptr = ospf_lsa_area_lookup (area_ptr, lsa_header_ptr->link_state_id,
			lsa_header_ptr->router_id, lsa_header_ptr->type);

		/* If the advertisement is equal to MaxAge, then take special action. */
		if ((lsa_header_ptr->age == OSPFC_MAX_AGE) && (dbase_lsa_ptr == OPC_NIL))
			{
			/* Acknowledge receipt if this advertisement does not appear in the database. */
			ospf_lsa_ack_direct_send (lsa_ptr, rcvd_nbr_ptr);

			/* Purge equal or previous instances from Link State Request list. */
			ospf_lsa_header_list_purge (lsr_list_ptr, lsa_header_ptr);

			/* If neighbor is in Exchange or Loading, then */
			/* install advertisement into database.        */
			if ((nbr_state == OspfC_Neighbor_State_Exchange) || 
				(nbr_state == OspfC_Neighbor_State_Loading))
				ospf_area_lsa_install (area_ptr, lsa_ptr);

			/* Process next LSA. */
			continue;
			}

		/* Take special action if the LSA in the message is new or more recent. */
		if ((dbase_lsa_ptr == OPC_NIL) ||
			(ospf_lsa_compare (lsa_header_ptr, dbase_lsa_ptr->lsa_header_ptr) == 1))
			{
			/* Is it too soon to add the LSA? */
			if ((dbase_lsa_ptr != OPC_NIL) &&
				((op_sim_time () - dbase_lsa_ptr->timestamp) < OSPFC_MIN_LS_INTERVAL))
				continue;

			/* Flood the advertisement out a subset of interfaces. */
			hold_ack = ospf_area_flood (area_ptr, lsa_ptr, rcvd_nbr_ptr, OPC_FALSE);
			
			/* Remove the database copy from all area neighbors' Link State Retransmission List. */
			if (dbase_lsa_ptr != OPC_NIL)
				{
				num_interfaces = op_prg_list_size (area_ptr->interface_list_ptr);
				for (interface_index = 0; interface_index < num_interfaces; interface_index++)
					{
					interface_ptr = op_prg_list_access (area_ptr->interface_list_ptr, interface_index);
					neighbor_list_ptr = ospf_interface_neighbor_list_get (interface_ptr);
					num_neighbors = op_prg_list_size (neighbor_list_ptr);	
					for (neighbor_index = 0; neighbor_index < num_neighbors; neighbor_index++)
						{
						neighbor_ptr = op_prg_list_access (neighbor_list_ptr, neighbor_index);
						neighbor_ls_rxmt_list_ptr = ospf_neighbor_ls_transmit_list_get (neighbor_ptr);
						ospf_lsa_rxmt_list_purge (neighbor_ls_rxmt_list_ptr, dbase_lsa_ptr);
						}
					}
				}

			/* Install LSA into database. */
			ospf_area_lsa_install (area_ptr, lsa_ptr);

			/* Acknowledge receipt if we didn't flood on the receiving interface. */
			if (!hold_ack)
				{
				if (ospf_interface_state_get (rcvd_nbr_ptr->parent_interface_ptr, OPC_NIL) ==
					OspfC_Interface_State_Backup)
					{
					if (received_from_dr)
						ospf_lsa_ack_delayed_send (lsa_ptr, rcvd_nbr_ptr->parent_interface_ptr);
					}
				else
					ospf_lsa_ack_delayed_send (lsa_ptr, rcvd_nbr_ptr->parent_interface_ptr);
				}

			/* Special handling for receiving self-originated advertisements. */
			if (ip_address_equal (lsa_header_ptr->router_id,
				rcvd_nbr_ptr->parent_interface_ptr->parent_area_ptr->parent_router_ptr->router_id))
				ospf_lsa_self_orig_rcvd (lsa_ptr, rcvd_nbr_ptr->parent_interface_ptr);

			continue;
			}

		/* Does this advertisement exist on the Link State Request list? */
		if (ospf_lsa_header_lookup (lsr_list_ptr, lsa_header_ptr->link_state_id, lsa_header_ptr->router_id,
			lsa_header_ptr->type) != OPC_NIL)
			{
			/* The request should have been removed by now; something */
			/* has gone wrong with the database exchange.  Restart    */
			/* the exchange by invoking BadLSReq.                     */
			ospf_neighbor_invoke (rcvd_nbr_ptr, OspfC_Neighbor_Event_Bad_Ls_Req);

			/* Do not process any more LSAs. */
			FOUT;
			}

		/* Is the message copy the same instance as the database copy? */
		if (ospf_lsa_compare (lsa_header_ptr, dbase_lsa_ptr->lsa_header_ptr) == 0)
			{
			/* Were we expecting an acknowledgement? */
			rxmt_lsa_ptr = ospf_lsa_lookup (ls_rxmt_list_ptr, lsa_header_ptr->link_state_id,
				lsa_header_ptr->router_id, lsa_header_ptr->type);

			if (rxmt_lsa_ptr != OPC_NIL)
				{
				/* This is treated as an 'implied acknowledgement'.  Remove */
				/* the LSA copy from this list.                             */
				ospf_neighbor_lsa_rxmt_remove (rcvd_nbr_ptr, rxmt_lsa_ptr);

				/* Send a delayed acknowledgement if we're the backup DR, and */
				/* we received the LSA from the DR.                           */
				if ((ospf_interface_state_get (rcvd_nbr_ptr->parent_interface_ptr, OPC_NIL) ==
					OspfC_Interface_State_Backup) && received_from_dr)
					ospf_lsa_ack_delayed_send (lsa_ptr, rcvd_nbr_ptr->parent_interface_ptr);
				}
			else
				{
				/* Duplicate, but not an 'implied acknowledgement'.  Send an */
				/* immediate and direct acknowledgement.                     */
				ospf_lsa_ack_direct_send (lsa_ptr, rcvd_nbr_ptr);
				}

			continue;
			}
		
		/* If we got here, the database copy is more recent than the */
		/* message copy.  Issue a warning in this case.              */
		ip_address_print (intf_addr_str, rcvd_nbr_ptr->parent_interface_ptr->interface_address);
		sprintf (err_str, "Received LSA (%d) on interface %s that is older than database instance.", 
			lsa_header_ptr->sequence_num, intf_addr_str);
		ospf_warn_error (err_str);
		}
	
	FOUT;
	}

void
ospf_lsa_self_orig_rcvd (OspfT_Lsa *lsa_ptr, OspfT_Interface *interface_ptr)
	{
	OspfT_Lsa *					dbase_lsa_ptr;
	char						ip_addr_str [IPC_ADDR_STR_LEN];
	char						trace_msg [64];

	/** Handles special case where a self-originated LSA is received. **/
	/** This is section 13.4 in RFC 1583.                             **/
	FIN (ospf_lsa_self_orig_rcvd (lsa_ptr, interface_ptr));

	/* Issue trace message. */
	if (op_prg_odb_ltrace_active ("ospf_lsa"))
		{
		ip_address_print (ip_addr_str, interface_ptr->interface_address);
		sprintf (trace_msg, "Received self-originated LSA on interface %s", ip_addr_str);
		op_prg_odb_print_minor (trace_msg, OPC_NIL);
		}

	/* Find the previous instance of this LSA. */
	dbase_lsa_ptr = ospf_lsa_area_lookup (interface_ptr->parent_area_ptr, 
		lsa_ptr->lsa_header_ptr->link_state_id,
		lsa_ptr->lsa_header_ptr->router_id, 
		lsa_ptr->lsa_header_ptr->type);

	/* Compare the LSAs.  If the received LSA is more recent, then */
	/* re-originate a new instance of the advertisement.           */
	if (ospf_lsa_compare (lsa_ptr->lsa_header_ptr, dbase_lsa_ptr->lsa_header_ptr) == 1)
		{
		switch (lsa_ptr->lsa_header_ptr->type)
			{
			case OspfC_Lsa_Router_Links:
				{
				ospf_area_router_links_originate (interface_ptr->parent_area_ptr);
				break;
				}
				
			case OspfC_Lsa_Network_Links:
				{
				ospf_interface_network_links_originate (interface_ptr);
				break;
				}

			default:
				{
				/* Unexpected type: give warning. */
				ospf_warn_error ("Received self-originated advertisement of unknown type");
				break;
				}
			}
		}

	FOUT;
	}

void
ospf_lsa_ack_direct_send (OspfT_Lsa *lsa_ptr, OspfT_Neighbor *nbr_ptr)
	{
	Packet *				lsack_msg_ptr;

	/** Send a direct and immediate Link State Acknowledgement to a neighbor. **/
	FIN (ospf_lsa_ack_direct_send (lsa_ptr, nbr_ptr));

	/* Create an acknowledgement message. */
	lsack_msg_ptr = ospf_message_lsack_create (nbr_ptr);
	
	/* Add the header of the LSA we want to acknowledge. */
	ospf_message_lsa_header_add (lsack_msg_ptr, lsa_ptr->lsa_header_ptr);

	/* Send directly to the neighbor. */
	ospf_neighbor_message_send (nbr_ptr, lsack_msg_ptr, OPC_FALSE);

	FOUT;
	}

void
ospf_lsa_ack_delayed_send (OspfT_Lsa *lsa_ptr, OspfT_Interface *intf_ptr)
	{
	/** Add a delayed acknowledgement to the interface's delayed acknowledgement **/
	/** list.  If we're adding to an empty list, then set up a timer to send     **/
	/** the advertisements in a single Link State Acknowledgement.  If we are    **/
	/** adding the ack to a non-empty list, then assume the timer to send the    **/
	/** acks has already been set.                                               **/
	FIN (ospf_lsa_ack_delayed_send (lsa_ptr, intf_ptr));

	if (op_prg_list_size (intf_ptr->delayed_ack_list_ptr) == 0)
		{
		/* Set up a one-shot timer to send all the acks in the list. */
		/* RFC 1583 does not specify the length of this timer, but   */
		/* does say the timer should be less than RxmtInterval.  The */
		/* timer we set here will be half of RxmtInterval.           */
		op_intrpt_schedule_call (op_sim_time () + (intf_ptr->retransmit_interval / 2),
			0, ospf_lsa_ack_delay_timer_handler, intf_ptr);
		}
	
	/* Add the ack to the list. */
	op_prg_list_insert (intf_ptr->delayed_ack_list_ptr, ospf_lsa_header_copy (lsa_ptr->lsa_header_ptr), 
		OPC_LISTPOS_TAIL);

	FOUT;
	}

void
ospf_lsa_ack_delay_timer_handler (OspfT_Interface *intf_ptr, int intrpt_code)
	{
	int						ack_index;
	OspfT_Lsa_Header *		lsa_header_ptr;
	Packet *				lsack_msg_ptr;

	/** Send the delayed acknowledgements accumulated by this interface in a **/
	/** single Link State Acknowledgement message.                           **/
	FIN (ospf_lsa_ack_delay_timer_handler (intf_ptr, intrpt_code));

	/* Create an acknowledgement message. */
	lsack_msg_ptr = ospf_message_lsack_create (OPC_NIL);

	/* Since we don't have a neighbor to help us initialize the header, */
	/* initialize it ourselves.                                         */
	ospf_message_header_init (lsack_msg_ptr, intf_ptr->parent_area_ptr->parent_router_ptr->router_id,
		intf_ptr->area_id);

	/* Loop through the accumulated link state headers and add them to the message. */
	while (op_prg_list_size (intf_ptr->delayed_ack_list_ptr) > 0)
		{
		lsa_header_ptr = op_prg_list_access (intf_ptr->delayed_ack_list_ptr, OPC_LISTPOS_HEAD);
		ospf_message_lsa_header_add (lsack_msg_ptr, lsa_header_ptr);
		op_prg_list_remove (intf_ptr->delayed_ack_list_ptr, OPC_LISTPOS_HEAD);
		ospf_lsa_header_destroy (lsa_header_ptr);
		}

	/* Send the acknowledgement. */
	ospf_interface_message_adj_send (intf_ptr, lsack_msg_ptr);

	FOUT;
	}

/***** Constructors *****/

OspfT_Lsa *
ospf_lsa_create (OspfT_Lsa_Header *lsa_header_ptr)
	{
	OspfT_Lsa *				lsa_ptr;
	char					err_msg [128];

	/** Allocate and initialize a link state advertisement.  As much initialization **/
	/** will be performed given the information available, although it is left to   **/
	/** the client to fill in much of the information.                              **/
	FIN (ospf_lsa_create (lsa_header_ptr));

	/* Allocate storage for the LSA. */
	lsa_ptr = (OspfT_Lsa *) op_prg_mem_alloc (sizeof (OspfT_Lsa));

	/* Create a header. */
	lsa_ptr->lsa_header_ptr = lsa_header_ptr;

	/* Set the creation time. */
	lsa_ptr->timestamp = op_sim_time ();

	/* Initially, the LSA is not slated for replacement. */
	lsa_ptr->replace = OPC_FALSE;

	/* Initially, the LSA is not on a retransmission list. */
	lsa_ptr->rxmt_count = 0;

	/* For a NIL header, return early. */
	if (lsa_header_ptr == OPC_NIL)
		FRET (lsa_ptr);

	/* Add the type specific part of the LSA. */
	switch (lsa_header_ptr->type)
		{
		case OspfC_Lsa_Router_Links:
			{
			lsa_ptr->lsa_data.lsa_router_links_ptr = ospf_lsa_router_links_create ();
			break;
			}

		case OspfC_Lsa_Network_Links:
			{
			lsa_ptr->lsa_data.lsa_network_links_ptr = ospf_lsa_network_links_create ();
			break;
			}

		case OspfC_Lsa_Summary_Links:
			{
			lsa_ptr->lsa_data.lsa_summary_links_ptr = ospf_lsa_summary_links_create ();
			break;
			}
			
		default:
			{
			sprintf (err_msg, "Trying to create LSA of unknown or unsupported type (%d)", 
				lsa_header_ptr->type);
			ospf_fatal_error (err_msg);
			break;
			}
		}

	FRET (lsa_ptr);
	}

OspfT_Lsa_Header *
ospf_lsa_header_create (OspfT_Lsa_Type lsa_type, IpT_Address orig_router_id, IpT_Address link_state_id)
	{
	OspfT_Lsa_Header *				lsa_header_ptr;

	/** Create a link state advertisement header.  The input denotes what header **/
	/** type to create (only affects the type field).                            **/
	FIN (ospf_lsa_header_create (lsa_type, orig_router_id, link_state_id));

	/* Allocate storage for the LSA header. */
	lsa_header_ptr = (OspfT_Lsa_Header *) op_prg_mem_alloc (sizeof (OspfT_Lsa_Header));

	/* Use reasonable values for the header. */
	lsa_header_ptr->age = 0;
	lsa_header_ptr->type = lsa_type;
	lsa_header_ptr->sequence_num = OspfI_Lsa_Seq_Num++;
	lsa_header_ptr->num_retrans = 0;

	/* Fill in the router ID (the router that originated this LSA). */
	lsa_header_ptr->router_id = ip_address_copy (orig_router_id);

	/* The link state ID depends on the LSA type.  What goes here exactly is */
	/* specified in section 12.1.4 in RFC 1583.  It is the responsibility    */
	/* of the client to pass it to this procedure.                           */
	lsa_header_ptr->link_state_id = ip_address_copy (link_state_id);

	FRET (lsa_header_ptr);
	}

OspfT_Lsa_Router_Links *
ospf_lsa_router_links_create (void)
	{
	OspfT_Lsa_Router_Links *			router_links_ptr;

	/** Allocate and initialize data specific to a router links advertisement. **/
	FIN (ospf_lsa_router_links_create (void));

	/* Allocate storage for the object. */
	router_links_ptr = (OspfT_Lsa_Router_Links *) op_prg_mem_alloc (sizeof (OspfT_Lsa_Router_Links));

	/* Use reasonable values for initialization. */
	router_links_ptr->is_asbr = OPC_FALSE;
	router_links_ptr->is_abr = OPC_FALSE;
	router_links_ptr->link_list_ptr = op_prg_list_create ();

	FRET (router_links_ptr);
	}

OspfT_Lsa_Router_Links_Info *
ospf_lsa_router_links_info_create (void)
	{
	OspfT_Lsa_Router_Links_Info *		link_info_ptr;

	/** Allocate and initialize link data used for router links advertisements. **/
	FIN (ospf_lsa_router_links_info_create (void));

	/* Allocate storage for the link information object. */
	link_info_ptr = (OspfT_Lsa_Router_Links_Info *) op_prg_mem_alloc (sizeof (OspfT_Lsa_Router_Links_Info));

	/* Use reasonable values for initialization. */
	link_info_ptr->link_id = OPC_NIL;
	link_info_ptr->link_data = OPC_NIL;
	link_info_ptr->link_type = OspfC_Lsa_Router_Link_Point_To_Point;
	link_info_ptr->link_cost = 1;

	FRET (link_info_ptr);
	}

OspfT_Lsa_Network_Links *
ospf_lsa_network_links_create (void)
	{
	OspfT_Lsa_Network_Links *		network_links_ptr;

	/** Allocate and initialize a network links object. **/
	FIN (ospf_lsa_network_links_create (void));

	/* Allocate storage for the network links object. */
	network_links_ptr = (OspfT_Lsa_Network_Links *) op_prg_mem_alloc (sizeof (OspfT_Lsa_Network_Links));

	/* Use reasonable values for initialization. */
	network_links_ptr->network_mask = OPC_NIL;
	network_links_ptr->router_list_ptr = op_prg_list_create ();

	FRET (network_links_ptr);
	}

OspfT_Lsa_Summary_Links *
ospf_lsa_summary_links_create (void)
	{
	OspfT_Lsa_Summary_Links *		summary_links_ptr;

	/** Allocate and initialize a summary links object. **/
	FIN (ospf_lsa_summary_links_create (void));

	/* Allocate storage for the summary links object. */
	summary_links_ptr = (OspfT_Lsa_Summary_Links *) op_prg_mem_alloc (sizeof (OspfT_Lsa_Summary_Links));
	
	/* Use reasonable values for initialization. */
	summary_links_ptr->network_mask = OPC_NIL;
	summary_links_ptr->network_cost = 0;

	FRET (summary_links_ptr);
	}

/***** Destructors *****/
void
ospf_lsa_header_destroy (OspfT_Lsa_Header *lsa_header_ptr)
	{
	/** Procedure to deallocate a LSA header. **/
	FIN (ospf_lsa_header_destroy (lsa_header_ptr));

	/* Destroy the components that are IP addresses. */
	ip_address_destroy (lsa_header_ptr->link_state_id);
	ip_address_destroy (lsa_header_ptr->router_id);

	/* Deallocate the object itself. */
	op_prg_mem_free (lsa_header_ptr);

	FOUT;
	}

void
ospf_lsa_destroy (OspfT_Lsa *lsa_ptr)
	{
	OspfT_Lsa_Type		lsa_type;

	/** Procedure to deallocate an LSA. **/
	FIN (ospf_lsa_destroy (lsa_ptr));

	/* First check the type to decide which part of the structure to deallocate. */
	lsa_type = ospf_lsa_type_get (lsa_ptr);

	switch (lsa_type)
		{
		case OspfC_Lsa_Router_Links:
			{
			ospf_lsa_router_links_destroy (lsa_ptr->lsa_data.lsa_router_links_ptr);
			break;
			}

		case OspfC_Lsa_Network_Links:
			{
			ospf_lsa_network_links_destroy (lsa_ptr->lsa_data.lsa_network_links_ptr);
			break;
			}

		case OspfC_Lsa_Summary_Links:
			{
			ospf_lsa_summary_links_destroy (lsa_ptr->lsa_data.lsa_summary_links_ptr);
			break;
			}

		default:
			{
			/* A type we don't handle.  Just break at this point. */
			ospf_warn_error ("Trying to destroy LSA of unknown type");
			break;
			}
		}

	/* Then destroy the header. */
	ospf_lsa_header_destroy (lsa_ptr->lsa_header_ptr);

	/* Finally, deallocate the structure itself. */
	op_prg_mem_free (lsa_ptr);

	FOUT;
	}

void
ospf_lsa_router_links_destroy (OspfT_Lsa_Router_Links *router_links_ptr)
	{
	int								num_links, link_index;
	OspfT_Lsa_Router_Links_Info *	router_link_info_ptr;

	/** Procedure to deallocate router links portion of LSA. **/
	FIN (ospf_lsa_router_links_destroy (router_links_ptr));

	/* Deallocate the router links information list. */
	num_links = op_prg_list_size (router_links_ptr->link_list_ptr);

	for (link_index = 0; link_index < num_links; link_index++)
		{
		router_link_info_ptr = op_prg_list_remove (router_links_ptr->link_list_ptr, OPC_LISTPOS_HEAD);
		ospf_lsa_router_links_info_destroy (router_link_info_ptr);
		}

	op_prg_list_free (router_links_ptr->link_list_ptr);

	/* Deallocate the rest of the structure. */
	op_prg_mem_free (router_links_ptr);

	FOUT;
	}

void
ospf_lsa_router_links_info_destroy (OspfT_Lsa_Router_Links_Info *router_links_info_ptr)
	{
	/** Procedure to deallocate router links information object. **/
	FIN (ospf_lsa_router_links_info_destroy (router_links_info_ptr));

	/* Destroy the IP address components. */
	ip_address_destroy (router_links_info_ptr->link_id);
	ip_address_destroy (router_links_info_ptr->link_data);

	/* Deallocate the structure. */
	op_prg_mem_free (router_links_info_ptr);

	FOUT;
	}

void
ospf_lsa_network_links_destroy (OspfT_Lsa_Network_Links *network_links_ptr)
	{
	int						num_routers, router_index;
	OspfT_Router_Id			router_id;

	/** Procedure to deallocate network links portion of LSA. **/
	FIN (ospf_lsa_network_links_destroy (network_links_ptr));

	/* Deallocate list of routers. */
	num_routers = op_prg_list_size (network_links_ptr->router_list_ptr);
	for (router_index = 0; router_index < num_routers; router_index++)
		{
		router_id = op_prg_list_remove (network_links_ptr->router_list_ptr, OPC_LISTPOS_HEAD);
		ip_address_destroy (router_id);
		}

	op_prg_list_free (network_links_ptr->router_list_ptr);

	/* Destroy the IP address components. */
	ip_address_destroy (network_links_ptr->network_mask);
	
	/* Then destroy the structure. */
	op_prg_mem_free (network_links_ptr);

	FOUT;
	}

void
ospf_lsa_summary_links_destroy (OspfT_Lsa_Summary_Links *summary_links_ptr)
	{
	/** Procedure to deallocate summary links portion of LSA. **/
	FIN (ospf_lsa_summary_links_destroy (summary_links_ptr));

	/* Deallocate the IP components. */
	ip_address_destroy (summary_links_ptr->network_mask);

	/* Deallocate the structure. */
	op_prg_mem_free (summary_links_ptr);

	FOUT;
	}

/***** Print Procedures *****/

void
ospf_lsa_list_print (List *lsa_list_ptr)
	{
	char			str [512];
	int				lsa_list_size, lsa_index;
	OspfT_Lsa *		cur_lsa_ptr;

	/** Prints out a list of link state advertisements. **/
	FIN (ospf_lsa_list_print (lsa_list_ptr));

	/* For a null list, then print out an appropriate message. */
	if (lsa_list_ptr == OPC_NIL)
		{
		op_prg_odb_print_minor ("Link state advertisement list is NIL.", OPC_NIL);
		FOUT;
		}

	/* Get size of list. */
	lsa_list_size = op_prg_list_size (lsa_list_ptr);
	sprintf (str, "Link state advertisement list size: %d", lsa_list_size);
	op_prg_odb_print_minor (str, "----------------------------------", OPC_NIL);

	/* Loop through the list and print out info about each LSA. */
	for (lsa_index = 0; lsa_index < lsa_list_size; lsa_index++)
		{
		/* Get current LSA. */
		cur_lsa_ptr = (OspfT_Lsa *) op_prg_list_access (lsa_list_ptr, lsa_index);

		/* Print out the LSA. */
		ospf_lsa_print (cur_lsa_ptr);
		}

	op_prg_odb_print_minor ("", OPC_NIL);
	
	FOUT;
	}

void
ospf_lsa_print (OspfT_Lsa *lsa_ptr)
	{
	/** Print out link state advertisement. **/
	FIN (ospf_lsa_print (lsa_ptr));
	
	/* First print out the header. */
	ospf_lsa_header_print (lsa_ptr->lsa_header_ptr);

	/* Then print out the contents.  The contents of the LSA depend on the type. */
	switch (lsa_ptr->lsa_header_ptr->type)
		{
		case OspfC_Lsa_Router_Links:
			{
			ospf_lsa_router_links_print (lsa_ptr->lsa_data.lsa_router_links_ptr);
			break;
			}

		case OspfC_Lsa_Network_Links:
			{
			ospf_lsa_network_links_print (lsa_ptr->lsa_data.lsa_network_links_ptr);
			break;
			}

		case OspfC_Lsa_Summary_Links:
			{
			ospf_lsa_summary_links_print (lsa_ptr->lsa_data.lsa_summary_links_ptr);
			break;
			}

		default:
			{
			op_prg_odb_print_minor ("Unknown LSA type encountered.", OPC_NIL);
			break;
			}
		}

	/* Add a divider. */
	op_prg_odb_print_minor ("", OPC_NIL);

	FOUT;
	}

void
ospf_lsa_header_print (OspfT_Lsa_Header *lsa_header_ptr)
	{
	char				adv_type [64];
	char				lsa_header1_str [1024];
	char				lsa_header2_str [1024];
	char				link_state_id_str [IPC_ADDR_STR_LEN];
	char				router_id_str [IPC_ADDR_STR_LEN];

	/** Print out link state advertisement header. **/
	FIN (ospf_lsa_header_print (lsa_header_ptr));

	/* First print out the LSA type. */
	switch (lsa_header_ptr->type)
		{
		case OspfC_Lsa_Router_Links:
			{
			strcpy (adv_type, "Router Links");
			break;
			}

		case OspfC_Lsa_Network_Links:
			{
			strcpy (adv_type, "Network Links");
			break;
			}

		case OspfC_Lsa_Summary_Links:
			{
			strcpy (adv_type, "Summary Links (type 3)");
			break;
			}

		default:
			{
			/* Shouldn't reach this part. */
			break;
			}
		}

	/* Now print out the rest of the fields. */
	ip_address_print (link_state_id_str, lsa_header_ptr->link_state_id);
	ip_address_print (router_id_str, lsa_header_ptr->router_id);
	sprintf (lsa_header1_str, "LSA Type: %s, Link State ID: %s, Adv Router ID: %s",
		adv_type, link_state_id_str, router_id_str);

	if (lsa_header_ptr->age == OSPFC_MAX_AGE)
		sprintf (lsa_header2_str, "Sequence Number: %d, LSA Age: MaxAge", lsa_header_ptr->sequence_num);
	else
		sprintf (lsa_header2_str, "Sequence Number: %d, LSA Age: %f", lsa_header_ptr->sequence_num,
			lsa_header_ptr->age);

	op_prg_odb_print_minor (lsa_header1_str, lsa_header2_str, OPC_NIL);

	FOUT;
	}

void
ospf_lsa_summary_links_print (OspfT_Lsa_Summary_Links *summary_links_ptr)
	{
	char			subnet_mask_str [IPC_ADDR_STR_LEN];
	char			str [512];

	/** Print out contents of a summary links advertisement. **/
	FIN (ospf_lsa_summary_links_print (summary_links_ptr));

	/* Print out subnet mask and cost to network. */
	ip_address_print (subnet_mask_str, summary_links_ptr->network_mask);
	sprintf (str, "  Subnet mask: %s\tAdvertised cost: %d", subnet_mask_str, 
		summary_links_ptr->network_cost);
	op_prg_odb_print_minor (str, OPC_NIL);
	
	FOUT;
	}

void
ospf_lsa_network_links_print (OspfT_Lsa_Network_Links *network_links_ptr)
	{
	int					num_routers, router_index;
	OspfT_Router_Id		router_id;
	char				subnet_mask_str [IPC_ADDR_STR_LEN];
	char				router_id_str [IPC_ADDR_STR_LEN];
	char				str [512];

	/** Print out contents of a network links advertisement. **/
	FIN (ospf_lsa_network_links_print (network_links_ptr));

	/* Print out subnet mask. */
	ip_address_print (subnet_mask_str, network_links_ptr->network_mask);
	sprintf (str, "  Subnet mask: %s", subnet_mask_str);
	op_prg_odb_print_minor (str, OPC_NIL);

	/* Print out the router list. */
	op_prg_odb_print_minor ("  Attached router IDs:", OPC_NIL);

	num_routers = op_prg_list_size (network_links_ptr->router_list_ptr);
	if (num_routers == 0)
		op_prg_odb_print_minor ("NONE", OPC_NIL);

	for (router_index = 0; router_index < num_routers; router_index++)
		{
		/* Get current router ID. */
		router_id = op_prg_list_access (network_links_ptr->router_list_ptr, router_index);
		
		ip_address_print (router_id_str, router_id);
		sprintf (str, "    %s", router_id_str);
		op_prg_odb_print_minor (str, OPC_NIL);
		}
	
	FOUT;
	}

void
ospf_lsa_router_links_print (OspfT_Lsa_Router_Links *router_links_ptr)
	{
    int								num_links, link_index;
	OspfT_Lsa_Router_Links_Info *	link_info_ptr;
	char							link_type_str [64];
	char							str [512];
	char							link_data_str [IPC_ADDR_STR_LEN], link_id_str [IPC_ADDR_STR_LEN];
	
	/** Print out contents of a router links advertisement. **/
	FIN (ospf_lsa_router_links_print (router_links_ptr));

	/* Print out whether or not the advertisement indicates a special router type. */
	if (router_links_ptr->is_asbr)
		op_prg_odb_print_minor ("  ** AS Boundary Router **", OPC_NIL);

	if (router_links_ptr->is_abr)
		op_prg_odb_print_minor ("  ** Area Border Router **", OPC_NIL);

	if (router_links_ptr->link_list_ptr == OPC_NIL)
		{
		op_prg_odb_print_minor ("  Advertisement has a NIL links list", OPC_NIL);
		FOUT;
		}

	/* Get the number of links advertised by the router. */
	num_links = op_prg_list_size (router_links_ptr->link_list_ptr);

	/* Print out the links connected to the router. */
	for (link_index = 0; link_index < num_links; link_index++)
		{
		/* Get current link. */
		link_info_ptr = (OspfT_Lsa_Router_Links_Info *) op_prg_list_access (router_links_ptr->link_list_ptr, link_index);

		switch (link_info_ptr->link_type)
			{
			case OspfC_Lsa_Router_Link_Point_To_Point:
				{
				strcpy (link_type_str, "Point-To-Point");
				break;
				}

			case OspfC_Lsa_Router_Link_Transit_Net:
				{
				strcpy (link_type_str, "Transit Network");
				break;
				}

			case OspfC_Lsa_Router_Link_Stub_Net:
				{
				strcpy (link_type_str, "Stub Network");
				break;
				}

			default:
				{
				strcpy (link_type_str, "Unknown");
				break;
				}
			}		

		ip_address_print (link_id_str, link_info_ptr->link_id);
		ip_address_print (link_data_str, link_info_ptr->link_data);
		sprintf (str, "  Link Type: %s, Link ID: %s, Link Data: %s, Link Cost: %d",
			link_type_str, link_id_str, link_data_str, link_info_ptr->link_cost);
		op_prg_odb_print_minor (str, OPC_NIL);
		}
	
	FOUT;
	}

/***** Copy constructors *****/
OspfT_Lsa *
ospf_lsa_copy (OspfT_Lsa *lsa_ptr)
	{
	OspfT_Lsa *			copy_lsa_ptr;
	OspfT_Lsa_Type		lsa_type;
	OspfT_Lsa_Header * 	lsa_header_ptr;

	/** Returns a copy of the input LSA. **/
	FIN (ospf_lsa_copy (lsa_ptr));

	/* Get the type of the LSA. */
	lsa_type = ospf_lsa_type_get (lsa_ptr);

	/* Create a copy of the header. */
	lsa_header_ptr = ospf_lsa_header_create (lsa_ptr->lsa_header_ptr->type, 
		lsa_ptr->lsa_header_ptr->router_id,
		lsa_ptr->lsa_header_ptr->link_state_id);

	/* Create a new LSA based on input. */
	copy_lsa_ptr = ospf_lsa_create (lsa_header_ptr);

	/* Transfer the header contents. */
	copy_lsa_ptr->lsa_header_ptr->age = lsa_ptr->lsa_header_ptr->age;
	copy_lsa_ptr->lsa_header_ptr->num_retrans = lsa_ptr->lsa_header_ptr->num_retrans;

	/* Transfer other contents. */
	copy_lsa_ptr->timestamp = lsa_ptr->timestamp;
	copy_lsa_ptr->replace = lsa_ptr->replace;
	copy_lsa_ptr->rxmt_count = lsa_ptr->rxmt_count;

	/* Initialize further based on type. */
	switch (lsa_type)
		{
		case OspfC_Lsa_Router_Links:
			{
			copy_lsa_ptr->lsa_data.lsa_router_links_ptr = 
				ospf_lsa_router_links_copy (lsa_ptr->lsa_data.lsa_router_links_ptr);
			break;
			}
			
		case OspfC_Lsa_Network_Links:
			{
			copy_lsa_ptr->lsa_data.lsa_network_links_ptr = 
				ospf_lsa_network_links_copy (lsa_ptr->lsa_data.lsa_network_links_ptr);
			break;
			}

		case OspfC_Lsa_Summary_Links:
			{
			copy_lsa_ptr->lsa_data.lsa_summary_links_ptr = 
				ospf_lsa_summary_links_copy (lsa_ptr->lsa_data.lsa_summary_links_ptr);
			break;
			}

		default:
			{
			/* Type not handled. */
			ospf_warn_error ("Unable to copy LSA of unknown type.");
			FRET (OPC_NIL);
			break;
			}
		}

	FRET (copy_lsa_ptr);
	}

OspfT_Lsa_Header *
ospf_lsa_header_copy (OspfT_Lsa_Header *lsa_header_ptr)
	{
	OspfT_Lsa_Header *				copy_lsa_header_ptr;
	
	/** Allocates, copies, and returns a new LSA header. **/
	FIN (ospf_lsa_header_copy (lsa_header_ptr));

	copy_lsa_header_ptr = ospf_lsa_header_create (lsa_header_ptr->type,
		lsa_header_ptr->router_id, lsa_header_ptr->link_state_id);

	FRET (copy_lsa_header_ptr);
	}

OspfT_Lsa_Router_Links *
ospf_lsa_router_links_copy (OspfT_Lsa_Router_Links *router_links_ptr)
	{
	int								num_info, info_index;
	OspfT_Lsa_Router_Links_Info *	info_ptr;
	OspfT_Lsa_Router_Links_Info *	copy_info_ptr;
	OspfT_Lsa_Router_Links *		copy_router_links_ptr;

	/** Create a copy of the router links portion of the LSA. **/
	FIN (ospf_lsa_router_links_copy (router_links_ptr));

	copy_router_links_ptr = ospf_lsa_router_links_create ();

	copy_router_links_ptr->is_asbr = router_links_ptr->is_asbr;
	copy_router_links_ptr->is_abr = router_links_ptr->is_abr;

	/* Copy the list of router links info. */
	num_info = op_prg_list_size (router_links_ptr->link_list_ptr);

	for (info_index = 0; info_index < num_info; info_index++)
		{
		/* Get current info object. */
		info_ptr = (OspfT_Lsa_Router_Links_Info *) op_prg_list_access (router_links_ptr->link_list_ptr,
			info_index);
		
		/* Copy info object. */
		copy_info_ptr = ospf_lsa_router_links_info_copy (info_ptr);

		/* Append this to the copy list. */
		op_prg_list_insert (copy_router_links_ptr->link_list_ptr, copy_info_ptr, OPC_LISTPOS_TAIL);
		}

	FRET (copy_router_links_ptr);
	}

OspfT_Lsa_Router_Links_Info *
ospf_lsa_router_links_info_copy (OspfT_Lsa_Router_Links_Info *info_ptr)
	{
	OspfT_Lsa_Router_Links_Info *		copy_info_ptr;

	/** Create a copy of a router links information object. **/
	FIN (ospf_lsa_router_links_info_copy (info_ptr));

	/* Allocate copy. */
	copy_info_ptr = ospf_lsa_router_links_info_create ();

	/* Transfer contents. */
	copy_info_ptr->link_id = ip_address_copy (info_ptr->link_id);
	copy_info_ptr->link_data = ip_address_copy (info_ptr->link_data);
	copy_info_ptr->link_type = info_ptr->link_type;
	copy_info_ptr->link_cost = info_ptr->link_cost;
	
	FRET (copy_info_ptr);
	}

OspfT_Lsa_Network_Links *	
ospf_lsa_network_links_copy (OspfT_Lsa_Network_Links *network_links_ptr)
	{
	OspfT_Lsa_Network_Links *		copy_network_links_ptr;
	int								num_routers, router_index;
	OspfT_Router_Id					router_id, copy_router_id;
	
	/** Create a copy of the network links portion of the LSA. **/
	FIN (ospf_lsa_network_links_copy (network_links_ptr));

	/* Allocate copy. */
	copy_network_links_ptr = ospf_lsa_network_links_create ();

	/* Transfer contents. */
	copy_network_links_ptr->network_mask = ip_address_copy (network_links_ptr->network_mask);

	/* Transfer connected router list. */
	num_routers = op_prg_list_size (network_links_ptr->router_list_ptr);

	for (router_index = 0; router_index < num_routers; router_index++)
		{
		/* Get current router ID. */
		router_id = op_prg_list_access (network_links_ptr->router_list_ptr, router_index);

		/* Create a new router ID. */
		copy_router_id = ip_address_copy (router_id);

		/* Add new router ID to list copy. */
		op_prg_list_insert (copy_network_links_ptr->router_list_ptr, copy_router_id, OPC_LISTPOS_TAIL);
		}

	FRET (copy_network_links_ptr);
	}

OspfT_Lsa_Summary_Links *
ospf_lsa_summary_links_copy (OspfT_Lsa_Summary_Links *summary_links_ptr)
	{
	OspfT_Lsa_Summary_Links *		copy_summary_links_ptr;

	/** Create a copy of the summary links portion of the LSA. **/
	FIN (ospf_lsa_summary_links_copy (summary_links_ptr, copy_summary_links_ptr));

	/* Allocate copy. */
	copy_summary_links_ptr = ospf_lsa_summary_links_create ();

	/* Transfer contents. */
	copy_summary_links_ptr->network_mask = ip_address_copy (summary_links_ptr->network_mask);
	copy_summary_links_ptr->network_cost = summary_links_ptr->network_cost;

	FOUT;
	}

/***** Interface to Dijkstra Package *****/
List *
ospf_lsa_djk_node_list_create (OspfT_Area *area_ptr)
	{
	List *					node_list_ptr;
	int						num_lsa, lsa_index;
	OspfT_Lsa *				lsa_ptr;
	DjkT_Node *				node_ptr;

	/** Create the initial working list of Dijkstra nodes for the area. **/
	FIN (ospf_lsa_djk_node_list_create (area_ptr));

	node_list_ptr = op_prg_list_create ();
	num_lsa = op_prg_list_size (area_ptr->router_lsa_list_ptr);
	for (lsa_index = 0; lsa_index < num_lsa; lsa_index++)
		{
		node_ptr = djk_node_create ();
		lsa_ptr = op_prg_list_access (area_ptr->router_lsa_list_ptr, lsa_index);

		/* Set the user-defined state of the node to be the LSA. */
		node_ptr->node_state_ptr = lsa_ptr;

		/* Add node to list. */
		op_prg_list_insert (node_list_ptr, node_ptr, OPC_LISTPOS_TAIL);
		}

	num_lsa = op_prg_list_size (area_ptr->network_lsa_list_ptr);
	for (lsa_index = 0; lsa_index < num_lsa; lsa_index++)
		{
		node_ptr = djk_node_create ();
		lsa_ptr = op_prg_list_access (area_ptr->network_lsa_list_ptr, lsa_index);

		/* Set the user-defined state of the node to be the LSA. */
		node_ptr->node_state_ptr = lsa_ptr;

		/* Add node to list. */
		op_prg_list_insert (node_list_ptr, node_ptr, OPC_LISTPOS_TAIL);
		}

	FRET (node_list_ptr);
	}

DjkT_Node *
ospf_lsa_djk_node_lookup (List *node_list_ptr, IpT_Address link_state_id, OspfT_Lsa_Type lsa_type)
	{
	DjkT_Node *			node_ptr;
	int					num_nodes, node_index;		
	OspfT_Lsa *			node_lsa_ptr;

	/** Look up a Dijkstra node that matches the link state ID and link state type **/
	/** found in the LSA stored (as user-defined state) in the node.  Returns      **/
	/** OPC_NIL if no matching nodes are found.                                    **/
	FIN (ospf_lsa_djk_node_lookup (node_list_ptr, link_state_id, lsa_type));

	num_nodes = op_prg_list_size (node_list_ptr);
	for (node_index = 0; node_index < num_nodes; node_index++)
		{
		node_ptr = op_prg_list_access (node_list_ptr, node_index);
		node_lsa_ptr = (OspfT_Lsa *) node_ptr->node_state_ptr;

		/* If no LSA is defined for this node, skip it. */
		if (node_lsa_ptr == OPC_NIL)
			continue;
		
		if ((node_lsa_ptr->lsa_header_ptr->type == lsa_type) &&
			(ip_address_equal (node_lsa_ptr->lsa_header_ptr->link_state_id, link_state_id)))
			FRET (node_ptr);
		}

	FRET (OPC_NIL);
	}

void
ospf_lsa_djk_nodes_add (OspfT_Lsa *lsa_ptr, List *node_list_ptr)
	{
	DjkT_Node *				djk_node_ptr;
	OspfT_Lsa_Header *		lsa_header_ptr;
	OspfT_Lsa_Type			lsa_type;

	/** Procedure that creates a Dijkstra node based on an LSA. **/
	FIN (ospf_lsa_djk_nodes_add (lsa_ptr, node_list_ptr));
	
	/* Get the LSA type. */
	lsa_type = ospf_lsa_type_get (lsa_ptr);

	/* Create a reference to the LSA header. */
	lsa_header_ptr = lsa_ptr->lsa_header_ptr;

	/* Find the node that matches this header. */
	djk_node_ptr = ospf_lsa_djk_node_lookup (node_list_ptr, lsa_header_ptr->link_state_id,
		lsa_header_ptr->type);
	
	/* Start a connection list; this will be based on the type of LSA. */
	switch (lsa_type)
		{
		case OspfC_Lsa_Router_Links:
			{
			ospf_lsa_djk_router_connect_create (djk_node_ptr, lsa_ptr, node_list_ptr);
			break;
			}

		case OspfC_Lsa_Network_Links:
			{
			ospf_lsa_djk_network_connect_create (djk_node_ptr, lsa_ptr, node_list_ptr);
			break;
			}

		default:
			{
			/* For cases that are not handled explicitly. */
			ospf_warn_error ("Trying to create Dijkstra node from a non-router or network LSA.");
			break;
			}
		}

	FOUT;
	}

void
ospf_lsa_djk_router_connect_create (DjkT_Node *node_ptr, OspfT_Lsa *lsa_ptr, List *node_list_ptr)
	{
	DjkT_Connection *				connect_ptr;
	DjkT_Connection *				stub_connect_ptr;
	OspfT_Lsa_Router_Links *		router_links_ptr;
	OspfT_Lsa_Router_Links_Info *	router_links_info_ptr;
	int								num_links, link_index;
	DjkT_Node *						connect_node_ptr;
	OspfT_Lsa *						stub_lsa_ptr;
	char							err_msg [256];
	char							vertex_rtr_id [IPC_ADDR_STR_LEN];
	char							cur_rtr_id [IPC_ADDR_STR_LEN];
	char							cur_rtrlink_link_id [IPC_ADDR_STR_LEN];
	char							cur_rtrlink_link_state_id [IPC_ADDR_STR_LEN];

	/** Create the connection list for a Dijkstra node based on a router links LSA. **/
	/** Note that this procedure may also return additional nodes representing      **/
	/** router connections to stub networks.                                        **/
	FIN (ospf_lsa_djk_router_connect_create (node_ptr, lsa_ptr, node_list_ptr));

	/* Create a reference to the router specific part of the LSA. */
	router_links_ptr = lsa_ptr->lsa_data.lsa_router_links_ptr;

	/* Loop through the connections, and add to the connection list for each router connection. */
	num_links = op_prg_list_size (router_links_ptr->link_list_ptr);
	
	for (link_index = 0; link_index < num_links; link_index++)
		{
		/* Get current link info object. */
		router_links_info_ptr = (OspfT_Lsa_Router_Links_Info *) 
			op_prg_list_access (router_links_ptr->link_list_ptr, link_index);

		/* Create a connection. */
		connect_ptr = djk_connection_create ();

		/* Set the connection elements to values based on the link info object. */
		connect_ptr->cost = router_links_info_ptr->link_cost;
		
		/* Set the user defined state as the router link element. */
		connect_ptr->connect_state_ptr = router_links_info_ptr;

		/* Find the connecting node. */
		if (router_links_info_ptr->link_type == OspfC_Lsa_Router_Link_Point_To_Point)
			{
			/* The connecting node is a router. */
			connect_node_ptr = ospf_lsa_djk_node_lookup (node_list_ptr, router_links_info_ptr->link_id,
				OspfC_Lsa_Router_Links);

			/* If connect_node_ptr == OPC_NIL, we did not find a LSA	*/
			/* from the router which is the target vertex for the link	*/ 
			/* that we are processing. Eliminate this link from route	*/
			/* table computation, output a diagnostic and move on.		*/
			if (connect_node_ptr == OPC_NIL)
				{
				ip_address_print (vertex_rtr_id, router_links_info_ptr->link_id);
				ip_address_print (cur_rtr_id, lsa_ptr->lsa_header_ptr->router_id); 
				ip_address_print (cur_rtrlink_link_id, router_links_info_ptr->link_id); 
				ip_address_print (cur_rtrlink_link_state_id, router_links_info_ptr->link_data);
				sprintf (err_msg, 
					"No Router Links LSA in LSDB from %s, when processing Router Links LSA from %s, whose Link ID = %s and Link Data = %s.", 
					vertex_rtr_id, cur_rtr_id, cur_rtrlink_link_id, cur_rtrlink_link_state_id ); 
				ospf_warn_error (err_msg);
				djk_connection_destroy (connect_ptr);
				continue;
				}

			}
		else if (router_links_info_ptr->link_type == OspfC_Lsa_Router_Link_Transit_Net)
			{
			/* The connecting node is a transit network. */
			connect_node_ptr = ospf_lsa_djk_node_lookup (node_list_ptr, router_links_info_ptr->link_id,
				OspfC_Lsa_Network_Links);

			/* Flag error if we didn't find the node. */
			if (connect_node_ptr == OPC_NIL)
				ospf_fatal_error ("Network links Dijkstra node lookup failed.");
			}
		else
			{
			/* The connecting node is a stub network. */
			connect_node_ptr = ospf_lsa_djk_node_lookup (node_list_ptr, router_links_info_ptr->link_id,
				OspfC_Lsa_Network_Links);

			/* If we didn't find the node, then one must be created. */
			if (connect_node_ptr == OPC_NIL)
				{
				connect_node_ptr = djk_node_create ();
				
				/* Create a 'fake' LSA to act as a placeholder for this stub network. */
				stub_lsa_ptr = ospf_lsa_create (ospf_lsa_header_create (OspfC_Lsa_Network_Links,
					IpI_Default_Addr, router_links_info_ptr->link_id));
				stub_lsa_ptr->lsa_data.lsa_network_links_ptr->network_mask = 
					ip_address_copy (router_links_info_ptr->link_data);
				connect_node_ptr->node_state_ptr = stub_lsa_ptr;

				/* Also add the stub node to the area node list. */
				op_prg_list_insert (node_list_ptr, connect_node_ptr, OPC_LISTPOS_TAIL);
				}

			/* Add a connection back to the router, assume the same cost. */
			stub_connect_ptr = djk_connection_create ();
			stub_connect_ptr->cost = router_links_info_ptr->link_cost;
			stub_connect_ptr->node_ptr = node_ptr;
			op_prg_list_insert (connect_node_ptr->connection_list_ptr, stub_connect_ptr, OPC_LISTPOS_TAIL);
			}
			
		connect_ptr->node_ptr = connect_node_ptr;

		/* Add this object to the node connection list. */
		op_prg_list_insert (node_ptr->connection_list_ptr, connect_ptr, OPC_LISTPOS_TAIL);
		}

	FOUT;
	}

void
ospf_lsa_djk_network_connect_create (DjkT_Node *node_ptr, OspfT_Lsa *lsa_ptr, List *node_list_ptr)
	{
	DjkT_Connection *				connect_ptr;
	OspfT_Lsa_Network_Links *		network_links_ptr;
	int								num_routers, router_index;
	OspfT_Router_Id					router_id;
	DjkT_Node *						router_node_ptr;

	/** Create the connection list for a Dijkstra node based on a network links LSA. **/
	FIN (ospf_lsa_djk_network_connect_create (node_ptr, lsa_ptr, node_list_ptr));

	/* Create a reference to the network specific part of the LSA. */
	network_links_ptr = lsa_ptr->lsa_data.lsa_network_links_ptr;

	/* Loop through all the router connections, and add to the connection list for each router. */
	num_routers = op_prg_list_size (network_links_ptr->router_list_ptr);

	for (router_index = 0; router_index < num_routers; router_index++)
		{
		/* Get current router connection. */
		router_id = (OspfT_Router_Id) op_prg_list_access (network_links_ptr->router_list_ptr,
			router_index);
		
		/* Create a connection. */
		connect_ptr = (DjkT_Connection *) djk_connection_create ();

		/* Set connection values based on router connection.  The cost to the */
		/* router from the network is always considered to be 0.              */
		connect_ptr->cost = 0;

		/* Find the router node connected to this network. */
		router_node_ptr = ospf_lsa_djk_node_lookup (node_list_ptr, router_id, OspfC_Lsa_Router_Links);

		/* Flag lookup failure. */
		if (router_node_ptr == OPC_NIL)
			ospf_fatal_error ("Router ID Dijkstra node lookup failed.");

		connect_ptr->node_ptr = router_node_ptr;

		/* Add this object to the node connection list. */
		op_prg_list_insert (node_ptr->connection_list_ptr, connect_ptr, OPC_LISTPOS_TAIL);
		}

	/* Also add a connection to the designated router itself. */
	connect_ptr = (DjkT_Connection *) djk_connection_create ();
	connect_ptr->cost = 0;
	router_node_ptr = ospf_lsa_djk_node_lookup (node_list_ptr, lsa_ptr->lsa_header_ptr->router_id,
		OspfC_Lsa_Router_Links);

	/* Flag lookup failure. */
	if (router_node_ptr == OPC_NIL)
		ospf_fatal_error ("Designated Router ID Dijkstra node lookup failed.");
	
	connect_ptr->node_ptr = router_node_ptr;
	
	/* Add this object to the node connection list. */
	op_prg_list_insert (node_ptr->connection_list_ptr, connect_ptr, OPC_LISTPOS_TAIL);

	FOUT;
	}