/* ospf_list_utilities.c - ospf list utilities *//* Copyright 2000-2003 Wind River Systems, Inc. */#include "copyright_wrs.h"/*modification history--------------------02o,17jul03,agi    made ospf_delete_entry_from_list() global02n,03jul03,agi    Fixed SPR#89187 - OSPF stack in exchange start problem02m,29may03,agi    Added ospf_add_entry_to_list(), ospf_delete_entry_from_list()02l,23may03,agi    Changed RWOS semaphores to vxWorks semaphores02k,22apr03,ram	   SPR#76812 Modifications for OSPF performance enhancements02j,19nov02,mwv    Merge TMS code SPR 8428402i,10oct02,hme    Fix TSR# 28703702h,19apr02,jkw    Fix memory leak for external lsas.02g,16apr02,jkw    One copy of external and type 11 lsa02f,04apr02,kc     Fixed ospf_free_all_the_associated_area_pointers() - set                   sptr_address_range for area to NULL. Also fixed                   ospf_free_areas_link_state_database() - set                   sptr_database_entry pointer for lsdb head to NULL.02e,09apr02,jkw    Sequence number wrap.02d,25mar02,kc     Fixed ospf_free_all_the_associated_area_pointers() again -                    explicitly set the forward pointer for the                   shortest_path_first_tree to NULL after freeing the memory                   pointed to by the given pointer.02c,23mar02,kc     Fixed ospf_free_all_the_associated_area_pointers() - explicitly set                    the pointer pointed to the sptr_candidate and                   sptr_summary_advertisement_list_head to NULL after freeing the                    memory pointed to by the given pointer.02b,09jan02,jkw    Add null pointer check for removing advertisement from retransmission                    list.02a,20dec01,jkw    Removed sptr_area->sptr_interfaces structure.01z,13oct01,kc     Dynamic configuration changes.01y,26sep01,kc     Modified ospf_free_areas_interfaces() to de-register multicast and                   to send empty hello to neighbors.01x,03sep01,jkw    Added Mistral updates for NULL pointer fix01w,23aug01,jkw    Fixed compiler warnings.01v,18jul01,jkw    Added opaque lsa request for ospf_free_neighbor_ls_request_list01u,19june01,aos   Calling to ospf_clean_up_retransmit_lists_affiliated_with_this_advertisement () function before freeing the LS database entry.01t,03may01,jkw    Added checks for NULL pointers and alarm messages01s,26sep00,reshma Added WindRiver CopyRight01r,25sep00,reshma RFC-1587 implementation for OSPF NSSA Option, also tested against ANVL.                   Also added ospf_mib_delete_xxx_entry functions.01q,07jul00,reshma Unix compatibility related changes.01p,04apr00,reshma Added some MIB support (Read only).Passed all important ANVL OSPF tests.01o,23dec99,reshma Compatibility with VxWorks-IP and VxWorks RTM-interface01n,28dec98,jack   Compiled and added some comments01m,11nov98,jack   Config changes, linted and big endian changes01l,30oct98,jack   Incorporate changes for compilation on Vxworks01k,23aug98,jack   ANVL tested OSPF with PATRICIA tree route table and no recursion01j,10aug98,jack   PATRICIA Route Table Based OSPF Code Base01i,19jun98,jack   listroutine changes. OSPF add and delete list routines, eventually call                   the rwutils list routines.01h,16jun98,jack   The ospf_add_to_list routine changed.01g,05jun98,jack   Fix in fn ospf_remove_current_database_copy_from_all_neigh_.....; NULL                   pointer check01f,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_list_utilities.c is used for creating and deleting lists.  These lists include: neighbor lists, neighbor retransmission lists, neighbor retransmit queues, database summary lists, area lists.This file is used for retrieving link state advertisements.This file is used when creating and deleting lists.*/#include "ospf.h"#if defined (__OSPF_VIRTUAL_STACK__)#include "ospf_vs_lib.h"#endif /* __OSPF_VIRTUAL_STACK__ */static void ospf_neighbors_remove_all_advertisement_from_transmit_list (OSPF_NEIGHBOR *sptr_neighbor, OSPF_LS_DATABASE_ENTRY *sptr_advertisement);/******************************************************************************/void ospf_insert_node_in_list (OSPF_GENERIC_NODE *sptr_node,OSPF_GENERIC_NODE *sptr_previous_node){	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_insert_node_in_list\r\n");	/*	 * This fn is always called from add_node_to_end at this point in time so comment out if condition	 */	sptr_node->sptr_backward_link = sptr_previous_node;	sptr_node->sptr_forward_link = NULL;  /* always added at end */	sptr_previous_node->sptr_forward_link = sptr_node;	return;}/*************************************************************************/void ospf_add_entry_to_list (LINK *sptr_link, LINK *sptr_link_to_add){        if (sptr_link == NULL)                {                printf ("LSL: Illegal List\r\n");                return;                }        if (sptr_link_to_add == NULL)                {                printf ("LSL: Illegal Element to Add\r\n");                return;                }        sptr_link_to_add->sptr_backward_link = sptr_link->sptr_backward_link;        if (sptr_link->sptr_backward_link != NULL)                sptr_link->sptr_backward_link->sptr_forward_link = sptr_link_to_add;        else                sptr_link->sptr_forward_link = sptr_link_to_add;        sptr_link->sptr_backward_link = sptr_link_to_add;        sptr_link_to_add->sptr_forward_link = NULL;}/************************************************************************/void ospf_delete_entry_from_list     (    LINK *sptr_list_link,     LINK *sptr_link_to_delete    )    {        if (sptr_list_link == NULL)                {                printf ("LSL: Illegal List\r\n");                return;                }        if (sptr_link_to_delete == NULL)                {                printf ("LSL: Illegal Element to Delete\r\n");                return;                }        if (sptr_link_to_delete->sptr_forward_link == NULL && sptr_link_to_delete->sptr_backward_link == NULL) /* 1 entry in list */                {                sptr_list_link->sptr_forward_link = NULL;                sptr_list_link->sptr_backward_link = NULL;                return;                }        if (sptr_link_to_delete->sptr_backward_link == NULL) /* First entry in N (N >= 2) entry list  */                sptr_list_link->sptr_forward_link = sptr_link_to_delete->sptr_forward_link; /* new first entry in list have list point to it */        else                sptr_link_to_delete->sptr_backward_link->sptr_forward_link = sptr_link_to_delete->sptr_forward_link;        if (sptr_link_to_delete->sptr_forward_link == NULL) /* Last entry in N (N >= 2) entry list */                sptr_list_link->sptr_backward_link = sptr_link_to_delete->sptr_backward_link; /* new last entry in list because we're deleting the end*/        else                sptr_link_to_delete->sptr_forward_link->sptr_backward_link = sptr_link_to_delete->sptr_backward_link;        sptr_link_to_delete->sptr_forward_link = NULL;        sptr_link_to_delete->sptr_backward_link = NULL;    }/******************************************************************************/void ospf_add_node_to_end_of_list (OSPF_GENERIC_NODE *sptr_node,OSPF_GENERIC_NODE *sptr_first_node_in_list){	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_add_node_to_end_of_list\r\n");	if (sptr_first_node_in_list->sptr_forward_link == NULL)		{		sptr_first_node_in_list->sptr_forward_link = sptr_node;		sptr_first_node_in_list->sptr_backward_link = sptr_node;		sptr_node->sptr_backward_link = sptr_first_node_in_list;		sptr_node->sptr_forward_link = NULL;		return;		}	ospf_add_entry_to_list ((LINK *) sptr_first_node_in_list, (LINK *) sptr_node);	return;}/******************************************************************************/OSPF_GENERIC_NODE *ospf_free_entire_list (OSPF_GENERIC_NODE *sptr_first_node_in_list){	OSPF_GENERIC_NODE *sptr_node;	OSPF_GENERIC_NODE *sptr_next_node;	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_free_entire_list\r\n");	for (sptr_node = sptr_first_node_in_list; sptr_node != NULL; sptr_node = sptr_next_node)		{		sptr_next_node = sptr_node->sptr_forward_link;		ospf_remove_node_from_list ((OSPF_GENERIC_NODE **) &sptr_first_node_in_list, sptr_node);		table_free ((void *) sptr_node);		sptr_node = NULL;		}	return (NULL);}/******************************************************************************/void ospf_remove_node_from_list (OSPF_GENERIC_NODE **ptr_sptr_first_node, OSPF_GENERIC_NODE *sptr_node){    OSPF_GENERIC_NODE *sptr_previous_node;    OSPF_GENERIC_NODE *sptr_next_node;    OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_remove_node_from_list\r\n");    sptr_previous_node = NULL;    sptr_next_node = NULL;    if ( (*ptr_sptr_first_node == NULL) || (sptr_node == NULL) )        return;    if (*ptr_sptr_first_node == sptr_node)        {        if (sptr_node->sptr_forward_link != NULL)            {            *ptr_sptr_first_node = sptr_node->sptr_forward_link;			/* Mistral Added on July 25th */	  		if(*ptr_sptr_first_node)                 {                (*ptr_sptr_first_node)->sptr_backward_link =                     sptr_node->sptr_backward_link;                }            }        else            {            *ptr_sptr_first_node = NULL;            }        sptr_node->sptr_forward_link = NULL;        sptr_node->sptr_backward_link = NULL;        return;        }    if ( *ptr_sptr_first_node != NULL )        {        ospf_delete_entry_from_list             ((LINK *) *ptr_sptr_first_node, (LINK *) sptr_node);        }    return;    }/******************************************************************************/void ospf_add_neighbor (OSPF_INTERFACE *sptr_interface,OSPF_NEIGHBOR *sptr_neighbor_to_add){	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_add_neighbor\r\n");    /* SPR#76812 */    semTake (ospf_config_mutex, WAIT_FOREVER);	if (sptr_interface->sptr_neighbor == NULL)		{		sptr_interface->sptr_neighbor = sptr_neighbor_to_add;		}	else		{		ospf_add_node_to_end_of_list ((OSPF_GENERIC_NODE *) sptr_neighbor_to_add, (OSPF_GENERIC_NODE *) sptr_interface->sptr_neighbor);		}	++ospf.number_of_neighbors;    semGive (ospf_config_mutex);	if (sptr_neighbor_to_add->sptr_interface->type == OSPF_VIRTUAL_LINK)		{        /* REVISIT(patch): obtained the proper transit area id */        sptr_neighbor_to_add->mib_area_id = sptr_neighbor_to_add->sptr_interface->sptr_transit_area->area_id;#if defined(__OSPF_MIB__)		/* tell MIB API to add this virtual neighbor to ospfVirtNbrTable */		ospf2Mapi_request( (void *)sptr_neighbor_to_add, ospfVirtNbrUpdateReqType );#endif /*__OSPF_MIB__*/		}	else		{#if defined(__OSPF_MIB__)		/* tell MIB API to add this virtual neighbor to ospfVirtNbrTable */		ospf2Mapi_request( (void *)sptr_neighbor_to_add, ospfNbrUpdateReqType );#endif /*__OSPF_MIB__*/		}	return;}/******************************************************************************/OSPF_LS_DATABASE_NODE *ospf_find_advertisement_on_neighbors_retransmit_list (OSPF_NEIGHBOR *sptr_neighbor,OSPF_LS_DATABASE_ENTRY *sptr_advertisement){	OSPF_LS_DATABASE_NODE *sptr_retransmission_node;	USHORT old_age;	USHORT length;	int result;	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_find_advertisement_on_neighbors_retransmit_list\r\n");	for (sptr_retransmission_node = sptr_neighbor->sptr_retransmit; sptr_retransmission_node != NULL;		sptr_retransmission_node = sptr_retransmission_node->sptr_forward_link)		{		old_age = sptr_retransmission_node->sptr_ls_database_entry->advertisement.sptr_router->ls_header.age;