DwmIpv4Routes.hh

Go to the documentation of this file.

//===========================================================================
// @(#) $DwmPath: dwm/libDwm/tags/libDwm-0.6.0/include/DwmIpv4Routes.hh 8955 $
// @(#) $Id: DwmIpv4Routes.hh 8955 2017-04-02 08:21:20Z dwm $
//===========================================================================
//  Copyright (c) Daniel W. McRobb 1999-2005, 2016
//  All rights reserved.
//
//  Redistribution and use in source and binary forms, with or without
//  modification, are permitted provided that the following conditions
//  are met:
//
//  1. Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
//  2. Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//  3. The names of the authors and copyright holders may not be used to
//    endorse or promote products derived from this software without
//    specific prior written permission.
//
//  IN NO EVENT SHALL DANIEL W. MCROBB BE LIABLE TO ANY PARTY FOR
//  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES,
//  INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE,
//  EVEN IF DANIEL W. MCROBB HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
//  DAMAGE.
//
//  THE SOFTWARE PROVIDED HEREIN IS ON AN "AS IS" BASIS, AND
//  DANIEL W. MCROBB HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT,
//  UPDATES, ENHANCEMENTS, OR MODIFICATIONS. DANIEL W. MCROBB MAKES NO
//  REPRESENTATIONS AND EXTENDS NO WARRANTIES OF ANY KIND, EITHER
//  IMPLIED OR EXPRESS, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
//  WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE,
//  OR THAT THE USE OF THIS SOFTWARE WILL NOT INFRINGE ANY PATENT,
//  TRADEMARK OR OTHER RIGHTS.
//===========================================================================

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

#ifndef _DWMIPV4ROUTES_HH_
#define _DWMIPV4ROUTES_HH_

extern "C" {
#include <assert.h>
}

#include <algorithm>
#include <unordered_map>
#include <vector>

#include "DwmPortability.hh"
#include "DwmIO.hh"
#include "DwmGZIO.hh"
#include "DwmBZ2IO.hh"
#include "DwmIpv4Prefix.hh"
#include "DwmOperators.hh"
#include "DwmReadable.hh"
#include "DwmWritable.hh"
#include "DwmGZReadable.hh"
#include "DwmGZWritable.hh"
#include "DwmBZ2Readable.hh"
#include "DwmBZ2Writable.hh"

namespace Dwm {
  struct OurIpv4AddressHash
  {
    inline size_t operator () (const Dwm::Ipv4Address & addr) const
    {
      return(addr.Raw());
    }
  };
}  // namespace Dwm

namespace Dwm {

