This template class provides an associative container keyed by IPv4 addresses, with longest-match searching. More...

#include <DwmIpv4Routes.hh>

Inheritance diagram for Dwm::Ipv4Routes< _valueT >:

[legend]

Collaboration diagram for Dwm::Ipv4Routes< _valueT >:

[legend]

Public Types
typedef std::unordered_map< Ipv4Address, _valueT, OurIpv4AddressHash >	_RepSubType

typedef _RepSubType::const_iterator	const_iterator

Public Member Functions
	Ipv4Routes ()
	Constructor.

void	Clear ()
	Clears all entries.

bool	Empty () const
	Returns true if there are no entries.

bool	Add (const Ipv4Prefix &prefix, const _valueT &value)
	Adds an entry. More...

_valueT &	operator[] (const Ipv4Prefix &prefix)
	operator [] works like you would expect from an STL map.

bool	Delete (const Ipv4Prefix &prefix)
	Deletes the entry for `prefix`. More...

bool	Find (const Ipv4Prefix &prefix, _valueT &match) const
	Find the entry for the given `prefix`. More...

bool	FindLongest (const Ipv4Address &ipAddr, std::pair< Ipv4Prefix, _valueT > &match) const
	Finds the longest match for `ipAddr`. More...

bool	FindLongest (const Ipv4Address &ipAddr, std::pair< Ipv4Prefix, const _valueT *> &match) const
	Finds the longest match for `ipAddr`. More...

bool	Find (const Ipv4Address &ipAddr, std::vector< std::pair< Ipv4Prefix, _valueT > > &matches) const
	Finds all matches for `ipAddr`. More...

void	MaxLoadFactor (float loadFactor)

bool	operator== (const Ipv4Routes< _valueT > &r) const
	operator == It's unlikely you'd ever need to use this, and it's expensive. More...

bool	operator!= (const Ipv4Routes< _valueT > &r) const
	operator != It's unlikely you'd ever need to use this, and it's expensive. More...

uint32_t	Size () const
	Returns the number of routes.

void	HashSizes (std::vector< std::pair< uint8_t, uint32_t > > &sizes) const

uint32_t	StreamedLength () const
	Returns the number of bytes that should be written if one of the Write() members is called. More...

std::istream &	Read (std::istream &is)
	Reads the routes from an istream. Returns the istream.

std::ostream &	Write (std::ostream &os) const
	Writes the routes to an ostream. Returns the ostream.

size_t	Read (FILE *f)
	Reades the routes from a FILE pointer. More...

size_t	Write (FILE *f) const
	Writes the routes to a FILE pointer. More...

ssize_t	Read (int fd)
	Reads the routes from a file descriptor. More...

ssize_t	Write (int fd) const
	Writes the routes to a file descriptor. More...

int	Read (gzFile gzf)
	Reads the routes from a gzFile. More...

int	Write (gzFile gzf) const
	Writes the routes to a gzFile. More...

int	BZRead (BZFILE *bzf)
	Reads the routes from a BZFILE pointer. More...

int	BZWrite (BZFILE *bzf) const
	Writes the routes to a BZFILE pointer. More...

void	SortByKey (std::vector< std::pair< Ipv4Prefix, _valueT >> &target, bool ascending=true) const

void	SortByValue (std::vector< std::pair< Ipv4Prefix, _valueT > > &target)
	Sorts the contained pair<Ipv4Prefix,_valueT> values into a vector, in descending order by the value stored for each prefix. More...

uint32_t	AddressesCovered () const
	Returns the number of addresses covered by the contained prefixes, not including 0/0. More...

Public Member Functions inherited from Dwm::Readable
virtual	~Readable ()
	destructor

Public Member Functions inherited from Dwm::Writable
virtual	~Writable ()
	Destructor.

Public Member Functions inherited from Dwm::GZReadable
virtual	~GZReadable ()
	destructor

Public Member Functions inherited from Dwm::GZWritable
virtual	~GZWritable ()
	destructor

Protected Attributes
std::vector< _RepSubType >	_hashMaps

Detailed Description

template<typename _valueT>
class Dwm::Ipv4Routes< _valueT >

This template class provides an associative container keyed by IPv4 addresses, with longest-match searching.

While this isn't as speedy to search as Patricia or radix, it is based on STL containers and is hence easy to understand and maintain (note how few lines of actual code are here).

I/O functionality is provided, but the real work there is done in the Dwm::IO class.

