X-Git-Url: http://git.meshlink.io/?a=blobdiff_plain;f=src%2Fgraph.c;h=d432023e496f4eb790804d545262a91ddfc07034;hb=86c2990327fdf7ec1197aa73cb2b9a926a734db4;hp=216f9de2754d054213bc08ee25892fba171bc6d9;hpb=886a6f61a1f4cc48a77b42d10f34f9126377d904;p=meshlink diff --git a/src/graph.c b/src/graph.c index 216f9de2..d432023e 100644 --- a/src/graph.c +++ b/src/graph.c @@ -1,6 +1,6 @@ /* graph.c -- graph algorithms - Copyright (C) 2001-2010 Guus Sliepen , + Copyright (C) 2001-2012 Guus Sliepen , 2001-2005 Ivo Timmermans This program is free software; you can redistribute it and/or modify @@ -49,6 +49,7 @@ #include "connection.h" #include "device.h" #include "edge.h" +#include "graph.h" #include "logger.h" #include "netutl.h" #include "node.h" @@ -57,13 +58,14 @@ #include "subnet.h" #include "utils.h" #include "xalloc.h" +#include "graph.h" /* Implementation of Kruskal's algorithm. Running time: O(E) Please note that sorting on weight is already done by add_edge(). */ -void mst_kruskal(void) { +static void mst_kruskal(void) { splay_node_t *node, *next; edge_t *e; node_t *n; @@ -76,7 +78,7 @@ void mst_kruskal(void) { c->status.mst = false; } - ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Kruskal's algorithm:"); + logger(DEBUG_SCARY_THINGS, LOG_DEBUG, "Running Kruskal's algorithm:"); /* Clear visited status on nodes */ @@ -103,7 +105,7 @@ void mst_kruskal(void) { if(e->reverse->connection) e->reverse->connection->status.mst = true; - ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name, + logger(DEBUG_SCARY_THINGS, LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name, e->to->name, e->weight); } } @@ -112,7 +114,7 @@ void mst_kruskal(void) { Running time: O(N^2) */ -void sssp_dijkstra(void) { +static void sssp_dijkstra(void) { splay_node_t *node, *to; edge_t *e; node_t *n, *m; @@ -122,7 +124,7 @@ void sssp_dijkstra(void) { todo_list = list_alloc(NULL); - ifdebug(SCARY_THINGS) logger(LOG_DEBUG, "Running Dijkstra's algorithm:"); + logger(DEBUG_SCARY_THINGS, LOG_DEBUG, "Running Dijkstra's algorithm:"); /* Clear visited status on nodes */ @@ -182,9 +184,6 @@ void sssp_dijkstra(void) { n->address is set to the e->address of the edge left of n to n. We are currently examining the edge e right of n from n: - - If e->reverse->address != n->address, then e->to is probably - not reachable for the nodes left of n. We do as if the indirectdata - flag is set on edge e. - If edge e provides for better reachability of e->to, update e->to. */ @@ -202,29 +201,10 @@ void sssp_dijkstra(void) { e->to->via = indirect ? n->via : e->to; e->to->options = e->options; - if(sockaddrcmp(&e->to->address, &e->address)) { - node = splay_unlink(node_udp_tree, e->to); - sockaddrfree(&e->to->address); - sockaddrcpy(&e->to->address, &e->address); - - if(e->to->hostname) - free(e->to->hostname); - - e->to->hostname = sockaddr2hostname(&e->to->address); - - if(node) - splay_insert_node(node_udp_tree, node); - - if(e->to->options & OPTION_PMTU_DISCOVERY) { - e->to->mtuprobes = 0; - e->to->minmtu = 0; - e->to->maxmtu = MTU; - if(e->to->status.validkey) - send_mtu_probe(e->to); - } - } + if(e->to->address.sa.sa_family == AF_UNSPEC && e->address.sa.sa_family != AF_UNKNOWN) + update_node_udp(e->to, &e->address); - ifdebug(SCARY_THINGS) logger(LOG_DEBUG, " Updating edge %s - %s weight %d distance %d", e->from->name, + logger(DEBUG_SCARY_THINGS, LOG_DEBUG, " Updating edge %s - %s weight %d distance %d", e->from->name, e->to->name, e->weight, e->to->distance); } } @@ -236,7 +216,7 @@ void sssp_dijkstra(void) { Running time: O(E) */ -void sssp_bfs(void) { +static void sssp_bfs(void) { splay_node_t *node, *to; edge_t *e; node_t *n; @@ -259,6 +239,7 @@ void sssp_bfs(void) { myself->status.visited = true; myself->status.indirect = false; myself->nexthop = myself; + myself->prevedge = NULL; myself->via = myself; list_insert_head(todo_list, myself); @@ -285,16 +266,12 @@ void sssp_bfs(void) { n->address is set to the e->address of the edge left of n to n. We are currently examining the edge e right of n from n: - - If e->reverse->address != n->address, then e->to is probably - not reachable for the nodes left of n. We do as if the indirectdata - flag is set on edge e. - If edge e provides for better reachability of e->to, update e->to and (re)add it to the todo_list to (re)examine the reachability of nodes behind it. */ - indirect = n->status.indirect || e->options & OPTION_INDIRECT - || ((n != myself) && sockaddrcmp(&n->address, &e->reverse->address)); + indirect = n->status.indirect || e->options & OPTION_INDIRECT; if(e->to->status.visited && (!e->to->status.indirect || indirect)) @@ -303,6 +280,7 @@ void sssp_bfs(void) { e->to->status.visited = true; e->to->status.indirect = indirect; e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop; + e->to->prevedge = e; e->to->via = indirect ? n->via : e->to; e->to->options = e->options; @@ -319,7 +297,7 @@ void sssp_bfs(void) { list_free(todo_list); } -void check_reachability() { +static void check_reachability(void) { splay_node_t *node, *next; node_t *n; char *name; @@ -337,10 +315,10 @@ void check_reachability() { n->status.reachable = !n->status.reachable; if(n->status.reachable) { - ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became reachable", + logger(DEBUG_TRAFFIC, LOG_DEBUG, "Node %s (%s) became reachable", n->name, n->hostname); } else { - ifdebug(TRAFFIC) logger(LOG_DEBUG, "Node %s (%s) became unreachable", + logger(DEBUG_TRAFFIC, LOG_DEBUG, "Node %s (%s) became unreachable", n->name, n->hostname); } @@ -353,7 +331,8 @@ void check_reachability() { n->minmtu = 0; n->mtuprobes = 0; - event_del(&n->mtuevent); + if(timeout_initialized(&n->mtuevent)) + event_del(&n->mtuevent); xasprintf(&envp[0], "NETNAME=%s", netname ? : ""); xasprintf(&envp[1], "DEVICE=%s", device ? : ""); @@ -390,7 +369,7 @@ void check_reachability() { void graph(void) { subnet_cache_flush(); - sssp_dijkstra(); + sssp_bfs(); check_reachability(); mst_kruskal(); }