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

#include <DwmIpv4Routes.hh>

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.

void	Add (const Ipv4Routes< _valueT > &routes)
	Bulk add all `routes`. Note this will overwrite existing routes.

_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`.

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

void	FindInSubMap (const _RepSubType &subMap, Ipv4Address ipAddr, std::pair< bool, _valueT > &result) const

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

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

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

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

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.

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

uint32_t	Size () const
	Returns the number of routes.

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

uint64_t	StreamedLength () const

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.

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

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

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

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

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

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

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

template<typename BinaryPredicate >
void	Coalesce (BinaryPredicate pred)
	Combines adjacent prefixes that can be combined (same value and prefixes can be represented by a prefix with a mask length one bit wider), then removes specific prefixes that are covered by a wider prefix with the same value.

void	Coalesce ()

void	GetAllKeys (std::vector< Ipv4Prefix > &keys) const

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.

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

const std::array< _RepSubType, 33 > &	HashMaps () const
	Returns a const reference to the contained hash maps.

Protected Member Functions
template<typename BinaryPredicate >
bool	HaveWiderMatch (const Ipv4Address &addr, uint8_t maskLen, const _valueT &val, BinaryPredicate pred) const

Protected Attributes
std::array< _RepSubType, 33 >	_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 *> &)

More current measurements in 2020 on a Threadripper 3960X: roughly 5.3 million lookups/second for Ipv4Routes<string>.

Note: I don't consider this code fast for lookups; it's a tradeoff. You can get much faster lookups with sorted instances of std::vector, but at the expense of poor average insertion and deletion (and linear in the size of each vector in the worst-case). On modern CPUs, cache-friendly containers like std::vector are a big advantage for lookups if you keep them sorted, but keeping them sorted is expensive. A quick hack using sorted std::vector and std::lower_bound yield about a 10X improvement in lookups but a severe penaly for insertions. This would be less true if the typical prefix length distribution was close to normal, but in the real world it's typically heavy-tailed with the peak between /22 and /24.

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:

◆ BZRead()

template<typename _valueT >

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

inline

Reads the routes from a BZFILE pointer.

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

Here is the call graph for this function:

◆ BZWrite()

template<typename _valueT >

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

inline

Writes the routes to a BZFILE pointer.

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

Here is the call graph for this function:

◆ Coalesce()

template<typename _valueT >

template<typename BinaryPredicate >

void Dwm::Ipv4Routes< _valueT >::Coalesce ( BinaryPredicate pred )

inline

Combines adjacent prefixes that can be combined (same value and prefixes can be represented by a prefix with a mask length one bit wider), then removes specific prefixes that are covered by a wider prefix with the same value.

While we accept a predicate used to compare the two values, it only makes sense to use std::equal_to<_valueT>() or an equivalent since we make no guarantee of which of the two values we will use in the combined entry.

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 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:

◆ Find() [2/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:

◆ 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 )

inline

Reades the routes from a FILE pointer.

Returns 1 on success, 0 on failure.

Here is the call graph for this function:

◆ Read() [2/3]

template<typename _valueT >

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

inline

Reads the routes from a gzFile.

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

Here is the call graph for this function:

◆ Read() [3/3]

template<typename _valueT >

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

inline

Reads the routes from a file descriptor.

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

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.

Here is the call graph for this function:

◆ Write() [1/3]

template<typename _valueT >

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

inline

Writes the routes to a FILE pointer.

Returns 1 on success, 0 on failure.

Here is the call graph for this function:

◆ Write() [2/3]

template<typename _valueT >

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

inline

Writes the routes to a gzFile.

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

Here is the call graph for this function:

◆ Write() [3/3]

template<typename _valueT >

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

inline

Writes the routes to a file descriptor.

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

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 Member Functions

Protected Attributes

Detailed Description

Performance

Member Function Documentation

◆ Add()

◆ BZRead()

◆ BZWrite()

◆ Coalesce()

◆ 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()

◆ Write() [1/3]

◆ Write() [2/3]

◆ Write() [3/3]