diff options
Diffstat (limited to 'ospf6d/ospf6_spf.c')
| -rw-r--r-- | ospf6d/ospf6_spf.c | 30 |
1 files changed, 13 insertions, 17 deletions
diff --git a/ospf6d/ospf6_spf.c b/ospf6d/ospf6_spf.c index f08426fb4..aa4a99517 100644 --- a/ospf6d/ospf6_spf.c +++ b/ospf6d/ospf6_spf.c @@ -27,7 +27,6 @@ #include "command.h" #include "vty.h" #include "prefix.h" -#include "pqueue.h" #include "linklist.h" #include "thread.h" #include "lib_errors.h" @@ -76,16 +75,18 @@ static unsigned int ospf6_spf_get_ifindex_from_nh(struct ospf6_vertex *v) 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) { @@ -461,7 +462,7 @@ void ospf6_spf_calculation(uint32_t router_id, 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; @@ -481,8 +482,7 @@ void ospf6_spf_calculation(uint32_t router_id, } /* initialize */ - candidate_list = pqueue_create(); - candidate_list->cmp = ospf6_vertex_cmp; + vertex_pqueue_init(&candidate_list); root = ospf6_vertex_create(lsa); root->area = oa; @@ -492,13 +492,10 @@ void ospf6_spf_calculation(uint32_t router_id, 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) @@ -557,12 +554,11 @@ void ospf6_spf_calculation(uint32_t router_id, 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); |