4
\$\begingroup\$

The actual data types here are probably not relevant to post an answer. I use Qt types here, but the question should apply for other structured types as well.

I receive a data frame via can bus using the QtSerialBus module in Qt. I want to look for each received frame, if it matches a QCanBusDevice::Filter that I maintain in a QList<QCanBusDevice::Filter>.

To see if one filter matches for the currently received frame, I initially came up with those lines of code. Edits below show the code evolution, so that anyone can see the progress.

bool MyCanClass::isFrameMatchedByFilter(const QCanBusFrame& frameToFilter)
{
    if (mFilterList.isEmpty()) {
        return true;
    } else {
        for (auto& filter : mFilterList) {
            // Go down the chain as far as needed and proceed to the next list entry as soon as a mismatch comes up
            // First ID/Mask filtering, format and type afterwards
            if ((frameToFilter.frameId() & filter.frameId) != (filter.frameId & filter.frameIdMask)) {
                continue;
            }
            // FrameFormat only matters if set either base or extended, not both
            if (filter.format != QCanBusDevice::Filter::FormatFilter::MatchBaseAndExtendedFormat) {
                if (!(frameToFilter.hasExtendedFrameFormat() == (filter.format == QCanBusDevice::Filter::FormatFilter::MatchExtendedFormat))) {
                    continue;
                }
            }
            // Invalid frame is the default and matches every frame type
            if (filter.type != QCanBusFrame::FrameType::InvalidFrame) {
                if (filter.type != frameToFilter.frameType()) {
                    continue;
                }
            }
            return true;
        }
        return false;
    }
}

I personally find the level of nesting and the general approach not too unclean here, but probably it can get improved, so that it is easier to understand or even faster.

Edit 1

After a few steps of refactoring, based on answers I got, I refactored everything a bit, made it more modular and easier to understand.

I might sort the IDs in the filter list beforehand to gain speed via binary search, but I am not sure, whether it is worth it, so I'll stay with that for now:

bool MyCanClass::isFrameOfInterest(const QCanBusFrame& frame)
{
    if (mFilterList.isEmpty()) {
        return true;
    } else {
        return isCanFrameMatchingFilterList(frame, mFilterList);
    }
}

bool isCanFrameMatchingFilterList(const QCanBusFrame& frame, const QList<QCanBusDevice::Filter>& filterList)
{
    for (auto& filter : filterList) {
        // Go down the chain as far as needed and proceed to the next list entry as soon as a mismatch comes up
        // First ID/Mask filtering, format and type afterwards
        if (!isCanIdMatchedByFilter(frame, filter)) {
            continue;
        }
        // FrameFormat only matters if set either base or extended, not both
        if (!isFrameFormatMatchedByFilter(frame, filter)) {
            continue;
        }
        // Invalid frame is the default and matches every frame type
        if (!isFrameTypeMatchedByFilter(frame, filter)) {
            continue;
        }
        return true;
    }
    return false;
}

bool isCanIdMatchedByFilter(const QCanBusFrame& frame, const QCanBusDevice::Filter& filter)
{
    return (frame.frameId() & filter.frameId) == (filter.frameId & filter.frameIdMask);
}

bool isFrameFormatMatchedByFilter(const QCanBusFrame& frame, const QCanBusDevice::Filter& filter)
{
    if (filter.format == QCanBusDevice::Filter::FormatFilter::MatchBaseAndExtendedFormat) {
        return true;
    }
    bool extended = frame.hasExtendedFrameFormat();
    if (filter.format == QCanBusDevice::Filter::FormatFilter::MatchBaseFormat) {
        return (extended) ? false : true;
    } else {
        return (extended) ? true : false;
    }
}

bool isFrameTypeMatchedByFilter(const QCanBusFrame& frame, const QCanBusDevice::Filter& filter)
{
    // invalid frame matches all frame types
    if (filter.type != QCanBusFrame::FrameType::InvalidFrame) {
        if (filter.type != frame.frameType()) {
            return false;
        }
    }
    return true;
}

While the new isFrameFormatMatchedByFilter() is way easier to understand at the first view, I assume that there are at least two extra instructions involved to execute that code on the CPU, am I wrong?

It's always a bit hard to figure out which part of your own codes are considered to be "too clever" and which aren't :-)

\$\endgroup\$
6
\$\begingroup\$

Cleaner and clearer it can certainly be:

  • your function is called isFrameMatchedByFilter but returns true if there is no filter in the filter list: does that mean the frame is matched by a void filter? It's rather unclear, you need to either find another name or change the behavior of the function.

  • your argument is called frameToFilter, but it's a bad idea. First because there's only one frame in this function and frame is shorter than frameToFilter; second because frameToFilter can also be interpreted as a kind of transformation from a frame to a filter (like in to_string for instance).

  • the whole loop could be subsumed in a named algorithm: either std::any_of, or, if you change the semantics a bit, std::find_if: it might be interesting to return the matching filter rather than a simple bool. You then only need to compare the return iterator to filter_list.end() to produce a bool.

  • the mask system comes with a cognitive cost. What (frameToFilter.frameId() & filter.frameId) != (filter.frameId & filter.frameIdMask) could possibly mean, I've no substantial idea. A function, or even a simple lambda to enlighten the reader would be nice. It would also encapsulate this calculation, and you could change this to a more robust system (like an enum -but I don't know the context, so it might not be the right choice) afterwards.

  • this kind of things: !(frameToFilter.hasExtendedFrameFormat() == (filter.format == QCanBusDevice::Filter::FormatFilter::MatchExtendedFormat)) is too clever. Again, write a one-liner around it or at least write it a way a mere mortal can read (I mean, without a 50% chance not to understand it correctly).

Can it be faster? It depends on several factors: you can rearrange the match conditions to have the fastest * most discriminating first if it isn't already done (but it looks like the right order); you can sort the filters by id and perform a binary search rather than a flat one; you can go parallel if there are a lot of them. But as always, only optimize if it's worth it -measure first.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for your precise comments. I refactored a bit with them in mind and updated the question. Your third point seems reasonable, but due to the fact, that multiple filters in the list could match the criteria for the frame, it is not possible, to return "the one filter found". The mask comparison is well-defined and I am not concerned about possible misunderstandings. Your "too clever" comment was absolutely right. One always is proud of such constructs unless hinted ;-) The binary search approach might be worth thinking about. But, as you guessed, I don't think it's worth it for now \$\endgroup\$ – darkmattercoder Apr 29 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.