4
\$\begingroup\$

(Before I even start: For reasons beyond my control, this code base is constrained to C++98 (so, no =delete, no auto etc., but that's also not the gist of this question). The code cannot use templates or the STL.)

I inherited code that combines calls from two distinct modules which both have the ability to set and remove "triggers" for certain actions. An action should be started if the trigger is set by one module while it is not set by the other; and the action should be stopped when the trigger is removed by one module, again while it was not set by the other. A module can set or remove the same trigger multiple times in succession; setting or removing an already set/removed trigger by the same module is a NOP.

Whether one of the other triggers is set is irrelevant. In other words, the action should be started if and only if a given module sets the given trigger first and be stopped if and only if the given module removes the given trigger last.

The logic is contained in a class which keeps track of the triggers currently set for each module and exposes just two public functions: Set/unset a trigger for one of the two modules. The possible triggers are passed in as a bit in a bit field (implemented as an unsigned int) and stored in an unsigned int for each module. Only one trigger can be present in a call.

The old implementation is unnecessarily complicated and redundant: Among other things, a third bitfield is stored that redundantly keeps track of the OR-ed state of each bit/trigger and must be updated along with the bitfield for each module. I found it hard to understand and verify in a review, wondered how a more concise and elegant solution might look, and gave it a try. The reasons I'm posting my attempt (together with the old code):

  • Most importantly: Is the new code correct, that is: functionally equivalent? We perform module tests beyond the cursory test presented in Main.cpp below, which pass, but I'm still not sure.
  • That I'm not sure about the correctness of the code makes me wonder how I could make it easier to understand. All functions are short now (so short that they can all be inline), I have tried to come up with better names, and still it is not perfectly trivial. I'm trying to be concise. An expression like (mTriggersByModule[module] &= ~trigger) != oldReason is pretty dense. It is using an assignment as an expression and is old-school C style; people familiar with bit manipulation will readily recognize the &= ~x pattern, others will not. Of course one could introduce temporary variables. Would a less dense style be better?
  • Would you actually use C++ bit fields, making each flag a member? In all reality there is no need to use (explicit or implicit) bit fields internally, one could as well use a bunch of booleans (not a vector though, because of project constraints).

My code design principles:

  • Remove redundancy: Eliminate the "combined" bit field, eliminate parallel code (see next point).
  • Compute rather than branch: I use the parameter specifying the module as an index into an array (mTriggersByModule[module] instead of using it to choose paths with different variables (if (isFromModule2) ...). The code is now branch-less.
  • The former point also made the interface type safe: Because ActionTriggerT is actually an unsigned integer, StartAction(const ActionTriggerT trigger, const bool isFromModule2) could actually be called with the arguments swapped. This is not possible any longer now that the second parameter has been made an enum (there is a default conversion integer->bool but not integer->enum).
  • Use better identifier names to make intent clearer (e.g. the old StopAction() does not actually stop anything but removes a trigger and returns whether it should be stopped, reflected by the new name RemoveTriggerAndCheckStop()).

OK, let's see some code. There is a godbolt project with the files below to see it live.

The bit flags and typedef for the trigger

This is more elaborate in the real project and simply acts as a minimal stand-in here.

#ifndef ACTIONTRIGGERS_H
#define ACTIONTRIGGERS_H

#include <cstdint>

typedef uint32_t ActionTriggerT;

// In reality, there are more of them where these come from.
const ActionTriggerT NO_TRIGGER = 0;
const ActionTriggerT TRIGGER1 = 1;
const ActionTriggerT TRIGGER2 = 2;
const ActionTriggerT TRIGGER3 = 4;

#endif // ndef ACTIONTRIGGERS_H

Old class definition


#ifndef TWOSETSOFTRIGGERS_H
#define TWOSETSOFTRIGGERS_H

#include "ActionTriggers.h"

/**
 * @brief This class coordinates action triggers from two modules.
 * StartAction() starts an action related to the trigger
 * if the trigger was not active from either module before, and StopAction()
 * stops it when the trigger was removed from one module and was not active from the other.
 *
 */
class TwoSetsOfTriggersT
{
public:
  /**
   * @brief Constructor.
   */
  TwoSetsOfTriggersT();

  /**
   * @brief Checks if the action has to be stopped after a module has
   * stopped the specific trigger.
   *
   * @param trigger the action trigger that was stopped by the module.
   * @param isFromModule2 @c true if module 2 did release the trigger,
   *                 @c false otherwise
   *
   * @return @c true if the trigger is set for the action by us, but should
   *         now be stopped, @c false if either the trigger was not set
   *         by us or it should not yet be stopped.
   */
  bool StopAction(ActionTriggerT trigger, bool isFromModule2 = true);

  /**
   * @brief Checks if the action has to be started after a module has
   * started the trigger.
   *
   * @param trigger the trigger that was started by the module.
   * @param isFromModule2 @c true if a module 2 did apply the trigger,
   *                 @c false otherwise
   *
   * @return @c true if the trigger is not yet set for the action by us, but
   *         should now be started, @c false if either the trigger is
   *         already started by us or it should not be started.
   */
  bool StartAction(ActionTriggerT trigger, bool isFromModule2 = true);

private:

  /// Current triggers for module 1
  ActionTriggerT mModuleTriggers;

  /// Current triggers for module 2
  ActionTriggerT mModule2Triggers;

  /// Current triggers for all modules combined
  ActionTriggerT mCombinedTriggers;
};

#endif // TWOSETSOFTRIGGERS_H

Old class implementation


#include "TwoSetsOfTriggersT.h"

/*****************************************************************************/

TwoSetsOfTriggersT::TwoSetsOfTriggersT() :
  mModuleTriggers(NO_TRIGGER),
  mModule2Triggers(NO_TRIGGER),
  mCombinedTriggers(NO_TRIGGER)
{
}

/*****************************************************************************/

bool TwoSetsOfTriggersT::StopAction(const uint32_t trigger, const bool isFromModule2)
{
  // Was it a change
  bool isChanged = false;
  if (isFromModule2)
  {
    if (trigger == (mModule2Triggers & trigger))
    {
      mModule2Triggers &= ~trigger;
      isChanged = true;
    }
  }
  else
  {
    if (trigger == (mModuleTriggers & trigger))
    {
      mModuleTriggers &= ~trigger;
      isChanged = true;
    }
  }

  // Return value
  bool isToBe = false;

  if (isChanged)
  {
    if (trigger == (mCombinedTriggers & trigger))
    {
      if ((0 == (mModuleTriggers & trigger)) &&
        (0 == (mModule2Triggers & trigger)))
      {
        mCombinedTriggers &= ~trigger;
        isToBe = true;
      }
    }
  }

  return isToBe;
}

/*****************************************************************************/

bool TwoSetsOfTriggersT::StartAction(const ActionTriggerT trigger, const bool isFromModule2)
{
  // Was it a change
  bool isChanged = false;
  if (isFromModule2)
  {
    if (0 == (mModule2Triggers & trigger))
    {
      mModule2Triggers |= trigger;
      isChanged = true;
    }
  }
  else
  {
    if (0 == (mModuleTriggers & trigger))
    {
      mModuleTriggers |= trigger;
      isChanged = true;
    }
  }

  // Return value
  bool isToBe = false;

  if (isChanged)
  {
    if (0 == (mCombinedTriggers & trigger))
    {
      mCombinedTriggers |= trigger;
      isToBe = true;
    }
  }

  return isToBe;
}

New class definition, with inline functions

#ifndef TWOSETSOFTRIGGERSNEW_H
#define TWOSETSOFTRIGGERSNEW_H

#include "ActionTriggers.h"

/**
 * This class coordinates triggers  which can be set by two modules to start and stop actions.
 * Both modules can set and remove the same set of triggers.
 * An action is started/stopped when a trigger is actually set/removed from one module
 * while it was not present from the other.
 */
class TwoSetsOfTriggersNewT
{
public:

  /**
   * @brief The enum values are used as type-safe parameters in the public API,
   * and as an index into the trigger bit field array.
   */
  enum Module_E { MODULE_1, MODULE_2 };

  /**
   * @brief Start with no trigger active.
   */
  TwoSetsOfTriggersNewT() // cannot initialize array in C++98 or C++03
  {
    mTriggersByModule[MODULE_1] = mTriggersByModule[MODULE_2] = NO_TRIGGER;
  }

  /**
   * @brief Checks if the action should be stopped 
   * after a module has removed the given trigger.
   *
   * @param trigger the action trigger that is removed by the module.
   * @param module MODULE_1 or MODULE_2, indicating the module removing the trigger.
   *
   * @return @c true if the trigger from the given module was
   * active before and is now removed, and if that trigger is not active for the
   * other module.
   */
  bool RemoveTriggerAndCheckStop(ActionTriggerT trigger, Module_E module = MODULE_2)
  {
    return TryDelete(trigger, module) &&
      !TriggerIsActive(trigger, OtherModule(module));
  }

  /**
   * @brief Checks if the action has to be started after a module has
   * activated the given trigger.
   *
   * @param trigger the trigger that was activated by the module.
   * @param module MODULE_1 or MODULE_2, indicating the calling module.
   *
   * @return @c true if the trigger was not yet set from either module
   *         and the action should be started
   */
  bool AddTriggerAndCheckStart(ActionTriggerT trigger, Module_E module = MODULE_2)
  {
    return TryAdd(trigger, module) &&
      !TriggerIsActive(trigger, OtherModule(module));
  }

private:
  /**
   * @brief Return the "other" module.
   * @param module the module for which we want to obtain the other module.
   * @return MODULE_1 if the argument was MODULE_2 and vice versa.
   */
  static Module_E OtherModule(Module_E module)
  {
    // This is much faster than a ternary conditional which may need a jump.
    return static_cast<Module_E>(!module);
  }

  /**
   * @brief Delete, if necessary, the given trigger for the given module
   * and return whether it was set before
   * @param trigger One of the triggers (a bit in a 32 bit field)
   * @param module MODULE_1 or MODULE_2, indicating the calling module. 
   * @return Whether the given trigger was set before for the given module
   */
  bool TryDelete(ActionTriggerT trigger, Module_E module)
  {
    ActionTriggerT oldReason = mTriggersByModule[module];
    return (mTriggersByModule[module] &= ~trigger) != oldReason;
  }

  /**
   * @brief Set the given trigger for the given module and return whether it
   * was unset before
   * @param trigger One of the triggers (a bit in a 32 bit field)
   * @param module MODULE_1 or MODULE_2, indicating the calling module
   * @return Whether the given trigger was unset before for the given module
   */
  bool TryAdd(ActionTriggerT trigger, Module_E module)
  {
    ActionTriggerT oldReason = mTriggersByModule[module];
    return (mTriggersByModule[module] |= trigger) != oldReason;
  }

  /**
   * @brief Check whether the given trigger is active for the given module
   * but do not change it.
   * @param trigger One of the triggers (a bit in a 32 bit field)
   * @param module MODULE_1 or MODULE_2, indicating the calling module
   * @return whether the given trigger is active for the given module
   */
  bool TriggerIsActive(ActionTriggerT trigger,
    Module_E module) const
  {
    return mTriggersByModule[module] & trigger;
  }

  /// Current triggers for module 1 and module 2 as a bit field.
  /// Reasons from module 1 are are in mTriggersByModule[MODULE_1], for module 2 in mTriggersByModule[MODULE_2]
  ActionTriggerT mTriggersByModule[2];
};

#endif // ndef TWOSETSOFTRIGGERSNEW_H

Main.cpp, a cursory test


#include "TwoSetsOfTriggersT.h"
#include "TwoSetsOfTriggersNewT.h"

#include <assert.h>

int main()
{
  {
    TwoSetsOfTriggersT tsot;

    assert(tsot.StartAction(TRIGGER1));
    assert(!tsot.StartAction(TRIGGER1)); // already started
    assert(!tsot.StartAction(TRIGGER1, false)); // already started by other source

    assert(tsot.StartAction(TRIGGER2, false));
    assert(!tsot.StartAction(TRIGGER2));
    assert(!tsot.StartAction(TRIGGER2));

    assert(!tsot.StopAction(TRIGGER3)); // was not started, cannot be stopped

    assert(!tsot.StopAction(TRIGGER1)); // still started by other source
    assert(tsot.StopAction(TRIGGER1, false)); // now yes

    assert(!tsot.StopAction(TRIGGER2, false)); // still started by other source
    assert(tsot.StopAction(TRIGGER2)); // now yes
  }

  {
    TwoSetsOfTriggersNewT tsot;

    assert(tsot.AddTriggerAndCheckStart(TRIGGER1));
    assert(!tsot.AddTriggerAndCheckStart(TRIGGER1)); // already started
    assert(!tsot.AddTriggerAndCheckStart(TRIGGER1, TwoSetsOfTriggersNewT::MODULE_1)); // already started by other source

    assert(tsot.AddTriggerAndCheckStart(TRIGGER2, TwoSetsOfTriggersNewT::MODULE_1));
    assert(!tsot.AddTriggerAndCheckStart(TRIGGER2));
    assert(!tsot.AddTriggerAndCheckStart(TRIGGER2));

    assert(!tsot.RemoveTriggerAndCheckStop(TRIGGER3)); // was not started, cannot be stopped

    assert(!tsot.RemoveTriggerAndCheckStop(TRIGGER1)); // still started by other source
    assert(tsot.RemoveTriggerAndCheckStop(TRIGGER1, TwoSetsOfTriggersNewT::MODULE_1)); // now yes

    assert(!tsot.RemoveTriggerAndCheckStop(TRIGGER2, TwoSetsOfTriggersNewT::MODULE_1)); // still started by other source
    assert(tsot.RemoveTriggerAndCheckStop(TRIGGER2)); // now yes
  }
}
\$\endgroup\$

2 Answers 2

7
\$\begingroup\$

About the constraints

For reasons beyond my control, this code base is constrained to C++98 (so, no =delete, no auto etc., but that's also not the gist of this question. The code cannot use templates or the STL.

I'll address this anyway: alarm bells should be ringing if you are constrained to use a 25 year old version of C++, and not even the full version at that. Are you compiling for some rare embedded CPU for which no compilers were written that support later versions?

Make constants static

In ActionTriggers.h, the constants should probably be made static. This will allow the compiler to optimize the storage away, and also prevents compilation failures if that header file gets included in multiple source files that are linked into the same executable.

Avoiding branches

Since you want to avoid branches, consider that && has short-cut semantics and thus also might cause a conditional jump. You can even avoid that:

bool AddTriggerAndCheckStart(ActionTriggerT trigger, Module_E module = MODULE_2)
{
    bool shouldStart = !((mTriggersByModule[0] | mTriggersByModule[1]) & trigger);
    mTriggersByModule[module] |= trigger;
    return shouldStart;
}

bool RemoveTriggerAndCheckStop(ActionTriggerT trigger, Module_E module = MODULE_2)
{
    bool shouldStop = mTriggersByModule[module] & ~mTriggersByModule[OtherModule(module)] & trigger;
    mTriggersByModule[module] &= ~trigger;
    return shouldStop;
}

What if trigger is not a power of two?

If you pass in a value for trigger that is a combination of two or more TRIGGER* constants, then these functions will do something unexpected. You might want to add assert()s to catch that.

Answers to your questions

  • Most importantly: Is the new code correct, that is: functionally equivalent? We perform module tests beyond the cursory test presented in Main.cpp below, which pass, but I'm still not sure.

I think it is. But if this is running on a billion dollar space probe, pacemaker or on a nuclear reactor, don't take my word for it.

  • Would you actually use C++ bit fields, making each flag a member? In all reality there is no need to use (explicit or implicit) bit fields internally, one could as well use a bunch of booleans (not a vector though, because of project constraints).

I actually thought that bit fields would be a good idea at first, but that isn't a great match for your use case. An array of booleans might be possible, and then pass an index into that array to RemoveTriggerAndCheckStop() and AddTriggerAndCheckStart(). It will use more storage though.

  • An expression like (mTriggersByModule[module] &= ~trigger) != oldReason is pretty dense. It is using an assignment as an expression and is old-school C style; people familiar with bit manipulation will readily recognize the &= ~x pattern, others will not. Of course one could introduce temporary variables. Would a less dense style be better?

I don't think it is that dense, and if people don't know bit manipulation, maybe they shouldn't be touching the code? At some point you should be able to rely on knowledge of the language. Also, your code has much fewer lines, so that makes it less complex than the original. That said, using an array of bools would probably be even easier to understand.

Swap the array and the bitmask

Instead of using two array of bools, one for each module, you could consider making a bitmask for the modules, and having one array of those bitmasks:

enum ActionTrigger_E {
    TRIGGER1; // = 0
    TRIGGER2;
    TRIGGER3;
};

static const std::size_t NUM_TRIGGERS = 3;
…
class TwoSetsOfTriggersT
{
    enum Module_E {
        MODULE_1 = 1; // 1 << 0
        MODULE_2 = 2;
    };
    …
    std::uint8_t mModulesByTrigger[NUM_TRIGGERS];
};

This way, you can write:

bool AddTriggerAndCheckStart(ActionTrigger_E trigger, Module_E module = MODULE_2)
{
    bool shouldStart = !mModulesByTrigger[trigger];
    mModulesByTrigger[trigger] |= module;
    return shouldStart;
}

bool RemoveTriggerAndCheckStop(ActionTrigger_E trigger, Module_E module = MODULE_2)
{
    bool shouldStop = mModulesByTrigger[trigger] == module;
    mModulesByTrigger[trigger] &= ~module;
    return shouldStop;
}
\$\endgroup\$
1
  • \$\begingroup\$ I like your last edit :-).-- The missing static is my fault, the original code base has it.-- The "inverted indexing" is an interested idea. Both "module sources" are in a single value and therefore can be summarily checked as a single value, ORed implicitly, if you want. Neat! Oh, and I think "OtherModule()" is not needed any longer either. \$\endgroup\$ Jan 7 at 15:16
4
\$\begingroup\$

You seem to be missing a using std::uint32_t between these two lines:

#include <cstdint>

typedef uint32_t ActionTriggerT;

I think it's better to write the type name in full - especially in a header file, where the global namespace isn't really your own.

But reconsider whether this type needs exactly 32 bits, and should fail to compile if that type is unavailable. In almost all cases, std::uint_fast32_t or std::uint_least32_t are better candidates.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks, interesting. My code compiles as-is with MSVC and gcc (see the godbolt link) even though cppreference claims the names are in namespace std. While the review goal I was aiming at was more concerned with logic and design this is an interesting detail. (I actually made the typedef and the constant definitions up; the original code base uses their own typedefs anyway. cpprefeence says cstdint was not available before C++11, so I'm inadvertently not sticking to my "C++98" stipulation here.) \$\endgroup\$ Jan 7 at 15:08
  • \$\begingroup\$ Your test platforms are no doubt availing themselves of the permission to also declare these types in the global namespace. Because that's a "may" rather than a "must", portable code cannot depend on that. \$\endgroup\$ Jan 7 at 15:16
  • \$\begingroup\$ Yes, I realised after answering that this was context code that's not the main part under review - I think that using blockquote for that and the "original" starting-point functions can help make this clearer. \$\endgroup\$ Jan 7 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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