DwmIpv4Routes.hh

Go to the documentation of this file.

//===========================================================================
// @(#) $DwmPath$
//===========================================================================
//  Copyright (c) Daniel W. McRobb 1999-2005, 2016, 2024
//  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_
 
#include <algorithm>
#include <cassert>
#include <future>
#include <unordered_map>
 
#include "DwmPortability.hh"
#include "DwmBZ2IO.hh"
#include "DwmDescriptorIO.hh"
#include "DwmFileIO.hh"
#include "DwmGZIO.hh"
#include "DwmIOUtils.hh"
#include "DwmStreamIO.hh"
#include "DwmIpv4Prefix.hh"
#include "DwmOperators.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:
    typedef std::unordered_map<Ipv4Address, _valueT, 
                               OurIpv4AddressHash> _RepSubType;
    typedef typename _RepSubType::const_iterator  const_iterator;
 
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    Ipv4Routes()
    : _hashMaps()
    {
      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);
    }
 
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    void Add(const Ipv4Routes<_valueT> & routes)
    {
      for (uint8_t i = 0; i < 33; ++i) {
        if (! routes._hashMaps[i].empty()) {
          for (const auto & entry : routes._hashMaps[i]) {
            _hashMaps[i][entry.first] = entry.second;
          }
        }
      }
      return;
    }
          
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    _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);
    }
 
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    void FindInSubMap(const _RepSubType & subMap, Ipv4Address ipAddr,
                      std::pair<bool,_valueT> & result) const
    {
      auto  iter = subMap.find(ipAddr);
      if (iter != subMap.end()) {
        result.first = true;
        result.second = iter->second;
      }
      return;
    }
 
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    bool NewFindLongest(const Ipv4Address & ipAddr,
                        std::pair<Ipv4Prefix,_valueT> & match) const
    {
      using std::map, std::pair, std::thread;
      bool  rc = false;
      map<uint8_t,pair<bool,_valueT>>  results;
      std::map<uint8_t,thread>         threads;
      for (int i = 32; i >= 0; --i) {
        if (! _hashMaps[i].empty()) {
          results[i] = {false,_valueT()};
          Ipv4Prefix  pfx(ipAddr, i);
          threads[i] = thread(&Ipv4Routes::FindInSubMap, this,
                              std::ref(_hashMaps[i]), pfx.Network(),
                              std::ref(results[i]));
        }
      }
      for (auto it = threads.rbegin(); it != threads.rend(); ++it) {
        it->second.join();
        if (results[it->first].first) {
          rc = true;
          match.first = Ipv4Prefix(ipAddr, it->first);
          match.second = results[it->first].second;
        }
      }
      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;
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    uint64_t StreamedLength() const
    {
      return(IOUtils::StreamedLength(_hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    std::istream & Read(std::istream & is)
    {
      return(StreamIO::Read(is, _hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    std::ostream & Write(std::ostream & os) const
    {
      return(StreamIO::Write(os, _hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    size_t Read(FILE *f)
    {
      return(FileIO::Read(f, _hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    size_t Write(FILE *f) const
    {
      return(FileIO::Write(f, _hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    ssize_t Read(int fd)
    {
      return(DescriptorIO::Read(fd, _hashMaps));
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    ssize_t Write(int fd) const
    {
      return(DescriptorIO::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));
    }
 
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    template <typename BinaryPredicate>
    void Coalesce(BinaryPredicate pred)
    {
      //  Combine adjacents.
      for (uint8_t maskLen = 32; maskLen > 0; --maskLen) {
        auto & hm = this->_hashMaps[maskLen];
        auto hmi = hm.begin();
        while (hmi != hm.end()) {
          bool        erased = false;
          Ipv4Prefix  pfx(hmi->first, maskLen);
          Ipv4Prefix  nextpfx = pfx;
          ++nextpfx;
          std::pair<bool,Ipv4Prefix>  combpfx = pfx.Combine(nextpfx);
          if (combpfx.first) {
            auto  nextit = hm.find(nextpfx.Network());
            if (nextit != hm.end()) {
              if (pred(hmi->second, nextit->second)) {
                hm.erase(nextit);
                _hashMaps[maskLen-1][combpfx.second.Network()] = hmi->second;
                hmi = hm.erase(hmi);
                erased = true;
              }
            }
          }
          if (! erased) {
            ++hmi;
          }
        }
      }
      //  Remove entries that are covered by matching entry with wider
      //  netmask.
      for (uint8_t maskLen = 32; maskLen > 0; --maskLen) {
        auto & hm = this->_hashMaps[maskLen];
        auto   hmi = hm.begin();
        while (hmi != hm.end()) {
          if (HaveWiderMatch(hmi->first, maskLen, hmi->second, pred)) {
            hmi = hm.erase(hmi);
          }
          else {
            ++hmi;
          }
        }
      }
      return;
    }
 
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    void Coalesce()
    {
      return Coalesce(std::equal_to<_valueT>());
    }
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    void GetAllKeys(std::vector<Ipv4Prefix> & keys) const
    {
      keys.resize(this->Size());
      if (! keys.empty()) {
        uint32_t  pfx = 0;
        for (uint8_t hashNum = 0; hashNum < 33; ++hashNum) {
          for (const auto & entry : this->_hashMaps[hashNum]) {
            keys[pfx] = Ipv4Prefix(entry.first, hashNum);
            ++pfx;
          }
        }
      }
      return;
    }
          
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    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());
        auto  iter = this->_hashMaps.begin();
        uint32_t  pfx = 0;
        for (uint8_t hashNum = 0; hashNum < 33; ++hashNum) {
          if (! this->_hashMaps[hashNum].empty()) {
            auto  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());
        auto iter = this->_hashMaps.begin();
        uint32_t  pfx = 0;
        for (uint8_t hashNum = 0; hashNum < 33; ++hashNum) {
          if (! this->_hashMaps[hashNum].empty()) {
            auto 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(),
                    [] (const auto & e1, const auto & e2)
                    { return (e1.second > e2.second); });
      }
     
      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);
      }
    };
 
#if 0
    struct ValueGreater
    {
    public:
      bool operator () (const std::pair<Ipv4Prefix,_valueT> & e1,
                        const std::pair<Ipv4Prefix,_valueT> & e2) const
      {
        return(e1.second > e2.second);
      }
    };
#endif
 
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    const std::array<_RepSubType,33> & HashMaps() const
    {
      return _hashMaps;
    }
    
  protected:
    std::array<_RepSubType,33>   _hashMaps;
 
    template <typename BinaryPredicate>
    bool HaveWiderMatch(const Ipv4Address & addr, uint8_t maskLen,
                        const _valueT & val, BinaryPredicate pred) const
    {
      bool  rc = false;
      if (maskLen > 0) {
        for (int8_t wml = maskLen - 1; wml > 0; --wml) {
          Ipv4Prefix  pfx(addr, wml);
          auto  iter = _hashMaps[wml].find(pfx.Network());
          if (iter != _hashMaps[wml].end()) {
            if (pred(iter->second, val)) {
              rc = true;
              break;
            }
          }
        }
      }
      return rc;
    }
    
  };
  
  
}  // namespace Dwm
 
#endif  // _DWMIPV4ROUTES_HH_
 
//---------------------------- emacs settings -----------------------------
//  Local Variables:
//  mode: C++
//  tab-width: 2
//  indent-tabs-mode: nil
//  c-basic-offset: 2
//  End:
//-------------------------------------------------------------------------