  //--------------------------------------------------------------------------
  //--------------------------------------------------------------------------
  template <typename _valueT>
  class Ipv4Routes
    : public Readable, public Writable, 
      public GZReadable, public GZWritable,
      public BZ2Readable, public BZ2Writable
  {
  public:
    typedef std::unordered_map<Ipv4Address, _valueT, 
                               OurIpv4AddressHash> _RepSubType;
    typedef typename _RepSubType::const_iterator  const_iterator;

    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    Ipv4Routes<_valueT>()
    : _hashMaps(33)
    {
      for (uint8_t i = 0; i < 33; ++i) {
        _hashMaps[i].max_load_factor(.08);
      }
    }

    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    void Clear()
    {
      for (uint8_t i = 0; i < 33; ++i)
        _hashMaps[i].clear();
      return;
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    bool Empty() const
    {
      bool  rc = true;
      for (uint8_t i = 0; i < 33; ++i) {
        if (! _hashMaps[i].empty()) {
          rc = false;
          break;
        }
      }
      return(rc);
    }

    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    bool Add(const Ipv4Prefix & prefix, const _valueT & value) 
    {
      bool  rc = false;
     
      typename _RepSubType::iterator  iter = 
        _hashMaps[prefix.MaskLength()].find(prefix.Network());
      if (iter == _hashMaps[prefix.MaskLength()].end()) {
        _hashMaps[prefix.MaskLength()][prefix.Network()] = value;
        rc = true;
      }
      return(rc);
    }

    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    _valueT & operator [] (const Ipv4Prefix & prefix)
    {
      return(_hashMaps[prefix.MaskLength()][prefix.Network()]);
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    bool Delete(const Ipv4Prefix & prefix)
    {
      bool  rc = false;
      typename _RepSubType::iterator  iter = 
        _hashMaps[prefix.MaskLength()].find(prefix.Network());
      if (iter != _hashMaps[prefix.MaskLength()].end()) {
        _hashMaps[prefix.MaskLength()].erase(iter);
        rc = true;
      }
      return(rc);
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    bool Find(const Ipv4Prefix & prefix, _valueT & match) const
    {
      bool  rc = false;
      if (! _hashMaps[prefix.MaskLength()].empty()) {
        typename _RepSubType::const_iterator  iter =
          _hashMaps[prefix.MaskLength()].find(prefix.Network());
        if (iter != _hashMaps[prefix.MaskLength()].end()) {
          match = iter->second;
          rc = true;
        }
      }
      return(rc);
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    bool FindLongest(const Ipv4Address & ipAddr,
                     std::pair<Ipv4Prefix,_valueT> & match) const
    {
      bool  rc = false;

      Ipv4Prefix   lp(ipAddr, 32);
     
      typename _RepSubType::const_iterator  iter;
      for (int8_t i = 32; i >= 0; --i) {
        if (_hashMaps[i].empty())
          continue;
        lp.MaskLength(i);
        iter = _hashMaps[i].find(lp.Network());
        if (iter != _hashMaps[i].end()) {
          match.first = lp;
          match.second = iter->second;
          rc = true;
          break;
        }
      }
      return(rc);
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    bool
    FindLongest(const Ipv4Address & ipAddr,
                std::pair<Ipv4Prefix, const _valueT *> & match) const
    {
      bool  rc = false;
      Ipv4Prefix   lp(ipAddr, 32);
      typename _RepSubType::const_iterator  iter;
      for (int8_t i = 32; i >= 0; --i) {
        if (_hashMaps[i].empty())
          continue;
        lp.MaskLength(i);
        iter = _hashMaps[i].find(lp.Network());
        if (iter != _hashMaps[i].end()) {
          match.first = lp;
          match.second = &(iter->second);
          rc = true;
          break;
        }
      }
      return(rc);
    }
        
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    bool Find(const Ipv4Address & ipAddr,
              std::vector<std::pair<Ipv4Prefix,_valueT> > & matches) const
    {
      if (! matches.empty())
        matches.clear();
     
      typename _RepSubType::const_iterator  iter;

      for (int8_t i = 32; i >= 0; --i) {
        if (_hashMaps[i].empty())
          continue;
        Ipv4Prefix  prefix(ipAddr, i);
        iter = _hashMaps[i].find(prefix.Network());
        if (iter != _hashMaps[i].end()) {
          std::pair<Ipv4Prefix,_valueT> match(prefix, iter->second);
          matches.push_back(match);
        }
      }
      return(! matches.empty());
    }

    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    void MaxLoadFactor(float loadFactor)
    {
      for (int8_t i = 32; i >= 0; --i) {
        _hashMaps[i].max_load_factor(loadFactor);
      }
      return;
    }

    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    bool operator == (const Ipv4Routes<_valueT> & r) const
    {
      for (int8_t i = 32; i >= 0; --i) {
        if (_hashMaps[i] != r._hashMaps[i])
          return(false);
      }
      return(true);
    }

    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    bool operator != (const Ipv4Routes<_valueT> & r) const
    {
      return(! (*this == r));
    }

    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    uint32_t Size() const
    {
      uint32_t  rc = 0;
      for (uint8_t i = 0; i < 33; ++i)
        rc += _hashMaps[i].size();
      return(rc);
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    void HashSizes(std::vector<std::pair<uint8_t, uint32_t> > & sizes) const
    {
      if (! sizes.empty())
        sizes.clear();
      for (uint8_t i = 0; i < 33; ++i) {
        if (! _hashMaps[i].empty()) {
          sizes.push_back(std::pair<uint8_t,uint32_t>(i,_hashMaps[i].size()));
        }
      }
      return;
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    uint32_t StreamedLength() const
    {
      return(IO::StreamedLength(_hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    std::istream & Read(std::istream & is)
    {
      return(IO::Read(is, _hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    std::ostream & Write(std::ostream & os) const
    {
      return(IO::Write(os, _hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    size_t Read(FILE *f)
    {
      return(IO::Read(f, _hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    size_t Write(FILE *f) const
    {
      return(IO::Write(f, _hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    ssize_t Read(int fd)
    {
      return(IO::Read(fd, _hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    ssize_t Write(int fd) const
    {
      return(IO::Write(fd, _hashMaps));
    }

    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    int Read(gzFile gzf)
    {
      return(GZIO::Read(gzf, _hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    int Write(gzFile gzf) const
    {
      return(GZIO::Write(gzf, _hashMaps));
    }

    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    int BZRead(BZFILE *bzf)
    {
      return(BZ2IO::BZRead(bzf, _hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    int BZWrite(BZFILE *bzf) const
    {
      return(BZ2IO::BZWrite(bzf, _hashMaps));
    }

    void SortByKey(std::vector<std::pair<Ipv4Prefix,_valueT>> & target,
                   bool ascending = true) const
    {
      if (! target.empty())
        target.clear();
      if (! this->_hashMaps.empty()) {
        target.resize(this->Size());
        typename std::vector<_RepSubType>::const_iterator  iter = 
          this->_hashMaps.begin();
        uint32_t  pfx = 0;
        for (uint8_t hashNum = 0; hashNum < 33; ++hashNum) {
          if (! this->_hashMaps[hashNum].empty()) {
            typename _RepSubType::const_iterator  hiter = 
              this->_hashMaps[hashNum].begin();
            for ( ; hiter != iter->end(); ++hiter) {
              target[pfx].first = Ipv4Prefix(hiter->first, hashNum);
              target[pfx].second = hiter->second;
              ++pfx;
            }
          }
        }
        if (! target.empty()) {
          if (ascending) {
            std::sort(target.begin(), target.end(), KeyLess());
          }
          else {
            std::sort(target.begin(), target.end(), KeyGreater());
          }
        }
      }
     
      return;
    }
      
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    void SortByValue(std::vector<std::pair<Ipv4Prefix,_valueT> > & target)
    {
      if (! target.empty())
        target.clear();
      if (! this->_hashMaps.empty()) {
        target.resize(this->Size());
        typename std::vector<_RepSubType>::const_iterator  iter = 
          this->_hashMaps.begin();
        uint32_t  pfx = 0;
        for (uint8_t hashNum = 0; hashNum < 33; ++hashNum) {
          if (! this->_hashMaps[hashNum].empty()) {
            typename _RepSubType::const_iterator  hiter = 
              this->_hashMaps[hashNum].begin();
            for ( ; hiter != iter->end(); ++hiter) {
              target[pfx].first = Ipv4Prefix(hiter->first, hashNum);
              target[pfx].second = hiter->second;
              ++pfx;
            }
          }
        }
        if (! target.empty())
          std::sort(target.begin(), target.end(), ValueGreater());
      }
     
      return;
    }

    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    uint32_t AddressesCovered() const
    {
      uint32_t  rc = 0;
      for (int8_t hashNum = 32; hashNum > 1; --hashNum) {
        typename _RepSubType::const_iterator  hiter =
          _hashMaps[hashNum].begin();
        for ( ; hiter != _hashMaps[hashNum].end(); ++hiter) {
          bool  foundWider = false;
          for (int8_t widerHash = hashNum - 1; widerHash > 0; --widerHash) {
            Ipv4Prefix  widerPfx(hiter->first, widerHash);
            if (_hashMaps[widerHash].find(widerPfx.Network())
                != _hashMaps[widerHash].end()) {
              //  found wider match, don't count
              foundWider = true;
              break;
            }
          }
          if (! foundWider) {
            rc += ((uint32_t)1 << (32 - hashNum));
          }
        }
      }
      return rc;
    }
    
    struct KeyGreater
    {
    public:
      bool operator () (const std::pair<Ipv4Prefix,_valueT> & e1,
                        const std::pair<Ipv4Prefix,_valueT> & e2) const
      {
        return(e1.first > e2.first);
      }
    };

    struct KeyLess
    {
    public:
      bool operator () (const std::pair<Ipv4Prefix,_valueT> & e1,
                        const std::pair<Ipv4Prefix,_valueT> & e2) const
      {
        return(e1.first < e2.first);
      }
    };
    
    struct ValueGreater
    {
    public:
      bool operator () (const std::pair<Ipv4Prefix,_valueT> & e1,
                        const std::pair<Ipv4Prefix,_valueT> & e2) const
      {
        return(e1.second > e2.second);
      }
    };
    
    
  protected:
    std::vector<_RepSubType>   _hashMaps;
  };
  
  
}  // namespace Dwm

#endif  // _DWMIPV4ROUTES_HH_

//---------------------------- emacs settings -----------------------------
//  Local Variables:
//  mode: C++/la
//  tab-width: 2
//  indent-tabs-mode: nil
//  c-basic-offset: 2
//  End:
//-------------------------------------------------------------------------