Performance

I tested this class with a global IPv4 routing table from October 7, 2005. It contained 178,567 unique prefixes. The code was compiled with 'g++ -O2 ...' and run on a Xeon 2.8GHz host running FreeBSD 5.3. Each test looked up one address from each of the 178,567 prefixes, and was run 10 times.

FindLongest(const Ipv4Address &, std::pair<Ipv4Prefix,_valueT> &)

yielded 830,000 lookups/sec with an Ipv4Routes<uint32_t>. Since this member copies into the value in the passed-in pair reference using operator =, it will be slower with larger _valueT types.

FindLongest(const Ipv4Address &, std::pair<Ipv4Prefix,_valueT *> &)

yielded 1,040,000 lookups/sec with an Ipv4Routes<string>. It makes sense to use this with larger _valueT types. I've no idea why it is faster than the previous FindLongest() function that copies by value; it should be just as cheap to copy a uint32_t as it is to copy a pointer.

In October 2007 I switched to using <unordered_map> for the internal containers. I set the max_load_factor to .15 and get 1,168,000 lookups/sec for Ipv4Routes<uint32_t> when calling FindLongest(const Ipv4Address &, std::pair<Ipv4Prefix,_valueT> &) and 1,489,081 lookups/sec with Ipv4Routes<string> when calling FindLongest(const Ipv4Address &, std::pair<Ipv4Prefix,_valueT *> &)

Member Function Documentation

◆ Add()

template<typename _valueT>

bool Dwm::Ipv4Routes< _valueT >::Add	(	const Ipv4Prefix &	prefix,
		const _valueT &	value
	)

inline

Adds an entry.

Returns false (and does nothing) if there was already an entry present for prefix.

Here is the call graph for this function:

◆ AddressesCovered()

template<typename _valueT>

uint32_t Dwm::Ipv4Routes< _valueT >::AddressesCovered ( ) const

inline

Returns the number of addresses covered by the contained prefixes, not including 0/0.

Here is the call graph for this function:

◆ BZRead()

template<typename _valueT>

int Dwm::Ipv4Routes< _valueT >::BZRead ( BZFILE * bzf )

inlinevirtual

Reads the routes from a BZFILE pointer.

Returns the number of bytes read on success, -1 on failure.

Implements Dwm::BZ2Readable.

Here is the call graph for this function:

◆ BZWrite()

template<typename _valueT>

int Dwm::Ipv4Routes< _valueT >::BZWrite ( BZFILE * bzf ) const

inlinevirtual

Writes the routes to a BZFILE pointer.

Returns the number of bytes written on success, -1 on failure.

Implements Dwm::BZ2Writable.

Here is the call graph for this function:

◆ Delete()

template<typename _valueT>

bool Dwm::Ipv4Routes< _valueT >::Delete ( const Ipv4Prefix & prefix )

inline

Deletes the entry for prefix.

Returns true on success, false if an entry wasn't found for prefix.

Here is the call graph for this function:

◆ Find() [1/2]

template<typename _valueT>

bool Dwm::Ipv4Routes< _valueT >::Find	(	const Ipv4Prefix &	prefix,
		_valueT &	match
	)		const

inline

Find the entry for the given prefix.

If an entry is found, the value is stored in match and true is returned. Else false is returned.

Here is the call graph for this function:

◆ Find() [2/2]

template<typename _valueT>

bool Dwm::Ipv4Routes< _valueT >::Find	(	const Ipv4Address &	ipAddr,
		std::vector< std::pair< Ipv4Prefix, _valueT > > &	matches
	)		const

inline

Finds all matches for ipAddr.

Places the results in matches (in longest-match-first order) and returns true if any matches were found. Returns false if no matches were found.

Here is the call graph for this function:

◆ FindLongest() [1/2]

template<typename _valueT>

bool Dwm::Ipv4Routes< _valueT >::FindLongest	(	const Ipv4Address &	ipAddr,
		std::pair< Ipv4Prefix, _valueT > &	match
	)		const

inline

Finds the longest match for ipAddr.

Places the result in match and returns true on success. Returns false if no match was found for ipAddr.

Here is the call graph for this function:

◆ FindLongest() [2/2]

template<typename _valueT>

bool Dwm::Ipv4Routes< _valueT >::FindLongest	(	const Ipv4Address &	ipAddr,
		std::pair< Ipv4Prefix, const _valueT *> &	match
	)		const

