7e40952ca2a3e193326e0de8a0ba0a8c4c8cb032
[olsrd.git] / src / tc_set.c
1 /*
2  * OLSR ad-hoc routing table management protocol
3  * Copyright (C) 2004 Andreas T√łnnesen (andreto@ifi.uio.no)
4  *
5  * This file is part of olsr.org.
6  *
7  * UniK olsrd is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * UniK olsrd is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with olsr.org; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20  *
21  */
22
23
24 #include "tc_set.h"
25 #include "olsr.h"
26 #include "scheduler.h"
27
28 /**
29  * Initialize the topology set
30  *
31  */
32
33 int
34 olsr_init_tc()
35 {
36   int index;
37   
38   /* Set timer to zero */
39   send_empty_tc.tv_sec = 0;
40   send_empty_tc.tv_usec = 0;
41
42   changes = 0;
43
44   olsr_printf(5, "TC: init topo\n");
45
46   olsr_register_timeout_function(&olsr_time_out_tc_set);
47
48   for(index=0;index<HASHSIZE;index++)
49     {
50       tc_table[index].next = &tc_table[index];
51       tc_table[index].prev = &tc_table[index];
52     }
53
54   return 1;
55 }
56
57
58 /**
59  *Delete a TC entry if it has no associated
60  *destinations
61  *
62  *@param entry the TC entry to check and possibly delete
63  *
64  *@return 1 if entry deleted 0 if not
65  */
66
67 int
68 olsr_tc_delete_entry_if_empty(struct tc_entry *entry)
69 {
70
71   //olsr_printf(1, "TC: del entry if empty\n");
72
73   if(entry->destinations.next == &entry->destinations)
74     {
75       /* dequeue */
76       DEQUEUE_ELEM(entry);
77       //entry->prev->next = entry->next;
78       //entry->next->prev = entry->prev;
79       olsr_printf(1, "TC-SET: Deleting empty entry %s ->\n", olsr_ip_to_string(&entry->T_last_addr));
80       free(entry);
81       return 1;
82     }
83   return 0;
84 }
85
86
87
88 /**
89  * Look up a entry from the TC tabe based
90  * on address
91  *
92  *@param adr the address to look for
93  *
94  *@return the entry found or NULL
95  */
96
97 struct tc_entry *
98 olsr_lookup_tc_entry(union olsr_ip_addr *adr)
99 {
100   struct tc_entry *entries;
101   olsr_u32_t hash;
102
103   //olsr_printf(1, "TC: lookup entry\n");
104
105   hash = olsr_hashing(adr);
106
107   for(entries = tc_table[hash].next; 
108       entries != &tc_table[hash]; 
109       entries = entries->next)
110     {
111       //printf("TC lookup checking: %s\n", olsr_ip_to_string(&entries->T_last_addr));
112       if(COMP_IP(adr, &entries->T_last_addr))
113         return entries;
114     }
115
116   return NULL;
117 }
118
119
120 /**
121  *Add a new tc_entry to the tc set
122  *
123  *@param (last)adr address of the entry
124  *
125  *@return a pointer to the created entry
126  */
127
128 struct tc_entry *
129 olsr_add_tc_entry(union olsr_ip_addr *adr)
130 {
131   struct tc_entry *new_entry;
132   olsr_u32_t hash;
133
134   olsr_printf(1, "TC: adding entry %s\n", olsr_ip_to_string(adr));
135
136   hash = olsr_hashing(adr);
137
138   new_entry = olsr_malloc(sizeof(struct tc_entry), "New TC entry");
139
140   /* Fill entry */
141   COPY_IP(&new_entry->T_last_addr, adr);
142   new_entry->destinations.next = &new_entry->destinations;
143   new_entry->destinations.prev = &new_entry->destinations;
144
145   /* Queue entry */
146   QUEUE_ELEM(tc_table[hash], new_entry);
147   /*
148   new_entry->next = tc_table[hash].next;
149   new_entry->prev = tc_table[hash].next->prev;
150   tc_table[hash].next->prev = new_entry;
151   tc_table[hash].next = new_entry;
152   */
153
154   return new_entry;
155 }
156
157
158 /**
159  *Delete all destinations that have a
160  *lower ANSN than the one in the message
161  *
162  *@param entry the entry to delete destenations from
163  *@param msg the message to fetch the ANSN from
164  *
165  *@return 1 if any destinations were deleted 0 if not
166  */
167
168 int
169 olsr_tc_delete_mprs(struct tc_entry *entry, struct tc_message *msg)
170 {
171   struct topo_dst *tmp_dsts, *dst_to_del;
172   int retval;
173
174   //olsr_printf(5, "TC: deleting MPRS\n");
175
176   tmp_dsts = entry->destinations.next;
177   retval = 0;
178
179   while(tmp_dsts != &entry->destinations)
180     {
181       if(SEQNO_GREATER_THAN(msg->ansn, tmp_dsts->T_seq))
182         {
183           /* Delete entry */
184           dst_to_del = tmp_dsts;
185           tmp_dsts = tmp_dsts->next;
186
187           /* dequeue */
188           DEQUEUE_ELEM(dst_to_del);
189           /*
190           dst_to_del->next->prev = dst_to_del->prev;
191           dst_to_del->prev->next = dst_to_del->next;
192           */
193
194           free(dst_to_del);
195           retval = 1;
196         }
197       else
198         tmp_dsts = tmp_dsts->next;
199
200     }
201
202   return retval;
203 }
204
205
206 /**
207  *Update the destinations registered on an entry.
208  *Creates new dest-entries if not registered.
209  *Bases update on a receivied TC message
210  *
211  *@param entry the TC entry to check
212  *@msg the TC message to update by
213  *
214  *@return 1 if entries are added 0 if not
215  */
216
217 int
218 olsr_tc_update_mprs(struct tc_entry *entry, struct tc_message *msg)
219 {
220   struct tc_mpr_addr *mprs;
221   struct topo_dst *new_topo_dst, *existing_dst;
222   int retval;
223
224   //olsr_printf(1, "TC: update MPRS\n");
225
226   retval = 0;
227
228
229   mprs = msg->multipoint_relay_selector_address;
230   
231   /* Add all the MPRs */
232
233   while(mprs != NULL)
234     {
235       existing_dst = olsr_tc_lookup_dst(entry, &mprs->address);
236
237       if(existing_dst == NULL)
238         {
239           /* New entry */
240           new_topo_dst = olsr_malloc(sizeof(struct topo_dst), "add TC destination");
241
242           COPY_IP(&new_topo_dst->T_dest_addr, &mprs->address);
243           olsr_get_timestamp((olsr_u32_t) msg->vtime*1000, &new_topo_dst->T_time);
244           new_topo_dst->T_seq = msg->ansn;
245           /* Add to queue */
246           new_topo_dst->prev = &entry->destinations;
247           new_topo_dst->next = entry->destinations.next;
248           entry->destinations.next->prev = new_topo_dst;
249           entry->destinations.next = new_topo_dst;
250
251           retval = 1;
252         }
253       else
254         {
255           /* Update entry */
256           olsr_get_timestamp((olsr_u32_t) msg->vtime*1000, &existing_dst->T_time);
257           existing_dst->T_seq = msg->ansn;
258         }
259
260       mprs = mprs->next;
261     }
262
263   return retval;
264 }
265
266
267
268 /**
269  *Lookup a destination in a TC entry
270  *
271  *@param entry the entry to check
272  *@param dst_addr the destination address to check for
273  *
274  *@return a pointer to the topo_dst found - or NULL
275  */
276 struct topo_dst *
277 olsr_tc_lookup_dst(struct tc_entry *entry, union olsr_ip_addr *dst_addr)
278 {
279   struct topo_dst *dsts;
280   
281   //olsr_printf(1, "TC: lookup dst\n");
282
283   for(dsts = entry->destinations.next; 
284       dsts != &entry->destinations; 
285       dsts = dsts->next)
286     {
287       if(COMP_IP(dst_addr, &dsts->T_dest_addr))
288         return dsts;
289     }
290   return NULL;
291 }
292
293
294
295
296
297
298 /**
299  * Time out entries
300  *
301  *@return nada
302  */
303
304 void
305 olsr_time_out_tc_set()
306 {
307   int index, deleted;
308   struct tc_entry *entry, *entry2;
309   struct topo_dst *dst_entry, *dst_to_delete;
310
311
312   for(index=0;index<HASHSIZE;index++)
313     {
314       /* For all TC entries */
315       entry = tc_table[index].next;
316       while(entry != &tc_table[index])
317         {
318           //printf("INDEX: %d\n", index);
319           /* For all destination entries of that TC entry */
320           deleted = 0;
321           dst_entry = entry->destinations.next;
322           while(dst_entry != &entry->destinations)
323             {
324               /* If timed out - delete */
325               if(TIMED_OUT(&dst_entry->T_time))
326                 {
327                   deleted = 1;
328                   /* Dequeue */
329                   DEQUEUE_ELEM(dst_entry);
330                   //dst_entry->prev->next = dst_entry->next;
331                   //dst_entry->next->prev = dst_entry->prev;
332
333                   dst_to_delete = dst_entry;
334
335                   dst_entry = dst_entry->next;
336
337                   /* Delete */
338                   free(dst_to_delete);
339
340                 }
341               else
342                 dst_entry = dst_entry->next;
343             }
344           /* Delete entry if no destinations */
345           entry2 = entry;
346           entry = entry->next;
347           if(deleted)
348             olsr_tc_delete_entry_if_empty(entry2);
349         }
350     }
351
352   return;
353 }
354
355
356 /**
357  *Print the topology table to stdout
358  */
359 int
360 olsr_print_tc_table()
361 {
362   int index;
363   struct tc_entry *entry;
364   struct topo_dst *dst_entry;
365   
366   olsr_printf(1, "topology table: %02d:%02d:%02d.%06lu\n",nowtm->tm_hour, nowtm->tm_min, nowtm->tm_sec, now.tv_usec);
367
368   for(index=0;index<HASHSIZE;index++)
369     {
370       /* For all TC entries */
371       entry = tc_table[index].next;
372       while(entry != &tc_table[index])
373         {
374           /* For all destination entries of that TC entry */
375           dst_entry = entry->destinations.next;
376           while(dst_entry != &entry->destinations)
377             {
378               olsr_printf(1, "%s", olsr_ip_to_string(&entry->T_last_addr));
379               olsr_printf(1, " -> %s\n", olsr_ip_to_string(&dst_entry->T_dest_addr));
380               dst_entry = dst_entry->next;
381             }
382           entry = entry->next;
383         }
384       
385     }
386
387   olsr_printf(1, "\n");
388   
389   return 1;
390 }