From Sven-Ola Tuecke <sven-ola@gmx.de>: add support for fixedpoint math
[olsrd.git] / src / tc_set.h
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
4  * LSDB rewrite (c) 2007, Hannes Gredler (hannes@gredler.at)
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without 
8  * modification, are permitted provided that the following conditions 
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright 
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright 
14  *   notice, this list of conditions and the following disclaimer in 
15  *   the documentation and/or other materials provided with the 
16  *   distribution.
17  * * Neither the name of olsr.org, olsrd nor the names of its 
18  *   contributors may be used to endorse or promote products derived 
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Visit http://www.olsr.org for more information.
35  *
36  * If you find this software useful feel free to make a donation
37  * to the project. For more information see the website or contact
38  * the copyright holders.
39  *
40  */
41
42 #ifndef _OLSR_TOP_SET
43 #define _OLSR_TOP_SET
44
45 #include "defs.h"
46 #include "packet.h"
47 #include "lq_avl.h"
48 #include "lq_list.h"
49
50 /*
51  * This file holds the definitions for the link state database.
52  * The lsdb consists of nodes and edges.
53  * During input parsing all nodes and edges are extracted and syntesized.
54  * The SPF calculation operates on these datasets.
55  */
56
57 struct tc_edge_entry
58 {
59   struct avl_node    edge_node; /* edge_tree node in tc_entry */
60   union olsr_ip_addr T_dest_addr; /* edge_node key */
61   struct tc_edge_entry *edge_inv; /* shortcut, used during SPF calculation */
62   struct tc_entry    *tc; /* backpointer to owning tc entry */
63   clock_t            T_time; /* expiration timer, timer_node key */
64   olsr_u16_t         T_seq; /* sequence number of the advertised neighbor set */
65   olsr_u16_t         flags; /* misc flags */
66 #ifdef USE_FPM
67   fpm                etx; /* metric used for SPF calculation */
68   fpm                link_quality;
69   fpm                inverse_link_quality;
70 #else
71   float              etx; /* metric used for SPF calculation */
72   float              link_quality;
73   float              inverse_link_quality;
74 #endif
75 };
76
77 #define OLSR_TC_EDGE_DOWN (1 << 0) /* this edge is down */
78
79 /*
80  * Garbage collection time for downed edges
81  */
82 #define OLSR_TC_EDGE_GC_TIME (15*1000) /* milliseconds */
83
84 struct tc_entry
85 {
86   struct avl_node    vertex_node; /* node keyed by ip address */
87   struct avl_node    cand_tree_node; /* SPF candidate heap, node keyed by path_etx */
88   struct list_node   path_list_node; /* SPF result list */
89   union olsr_ip_addr addr; /* vertex_node key */
90   struct avl_tree    edge_tree; /* subtree for edges */
91   struct avl_tree    prefix_tree; /* subtree for prefixes */
92   struct link_entry  *next_hop; /* SPF calculated link to the 1st hop neighbor */
93 #ifdef USE_FPM
94   fpm                path_etx; /* SPF calculated distance, cand_tree_node key */
95 #else
96   float              path_etx; /* SPF calculated distance, cand_tree_node key */
97 #endif
98   olsr_u16_t         msg_seq; /* sequence number of the tc message */
99   olsr_u8_t          msg_hops; /* hopcount as per the tc message */
100   olsr_u8_t          hops; /* SPF calculated hopcount */
101   olsr_u16_t         ansn; /* ANSN number of the tc message */
102   olsr_u16_t         ignored; /* how many TC messages ignored in a sequence (kindof emergency brake) */
103   olsr_u16_t         err_seq; /* sequence number of an unplausible TC */
104   olsr_bool          err_seq_valid; /* do we have an error (unplauible seq/ansn) */
105 };
106
107 /*
108  * macros for traversing vertices, edges and prefixes in the link state database.
109  * it is recommended to use this because it hides all the internal
110  * datastructure from the callers.
111  *
112  * the loop prefetches the next node in order to not loose context if
113  * for example the caller wants to delete the current entry.
114  */
115 #define OLSR_FOR_ALL_TC_ENTRIES(tc) \
116 { \
117   struct avl_node *tc_tree_node, *next_tc_tree_node; \
118   for (tc_tree_node = avl_walk_first(&tc_tree); \
119     tc_tree_node; tc_tree_node = next_tc_tree_node) { \
120     next_tc_tree_node = avl_walk_next(tc_tree_node); \
121     tc = tc_tree_node->data;
122 #define OLSR_FOR_ALL_TC_ENTRIES_END(tc) }}
123
124 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) \
125 { \
126   struct avl_node *tc_edge_node, *next_tc_edge_node; \
127   for (tc_edge_node = avl_walk_first(&tc->edge_tree); \
128     tc_edge_node; tc_edge_node = next_tc_edge_node) { \
129     next_tc_edge_node = avl_walk_next(tc_edge_node); \
130     tc_edge = tc_edge_node->data;
131 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge) }}
132
133 extern struct avl_tree tc_tree;
134 extern struct tc_entry *tc_myself;
135
136 void olsr_init_tc(void);
137 void olsr_change_myself_tc(void);
138 void olsr_print_tc_table(void);
139 void olsr_time_out_tc_set(void);
140
141 /* tc msg input parser */
142 void olsr_input_tc(union olsr_message *, struct interface *,
143                    union olsr_ip_addr *from);
144
145 /* tc_entry manipulation */
146 struct tc_entry *olsr_lookup_tc_entry(union olsr_ip_addr *);
147 struct tc_entry *olsr_locate_tc_entry(union olsr_ip_addr *);
148
149 /* tc_edge_entry manipulation */
150 char *olsr_tc_edge_to_string(struct tc_edge_entry *);
151 struct tc_edge_entry *olsr_lookup_tc_edge(struct tc_entry *,
152                                           union olsr_ip_addr *);
153 struct tc_edge_entry *olsr_add_tc_edge_entry(struct tc_entry *,
154                                              union olsr_ip_addr *, olsr_u16_t,
155                                              unsigned int,
156 #ifdef USE_FPM
157                                              fpm, fpm
158 #else
159                                              float, float
160 #endif
161                                              );
162 void olsr_delete_tc_entry(struct tc_entry *);
163 void olsr_delete_tc_edge_entry(struct tc_edge_entry *);
164 void olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *);
165 #ifdef USE_FPM
166 fpm
167 #else
168 float
169 #endif
170 olsr_calc_tc_etx(const struct tc_edge_entry *);
171 void olsr_set_tc_edge_timer(struct tc_edge_entry *, unsigned int);
172
173 #endif
174
175 /*
176  * Local Variables:
177  * c-basic-offset: 2
178  * End:
179  */