From 0847da715c82d49b01758d88ecca496eba2c8d34 Mon Sep 17 00:00:00 2001
From: Sander Vrijders <sander.vrijders@ugent.be>
Date: Mon, 25 Sep 2017 15:31:20 +0200
Subject: ipcpd: normal: Keep index in vertex struct

This keeps the index in the vertex struct so that is more easily
available during Dijkstra.
---
 src/ipcpd/normal/pol/graph.c      | 49 ++++++++++++++++++---------------------
 src/ipcpd/normal/pol/link_state.c |  2 +-
 2 files changed, 24 insertions(+), 27 deletions(-)

(limited to 'src')

diff --git a/src/ipcpd/normal/pol/graph.c b/src/ipcpd/normal/pol/graph.c
index 1a6ad2b3..27c5cfca 100644
--- a/src/ipcpd/normal/pol/graph.c
+++ b/src/ipcpd/normal/pol/graph.c
@@ -46,6 +46,7 @@ struct vertex {
         struct list_head next;
         uint64_t         addr;
         struct list_head edges;
+        int              index;
 };
 
 struct graph {
@@ -110,6 +111,7 @@ static struct vertex * add_vertex(struct graph * graph,
 {
         struct vertex *    vertex;
         struct list_head * p;
+        int                i = 0;
 
         vertex = malloc(sizeof(*vertex));
         if (vertex == NULL)
@@ -124,10 +126,20 @@ static struct vertex * add_vertex(struct graph * graph,
                 struct vertex * v = list_entry(p, struct vertex, next);
                 if (v->addr > addr)
                         break;
+                i++;
         }
 
+        vertex->index = i;
+
         list_add_tail(&vertex->next, p);
 
+        /* Increase the index of the vertices to the right. */
+        list_for_each(p, &graph->vertices) {
+                struct vertex * v = list_entry(p, struct vertex, next);
+                if (v->addr > addr)
+                        v->index++;
+        }
+
         graph->nr_vertices++;
 
         return vertex;
@@ -141,6 +153,13 @@ static void del_vertex(struct graph * graph,
 
         list_del(&vertex->next);
 
+        /* Decrease the index of the vertices to the right. */
+        list_for_each(p, &graph->vertices) {
+                struct vertex * v = list_entry(p, struct vertex, next);
+                if (v->addr > vertex->addr)
+                        v->index--;
+        }
+
         list_for_each_safe(p, n, &vertex->edges) {
                 struct edge * e = list_entry(p, struct edge, next);
                 del_edge(e);
@@ -353,23 +372,6 @@ static int get_min_vertex(struct graph *   graph,
         return index;
 }
 
-static int get_vertex_number(struct graph *  graph,
-                             struct vertex * v)
-
-{
-        int                i = 0;
-        struct list_head * p = NULL;
-
-        list_for_each(p, &graph->vertices) {
-                struct vertex * vertex = list_entry(p, struct vertex, next);
-                if (vertex == v)
-                        return i;
-                i++;
-        }
-
-        return -1;
-}
-
 static struct vertex ** dijkstra(struct graph * graph,
                                  uint64_t       src)
 {
@@ -377,7 +379,6 @@ static struct vertex ** dijkstra(struct graph * graph,
         bool               used[graph->nr_vertices];
         struct list_head * p = NULL;
         int                i = 0;
-        int                j = 0;
         struct vertex *    v = NULL;
         struct edge *      e = NULL;
         int                alt;
@@ -406,22 +407,18 @@ static struct vertex ** dijkstra(struct graph * graph,
                 list_for_each(p, &v->edges) {
                         e = list_entry(p, struct edge, next);
 
-                        j = get_vertex_number(graph, e->nb);
-                        if (j == -1)
-                                continue;
-
                         /*
                          * NOTE: Current weight is just hop count.
                          * Method could be extended to use a different
                          * weight for a different QoS cube.
                          */
                         alt = dist[i] + 1;
-                        if (alt < dist[j]) {
-                                dist[j] = alt;
+                        if (alt < dist[e->nb->index]) {
+                                dist[e->nb->index] = alt;
                                 if (v->addr == src)
-                                        nhop[j] = e->nb;
+                                        nhop[e->nb->index] = e->nb;
                                 else
-                                        nhop[j] = nhop[i];
+                                        nhop[e->nb->index] = nhop[i];
                         }
                 }
                 i = get_min_vertex(graph, dist, used, &v);
diff --git a/src/ipcpd/normal/pol/link_state.c b/src/ipcpd/normal/pol/link_state.c
index ca837cc1..d45dae15 100644
--- a/src/ipcpd/normal/pol/link_state.c
+++ b/src/ipcpd/normal/pol/link_state.c
@@ -379,7 +379,7 @@ static int nbr_to_fd(uint64_t addr)
 static void * calculate_pff(void * o)
 {
         struct routing_i * instance;
-        int                i;
+        int                i = 0;
         int                fd;
         struct list_head   table;
         struct list_head * p;
-- 
cgit v1.2.3