]> git.meshlink.io Git - meshlink/blob - src/node.c
Use Dijkstra's algorithm. Based on patches from Max Rijevskiy.
[meshlink] / src / node.c
1 /*
2     node.c -- node tree management
3     Copyright (C) 2001-2006 Guus Sliepen <guus@tinc-vpn.org>,
4                   2001-2005 Ivo Timmermans
5
6     This program is free software; you can redistribute it and/or modify
7     it under the terms of the GNU General Public License as published by
8     the Free Software Foundation; either version 2 of the License, or
9     (at your option) any later version.
10
11     This program is distributed in the hope that it will be useful,
12     but WITHOUT ANY WARRANTY; without even the implied warranty of
13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14     GNU General Public License for more details.
15
16     You should have received a copy of the GNU General Public License
17     along with this program; if not, write to the Free Software
18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19
20     $Id$
21 */
22
23 #include "system.h"
24
25 #include "splay_tree.h"
26 #include "logger.h"
27 #include "net.h"
28 #include "netutl.h"
29 #include "node.h"
30 #include "utils.h"
31 #include "xalloc.h"
32
33 splay_tree_t *node_tree;                        /* Known nodes, sorted by name */
34 splay_tree_t *node_udp_tree;            /* Known nodes, sorted by address and port */
35
36 node_t *myself;
37
38 static int node_compare(const node_t *a, const node_t *b) {
39         return strcmp(a->name, b->name);
40 }
41
42 static int node_udp_compare(const node_t *a, const node_t *b) {
43         int result;
44
45         cp();
46
47         result = sockaddrcmp(&a->address, &b->address);
48
49         if(result)
50                 return result;
51
52         return (a->name && b->name) ? strcmp(a->name, b->name) : 0;
53 }
54
55 void init_nodes(void) {
56         cp();
57
58         node_tree = splay_alloc_tree((splay_compare_t) node_compare, (splay_action_t) free_node);
59         node_udp_tree = splay_alloc_tree((splay_compare_t) node_udp_compare, NULL);
60 }
61
62 void exit_nodes(void) {
63         cp();
64
65         splay_delete_tree(node_udp_tree);
66         splay_delete_tree(node_tree);
67 }
68
69 node_t *new_node(void) {
70         node_t *n = xmalloc_and_zero(sizeof *n);
71
72         cp();
73
74         n->subnet_tree = new_subnet_tree();
75         n->edge_tree = new_edge_tree();
76         n->queue = list_alloc((list_action_t) free);
77         n->mtu = MTU;
78         n->maxmtu = MTU;
79
80         return n;
81 }
82
83 void free_node(node_t *n) {
84         cp();
85
86         if(n->queue)
87                 list_delete_list(n->queue);
88
89         if(n->subnet_tree)
90                 free_subnet_tree(n->subnet_tree);
91
92         if(n->edge_tree)
93                 free_edge_tree(n->edge_tree);
94
95         sockaddrfree(&n->address);
96
97         cipher_close(&n->cipher);
98         digest_close(&n->digest);
99
100         event_del(&n->mtuevent);
101         
102         if(n->hostname)
103                 free(n->hostname);
104
105         if(n->name)
106                 free(n->name);
107
108         free(n);
109 }
110
111 void node_add(node_t *n) {
112         cp();
113
114         splay_insert(node_tree, n);
115 }
116
117 void node_del(node_t *n) {
118         splay_node_t *node, *next;
119         edge_t *e;
120         subnet_t *s;
121
122         cp();
123
124         for(node = n->subnet_tree->head; node; node = next) {
125                 next = node->next;
126                 s = node->data;
127                 subnet_del(n, s);
128         }
129
130         for(node = n->edge_tree->head; node; node = next) {
131                 next = node->next;
132                 e = node->data;
133                 edge_del(e);
134         }
135
136         splay_delete(node_tree, n);
137 }
138
139 node_t *lookup_node(char *name) {
140         node_t n = {0};
141
142         cp();
143         
144         n.name = name;
145
146         return splay_search(node_tree, &n);
147 }
148
149 node_t *lookup_node_udp(const sockaddr_t *sa) {
150         node_t n = {0};
151
152         cp();
153
154         n.address = *sa;
155         n.name = NULL;
156
157         return splay_search(node_udp_tree, &n);
158 }
159
160 int dump_nodes(struct evbuffer *out) {
161         splay_node_t *node;
162         node_t *n;
163
164         cp();
165
166         for(node = node_tree->head; node; node = node->next) {
167                 n = node->data;
168                 if(evbuffer_add_printf(out, _(" %s at %s cipher %d digest %d maclength %d compression %d options %lx status %04x nexthop %s via %s distance %d pmtu %d (min %d max %d)\n"),
169                            n->name, n->hostname, cipher_get_nid(&n->cipher),
170                            digest_get_nid(&n->digest), n->maclength, n->compression,
171                            n->options, *(uint32_t *)&n->status, n->nexthop ? n->nexthop->name : "-",
172                            n->via ? n->via->name : "-", n->distance, n->mtu, n->minmtu, n->maxmtu) == -1)
173                         return errno;
174         }
175
176         return 0;
177 }