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