summaryrefslogtreecommitdiff
path: root/src/ipcpd/unicast/routing/graph.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/ipcpd/unicast/routing/graph.c')
-rw-r--r--src/ipcpd/unicast/routing/graph.c84
1 files changed, 39 insertions, 45 deletions
diff --git a/src/ipcpd/unicast/routing/graph.c b/src/ipcpd/unicast/routing/graph.c
index 32442dad..0226c762 100644
--- a/src/ipcpd/unicast/routing/graph.c
+++ b/src/ipcpd/unicast/routing/graph.c
@@ -1,5 +1,5 @@
/*
- * Ouroboros - Copyright (C) 2016 - 2024
+ * Ouroboros - Copyright (C) 2016 - 2026
*
* Undirected graph structure
*
@@ -57,10 +57,7 @@ struct edge {
};
struct graph {
- struct {
- struct list_head list;
- size_t len;
- } vertices;
+ struct llist vertices;
pthread_mutex_t lock;
};
@@ -88,7 +85,7 @@ static struct vertex * find_vertex_by_addr(struct graph * graph,
assert(graph);
- list_for_each(p, &graph->vertices.list) {
+ llist_for_each(p, &graph->vertices) {
struct vertex * e = list_entry(p, struct vertex, next);
if (e->addr == addr)
return e;
@@ -142,7 +139,7 @@ static struct vertex * add_vertex(struct graph * graph,
vertex->addr = addr;
/* Keep them ordered on address. */
- list_for_each(p, &graph->vertices.list) {
+ llist_for_each(p, &graph->vertices) {
struct vertex * v = list_entry(p, struct vertex, next);
if (v->addr > addr)
break;
@@ -151,7 +148,7 @@ static struct vertex * add_vertex(struct graph * graph,
vertex->index = i;
- list_add_tail(&vertex->next, p);
+ llist_add_tail_at(&vertex->next, p, &graph->vertices);
/* Increase the index of the vertices to the right. */
list_for_each(p, &vertex->next) {
@@ -160,37 +157,41 @@ static struct vertex * add_vertex(struct graph * graph,
v->index++;
}
- ++graph->vertices.len;
-
return vertex;
}
+static void free_edges(struct list_head * edges)
+{
+ struct list_head * p;
+ struct list_head * h;
+
+ list_for_each_safe(p, h, edges) {
+ struct edge * e = list_entry(p, struct edge, next);
+ list_del(&e->next);
+ free(e);
+ }
+}
+
static void del_vertex(struct graph * graph,
struct vertex * vertex)
{
struct list_head * p;
- struct list_head * h;
assert(graph != NULL);
assert(vertex != NULL);
- list_del(&vertex->next);
+ llist_del(&vertex->next, &graph->vertices);
/* Decrease the index of the vertices to the right. */
- list_for_each(p, &graph->vertices.list) {
+ llist_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, h, &vertex->edges) {
- struct edge * e = list_entry(p, struct edge, next);
- del_edge(e);
- }
+ free_edges(&vertex->edges);
free(vertex);
-
- --graph->vertices.len;
}
struct graph * graph_create(void)
@@ -206,8 +207,7 @@ struct graph * graph_create(void)
return NULL;
}
- graph->vertices.len = 0;
- list_head_init(&graph->vertices.list);
+ llist_init(&graph->vertices);
return graph;
}
@@ -221,7 +221,7 @@ void graph_destroy(struct graph * graph)
pthread_mutex_lock(&graph->lock);
- list_for_each_safe(p, n, &graph->vertices.list) {
+ llist_for_each_safe(p, n, &graph->vertices) {
struct vertex * e = list_entry(p, struct vertex, next);
del_vertex(graph, e);
}
@@ -230,7 +230,7 @@ void graph_destroy(struct graph * graph)
pthread_mutex_destroy(&graph->lock);
- assert(graph->vertices.len == 0);
+ assert(llist_is_empty(&graph->vertices));
free(graph);
}
@@ -371,7 +371,7 @@ static int get_min_vertex(struct graph * graph,
*v = NULL;
- list_for_each(p, &graph->vertices.list) {
+ llist_for_each(p, &graph->vertices) {
if (!used[i] && dist[i] < min) {
min = dist[i];
index = i;
@@ -420,7 +420,7 @@ static int dijkstra(struct graph * graph,
memset(*nhops, 0, sizeof(**nhops) * graph->vertices.len);
memset(*dist, 0, sizeof(**dist) * graph->vertices.len);
- list_for_each(p, &graph->vertices.list) {
+ llist_for_each(p, &graph->vertices) {
v = list_entry(p, struct vertex, next);
(*dist)[i++] = (v->addr == src) ? 0 : INT_MAX;
}
@@ -526,7 +526,7 @@ static int graph_routing_table_simple(struct graph * graph,
list_head_init(table);
/* Now construct the routing table from the nhops. */
- list_for_each(p, &graph->vertices.list) {
+ llist_for_each(p, &graph->vertices) {
v = list_entry(p, struct vertex, next);
/* This is the src */
@@ -624,7 +624,7 @@ static int graph_routing_table_lfa(struct graph * graph,
addrs[j] = -1;
}
- list_for_each(p, &graph->vertices.list) {
+ llist_for_each(p, &graph->vertices) {
v = list_entry(p, struct vertex, next);
if (v->addr != s_addr)
@@ -650,7 +650,7 @@ static int graph_routing_table_lfa(struct graph * graph,
}
/* Loop though all nodes to see if we have a LFA for them. */
- list_for_each(p, &graph->vertices.list) {
+ llist_for_each(p, &graph->vertices) {
v = list_entry(p, struct vertex, next);
if (v->addr == s_addr)
@@ -695,7 +695,6 @@ static int graph_routing_table_ecmp(struct graph * graph,
{
struct vertex ** nhops;
struct list_head * p;
- struct list_head * h;
size_t i;
struct vertex * v;
struct vertex * src_v;
@@ -735,16 +734,15 @@ static int graph_routing_table_ecmp(struct graph * graph,
free(nhops);
- list_for_each(h, &graph->vertices.list) {
- v = list_entry(h, struct vertex, next);
- if (tmp_dist[v->index] + 1 == (*dist)[v->index]) {
+ for (i = 0; i < graph->vertices.len; ++i) {
+ if (tmp_dist[i] + 1 == (*dist)[i]) {
n = malloc(sizeof(*n));
if (n == NULL) {
free(tmp_dist);
goto fail_src_v;
}
n->nhop = e->nb->addr;
- list_add_tail(&n->next, &forwarding[v->index]);
+ list_add_tail(&n->next, &forwarding[i]);
}
}
@@ -753,38 +751,34 @@ static int graph_routing_table_ecmp(struct graph * graph,
list_head_init(table);
i = 0;
- list_for_each(p, &graph->vertices.list) {
+ llist_for_each(p, &graph->vertices) {
v = list_entry(p, struct vertex, next);
- if (v->addr == s_addr) {
+ if (v->addr == s_addr || list_is_empty(&forwarding[i])) {
++i;
continue;
}
t = malloc(sizeof(*t));
if (t == NULL)
- goto fail_t;
+ goto fail_malloc;
t->dst = v->addr;
list_head_init(&t->nhops);
- if (&forwarding[i] != forwarding[i].nxt) {
- t->nhops.nxt = forwarding[i].nxt;
- t->nhops.prv = forwarding[i].prv;
- forwarding[i].prv->nxt = &t->nhops;
- forwarding[i].nxt->prv = &t->nhops;
- }
+ t->nhops.nxt = forwarding[i].nxt;
+ t->nhops.prv = forwarding[i].prv;
+ forwarding[i].prv->nxt = &t->nhops;
+ forwarding[i].nxt->prv = &t->nhops;
list_add(&t->next, table);
++i;
}
- free(*dist);
- *dist = NULL;
free(forwarding);
return 0;
- fail_t:
+ fail_malloc:
free_routing_table(table);
fail_src_v:
free(*dist);
generated by cgit v1.2.3 (git 2.39.1) at 2026-03-01 10:32:58 +0000