xorp

mrt.hh

00001 // -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
00002 // vim:set sts=4 ts=8:
00003 
00004 // Copyright (c) 2001-2011 XORP, Inc and Others
00005 //
00006 // This program is free software; you can redistribute it and/or modify
00007 // it under the terms of the GNU General Public License, Version 2, June
00008 // 1991 as published by the Free Software Foundation. Redistribution
00009 // and/or modification of this program under the terms of any other
00010 // version of the GNU General Public License is not permitted.
00011 // 
00012 // This program is distributed in the hope that it will be useful, but
00013 // WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. For more details,
00015 // see the GNU General Public License, Version 2, a copy of which can be
00016 // found in the XORP LICENSE.gpl file.
00017 // 
00018 // XORP Inc, 2953 Bunker Hill Lane, Suite 204, Santa Clara, CA 95054, USA;
00019 // http://xorp.net
00020 
00021 
00022 #ifndef __MRT_MRT_HH__
00023 #define __MRT_MRT_HH__
00024 
00025 
00026 //
00027 // Multicast Routing Table implementation.
00028 //
00029 
00030 
00031 #include "libxorp/xorp.h"
00032 #include "libxorp/ipvx.hh"
00033 #include "libxorp/ipvxnet.hh"
00034 
00035 
00039 class SourceGroup {
00040 public:
00047     SourceGroup(const IPvX& source_addr, const IPvX& group_addr)
00048     : _source_addr(source_addr), _group_addr(group_addr) {}
00049     
00055     const IPvX& source_addr() const { return (_source_addr); }
00056     
00062     const IPvX& group_addr() const { return (_group_addr); }
00063     
00064 private:
00065     IPvX _source_addr;      // The source address
00066     IPvX _group_addr;       // The group address
00067 };
00068 
00072 class MreSgKey {
00073 public:
00079     MreSgKey(const SourceGroup& source_group) : _source_group(&source_group) {}
00080     
00086     const SourceGroup& source_group() const { return (*_source_group); }
00087     
00096     bool operator<(const MreSgKey& other) const {
00097     if (_source_group && other._source_group) {
00098         if (_source_group->source_addr() == other.source_group().source_addr())
00099         return (_source_group->group_addr()
00100             < other.source_group().group_addr());   
00101         return (_source_group->source_addr()
00102             < other.source_group().source_addr());
00103     }
00104     else {
00105         if (_source_group)
00106         return false;
00107         return true;
00108     }
00109     }
00110     
00118     bool operator==(const MreSgKey& other) const {
00119     if (_source_group == other._source_group)
00120         return true;
00121     if (!(_source_group && other._source_group))
00122         return false;
00123     return ((_source_group->source_addr()
00124          == other.source_group().source_addr())
00125         && (_source_group->group_addr()
00126             == other.source_group().group_addr()));
00127     }
00128 
00129     MreSgKey() { _source_group = NULL; }
00130 
00131     MreSgKey& operator=(const MreSgKey& rhs) {
00132     if (this != &rhs) {
00133         _source_group = rhs._source_group;
00134     }
00135     return *this;
00136     }
00137     
00138 private:
00139     // A reference to the corresponding
00140     // (S,G) used for comparison.
00141     mutable const SourceGroup* _source_group;
00142 };
00143 
00147 class MreGsKey {
00148 public:
00154     MreGsKey(const SourceGroup& source_group) : _source_group(&source_group) {}
00155 
00161     const SourceGroup& source_group() const { return (*_source_group); }
00162 
00171     bool operator<(const MreGsKey& other) const {
00172     if (_source_group && other._source_group) {
00173         if (_source_group->group_addr() == other.source_group().group_addr())
00174         return (_source_group->source_addr()
00175             < other.source_group().source_addr());
00176         return (_source_group->group_addr()
00177             < other.source_group().group_addr());
00178     }
00179     else {
00180         if (_source_group)
00181         return false;
00182         return true;
00183     }
00184     }
00185     
00193     bool operator==(const MreGsKey& other) const {
00194     if (_source_group == other._source_group)
00195         return true;
00196     if (!(_source_group && other._source_group))
00197         return false;
00198     return ((_source_group->source_addr()
00199          == other.source_group().source_addr())
00200         && (_source_group->group_addr()
00201             == other.source_group().group_addr()) );
00202     }
00203 
00204     MreGsKey() { _source_group = NULL; }
00205 
00206     MreGsKey& operator=(const MreGsKey& rhs) {
00207     if (this != &rhs) {
00208         _source_group = rhs._source_group;
00209     }
00210     return *this;
00211     }
00212     
00213 private:
00214     // A reference to the corresponding
00215     // (S,G) used for comparison.
00216     mutable const SourceGroup* _source_group;
00217 };
00218 
00222 template <class E>
00223 class Mrt {
00224 public:
00228     Mrt() {}
00229     
00233     virtual ~Mrt() { clear(); }
00234     
00235     //
00236     // Typedefs for lookup maps and iterators.
00237     //
00238     typedef map<MreSgKey, E*>       SgMap;
00239     typedef map<MreGsKey, E*>       GsMap;
00240     
00241     typedef typename SgMap::iterator    sg_iterator;
00242     typedef typename GsMap::iterator    gs_iterator;
00243     typedef typename SgMap::const_iterator const_sg_iterator;
00244     typedef typename GsMap::const_iterator const_gs_iterator;
00245     
00251     void clear() {
00252     // Remove all multicast routing entries.
00253     for (sg_iterator iter = _sg_table.begin(); iter != _sg_table.end(); ) {
00254         E *mre = iter->second;
00255         ++iter;
00256         delete mre;
00257     }
00258     // Clear the (S,G) and (G,S) lookup tables
00259     _sg_table.clear();
00260     _gs_table.clear();
00261     }
00262     
00273     E *insert(E *mre) {
00274     pair<sg_iterator, bool> sg_pos
00275         = _sg_table.insert(
00276         pair<MreSgKey, E*>(MreSgKey(mre->source_group()), mre));
00277     if (! sg_pos.second)
00278         return (NULL);
00279     pair<gs_iterator, bool> gs_pos
00280         = _gs_table.insert(
00281         pair<MreGsKey, E*>(MreGsKey(mre->source_group()), mre));
00282     if (! gs_pos.second) {
00283         _sg_table.erase(sg_pos.first);
00284         return (NULL);
00285     }
00286     mre->_sg_key = sg_pos.first;
00287     mre->_gs_key = gs_pos.first;
00288     
00289     return (mre);
00290     }
00291     
00301     int remove(E *mre) {
00302     int ret_value = XORP_ERROR;
00303     
00304     if (mre->_sg_key != _sg_table.end()) {
00305         _sg_table.erase(mre->_sg_key);
00306         mre->_sg_key = _sg_table.end();
00307         ret_value = XORP_OK;
00308     }
00309     if (mre->_gs_key != _gs_table.end()) {
00310         _gs_table.erase(mre->_gs_key);
00311         mre->_gs_key = _gs_table.end();
00312         ret_value = XORP_OK;
00313     }
00314     
00315     return (ret_value);
00316     }
00317     
00326     E *find(const IPvX& source_addr, const IPvX& group_addr) const {
00327     const_sg_iterator pos = _sg_table.find(
00328         MreSgKey(SourceGroup(source_addr, group_addr)));
00329     if (pos != _sg_table.end())
00330         return (pos->second);
00331     return (NULL);
00332     }
00333     
00341     E *find_source(const IPvX& source_addr) const {
00342     const_sg_iterator pos
00343         = _sg_table.lower_bound(
00344         MreSgKey(SourceGroup(source_addr,
00345                      IPvX::ZERO(source_addr.af()) ) ) );
00346     if (pos != _sg_table.end()) {
00347         if (pos->second->source_addr() == source_addr)
00348         return (pos->second);
00349     }
00350     return (NULL);
00351     }
00352     
00360     E *find_group(const IPvX& group_addr) const {
00361     const_gs_iterator pos
00362         = _gs_table.lower_bound(
00363         MreGsKey(SourceGroup(IPvX::ZERO(group_addr.af()),
00364                      group_addr)));
00365     if (pos != _gs_table.end()) {
00366         if (pos->second->group_addr() == group_addr)
00367         return (pos->second);
00368     }
00369     return (NULL);
00370     }
00371     
00379     E *find_source_by_prefix(const IPvXNet& prefix_s) const {
00380     const_sg_iterator pos
00381         = _sg_table.lower_bound(
00382         MreSgKey(SourceGroup(prefix_s.masked_addr(),
00383                      IPvX::ZERO(prefix_s.af()) ) ) );
00384     if (pos == _sg_table.end())
00385         return (NULL);
00386     E *mre = pos->second;
00387     if (mre->is_same_prefix_s(prefix_s))
00388         return (mre);
00389     return (NULL);
00390     }
00391     
00399     E *find_group_by_prefix(const IPvXNet& prefix_g) const {
00400     const_gs_iterator pos
00401         = _gs_table.lower_bound(
00402         MreGsKey(SourceGroup(prefix_g.masked_addr(),
00403                      IPvX::ZERO(prefix_g.af()) ) ) );
00404     if (pos == _gs_table.end())
00405         return (NULL);
00406     E *mre = pos->second;
00407     if (mre->is_same_prefix_g(prefix_g))
00408         return (mre);
00409     return (NULL);
00410     }
00411     
00417     size_t  size()          const { return (_sg_table.size());  }
00418     
00424     const_sg_iterator sg_begin()    const { return (_sg_table.begin()); }
00425 
00431     const_gs_iterator gs_begin()    const { return (_gs_table.begin()); }
00432     
00438     const_sg_iterator sg_end()      const { return (_sg_table.end());   }
00439     
00445     const_gs_iterator gs_end()      const { return (_gs_table.end());   }
00446     
00456     const_sg_iterator source_by_prefix_begin(const IPvXNet& prefix_s) const {
00457     const_sg_iterator pos
00458         = _sg_table.lower_bound(
00459         MreSgKey(SourceGroup(prefix_s.masked_addr(),
00460                      IPvX::ZERO(prefix_s.af()) ) ) );
00461     return (pos);
00462     }
00463     
00473     const_sg_iterator source_by_prefix_end(const IPvXNet& prefix_s) const {
00474     if (prefix_s.prefix_len() == 0)
00475         return (_sg_table.end());       // XXX: special case
00476     
00477     IPvXNet next_prefix_s(prefix_s);
00478     ++next_prefix_s;
00479     if (next_prefix_s.masked_addr().is_zero())
00480         return (_sg_table.end());       // XXX: special case
00481     
00482     const_sg_iterator pos
00483         = _sg_table.lower_bound(
00484         MreSgKey(SourceGroup(next_prefix_s.masked_addr(),
00485                      IPvX::ZERO(next_prefix_s.af()) ) ) );
00486     return (pos);
00487     }
00488     
00498     const_gs_iterator group_by_prefix_begin(const IPvXNet& prefix_g) const {
00499     const_gs_iterator pos
00500         = _gs_table.lower_bound(
00501         MreGsKey(SourceGroup(IPvX::ZERO(prefix_g.af()),
00502                      prefix_g.masked_addr() ) ) );
00503     return (pos);
00504     }
00505     
00515     const_gs_iterator group_by_prefix_end(const IPvXNet& prefix_g) const {
00516     if (prefix_g.prefix_len() == 0)
00517         return (_gs_table.end());       // XXX: special case
00518     
00519     IPvXNet next_prefix_g(prefix_g);
00520     ++next_prefix_g;
00521     if (next_prefix_g.masked_addr().is_zero())
00522         return (_gs_table.end());       // XXX: special case
00523     
00524     const_gs_iterator pos
00525         = _gs_table.lower_bound(
00526         MreGsKey(SourceGroup(IPvX::ZERO(next_prefix_g.af()),
00527                      next_prefix_g.masked_addr() ) ) );
00528     return (pos);
00529     }
00530     
00540     const_sg_iterator source_by_addr_begin(const IPvX& source_addr) const {
00541     const_sg_iterator pos
00542         = _sg_table.lower_bound(
00543         MreSgKey(SourceGroup(source_addr,
00544                      IPvX::ZERO(source_addr.af()) ) ) );
00545     return (pos);
00546     }
00547     
00557     const_sg_iterator source_by_addr_end(const IPvX& source_addr) const {
00558     if (source_addr == IPvX::ALL_ONES(source_addr.af()))
00559         return (_sg_table.end());       // XXX: special case
00560     
00561     IPvX next_source_addr(source_addr);
00562     ++next_source_addr;
00563     
00564     const_sg_iterator pos
00565         = _sg_table.lower_bound(
00566         MreSgKey(SourceGroup(next_source_addr,
00567                      IPvX::ZERO(next_source_addr.af()) ) ) );
00568     return (pos);
00569     }
00570     
00580     const_gs_iterator group_by_addr_begin(const IPvX& group_addr) const {
00581     const_gs_iterator pos
00582         = _gs_table.lower_bound(
00583         MreGsKey(SourceGroup(IPvX::ZERO(group_addr.af()),
00584                      group_addr ) ) );
00585     return (pos);
00586     }
00587     
00597     const_gs_iterator group_by_addr_end(const IPvX& group_addr) const {
00598     if (group_addr == IPvX::ALL_ONES(group_addr.af()))
00599         return (_gs_table.end());       // XXX: special case
00600     
00601     IPvX next_group_addr(group_addr);
00602     ++next_group_addr;
00603     
00604     const_gs_iterator pos
00605         = _gs_table.lower_bound(
00606         MreGsKey(SourceGroup(IPvX::ZERO(next_group_addr.af()),
00607                      next_group_addr ) ) );
00608     return (pos);
00609     }
00610     
00621     const_gs_iterator group_source_by_addr_begin(
00622     const IPvX& source_addr,
00623     const IPvX& group_addr) const {
00624     const_gs_iterator pos
00625         = _gs_table.lower_bound(
00626         MreGsKey(SourceGroup(source_addr,
00627                      group_addr ) ) );
00628     return (pos);
00629     }
00630     
00641     const_sg_iterator source_group_by_addr_begin(
00642     const IPvX& source_addr,
00643     const IPvX& group_addr) const {
00644     const_sg_iterator pos
00645         = _sg_table.lower_bound(
00646         MreSgKey(SourceGroup(source_addr,
00647                      group_addr ) ) );
00648     return (pos);
00649     }
00650     
00651 private:
00652     SgMap _sg_table;        // The (S,G) source-first lookup table
00653     GsMap _gs_table;        // The (G,S) group-first lookup table
00654 };
00655 
00659 template <class E>
00660 class Mre {
00661 public:
00668     Mre(const IPvX& source_addr, const IPvX& group_addr)
00669     : _source_group(source_addr, group_addr) {
00670     //
00671     // XXX: the iterators below should be set to
00672     // _sg_table.end() and _gs_table.end() in the Mrt, but here
00673     // we don't know those values. Sigh...
00674     //
00675     memset(&_sg_key, 0, sizeof(_sg_key));
00676     memset(&_gs_key, 0, sizeof(_gs_key));
00677     }
00678     
00682     virtual ~Mre() {};
00683     
00689     const SourceGroup& source_group() const { return (_source_group); }
00690     
00696     const IPvX& source_addr() const { return (_source_group.source_addr()); }
00697     
00703     const IPvX& group_addr() const { return (_source_group.group_addr()); }
00704     
00712     bool    is_same_prefix_s(const IPvXNet& prefix_s) const {
00713     return (prefix_s.contains(source_addr()));
00714     }
00715     
00723     bool    is_same_prefix_g(const IPvXNet& prefix_g) const {
00724     return (prefix_g.contains(group_addr()));
00725     }
00726     
00732     const typename Mrt<E>::sg_iterator& sg_key() const { return (_sg_key); }
00733     
00739     const typename Mrt<E>::gs_iterator& gs_key() const { return (_gs_key); }
00740 
00747     string  str() const {
00748     return (string("(") + source_addr().str()
00749         + string(", ") + group_addr().str()
00750         + string(")"));
00751     }
00752     
00753 protected:
00754     friend class Mrt<E>;
00755     
00756 private:
00757     // Mre state
00758     const SourceGroup _source_group;    // The source and group addresses
00759     typename Mrt<E>::sg_iterator _sg_key; // The source-group table iterator
00760     typename Mrt<E>::gs_iterator _gs_key; // The group-source table iterator
00761 };
00762 
00763 //
00764 // Deferred definitions
00765 //
00766 
00767 //
00768 // Global variables
00769 //
00770 
00771 //
00772 // Global functions prototypes
00773 //
00774 
00775 #endif // __MRT_MRT_HH__
 All Classes Namespaces Functions Variables Typedefs Enumerations