inline

Finds the longest match for ipAddr.

Places the result in match and returns true on success. Returns false if no match was found for ipAddr. Note that match.second is a pointer to const for the value stored under the prefix. That means you need to be careful using this member; don't call free() or delete() on match.second.

Here is the call graph for this function:

◆ operator!=()

template<typename _valueT>

bool Dwm::Ipv4Routes< _valueT >::operator!= ( const Ipv4Routes< _valueT > & r ) const

inline

operator != It's unlikely you'd ever need to use this, and it's expensive.

It's mainly here for unit testing.

◆ operator==()

template<typename _valueT>

bool Dwm::Ipv4Routes< _valueT >::operator== ( const Ipv4Routes< _valueT > & r ) const

inline

operator == It's unlikely you'd ever need to use this, and it's expensive.

It's mainly here for unit testing.

◆ Read() [1/3]

template<typename _valueT>

size_t Dwm::Ipv4Routes< _valueT >::Read ( FILE * f )

inlinevirtual

Reades the routes from a FILE pointer.

Returns 1 on success, 0 on failure.

Implements Dwm::Readable.

Here is the call graph for this function:

◆ Read() [2/3]

template<typename _valueT>

ssize_t Dwm::Ipv4Routes< _valueT >::Read ( int fd )

inlinevirtual

Reads the routes from a file descriptor.

Returns the number of bytes read on success, -1 on failure.

Implements Dwm::Readable.

Here is the call graph for this function:

◆ Read() [3/3]

template<typename _valueT>

int Dwm::Ipv4Routes< _valueT >::Read ( gzFile gzf )

inlinevirtual

Reads the routes from a gzFile.

Returns the number of bytes read on success, -1 on failure.

Implements Dwm::GZReadable.

Here is the call graph for this function:

◆ SortByValue()

template<typename _valueT>

void Dwm::Ipv4Routes< _valueT >::SortByValue ( std::vector< std::pair< Ipv4Prefix, _valueT > > & target )

inline

Sorts the contained pair<Ipv4Prefix,_valueT> values into a vector, in descending order by the value stored for each prefix.

For example, if you had an Ipv4Routes<uint32_t> object, target would contain the pair<Ipv4Prefix,_valueT> objects sorted in descending order by the uint32_t values.

◆ StreamedLength()

template<typename _valueT>

uint32_t Dwm::Ipv4Routes< _valueT >::StreamedLength ( ) const

inlinevirtual

Returns the number of bytes that should be written if one of the Write() members is called.

Implements Dwm::Writable.

Here is the call graph for this function:

◆ Write() [1/3]

template<typename _valueT>

size_t Dwm::Ipv4Routes< _valueT >::Write ( FILE * f ) const

inlinevirtual

Writes the routes to a FILE pointer.

Returns 1 on success, 0 on failure.

Implements Dwm::Writable.

Here is the call graph for this function:

◆ Write() [2/3]

template<typename _valueT>

ssize_t Dwm::Ipv4Routes< _valueT >::Write ( int fd ) const

inlinevirtual

Writes the routes to a file descriptor.

Returns the number of bytes written on success, -1 on failure.

Implements Dwm::Writable.

Here is the call graph for this function:

◆ Write() [3/3]

template<typename _valueT>

int Dwm::Ipv4Routes< _valueT >::Write ( gzFile gzf ) const

inlinevirtual

Writes the routes to a gzFile.

Returns the number of bytes written on success, -1 on failure.

Implements Dwm::GZWritable.

Here is the call graph for this function:

The documentation for this class was generated from the following file:

DwmIpv4Routes.hh

Public Types

Public Member Functions

Protected Attributes

Detailed Description

template<typename _valueT> class Dwm::Ipv4Routes< _valueT >

Performance

Member Function Documentation

◆ Add()

◆ AddressesCovered()

◆ BZRead()

◆ BZWrite()

◆ Delete()

◆ Find() [1/2]

◆ Find() [2/2]

◆ FindLongest() [1/2]

◆ FindLongest() [2/2]

◆ operator!=()

◆ operator==()

◆ Read() [1/3]

◆ Read() [2/3]

◆ Read() [3/3]

◆ SortByValue()

◆ StreamedLength()

◆ Write() [1/3]

◆ Write() [2/3]

◆ Write() [3/3]

template<typename _valueT>
class Dwm::Ipv4Routes< _valueT >