www.tinc-vpn.org Git - tinc/blob - test/unit/test_graph.c

   1 #include "unittest.h"
   2 #include "../../src/connection.h"
   3 #include "../../src/node.h"
   4 #include "../../src/xalloc.h"
   5
   6 extern void sssp_bfs(void);
   7
   8 static void connect_nodes(node_t *from, node_t *to, int weight) {
   9         edge_t *direct = new_edge();
  10         direct->from = from;
  11         direct->to = to;
  12         direct->weight = weight;
  13         edge_add(direct);
  14
  15         edge_t *reverse = new_edge();
  16         reverse->from = to;
  17         reverse->to = from;
  18         reverse->weight = weight;
  19         edge_add(reverse);
  20 }
  21
  22 static node_t *make_node(const char *name) {
  23         node_t *node = new_node(name);
  24         node->status.reachable = true;
  25         node_add(node);
  26         return node;
  27 }
  28
  29 static void test_sssp_bfs_2(void **state) {
  30         (void)state;
  31
  32         node_t *mars = make_node("mars");
  33         node_t *saturn = make_node("saturn");
  34         node_t *neptune = make_node("neptune");
  35
  36         //          1000            500
  37         // myself ---------- mars ------------- neptune
  38         //      \                              /
  39         //       ------- saturn --------------
  40         //          50               501
  41
  42         // Upper route
  43         connect_nodes(myself, mars, 1000);
  44         connect_nodes(mars, neptune, 500);
  45
  46         // Lower route
  47         connect_nodes(myself, saturn, 50);
  48         connect_nodes(saturn, neptune, 501);
  49
  50         sssp_bfs();
  51
  52         assert_true(mars->status.visited);
  53         assert_true(saturn->status.visited);
  54         assert_true(neptune->status.visited);
  55
  56         assert_false(mars->status.indirect);
  57         assert_false(saturn->status.indirect);
  58         assert_false(neptune->status.indirect);
  59
  60         assert_int_equal(1, mars->distance);
  61         assert_int_equal(1, saturn->distance);
  62         assert_int_equal(2, neptune->distance);
  63
  64         assert_ptr_equal(mars, mars->nexthop);
  65         assert_ptr_equal(saturn, saturn->nexthop);
  66         assert_ptr_equal(saturn, neptune->nexthop);
  67
  68         assert_ptr_equal(lookup_edge(myself, mars), mars->prevedge);
  69         assert_ptr_equal(lookup_edge(myself, saturn), saturn->prevedge);
  70         assert_ptr_equal(lookup_edge(saturn, neptune), neptune->prevedge);
  71
  72         assert_ptr_equal(mars, mars->via);
  73         assert_ptr_equal(saturn, saturn->via);
  74         assert_ptr_equal(neptune, neptune->via);
  75 }
  76
  77 static void test_sssp_bfs(void **state) {
  78         (void)state;
  79
  80         node_t *mars = make_node("mars");
  81         node_t *saturn = make_node("saturn");
  82         node_t *neptune = make_node("neptune");
  83
  84         //          50            1000
  85         // myself ------ mars ------------- neptune
  86         //      \                             /
  87         //       ----------------- saturn ----
  88         //              500                10
  89
  90         // Upper route
  91         connect_nodes(myself, mars, 50);
  92         connect_nodes(mars, neptune, 1000);
  93
  94         // Lower route
  95         connect_nodes(myself, saturn, 500);
  96         connect_nodes(saturn, neptune, 10);
  97
  98         sssp_bfs();
  99
 100         assert_true(mars->status.visited);
 101         assert_true(saturn->status.visited);
 102         assert_true(neptune->status.visited);
 103
 104         assert_false(mars->status.indirect);
 105         assert_false(saturn->status.indirect);
 106         assert_false(neptune->status.indirect);
 107
 108         assert_int_equal(1, mars->distance);
 109         assert_int_equal(1, saturn->distance);
 110         assert_int_equal(2, neptune->distance);
 111
 112         assert_ptr_equal(mars, mars->nexthop);
 113         assert_ptr_equal(saturn, saturn->nexthop);
 114         assert_ptr_equal(saturn, neptune->nexthop);
 115
 116         assert_ptr_equal(lookup_edge(myself, mars), mars->prevedge);
 117         assert_ptr_equal(lookup_edge(myself, saturn), saturn->prevedge);
 118         assert_ptr_equal(lookup_edge(saturn, neptune), neptune->prevedge);
 119
 120         assert_ptr_equal(mars, mars->via);
 121         assert_ptr_equal(saturn, saturn->via);
 122         assert_ptr_equal(neptune, neptune->via);
 123 }
 124
 125 static int setup(void **state) {
 126         (void)state;
 127         myself = new_node("myself");
 128         return 0;
 129 }
 130
 131 static int teardown(void **state) {
 132         (void)state;
 133         free_node(myself);
 134         exit_nodes();
 135         exit_edges();
 136         return 0;
 137 }
 138
 139 int main(void) {
 140         const struct CMUnitTest tests[] = {
 141                 cmocka_unit_test_setup_teardown(test_sssp_bfs, setup, teardown),
 142                 cmocka_unit_test_setup_teardown(test_sssp_bfs_2, setup, teardown)
 143         };
 144         return cmocka_run_group_tests(tests, NULL, NULL);
 145 }