|
/*Calculating
the shortest path tree for an area*/
void
ospf_spf_calculate (struct ospf_area *area, struct route_table
*new_table,
struct route_table *new_rtrs)
{
struct pqueue *candidate;
struct vertex *v;
/*
struct route_table *rv;
struct route_table *nv;
*/
[...]
/*
RFC2328 16.1. (1). */
/* Initialize the algorithm's data structures. */
/*
rv = route_table_init ();
nv = route_table_init ();
*/
/* this function scan all the LSA database and set the stat field to notEXPLORED */
ospf_lsdb_clean_stat (area->lsdb); /* set all LSAs to
notEXPLORED status */
/*
Create a new heap for the candidates. */
candidate = pqueue_create ();
candidate->cmp=cmp;
candidate->update=update_stat;
/* Initialize the shortest-path tree to only the root (which is
the
router doing the calculation). */
ospf_spf_init (area);
v = area->spf;
/* set LSA position to inSPFtree. This vertex is the root of the
spanning tree */
*(v->stat)=
inSPFtree;
/* ospf_spf_register (v, rv, nv); */
/* Set Area A's TransitCapability to FALSE. */
area->transit = OSPF_TRANSIT_FALSE;
area->shortcut_capability = 1;
for (;;)
{
/* RFC2328 16.1. (2). */
/* now ospf_spf_next (v, area, candidate,
rv , nv); becomes... */
ospf_spf_next (v , area , candidate );
/* RFC2328 16.1. (3). */
/* If at this step the candidate list is
empty, the shortest-
path tree (of transit
vertices) has been completely built and
this stage of the
procedure terminates. */
if ( candidate->size == 0 ) /*size is the
length of the Binary Heap */
{
break;
}
/* Otherwise, choose the vertex
belonging to the candidate list
that is closest to the
root, and add it to the shortest-path
tree (removing it from
the candidate list in the
process). */
/*
extract from the candidates the
node with the lower key */
v = (struct vertex
*) pqueue_dequeue (candidate);
*(v->stat) =
inSPFtree; /* this should be already
done by pqueue_dequeue,
but
twice is better than never ! */
ospf_vertex_add_parent (v);
/* ospf_spf_register (v,
rv, nv); */
/* Note that when there is a choice of vertices
closest to the
root, network vertices
must be chosen before router vertices
in order to necessarily
find all equal-cost paths. */
/* We don't do this at this moment, we
should add the treatment
above codes. --
kunihiro. */
/* RFC2328 16.1. (4). */
if (v->type == OSPF_VERTEX_ROUTER)
ospf_intra_add_router
(new_rtrs, v, area);
else
ospf_intra_add_transit
(new_table, v, area);
/* RFC2328 16.1. (5). */
/* Iterate the algorithm by returning to
Step 2. */
} /*end loop until no more candidate vertices */
[...]
/* Free all vertices which allocated
for SPF calculation */
/*
ospf_spf_route_free (rv);
ospf_spf_route_free (nv);
*/
/* Free
candidate list */
pqueue_delete (candidate);
[...]
|
