Auto populating Lists in C++ at compile time

October 12, 2022
 |  No Comments

Before I get into the how to auto-populate lists, let’s talk about why I would want to.  Auto populating lists is useful when you have a set of statically allocated instances that need to be iterated over at run time.  Some examples:

  • In an embedded system there is typically a CLI interface running over a UART that is used for troubleshooting and debugging the application.  The CLI processing involves parsing the incoming command and then searching for a matching command object or function to execute the command.  This requires a list (array, map, etc.) that contains references to individual command object or functions. 
  • You are developing your own unit test framework and need to construct a list of the individual tests that to be executed at runtime. 

In both examples above, the lists and the elements of lists are known at compile time which means they could be statically allocated.  Since I am embedded software developer by day – anything I can statically allocate is good thing. 

However, just statically allocating the list and the elements does not necessarily mean that the list is actually populated at compile time.  One way to statically populate these lists is to take advantage of the C++ language feature where the constructors for statically allocated objects execute before main() is called.

Full Disclosure: The blog title is not correct from the actual compiler/C++ language mechanics involved.  The title should be: Auto populating Lists in C++ before main() executes. The correct title seems a bit too nuanced for a blog title 😉. From the perspective of writing the actual C++ statements, the item is inserted into the list by statically allocating the object instance, i.e. the mental model of building the list at compile time is conceptually correct, while being technically incorrect.

CLI Example

To continue the CLI example.  The pseudo-code below is for a hypothetical C++ implementation of a CLI interface. Given the following class declarations:

/// Interface for a command
class CommandApi
{
public:
    /// Command verb
    virtual const char* getVerb() const = 0;

    /// Execute Function. This method is called
    /// when the first token of a newline matches
    /// getVerb()
    virtual bool execute( int argc, char** argv ) = 0;
};

/// Concrete HELP command
class Help: public CommandApi
{
public:
    /// Constructor
    Help();

    /// Command verb
    const char* getVerb() const { return "help";}

    /// Execute Function
    bool execute( int argc, char** argv );
};

/// Concrete FOO command
class Foo: public CommandApi
{
public:
    /// Constructor
    Foo();

    /// Command verb
    const char* getVerb() const { return "foo"; }

    /// Execute Function
    bool execute( int argc, char** argv );
};

The above commands and the command list can be statically allocated and the list (truly) populated at compile time.

/// Commands
Help cliHelp;
Foo  cliFoo;

/// Command List
CommandApi* cliCommandList[2] ={
    &cliHelp,
    &cliFoo
};

The above approach works well and is representative of many embedded projects that I have worked on.  One downside to the above approach is that it requires that the cliCommandList array definition to be updated every time a new command is added or deleted.  The majority of the time this is not an issue.  However, if your project is built for multiple targets (e.g. target hardware vs simulation, or multiple hardware platforms) there can be CLI commands that are unique to each target.  Using the above approach, you have to perform some #ifdef gymnastics to have a single definition of the cliCommandList array that supports all platform variants.  This also requires that the file containing the cliCommandList array definition to be dependent on all of the platform variants.

One way to overcome the scalability issue described above is to take advantage of the C++ language feature where the constructors of statically allocated object instances execute before main() is called. This approach requires the following changes:

  1. Using a list to store for the references to the command instances instead of an array
    • Since in this example, I am using an intrusive list – the CommandApi class declaration also has to be updated.
  2. The constructors of the individual concrete command classes are updated to be passed a reference to the command list instance they are to self-populate with.

New class declarations:

// Interface for a command. Inherit from 'item' so 
// instances can be put into a singly linked list.
class CommandApi: public Item
{
public:
    /// Command verb
    virtual const char* getVerb() const = 0;

    /// Execute Function
    virtual bool execute( int argc, char** argv ) = 0;
};

// Concrete HELP command
class Help: public CommandApi
{
public:
    /// Constructor
    Help( SList<CommandApi>& commandList ) {
        // Self register with the command list
        commandList.put( *this );
    }

    /// Command verb
    const char* getVerb() const { return "help"; }

    /// Execute Function
    bool execute( int argc, char** argv );
};


// Concrete FOO command
class Foo: public CommandApi
{
public:
    /// Constructor
    Foo( SList<CommandApi>& commandList ) {
        // Self register with the command list
        commandList.put( *this );
    }

    /// Command verb
    const char* getVerb() const { return "foo"; }

    /// Execute Function
    bool execute( int argc, char** argv );
};

