source: routing/route_table.h @ e8f2d4c

Last change on this file since e8f2d4c was f24fc8d, checked in by Ted Faber <faber@…>, 12 years ago

Routing under here, too

  • Property mode set to 100644
File size: 5.1 KB
Line 
1#ifndef ROUTE_TABLE_H
2#define ROUTE_TABLE_H
3
4#include "net.h"
5#include <vector>
6#include <set>
7#include <map>
8
9#include <algorithm>
10#include <functional>
11#include <ext/functional>
12
13using __gnu_cxx::compose1;
14
15class route_table {
16    protected:
17        typedef std::set<Net> net_set_t;
18        typedef std::map<Net, Host> net_map_t;
19        typedef std::map<Host, net_set_t> route_map_t;
20        route_map_t rm;
21        net_map_t nm;
22        net_set_t empty;
23        // Helper functor that just returns the first member of a
24        // pair
25        template <class p>
26            class select1st {
27                public:
28                typename p::first_type operator()(p x) const { return x.first; }
29            };
30
31        class contains : public std::unary_function<Net, bool> {
32            protected:
33                const Net& container;   // Net that may contain test values
34            public:
35                contains(const Net& c) : container(c) { }
36                bool operator()(const Net& n) const {
37                    return n.inside(container);
38                }
39        };
40
41        class set_remover : public std::unary_function<Net, void> {
42            protected:
43                net_set_t& s;
44            public:
45                set_remover(net_set_t& ss) : s(ss) { }
46                void operator()(const Net& n) { s.erase(n); }
47        };
48
49    public:
50        route_table() : rm(), nm(), empty() { }
51        void insert(const Net& dest, const Host& gw) {
52            net_map_t::iterator n = nm.find(dest);
53
54            if ( n == nm.end() || gw < (*n).second) {
55                // never seen this network before, insert it, or it's a
56                // duplicate and the next hop is a lower IP address than the
57                // last attempted insert.  Keep the lower GW for consistency
58                // (Remove any dupes, though)
59                if (gw <  (*n).second) {
60                    remove(dest, (*n).second);
61                }
62
63                route_map_t::iterator r = rm.find(gw);
64
65                if ( r != rm.end()) {
66                    (*r).second.insert(dest);
67                }
68                else { 
69                    rm[gw] = net_set_t();
70                    rm[gw].insert(dest);
71                }
72                nm.insert(net_map_t::value_type(dest, gw));
73            }
74        }
75        const net_set_t& get(const Host& gw) const { 
76            route_map_t::const_iterator r = rm.find(gw);
77
78            if ( r != rm.end()) return (*r).second;
79            else return empty;
80        }
81
82        void remove(const Net& dest, const Host& gw) {
83            route_map_t::iterator r = rm.find(gw);
84
85            if ( r != rm.end()) {
86                (*r).second.erase(dest);
87                // Remove the entry from the netmap
88                nm.erase(dest);
89                // If this gateway has no destinations, remove it from the map
90                // all togther.
91                if ((*r).second.empty()) 
92                    rm.erase(gw);
93            }
94        }
95
96        std::ostream& print(std::ostream& f) const {
97            for (route_map_t::const_iterator i = rm.begin(); i != rm.end(); i++)
98                for (net_set_t::const_iterator j = (*i).second.begin();
99                        j != (*i).second.end(); j++)
100                    f << (*j) << " " << (*i).first << std::endl;
101            return f;
102        }
103
104        bool collision(const Net& tryit, const Host& out) const {
105            // Return true if there is a routing in rm that would be dirsupted
106            // by adding the net in tryit to the out gateway.  That is, if any
107            // destination network on another interface is inside tryit, return
108            // false.
109            for (route_map_t::const_iterator r = rm.begin(); 
110                    r != rm.end(); r++) {
111                if ((*r).first == out) continue;
112                for (net_set_t::const_iterator n = (*r).second.begin(); 
113                        n != (*r).second.end(); n++) {
114                    if ((*n).inside(tryit)) return true;
115                }
116            }
117            return false;
118        }
119
120
121        void collapse() {
122            // Try to make rm as small as possible by expanding each
123            // destination network until it either conflicts with a destination
124            // network on another gateway or is a /8.
125            std::vector<Host> gateways;
126
127            transform(rm.begin(), rm.end(), back_inserter(gateways), 
128                    select1st<route_map_t::value_type>());
129
130            for (std::vector<Host>::const_iterator gw = gateways.begin(); 
131                    gw != gateways.end(); gw++) {
132                // Try to expand all the destinations on gw.  Copy them into
133                // candidates for expansion and try all the candidates.
134                net_set_t candidates = get(*gw);
135
136                while (! candidates.empty()) {
137
138                    // Pop a value from the set.
139                    Net tryit = *candidates.begin();
140                    candidates.erase(tryit);
141
142                    // While it grows, try to expand it and remove any networks
143                    // it expands over.
144                    bool growing = true;
145                    while (growing && tryit.get_mask() > 8) {
146                        tryit.set_mask(tryit.get_mask() - 1);
147
148                        if ( collision(tryit, *gw) ) {
149                            growing = false; 
150                        }
151                        else {
152                            // Successfully got bigger.  Remove nets inside the
153                            // new new from the routing table and candidate
154                            // set, and insert the larger net into the table.
155                            std::vector<Net> to_remove;
156
157                            // Collect the Nets to remove
158                            std::remove_copy_if(get(*gw).begin(), 
159                                    get(*gw).end(),
160                                    std::back_inserter(to_remove),
161                                    compose1(std::logical_not<bool>(),
162                                        contains(tryit)));
163                            // Remove 'em - calling remove makes sure the
164                            // internal route_table data structures stay in
165                            // sync.  This has been a bug source in the past.
166                            for (std::vector<Net>::const_iterator tr = 
167                                    to_remove.begin(); 
168                                    tr != to_remove.end(); tr++) {
169                                remove(*tr, *gw);
170                                candidates.erase(*tr);
171                            }
172                            // New bigger candidate gots into the route_table
173                            // here.
174                            insert(tryit, *gw);
175                        }
176                    }
177                }
178            }
179        }
180};
181
182inline std::ostream& operator<<(std::ostream& f, const route_table& rt ) {
183    return rt.print(f);
184}
185
186#endif
Note: See TracBrowser for help on using the repository browser.