git.meshlink.io Git - meshlink/blob - src/edge.c

   1 /*
   2     edge.c -- edge tree management
   3     Copyright (C) 2000-2002 Guus Sliepen <guus@sliepen.warande.net>,
   4                   2000-2002 Ivo Timmermans <itimmermans@bigfoot.com>
   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: edge.c,v 1.1.2.6 2002/02/10 21:57:54 guus Exp $
  21 */
  22
  23 #include "config.h"
  24
  25 #include <stdio.h>
  26 #include <syslog.h>
  27 #include <string.h>
  28
  29 #include <avl_tree.h>
  30 #include <list.h>
  31
  32 #include "net.h"        /* Don't ask. */
  33 #include "netutl.h"
  34 #include "config.h"
  35 #include "conf.h"
  36 #include <utils.h>
  37 #include "subnet.h"
  38
  39 #include "xalloc.h"
  40 #include "system.h"
  41
  42 avl_tree_t *edge_tree;        /* Tree with all known edges (replaces active_tree) */
  43 avl_tree_t *edge_weight_tree; /* Tree with all edges, sorted on weight */
  44
  45 int edge_compare(edge_t *a, edge_t *b)
  46 {
  47   int result;
  48
  49   result = strcmp(a->from.node->name, b->from.node->name);
  50
  51   if(result)
  52     return result;
  53   else
  54     return strcmp(a->to.node->name, b->to.node->name);
  55 }
  56
  57 /* Evil edge_compare() from a parallel universe ;)
  58
  59 int edge_compare(edge_t *a, edge_t *b)
  60 {
  61   int result;
  62
  63   return (result = strcmp(a->from.node->name, b->from.node->name)) || (result = strcmp(a->to.node->name, b->to.node->name)), result;
  64 }
  65
  66 */
  67
  68 int edge_name_compare(edge_t *a, edge_t *b)
  69 {
  70   int result;
  71   char *name_a1, *name_a2, *name_b1, *name_b2;
  72
  73   if(strcmp(a->from.node->name, a->to.node->name) < 0)
  74     name_a1 = a->from.node->name, name_a2 = a->to.node->name;
  75   else
  76     name_a1 = a->to.node->name, name_a2 = a->from.node->name;
  77
  78   if(strcmp(b->from.node->name, b->to.node->name) < 0)
  79     name_b1 = b->from.node->name, name_b2 = b->to.node->name;
  80   else
  81     name_b1 = b->to.node->name, name_b2 = b->from.node->name;
  82
  83   result = strcmp(name_a1, name_b1);
  84
  85   if(result)
  86     return result;
  87   else
  88     return strcmp(name_a2, name_b2);
  89 }
  90
  91 int edge_weight_compare(edge_t *a, edge_t *b)
  92 {
  93   int result;
  94
  95   result = a->weight - b->weight;
  96
  97   if(result)
  98     return result;
  99   else
 100     return edge_name_compare(a, b);
 101 }
 102
 103 void init_edges(void)
 104 {
 105 cp
 106   edge_tree = avl_alloc_tree((avl_compare_t)edge_compare, NULL);
 107   edge_weight_tree = avl_alloc_tree((avl_compare_t)edge_weight_compare, NULL);
 108 cp
 109 }
 110
 111 avl_tree_t *new_edge_tree(void)
 112 {
 113 cp
 114   return avl_alloc_tree((avl_compare_t)edge_name_compare, NULL);
 115 cp
 116 }
 117
 118 void free_edge_tree(avl_tree_t *edge_tree)
 119 {
 120 cp
 121   avl_delete_tree(edge_tree);
 122 cp
 123 }
 124
 125 void exit_edges(void)
 126 {
 127 cp
 128   avl_delete_tree(edge_tree);
 129 cp
 130 }
 131
 132 /* Creation and deletion of connection elements */
 133
 134 edge_t *new_edge(void)
 135 {
 136   edge_t *e;
 137 cp
 138   e = (edge_t *)xmalloc_and_zero(sizeof(*e));
 139 cp
 140   return e;
 141 }
 142
 143 void free_edge(edge_t *e)
 144 {
 145 cp
 146   free(e);
 147 cp
 148 }
 149
 150 void edge_add(edge_t *e)
 151 {
 152 cp
 153   avl_insert(edge_tree, e);
 154   avl_insert(edge_weight_tree, e);
 155   avl_insert(e->from.node->edge_tree, e);
 156   avl_insert(e->to.node->edge_tree, e);
 157 cp
 158 }
 159
 160 void edge_del(edge_t *e)
 161 {
 162 cp
 163   avl_delete(edge_tree, e);
 164   avl_delete(edge_weight_tree, e);
 165   avl_delete(e->from.node->edge_tree, e);
 166   avl_delete(e->to.node->edge_tree, e);
 167 cp
 168 }
 169
 170 edge_t *lookup_edge(node_t *from, node_t *to)
 171 {
 172   edge_t v, *result;
 173 cp
 174   v.from.node = from;
 175   v.to.node = to;
 176
 177   result = avl_search(edge_tree, &v);
 178
 179   if(result)
 180     return result;
 181 cp
 182   v.from.node = to;
 183   v.to.node = from;
 184
 185   return avl_search(edge_tree, &v);
 186 }
 187
 188 void dump_edges(void)
 189 {
 190   avl_node_t *node;
 191   edge_t *e;
 192   char *from_address, *to_address;
 193 cp
 194   syslog(LOG_DEBUG, _("Edges:"));
 195
 196   for(node = edge_tree->head; node; node = node->next)
 197     {
 198       e = (edge_t *)node->data;
 199       from_address = address2str(e->from.address);
 200       to_address = address2str(e->to.address);
 201       syslog(LOG_DEBUG, _(" %s at %s port %hd - %s at %s port %hd options %ld weight %d"),
 202              e->from.node->name, from_address, e->from.port,
 203              e->to.node->name, to_address, e->to.port,
 204              e->options, e->weight);
 205       free(from_address);
 206       free(to_address);
 207     }
 208
 209   syslog(LOG_DEBUG, _("End of edges."));
 210 cp
 211 }