#include "command.h"
#include "vty.h"
#include "prefix.h"
-#include "pqueue.h"
#include "linklist.h"
#include "thread.h"
#include "lib_errors.h"
return 0;
}
-static int ospf6_vertex_cmp(void *a, void *b)
+static int ospf6_vertex_cmp(const struct ospf6_vertex *va,
+ const struct ospf6_vertex *vb)
{
- struct ospf6_vertex *va = (struct ospf6_vertex *)a;
- struct ospf6_vertex *vb = (struct ospf6_vertex *)b;
-
/* ascending order */
if (va->cost != vb->cost)
return (va->cost - vb->cost);
- return (va->hops - vb->hops);
+ if (va->hops != vb->hops)
+ return (va->hops - vb->hops);
+ return 0;
}
+DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue, struct ospf6_vertex, pqi,
+ ospf6_vertex_cmp)
static int ospf6_vertex_id_cmp(void *a, void *b)
{
{
struct ospf6_vertex *v;
- v = (struct ospf6_vertex *)XMALLOC(MTYPE_OSPF6_VERTEX,
- sizeof(struct ospf6_vertex));
+ v = XMALLOC(MTYPE_OSPF6_VERTEX, sizeof(struct ospf6_vertex));
/* type */
if (ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER) {
}
}
-static const char *ospf6_spf_reason_str[] = {
+static const char *const ospf6_spf_reason_str[] = {
"R+", "R-", "N+", "N-", "L+", "L-", "R*", "N*",
};
struct ospf6_route_table *result_table,
struct ospf6_area *oa)
{
- struct pqueue *candidate_list;
+ struct vertex_pqueue_head candidate_list;
struct ospf6_vertex *root, *v, *w;
int size;
caddr_t lsdesc;
lsa = ospf6_create_single_router_lsa(oa, oa->lsdb_self, router_id);
if (lsa == NULL) {
if (IS_OSPF6_DEBUG_SPF(PROCESS))
- zlog_debug("%s: No router LSA for area %s\n", __func__,
+ zlog_debug("%s: No router LSA for area %s", __func__,
oa->name);
return;
}
/* initialize */
- candidate_list = pqueue_create();
- candidate_list->cmp = ospf6_vertex_cmp;
+ vertex_pqueue_init(&candidate_list);
root = ospf6_vertex_create(lsa);
root->area = oa;
inet_pton(AF_INET6, "::1", &address);
/* Actually insert root to the candidate-list as the only candidate */
- pqueue_enqueue(root, candidate_list);
+ vertex_pqueue_add(&candidate_list, root);
/* Iterate until candidate-list becomes empty */
- while (candidate_list->size) {
- /* get closest candidate from priority queue */
- v = pqueue_dequeue(candidate_list);
-
+ while ((v = vertex_pqueue_pop(&candidate_list))) {
/* installing may result in merging or rejecting of the vertex
*/
if (ospf6_spf_install(v, result_table) < 0)
zlog_debug(
" New candidate: %s hops %d cost %d",
w->name, w->hops, w->cost);
- pqueue_enqueue(w, candidate_list);
+ vertex_pqueue_add(&candidate_list, w);
}
}
-
- pqueue_delete(candidate_list);
+ //vertex_pqueue_fini(&candidate_list);
ospf6_remove_temp_router_lsa(oa);
new_header = XMALLOC(MTYPE_OSPF6_LSA_HEADER, total_lsa_length);
/* LSA information structure */
- lsa = (struct ospf6_lsa *)XCALLOC(MTYPE_OSPF6_LSA,
- sizeof(struct ospf6_lsa));
+ lsa = XCALLOC(MTYPE_OSPF6_LSA, sizeof(struct ospf6_lsa));
lsa->header = (struct ospf6_lsa_header *)new_header;