Index: routing/route_table.h
===================================================================
--- routing/route_table.h	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
+++ routing/route_table.h	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
@@ -0,0 +1,186 @@
+#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
