Kai-Uwe Bux wrote:
in*************@gmail.com wrote:
>In a recent job interview, the interviewer asked me how I'd design
classes for the following problem: let's consider a hypothetical
firewall, which filters network packets by either IP address, port
number, or both. How should we design the classes to represent these
filters?
My answer was:
class FilterRule
{
public:
virtual bool Accept(const Packet&) const = 0; //Packet is a
representation of a network packet
};
class FilterByIP: public FilterRule { /* members here */ };
class FilterByPort: public FilterRule { /* members here */ };
class Filter
{
public:
bool Accept(const Packet&) const; //returns true if ALL
filterRules Accept() the Packet
private:
std::vector<FilterRulefilterRules;
};
You mean
std::vector< some_smart_pointer<FilterRule filterRules;
>>
However, the interviewer said that he preferred this solution instead:
class Filter
{
public:
virtual bool Accept(const Packet&) const = 0;
};
class FilterByIP: public Filter { /* members here */ }
class FilterByPort: public Filter { /* members here */ }
class FilterByIPAndPort: public Filter
{
protected:
FilterByIP ipFilter;
FilterByPort portFilter;
/* other members */
};
I reasoned that with his solution, there may be too many class numbers
if down the road we decide to filter packets by methods other than IP
address and Port, but somehow he was not convinced. Oh well, I didn't
get the job, but this question continues to haunt me to this day. What
do you C++ experts think? Or is there another better solution that I
did not consider? Thank you.
I like your idea of representing a filter just as a vector of filter
rules. If you want to actually reduce that to practice, you could use duck
typing instead of inheritance. E.g.:
typedef bool (sig) (Paket const &)
typedef std::tr1::function<sigFilterRule;
Now, FilterRule can hold any value that supports
bool operator() ( Paket const & )
In particular, the concrete classes could be:
class IpFilterRule {
...
public:
bool operator() ( Paket const & p ) {
}
};
class PortFilterRule {
...
public:
bool operator() ( Paket const & p ) {
}
};
and a Filter can now easily be represented as a std::vector< FilterRule >.
Note that there is no coupling between the classes. Should there be common
code, one can incorporate that into the classes using private inheritance.
It would be considered an implementation detail.
Also, the client code would use objects of type FilterRule (or
IpFilterrule, etc) instead of FilterRule* (or IpFilterRule*, etc).
I just realized that one can go even further with this idea:
#include <tr1/functional>
#include <vector>
#include <iostream>
typedef unsigned int Paket;
// machinery for predicates
// ========================
typedef bool(sig)(Paket const &);
typedef std::tr1::function<sigPaketPredicate;
class AndPredicate {
PaketPredicate the_lhs;
PaketPredicate the_rhs;
AndPredicate ( PaketPredicate const & lhs,
PaketPredicate const & rhs )
: the_lhs ( lhs )
, the_rhs ( rhs )
{}
public:
friend
AndPredicate operator&& ( PaketPredicate const & lhs,
PaketPredicate const & rhs );
bool operator() ( Paket const & p ) const {
return ( the_lhs(p) && the_rhs(p) );
}
};
AndPredicate operator&& ( PaketPredicate const & lhs,
PaketPredicate const & rhs ) {
return ( AndPredicate( lhs, rhs ) );
}
class OrPredicate {
PaketPredicate the_lhs;
PaketPredicate the_rhs;
OrPredicate ( PaketPredicate const & lhs,
PaketPredicate const & rhs )
: the_lhs ( lhs )
, the_rhs ( rhs )
{}
public:
friend
OrPredicate operator|| ( PaketPredicate const & lhs,
PaketPredicate const & rhs );
bool operator() ( Paket const & p ) const {
return ( the_lhs(p) || the_rhs(p) );
}
};
OrPredicate operator|| ( PaketPredicate const & lhs,
PaketPredicate const & rhs ) {
return ( OrPredicate( lhs, rhs ) );
}
class NotPredicate {
PaketPredicate the_lhs;
NotPredicate ( PaketPredicate const & lhs )
: the_lhs ( lhs )
{}
public:
friend
NotPredicate operator! ( PaketPredicate const & lhs );
bool operator() ( Paket const & p ) const {
return ( ! the_lhs(p) );
}
};
NotPredicate operator! ( PaketPredicate const & lhs ) {
return ( NotPredicate( lhs ) );
}
class ForallPredicate
// [should use private inheritance]
: public std::vector< PaketPredicate >
{
typedef std::vector< PaketPredicate base;
public:
bool operator() ( Paket const & p ) const {
for ( base::const_iterator iter = this->begin();
iter != this->end(); ++iter ) {
if ( ! (*iter)(p) ) {
return ( false );
}
}
return ( true );
}
};
class ExistsPredicate
// [should use private inheritance]
: public std::vector< PaketPredicate >
{
typedef std::vector< PaketPredicate base;
public:
bool operator() ( Paket const & p ) const {
for ( base::const_iterator iter = this->begin();
iter != this->end(); ++iter ) {
if ( (*iter)(p) ) {
return ( true );
}
}
return ( false );
}
};
// basic paket properties
// ======================
class Divisible {
unsigned int the_modulus;
public:
Divisible ( unsigned int m )
: the_modulus ( m )
{}
bool operator() ( Paket const & p ) const {
return ( p % the_modulus == 0 );
}
};
// sanity check
// ============
int main ( void ) {
for ( unsigned int i = 0; i < 100; ++i ) {
std::cout << i << " "
<< ((Divisible(2) && Divisible(3)) || Divisible(5))(i)
<< '\n';
}
std::cout << '\n';
Divisible even ( 2 );
Divisible five ( 5 );
PaketPredicate ten = even && five;
for ( unsigned int i = 0; i < 20; ++i ) {
std::cout << i << " " << ten(i) << '\n';
}
std::cout << '\n';
ForallPredicate rare;
rare.push_back( ten );
rare.push_back( ! Divisible( 7 ) );
for ( unsigned int i = 60; i < 100; ++i ) {
std::cout << i << " " << rare(i) << '\n';
}
}
/*
For actual paket filtering, you may have Predicates that
check whether IP addresses are inside a specified range.
*/
// E.g.:
class DestinationIpInRange {};
class SourcePortInRange {};
/*
Other predicates can then be defined in terms of these
basic paket properties using the logic machinery. In the
end, a filter would be just a ForallPredicate.
*/
Best
Kai-Uwe Bux