The following pseudo code statically allocate the commands and the list. While the cliCommandList is not populate at compile time as in the first example, it is populated before main() executes

/// Command list
SList<CommandApi> cliCommandList;

/// Commands
Help cliHelp( cliCommandList );
Foo  cliFoo( cliCommandList );

The above solution allows individual CLI commands to be statically in any file and inserted into the command list – assuming that cliCommandList variable is extern’d so that it is visible in other files.  Not a perfect solution, but definitely much more scalable than the first solution.  The new solution also does not limit the number of commands to a compile time constant and additional commands can be added at run time.

Fine Print

There is always a catch.  In the above solution – the sticking point is that while the C++ standard guarantees that the constructors of statically allocated instances will execute before main() is called, it does not define the order in which those constructor are executed.  This is a problem because the list needs to be initialized before any items are inserted. There is no mechanism for the developer to tell the compiler that the constructor for the cliCommandList instance needs to be executed before any of the individual concrete command constructors execute.

The solution to this conundrum is:

  1. Take advantage of the C++ language standard that states all statically allocated data will be initialized to zero by default.  This means that a statically allocated list instance will start out with all of its member data set to zeros before its constructor executes.
  2. Design the list (or container) class such that its initialized state for its member variables is all zeros. Then Provide alternate constructors.
    • One set to be called for statically allocated instances that do not perform any explicit initialization of the member variables. 
    • And a second set to be called when creating instances at run time that sets the member variables to zero.
      Note: This constructor issue only applies to the list, not to the elements in the list.

For example, the SList<> class would have the following constructors:

public:
    /** Constructor initializes head and tail pointers.
     */
    SList()
        :m_headPtr( 0 ), m_tailPtr( 0 )
    {
    }

    /** This is a special constructor for when the list is
        statically declared 
     */
    SList( const char* usedToCreateAUniqueConstructor )
    {
    }

Then statically creating the list and commands would be:

/// Command list
SList<CommandApi> cliCommandList("useStaticConstructor");

/// Commands
Help cliHelp( cliCommandList );
Foo  cliFoo( cliCommandList );

Unit Test Framework Example

Looking a C based unit test framework such a CUnit.  The developer is required to manually add the individual tests to the test framework.  Below is pseudo code for a CUnit test executable.

/// Test suite setup
int init_suite1( void ) { ... }

/// Test suite clean-up
int clean_suite1( void ) { ... }

/// Test
void testFPRINTF( void ) { ... }

/// Test
void testFREAD( void ) { ... }

/// Test application
int main( int argc, char* argv[] )
{
    /// Handle to test suite#1
    CU_pSuite pSuite = NULL;

    /// Add test suite#1
    pSuite = CU_add_suite( "Suite_1", init_suite1, clean_suite1 );

    /// Add tests to test suite#1
    CU_add_test( pSuite, "test of fprintf()", testFPRINTF );
    CU_add_test( pSuite, "test of fread()", testFREAD );

    /// Run the tests
    CU_basic_run_tests();
    return CU_get_error();
}

While the individual test suite and test definitions can be in different files, the main() function has to be edited every time a new test suite or test is added or delete.   

Now let’s compare with a C++ based unit test framework that uses self-populating static lists.  The following pseudo is the Catch2 unit test framework equivalent to the above CUnit pseudo code.

/// main.cpp
int main( int argc, char* argv[] )
{
    // Run the test(s)
    return Catch::Session().run( argc, argv );
}

/// test1.cpp (does not have to be the same file as main())
TEST_CASE( "Test Suite1" )
{
    // Test suite setup code here (i.e. init_suite1())
    ...

    SECTION( "test of fprintf()" )
    {
        // testFPRINTF test code here
    }

    SECTION( "test of fread()" )
    {
        // testFREAD code here
    }

    /// Test suite clean-up code here (i.e. clean_suite1())
    ...
}

The simple fact of defining a test case and a test section populates the list that the Catch2 test runner uses execute the individual tests.  Hidden in the TEST_CASE and SECTION macros are statically allocated object instances (per test case/section) that self register the function pointers with the test runner’s list of tests.  The mechanics are the same as described in the CLI example.

Sidebar: This is the main reason why I recommend using a C++ based unit test framework even when your code base is only C.  Not having to manually maintain a list of tests is one less barrier to entry for developers who are new to doing unit tests for embedded projects. Wait does that mean I use Catch2 to run tests on the target hardware?  No.  If the majority of your code base is platform independent then you can write and automate unit tests to run on a Windows/Linux box.  For more on the topic of writing platform independent code see the following postings: