* ospf_lsa.h: New flag to the LSA structure for the SPF calculation.
* ospf_lsdb.h: Export ospf_lsdb_clean_stat() function.
* ospf_spf.h: Add link to the LSA stat structure into vertex.
* ospf_spf.c: New functions cmp() and update_stat() to manage
candidates. Remove ospf_spf_has_vertex(), ospf_vertex_lookup(),
ospf_install_candidate() and ospf_spf_register() functions not needed
any more. Update ospf_vertex_new(), ospf_spf_next() and
ospf_spf_calculate() functions to use pqueue instead of linked list.
diff --git a/ospfd/ChangeLog b/ospfd/ChangeLog
index 396ac71..ee30e55 100644
--- a/ospfd/ChangeLog
+++ b/ospfd/ChangeLog
@@ -1,3 +1,14 @@
+2005-02-23 Vincenzo Eramo <eramo at infocom.ing.uniroma1.it>
+
+ * ospf_lsa.h: New flag to the LSA structure for the SPF calculation.
+ * ospf_lsdb.h: Export ospf_lsdb_clean_stat() function.
+ * ospf_spf.h: Add link to the LSA stat structure into vertex.
+ * ospf_spf.c: New functions cmp() and update_stat() to manage
+ candidates. Remove ospf_spf_has_vertex(), ospf_vertex_lookup(),
+ ospf_install_candidate() and ospf_spf_register() functions not needed
+ any more. Update ospf_vertex_new(), ospf_spf_next() and
+ ospf_spf_calculate() functions to use pqueue instead of linked list.
+
2005-02-21 Hasso Tepper <hasso at quagga.net>
* ospf_ase.c: Don't show messages related to the ase calculations if
diff --git a/ospfd/ospf_lsa.h b/ospfd/ospf_lsa.h
index 6d10e64..952ca77 100644
--- a/ospfd/ospf_lsa.h
+++ b/ospfd/ospf_lsa.h
@@ -90,6 +90,12 @@
/* All of reference count, also lock to remove. */
int lock;
+ /* Flags for the SPF calculation. */
+ int stat;
+ #define LSA_SPF_NOT_EXPLORED -1
+ #define LSA_SPF_IN_SPFTREE -2
+ /* If stat >= 0, stat is LSA position in candidates heap. */
+
/* References to this LSA in neighbor retransmission lists*/
int retransmit_counter;
diff --git a/ospfd/ospf_lsdb.c b/ospfd/ospf_lsdb.c
index 94d839f..56ab9e2 100644
--- a/ospfd/ospf_lsdb.c
+++ b/ospfd/ospf_lsdb.c
@@ -180,6 +180,23 @@
}
}
+void
+ospf_lsdb_clean_stat (struct ospf_lsdb *lsdb)
+{
+ struct route_table *table;
+ struct route_node *rn;
+ struct ospf_lsa *lsa;
+ int i;
+
+ for (i = OSPF_MIN_LSA; i < OSPF_MAX_LSA; i++)
+ {
+ table = lsdb->type[i].db;
+ for (rn = route_top (table); rn; rn = route_next (rn))
+ if ((lsa = (rn->info)) != NULL)
+ lsa->stat = LSA_SPF_NOT_EXPLORED;
+ }
+}
+
struct ospf_lsa *
ospf_lsdb_lookup (struct ospf_lsdb *lsdb, struct ospf_lsa *lsa)
{
diff --git a/ospfd/ospf_lsdb.h b/ospfd/ospf_lsdb.h
index 8ae66a1..e192308 100644
--- a/ospfd/ospf_lsdb.h
+++ b/ospfd/ospf_lsdb.h
@@ -69,6 +69,8 @@
void ospf_lsdb_add (struct ospf_lsdb *, struct ospf_lsa *);
void ospf_lsdb_delete (struct ospf_lsdb *, struct ospf_lsa *);
void ospf_lsdb_delete_all (struct ospf_lsdb *);
+/* Set all stats to -1 (LSA_SPF_NOT_EXPLORED). */
+void ospf_lsdb_clean_stat (struct ospf_lsdb *lsdb);
struct ospf_lsa *ospf_lsdb_lookup (struct ospf_lsdb *, struct ospf_lsa *);
struct ospf_lsa *ospf_lsdb_lookup_by_id (struct ospf_lsdb *, u_char,
struct in_addr, struct in_addr);
diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
index 1298ebe..9a4e8ff 100644
--- a/ospfd/ospf_spf.c
+++ b/ospfd/ospf_spf.c
@@ -29,6 +29,7 @@
#include "table.h"
#include "log.h"
#include "sockunion.h" /* for inet_ntop () */
+#include "pqueue.h"
#include "ospfd/ospfd.h"
#include "ospfd/ospf_interface.h"
@@ -47,6 +48,28 @@
#define DEBUG
+/* Heap related functions, for the managment of the candidates, to
+ * be used with pqueue. */
+static int
+cmp (void * node1 , void * node2)
+{
+ struct vertex * v1 = (struct vertex *) node1;
+ struct vertex * v2 = (struct vertex *) node2;
+ if (v1 != NULL && v2 != NULL )
+ return (v1->distance - v2->distance);
+ else
+ return 0;
+}
+
+static void
+update_stat (void * node , int position)
+{
+ struct vertex * v = (struct vertex *) node;
+ /* Set the status of the vertex, when its position changes. */
+ *(v->stat) = position;
+}
+/* End of the heap related functions. */
+
struct vertex_nexthop *
vertex_nexthop_new (struct vertex *parent)
{
@@ -87,6 +110,7 @@
memset (new, 0, sizeof (struct vertex));
new->flags = 0;
+ new->stat = &(lsa->stat);
new->type = lsa->data->type;
new->id = lsa->data->id;
new->lsa = lsa->data;
@@ -197,50 +221,6 @@
area->asbr_count = 0;
}
-/* Check if the vertex represented by lsa is on the SPF tree. */
-int
-ospf_spf_has_vertex (struct route_table *rv, struct route_table *nv,
- struct lsa_header *lsa)
-{
- struct prefix p;
- struct route_node *rn;
-
- p.family = AF_INET;
- p.prefixlen = IPV4_MAX_BITLEN;
- p.u.prefix4 = lsa->id;
-
- if (lsa->type == OSPF_ROUTER_LSA)
- rn = route_node_get (rv, &p);
- else
- rn = route_node_get (nv, &p);
-
- if (rn->info != NULL)
- {
- route_unlock_node (rn);
- return 1;
- }
- return 0;
-}
-
-/* Find the vertex specified by the given id and LSA type
- * in vlist (the candidate list).
- */
-struct listnode *
-ospf_vertex_lookup (struct list *vlist, struct in_addr id, int type)
-{
- struct listnode *node;
- struct vertex *v;
-
- for (node = listhead (vlist); node; nextnode (node))
- {
- v = (struct vertex *) getdata (node);
- if (IPV4_ADDR_SAME (&id, &v->id) && type == v->type)
- return node;
- }
-
- return NULL;
-}
-
/* return index of link back to V from W, or -1 if no link found */
int
ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v)
@@ -643,48 +623,6 @@
}
}
-/* Add a vertex to the SPF candidate list. */
-void
-ospf_install_candidate (struct list *candidate, struct vertex *w)
-{
- struct listnode *node;
- struct vertex *cw;
-
- ospf_vertex_dump("ospf_install_candidate(): add to candidate list", w, 1, 1);
-
- if (list_isempty (candidate))
- {
- listnode_add (candidate, w);
- return;
- }
-
- /* Install vertex with sorting by distance. */
- for (node = listhead (candidate); node; nextnode (node))
- {
- cw = (struct vertex *) getdata (node);
- if (cw->distance > w->distance)
- {
- list_add_node_prev (candidate, node, w);
- break;
- }
- else if (node->next == NULL)
- {
- list_add_node_next (candidate, node, w);
- break;
- }
- }
-
- if (IS_DEBUG_OSPF_EVENT)
- {
- zlog_debug("ospf_install_candidate(): candidate list now contains:");
- for (node = listhead (candidate); node; nextnode (node))
- {
- cw = (struct vertex *) getdata (node);
- ospf_vertex_dump(" candidate:", cw, 0, 0);
- }
- }
-}
-
/* RFC2328 Section 16.1 (2).
* v is on the SPF tree. Examine the links in v's LSA. Update the list
* of candidates with any vertices not already on the list. If a lower-cost
@@ -692,8 +630,7 @@
*/
void
ospf_spf_next (struct vertex *v, struct ospf_area *area,
- struct list *candidate, struct route_table *rv,
- struct route_table *nv)
+ struct pqueue * candidate)
{
struct ospf_lsa *w_lsa = NULL;
struct vertex *w, *cw;
@@ -701,7 +638,6 @@
u_char *lim;
struct router_lsa_link *l = NULL;
struct in_addr *r;
- struct listnode *node;
int type = 0;
/* If this is a router-LSA, and bit V of the router-LSA (see Section
@@ -799,12 +735,12 @@
/* (c) If vertex W is already on the shortest-path tree, examine
the next link in the LSA. */
- if (ospf_spf_has_vertex (rv, nv, w_lsa->data))
- {
- if (IS_DEBUG_OSPF_EVENT)
- zlog_debug ("The LSA is already in SPF");
- continue;
- }
+ if (w_lsa->stat == LSA_SPF_IN_SPFTREE)
+ {
+ if (IS_DEBUG_OSPF_EVENT)
+ zlog_debug ("The LSA is already in SPF");
+ continue;
+ }
/* (d) Calculate the link state cost D of the resulting path
from the root to vertex W. D is equal to the sum of the link
@@ -825,34 +761,25 @@
w->distance = v->distance;
/* Is there already vertex W in candidate list? */
- node = ospf_vertex_lookup (candidate, w->id, w->type);
- if (node == NULL)
- {
- /* W is a new candidate. Calculate nexthop to W and add W
- * to the candidate list.
- */
- ospf_nexthop_calculation (area, v, w);
+ if (w_lsa->stat == LSA_SPF_NOT_EXPLORED)
+ {
+ /* Calculate nexthop to W. */
+ ospf_nexthop_calculation (area, v, w);
+ pqueue_enqueue (w, candidate);
+ }
+ else if (w_lsa->stat >= 0)
+ {
+ /* Get the vertex from candidates. */
+ cw = (struct vertex *) candidate->array[w_lsa->stat];
- ospf_install_candidate (candidate, w);
- }
- else
- {
- /* W is already on the candidate list; call it cw.
- * Compare the previously calculated cost (cw->distance)
- * with the cost we just determined (w->distance) to see
- * if we've found a shorter path.
- */
- cw = (struct vertex *) getdata (node);
-
- /* If the previous cost was lower, we didn't find a
- * shorter path, so we're done with w.
- */
- if (cw->distance < w->distance)
+ /* if D is greater than. */
+ if (cw->distance < w->distance)
{
ospf_vertex_free (w);
continue;
}
- else if (cw->distance == w->distance)
+ /* equal to. */
+ else if (cw->distance == w->distance)
{
/* Found an equal-cost path to W. Calculate nexthop to W. */
ospf_nexthop_calculation (area, v, w);
@@ -860,44 +787,22 @@
list_delete_all_node (w->nexthop);
ospf_vertex_free (w);
}
- else
+ /* less than. */
+ else
{
/* Found a lower-cost path to W. Calculate nexthop to W. */
ospf_nexthop_calculation (area, v, w);
/* Remove old vertex from candidate list. */
ospf_vertex_free (cw);
- listnode_delete (candidate, cw);
-
- /* Install new W to candidate list. */
- ospf_install_candidate (candidate, w);
+ candidate->array[w_lsa->stat] = w;
+ /* Decrease the key of the node in the heap, re-sort the heap. */
+ trickle_down (w_lsa->stat, candidate);
}
} /* end W is already on the candidate list */
} /* end loop over the links in V's LSA */
}
-/* Add vertex V to SPF tree. */
-void
-ospf_spf_register (struct vertex *v, struct route_table *rv,
- struct route_table *nv)
-{
- struct prefix p;
- struct route_node *rn;
-
- ospf_vertex_dump("ospf_spf_register(): adding to SPF tree:", v, 1, 1);
-
- p.family = AF_INET;
- p.prefixlen = IPV4_MAX_BITLEN;
- p.u.prefix4 = v->id;
-
- if (v->type == OSPF_VERTEX_ROUTER)
- rn = route_node_get (rv, &p);
- else
- rn = route_node_get (nv, &p);
-
- rn->info = v;
-}
-
void
ospf_spf_route_free (struct route_table *table)
{
@@ -1103,11 +1008,8 @@
ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table,
struct route_table *new_rtrs)
{
- struct list *candidate;
- struct listnode *node;
+ struct pqueue *candidate;
struct vertex *v;
- struct route_table *rv;
- struct route_table *nv;
if (IS_DEBUG_OSPF_EVENT)
{
@@ -1129,17 +1031,22 @@
/* RFC2328 16.1. (1). */
/* Initialize the algorithm's data structures. */
- rv = route_table_init ();
- nv = route_table_init ();
-
- /* Clear the list of candidate vertices. */
- candidate = list_new ();
+
+ /* This function scans all the LSA database and set the stat field to
+ * LSA_SPF_NOT_EXPLORED. */
+ ospf_lsdb_clean_stat (area->lsdb);
+ /* 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;
- ospf_spf_register (v, rv, nv);
+ /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the
+ * spanning tree. */
+ *(v->stat) = LSA_SPF_IN_SPFTREE;
/* Set Area A's TransitCapability to FALSE. */
area->transit = OSPF_TRANSIT_FALSE;
@@ -1148,29 +1055,25 @@
for (;;)
{
/* RFC2328 16.1. (2). */
- ospf_spf_next (v, area, candidate, rv, nv);
+ 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 (listcount (candidate) == 0)
+ if (candidate->size == 0)
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). */
- node = listhead (candidate);
- v = getdata (node);
+ /* Extract from the candidates the node with the lower key. */
+ v = (struct vertex *) pqueue_dequeue (candidate);
+ /* Update stat field in vertex. */
+ *(v->stat) = LSA_SPF_IN_SPFTREE;
ospf_vertex_add_parent (v);
- /* Remove from the candidate list. */
- listnode_delete (candidate, v);
-
- /* Add to SPF tree. */
- 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. */
@@ -1197,12 +1100,8 @@
/* Second stage of SPF calculation procedure's */
ospf_spf_process_stubs (area, area->spf, new_table);
- /* Free all vertices which allocated for SPF calculation */
- ospf_spf_route_free (rv);
- ospf_spf_route_free (nv);
-
- /* Free candidate list */
- list_free (candidate);
+ /* Free candidates. */
+ pqueue_delete (candidate);
/* Increment SPF Calculation Counter. */
area->spf_calculation++;
diff --git a/ospfd/ospf_spf.h b/ospfd/ospf_spf.h
index 25b1d79..57f9d28 100644
--- a/ospfd/ospf_spf.h
+++ b/ospfd/ospf_spf.h
@@ -36,6 +36,7 @@
u_char type; /* copied from LSA header */
struct in_addr id; /* copied from LSA header */
struct lsa_header *lsa; /* Router or Network LSA */
+ int * stat; /* Link to LSA status. */
u_int32_t distance; /* from root to this vertex */
int backlink; /* link index of back-link */
struct list *child; /* list of vertex: children in SPF tree*/