#include "table.h"
#include "log.h"
#include "sockunion.h" /* for inet_ntop () */
-#include "pqueue.h"
#include "ospfd/ospfd.h"
#include "ospfd/ospf_interface.h"
static unsigned int spf_reason_flags = 0;
+/* dummy vertex to flag "in spftree" */
+static const struct vertex vertex_in_spftree = {};
+#define LSA_SPF_IN_SPFTREE (struct vertex *)&vertex_in_spftree
+#define LSA_SPF_NOT_EXPLORED NULL
+
static void ospf_clear_spf_reason_flags(void)
{
spf_reason_flags = 0;
/* Heap related functions, for the managment of the candidates, to
* be used with pqueue. */
-static int cmp(void *node1, void *node2)
+static int vertex_cmp(const struct vertex *v1, const struct vertex *v2)
{
- struct vertex *v1 = (struct vertex *)node1;
- struct vertex *v2 = (struct vertex *)node2;
- if (v1 != NULL && v2 != NULL) {
- /* network vertices must be chosen before router vertices of
- * same
- * cost in order to find all shortest paths
- */
- if (((v1->distance - v2->distance) == 0)
- && (v1->type != v2->type)) {
- switch (v1->type) {
- case OSPF_VERTEX_NETWORK:
- return -1;
- case OSPF_VERTEX_ROUTER:
- return 1;
- }
- } else
- return (v1->distance - v2->distance);
+ if (v1->distance != v2->distance)
+ return v1->distance - v2->distance;
+
+ if (v1->type != v2->type) {
+ switch (v1->type) {
+ case OSPF_VERTEX_NETWORK:
+ return -1;
+ case OSPF_VERTEX_ROUTER:
+ return 1;
+ }
}
return 0;
}
+DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue, struct vertex, pqi, vertex_cmp)
-static void update_stat(void *node, int position)
+static void lsdb_clean_stat(struct ospf_lsdb *lsdb)
{
- struct vertex *v = node;
-
- /* Set the status of the vertex, when its position changes. */
- *(v->stat) = position;
+ 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;
+ }
}
static struct vertex_nexthop *vertex_nexthop_new(void)
XFREE(MTYPE_OSPF_VERTEX_PARENT, p);
}
+static int vertex_parent_cmp(void *aa, void *bb)
+{
+ struct vertex_parent *a = aa, *b = bb;
+ return IPV4_ADDR_CMP(&a->nexthop->router, &b->nexthop->router);
+}
+
static struct vertex *ospf_vertex_new(struct ospf_lsa *lsa)
{
struct vertex *new;
new = XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex));
new->flags = 0;
- new->stat = &(lsa->stat);
new->type = lsa->data->type;
new->id = lsa->data->id;
new->lsa = lsa->data;
new->children = list_new();
new->parents = list_new();
new->parents->del = vertex_parent_free;
+ new->parents->cmp = vertex_parent_cmp;
+ new->lsa_p = lsa;
+
+ lsa->stat = new;
listnode_add(&vertex_list, new);
}
vp = vertex_parent_new(v, ospf_lsa_has_link(w->lsa, v->lsa), newhop);
- listnode_add(w->parents, vp);
+ listnode_add_sort(w->parents, vp);
return;
}
* path is found to a vertex already on the candidate list, store the new cost.
*/
static void ospf_spf_next(struct vertex *v, struct ospf *ospf,
- struct ospf_area *area, struct pqueue *candidate)
+ struct ospf_area *area,
+ struct vertex_pqueue_head *candidate)
{
struct ospf_lsa *w_lsa = NULL;
uint8_t *p;
int type = 0, lsa_pos = -1, lsa_pos_next = 0;
/* If this is a router-LSA, and bit V of the router-LSA (see Section
- A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
+ A.4.2:RFC2328) is set, set Area A's TransitCapability to true. */
if (v->type == OSPF_VERTEX_ROUTER) {
if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa *)v->lsa))
area->transit = OSPF_TRANSIT_TRUE;
/* Calculate nexthop to W. */
if (ospf_nexthop_calculation(area, v, w, l, distance,
lsa_pos))
- pqueue_enqueue(w, candidate);
+ vertex_pqueue_add(candidate, w);
else if (IS_DEBUG_OSPF_EVENT)
zlog_debug("Nexthop Calc failed");
- } else if (w_lsa->stat >= 0) {
- /* Get the vertex from candidates. */
- w = candidate->array[w_lsa->stat];
-
+ } else if (w_lsa->stat != LSA_SPF_IN_SPFTREE) {
+ w = w_lsa->stat;
/* if D is greater than. */
if (w->distance < distance) {
continue;
* which
* will flush the old parents
*/
- if (ospf_nexthop_calculation(area, v, w, l,
- distance, lsa_pos))
- /* Decrease the key of the node in the
- * heap.
- * trickle-sort it up towards root, just
- * in case this
- * node should now be the new root due
- * the cost change.
- * (next pqueu_{de,en}queue will fully
- * re-heap the queue).
- */
- trickle_up(w_lsa->stat, candidate);
+ vertex_pqueue_del(candidate, w);
+ ospf_nexthop_calculation(area, v, w, l,
+ distance, lsa_pos);
+ vertex_pqueue_add(candidate, w);
}
} /* end W is already on the candidate list */
} /* end loop over the links in V's LSA */
struct route_table *new_table,
struct route_table *new_rtrs)
{
- struct pqueue *candidate;
+ struct vertex_pqueue_head candidate;
struct vertex *v;
if (IS_DEBUG_OSPF_EVENT) {
/* This function scans all the LSA database and set the stat field to
* LSA_SPF_NOT_EXPLORED. */
- ospf_lsdb_clean_stat(area->lsdb);
+ lsdb_clean_stat(area->lsdb);
/* Create a new heap for the candidates. */
- candidate = pqueue_create();
- candidate->cmp = cmp;
- candidate->update = update_stat;
+ vertex_pqueue_init(&candidate);
/* Initialize the shortest-path tree to only the root (which is the
router doing the calculation). */
/* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of
* the
* spanning tree. */
- *(v->stat) = LSA_SPF_IN_SPFTREE;
+ v->lsa_p->stat = LSA_SPF_IN_SPFTREE;
- /* Set Area A's TransitCapability to FALSE. */
+ /* Set Area A's TransitCapability to false. */
area->transit = OSPF_TRANSIT_FALSE;
area->shortcut_capability = 1;
for (;;) {
/* RFC2328 16.1. (2). */
- ospf_spf_next(v, ospf, area, candidate);
+ ospf_spf_next(v, ospf, 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)
- 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 = vertex_pqueue_pop(&candidate);
+ if (!v)
+ break;
/* Update stat field in vertex. */
- *(v->stat) = LSA_SPF_IN_SPFTREE;
+ v->lsa_p->stat = LSA_SPF_IN_SPFTREE;
ospf_vertex_add_parent(v);
ospf_spf_process_stubs(area, area->spf, new_table, 0);
/* Free candidate queue. */
- pqueue_delete(candidate);
+ //vertex_pqueue_fini(&candidate);
ospf_vertex_dump(__func__, area->spf, 0, 1);
/* Free nexthop information, canonical versions of which are attached
projects / mirror_frr.git / blobdiff