OSDev.org

I was wondering how to work around this problem.

I have a firewall where rules are stored on the basis of priority.
So if there are 10 rules a packet that comes in will have to pass though all 10 to pass or be rejected by any one to be rejected.
Different types of packets come through (tcp,udp etc...) and rules of only the specific packet-type should be applied on it.

If I have the rules stored in a map/multimap based on the priority I could traverse the map priority-wise, but what I want to do is traverse the map for only the rules that are applicable for that particular packet-type (as this would be more efficient & fast) in a priority-wise manner.

Does anyone have any ideas on how to do this?

More a problem of data modelling than of C++. As such, I'll blissfully ignore that you already have your rules in a multimap and brainstorm about some modelling approaches.

A rule has 1..n applicable packet type, 1 priority.

First (intuitive) approach: Pack the rules into a vector, using the sequence in the vector as implicit priority. Define a member function for rules that returns true if it applies for a given packet type. Traverse the vector from begin() to end() and check that member function for true rc before trying to match the rule.

Second approach: Pack the rules into a vector, with overloaded push_back() / remove(). Keep a map with first = packet type, second = vector<rule *>. Make the custom push_back() insert a pointer to that rule into all applicable vectors at the appropriate place (priority!), and the remove() function removing those pointers. When you receive a package, find its rule pointer vector in the map, and process the rules in the order you find them in the vector.

Third approach: Create a struct holding a bit mask (for packet type) and a rule*. Create an array (well, vector...) of those structs, in order of rule priority. Set up the bit mask of the current packet, iterate through the struct array, and execute all matching rules. You traverse all rules, but I'd guess this is nevertheless the fastest method.

That's what I come up with without engaging major parts of my brain. Contact me for consulting fees if you want approach four, five and six.

Am really thinking about that offer.

Neo wrote: Am really thinking about that offer.

If you're doing generic data modeling, why not use a priority queue? You could model the types of packets as bits in a bitfield and AND-out the ones that don't apply.

PS: a map isn't sorted so it wouldn't give predictable behaviour.

Candy wrote: PS: a map isn't sorted so it wouldn't give predictable behaviour.

If we're talking about std::map in the STL, then that statement is incorrect. If you iterate through a map, you will get back key/value pairs sorted in key order. The sort is based on whatever "less-than" function you used when defining the map (usually the default std::less<T>).

I was just wondering if it is possible to have a nested implementation of a multimap?
i.e. a multimap within a multimap.

Neo wrote: I was just wondering if it is possible to have a nested implementation of a multimap?
i.e. a multimap within a multimap.

Sure. That's not to say it would be a good choice for whatever you're modelling, but AFAIK it is possible.

Ok. I have a choice of implementing my code as either nested multimaps or as an array of multimaps.

I am deciding to go the array way, because the array method looks to be more efficient for lookups (except I would need to do bounds checking).

Any opinions on this?

Neo wrote: Ok. I have a choice of implementing my code as either nested multimaps or as an array of multimaps.

I am deciding to go the array way, because the array method looks to be more efficient for lookups (except I would need to do bounds checking).

Any opinions on this?

Depends on the implementation you choose. Indexing an array is constant time, indexing a tree-map is logarithmic time,indexing a hashed map is amortized constant time assuming a map larger than the keyset and closed hashing, or probably close to logarithmic for open hashing. The array probably is faster. Why would you make it a multimap?

Coz I can't use a array (index is not continuous sequence).

Neo wrote: Coz I can't use a array (index is not continuous sequence).

What about using a plain map then? If the amount of multimaps is low, how about still using an array, linked list or such and iterating over them?

Nope. There is a possibility of the same index being used as key for 1 or more elements later.

I thought that the mulitmap implementation would be more efficient than a linked list implementation or such?

Neo wrote: I thought that the mulitmap implementation would be more efficient than a linked list implementation or such?

The C++ STL isn't an all-purpose tool, it's just a basic toolset. If the standard lib does not do what you need, find an extension - few languages have a bigger choice in libs than C/C++. stdext::hash_map or boost::multi_index could be what you're looking for.