source: routing/route_table.h @ f0b96ba

#ifndef ROUTE_TABLE_H
#define ROUTE_TABLE_H

#include "net.h"
#include <vector>
#include <set>
#include <map>

#include <algorithm>
#include <functional>
#include <ext/functional>

using __gnu_cxx::compose1;

class route_table {
    protected:
        typedef std::set<Net> net_set_t;
        typedef std::map<Net, Host> net_map_t;
        typedef std::map<Host, net_set_t> route_map_t;
        route_map_t rm;
        net_map_t nm;
        net_set_t empty;
        // Helper functor that just returns the first member of a
        // pair
        template <class p>
            class select1st {
                public:
                typename p::first_type operator()(p x) const { return x.first; }
            };

        class contains : public std::unary_function<Net, bool> {
            protected:
                const Net& container;   // Net that may contain test values
            public:
                contains(const Net& c) : container(c) { }
                bool operator()(const Net& n) const {
                    return n.inside(container);
                }
        };

        class set_remover : public std::unary_function<Net, void> {
            protected:
                net_set_t& s;
            public:
                set_remover(net_set_t& ss) : s(ss) { }
                void operator()(const Net& n) { s.erase(n); }
        };

    public:
        route_table() : rm(), nm(), empty() { }
        void insert(const Net& dest, const Host& gw) {
            net_map_t::iterator n = nm.find(dest);

            if ( n == nm.end() || gw < (*n).second) {
                // never seen this network before, insert it, or it's a
                // duplicate and the next hop is a lower IP address than the
                // last attempted insert.  Keep the lower GW for consistency
                // (Remove any dupes, though)
                if (gw <  (*n).second) {
                    remove(dest, (*n).second);
                }

                route_map_t::iterator r = rm.find(gw);

                if ( r != rm.end()) {
                    (*r).second.insert(dest);
                }
                else { 
                    rm[gw] = net_set_t();
                    rm[gw].insert(dest);
                }
                nm.insert(net_map_t::value_type(dest, gw));
            }
        }
        const net_set_t& get(const Host& gw) const { 
            route_map_t::const_iterator r = rm.find(gw);

            if ( r != rm.end()) return (*r).second;
            else return empty;
        }

        void remove(const Net& dest, const Host& gw) {
            route_map_t::iterator r = rm.find(gw);

            if ( r != rm.end()) {
                (*r).second.erase(dest);
                // Remove the entry from the netmap
                nm.erase(dest);
                // If this gateway has no destinations, remove it from the map
                // all togther.
                if ((*r).second.empty()) 
                    rm.erase(gw);
            }
        }

        std::ostream& print(std::ostream& f) const {
            for (route_map_t::const_iterator i = rm.begin(); i != rm.end(); i++)
                for (net_set_t::const_iterator j = (*i).second.begin();
                        j != (*i).second.end(); j++)
                    f << (*j) << " " << (*i).first << std::endl;
            return f;
        }

        bool collision(const Net& tryit, const Host& out) const {
            // Return true if there is a routing in rm that would be dirsupted
            // by adding the net in tryit to the out gateway.  That is, if any
            // destination network on another interface is inside tryit, return
            // false.
            for (route_map_t::const_iterator r = rm.begin(); 
                    r != rm.end(); r++) {
                if ((*r).first == out) continue;
                for (net_set_t::const_iterator n = (*r).second.begin(); 
                        n != (*r).second.end(); n++) {
                    if ((*n).inside(tryit)) return true;
                }
            }
            return false;
        }


        void collapse() {
            // Try to make rm as small as possible by expanding each
            // destination network until it either conflicts with a destination
            // network on another gateway or is a /8.
            std::vector<Host> gateways;

            transform(rm.begin(), rm.end(), back_inserter(gateways), 
                    select1st<route_map_t::value_type>());

            for (std::vector<Host>::const_iterator gw = gateways.begin(); 
                    gw != gateways.end(); gw++) {
                // Try to expand all the destinations on gw.  Copy them into
                // candidates for expansion and try all the candidates.
                net_set_t candidates = get(*gw);

                while (! candidates.empty()) {

                    // Pop a value from the set.
                    Net tryit = *candidates.begin();
                    candidates.erase(tryit);

                    // While it grows, try to expand it and remove any networks
                    // it expands over.
                    bool growing = true;
                    while (growing && tryit.get_mask() > 8) {
                        tryit.set_mask(tryit.get_mask() - 1);

                        if ( collision(tryit, *gw) ) {
                            growing = false; 
                        }
                        else {
                            // Successfully got bigger.  Remove nets inside the
                            // new new from the routing table and candidate
                            // set, and insert the larger net into the table.
                            std::vector<Net> to_remove;

                            // Collect the Nets to remove
                            std::remove_copy_if(get(*gw).begin(), 
                                    get(*gw).end(),
                                    std::back_inserter(to_remove),
                                    compose1(std::logical_not<bool>(),
                                        contains(tryit)));
                            // Remove 'em - calling remove makes sure the
                            // internal route_table data structures stay in
                            // sync.  This has been a bug source in the past.
                            for (std::vector<Net>::const_iterator tr = 
                                    to_remove.begin(); 
                                    tr != to_remove.end(); tr++) {
                                remove(*tr, *gw);
                                candidates.erase(*tr);
                            }
                            // New bigger candidate gots into the route_table
                            // here.
                            insert(tryit, *gw);
                        }
                    }
                }
            }
        }
};

inline std::ostream& operator<<(std::ostream& f, const route_table& rt ) {
    return rt.print(f);
}

#endif