从链路状态计算 OSPF 区域内路由

66static int vertex_cmp(const struct vertex *v1, const struct vertex *v2)67{68	if (v1->distance != v2->distance)69		return v1->distance - v2->distance;7071	if (v1->type != v2->type) {72		switch (v1->type) {73		case OSPF_VERTEX_NETWORK:74			return -1;75		case OSPF_VERTEX_ROUTER:76			return 1;77		}78	}79	return 0;80}81DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue, struct vertex, pqi, vertex_cmp);

1749	for (;;) {1750		/* RFC2328 16.1. (2). */1751		ospf_spf_next(v, area, &candidate);17521753		/* RFC2328 16.1. (3). */1754		v = vertex_pqueue_pop(&candidate);1755		if (!v)1756			/* No more vertices left. */1757			break;17581759		v->lsa_p->stat = LSA_SPF_IN_SPFTREE;17601761		ospf_vertex_add_parent(v);

1499			else if (w->distance == distance) {1500				/*1501				 * Found an equal-cost path to W.1502				 * Calculate nexthop of to W from V.1503				 */1504				ospf_nexthop_calculation(area, v, w, l,1505							 distance, lsa_pos);1506			}1507			else {1508				/*1509				 * Found a lower-cost path to W.1510				 * nexthop_calculation is conditional, if it1511				 * finds valid nexthop it will call1512				 * spf_add_parents, which will flush the old1513				 * parents.1514				 */1515				vertex_pqueue_del(candidate, w);1516				ospf_nexthop_calculation(area, v, w, l,1517							 distance, lsa_pos);1518				vertex_pqueue_add(candidate, w);1519			}

1862	/* Execute SPF for each area including backbone, see RFC 2328 16.1. */1863	monotime(&spf_start_time);1864	new_table = route_table_init(); /* routing table */1865	new_rtrs = route_table_init();  /* ABR/ASBR routing table */18661867	/* If we have opaque enabled then track all router reachability */1868	if (CHECK_FLAG(ospf->opaque, OPAQUE_OPERATION_READY_BIT))1869		all_rtrs = route_table_init();18701871	ospf_spf_calculate_areas(ospf, new_table, all_rtrs, new_rtrs);1872	spf_time = monotime_since(&spf_start_time, NULL);18731874	ospf_vl_shut_unapproved(ospf);18751876	/* Calculate inter-area routes, see RFC 2328 16.2. */1877	monotime(&start_time);1878	ospf_ia_routing(ospf, new_table, new_rtrs);