DwmRDAPIpv4Routes.hh

Go to the documentation of this file.

//===========================================================================
// @(#) $DwmPath: dwm/libDwmRDAP/tags/libDwmRDAP-0.1.4/include/DwmRDAPIpv4Routes.hh 8963 $
// @(#) $Id: DwmRDAPIpv4Routes.hh 8963 2017-04-03 04:58:48Z dwm $
//===========================================================================
//  Copyright (c) Daniel W. McRobb 1999-2005, 2016, 2017
//  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 _DWMRDAPIPV4ROUTES_HH_
#define _DWMRDAPIPV4ROUTES_HH_

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

#include <algorithm>
#include <unordered_map>
#include <shared_mutex>
#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 {

  namespace RDAP {
    
    //------------------------------------------------------------------------
    //------------------------------------------------------------------------
    template <typename _valueT>
    class Ipv4Routes
      : public Readable, public Writable, 
        public GZReadable, public GZWritable,
        public BZ2Readable, public BZ2Writable
    {
    public:
      typedef std::map<Ipv4Address, _valueT>        _RepSubType;
      typedef typename _RepSubType::const_iterator  const_iterator;
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      Ipv4Routes<_valueT>()
          : _maps(33)
      {
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      void Clear()
      {
        std::shared_lock<std::shared_mutex>  lock(_mtx);
        for (uint8_t i = 0; i < 33; ++i)
          _maps[i].clear();
        return;
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      bool Empty() const
      {
        bool  rc = true;
        std::shared_lock<std::shared_mutex>  lock(_mtx);
        for (uint8_t i = 0; i < 33; ++i) {
          if (! _maps[i].empty()) {
            rc = false;
            break;
          }
        }
        return(rc);
      }

      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      bool Add(const Ipv4Prefix & prefix, const _valueT & value) 
      {
        bool  rc = false;

        std::shared_lock<std::shared_mutex>  lock(_mtx);
        typename _RepSubType::iterator  iter = 
          _maps[prefix.MaskLength()].find(prefix.Network());
        if (iter == _maps[prefix.MaskLength()].end()) {
          _maps[prefix.MaskLength()][prefix.Network()] = value;
          rc = true;
        }
        return(rc);
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      _valueT & operator [] (const Ipv4Prefix & prefix)
      {
        std::shared_lock<std::shared_mutex>  lock(_mtx);
        return(_maps[prefix.MaskLength()][prefix.Network()]);
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      bool Delete(const Ipv4Prefix & prefix)
      {
        bool  rc = false;
        std::lock_guard<std::shared_mutex>  lock(_mtx);
        typename _RepSubType::iterator  iter = 
          _maps[prefix.MaskLength()].find(prefix.Network());
        if (iter != _maps[prefix.MaskLength()].end()) {
          _maps[prefix.MaskLength()].erase(iter);
          rc = true;
        }
        return(rc);
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      bool Find(const Ipv4Prefix & prefix, _valueT & match) const
      {
        bool  rc = false;
        std::shared_lock<std::shared_mutex>  lock(_mtx);
        if (! _maps[prefix.MaskLength()].empty()) {
          typename _RepSubType::const_iterator  iter =
            _maps[prefix.MaskLength()].find(prefix.Network());
          if (iter != _maps[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) {
          std::shared_lock<std::shared_mutex>  lock(_mtx);
          if (_maps[i].empty())
            continue;
          lp.MaskLength(i);
          iter = _maps[i].find(lp.Network());
          if (iter != _maps[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) {
          std::shared_lock<std::shared_mutex>  lock(_mtx);
          if (_maps[i].empty())
            continue;
          lp.MaskLength(i);
          iter = _maps[i].find(lp.Network());
          if (iter != _maps[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) {
          std::shared_lock<std::shared_mutex>  lock(_mtx);
          if (_maps[i].empty())
            continue;
          Ipv4Prefix  prefix(ipAddr, i);
          iter = _maps[i].find(prefix.Network());
          if (iter != _maps[i].end()) {
            std::pair<Ipv4Prefix,_valueT> match(prefix, iter->second);
            matches.push_back(match);
          }
        }
        return(! matches.empty());
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      bool operator == (const Ipv4Routes<_valueT> & r) const
      {
        for (int8_t i = 32; i >= 0; --i) {
          std::shared_lock<std::shared_mutex>  lock(_mtx);
          if (_maps[i] != r._maps[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) {
          std::shared_lock<std::shared_mutex>  lock(_mtx);
          rc += _maps[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) {
          std::shared_lock<std::shared_mutex>  lock(_mtx);
          if (! _maps[i].empty()) {
            sizes.push_back(std::pair<uint8_t,uint32_t>(i,_maps[i].size()));
          }
        }
        return;
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      uint32_t StreamedLength() const
      {
        std::shared_lock<std::shared_mutex>  lock(_mtx);
        return(IO::StreamedLength(_maps));
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      std::istream & Read(std::istream & is)
      {
        std::lock_guard<std::shared_mutex>  lock(_mtx);
        return(IO::Read(is, _maps));
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      std::ostream & Write(std::ostream & os) const
      {
        std::shared_lock<std::shared_mutex>  lock(_mtx);
        return(IO::Write(os, _maps));
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      size_t Read(FILE *f)
      {
        std::lock_guard<std::shared_mutex>  lock(_mtx);
        return(IO::Read(f, _maps));
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      size_t Write(FILE *f) const
      {
        std::shared_lock<std::shared_mutex>  lock(_mtx);
        return(IO::Write(f, _maps));
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      ssize_t Read(int fd)
      {
        std::lock_guard<std::shared_mutex>  lock(_mtx);
        return(IO::Read(fd, _maps));
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      ssize_t Write(int fd) const
      {
        std::shared_lock<std::shared_mutex>  lock(_mtx);
        return(IO::Write(fd, _maps));
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      int Read(gzFile gzf)
      {
        std::lock_guard<std::shared_mutex>  lock(_mtx);
        return(GZIO::Read(gzf, _maps));
      }
    
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      int Write(gzFile gzf) const
      {
        std::shared_lock<std::shared_mutex>  lock(_mtx);
        return(GZIO::Write(gzf, _maps));
      }

      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      int BZRead(BZFILE *bzf)
      {
        std::lock_guard<std::shared_mutex>  lock(_mtx);
        return(BZ2IO::BZRead(bzf, _maps));
      }
      
      //----------------------------------------------------------------------
      //----------------------------------------------------------------------
      int BZWrite(BZFILE *bzf) const
      {
        std::shared_lock<std::shared_mutex>  lock(_mtx);
        return(BZ2IO::BZWrite(bzf, _maps));
      }

      void SortByKey(std::vector<std::pair<Ipv4Prefix,_valueT>> & target,
                     bool ascending = true) const
      {
        if (! target.empty())
          target.clear();
        std::shared_lock<std::shared_mutex>  lock(_mtx);
        if (! this->_maps.empty()) {
          target.resize(this->Size());
          typename std::vector<_RepSubType>::const_iterator  iter = 
            this->_maps.begin();
          uint32_t  pfx = 0;
          for (uint8_t hashNum = 0; hashNum < 33; ++hashNum) {
            if (! this->_maps[hashNum].empty()) {
              typename _RepSubType::const_iterator  hiter = 
                this->_maps[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();
        std::shared_lock<std::shared_mutex>  lock(_mtx);
        if (! this->_maps.empty()) {
          target.resize(this->Size());
          typename std::vector<_RepSubType>::const_iterator  iter = 
            this->_maps.begin();
          uint32_t  pfx = 0;
          for (uint8_t hashNum = 0; hashNum < 33; ++hashNum) {
            if (! this->_maps[hashNum].empty()) {
              typename _RepSubType::const_iterator  hiter = 
                this->_maps[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 > 0; --hashNum) {
          typename _RepSubType::const_iterator  hiter =
            _maps[hashNum].begin();
          for ( ; hiter != _maps[hashNum].end(); ++hiter) {
            bool  foundWider = false;
            for (int8_t widerHash = hashNum - 1; widerHash > 0; --widerHash) {
              if (_maps[widerHash].find(Ipv4Prefix(hiter->first,widerHash).Network())
                  != _maps[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>   _maps;
      mutable std::shared_mutex  _mtx;
    };

  }  // namespace RDAP
  
}  // namespace Dwm

#endif  // _DWMRDAPIPV4ROUTES_HH_