List of generic references to mixed types

[NorseMN]

I just posted a topic titled: "template for access of single element of static array". But after second thoughts, that might be a false start. It might be best to provide a bigger picture of my goals.

What I really want to have is a simple structure or class like:
struct valRef
{
unsigned char typNum;
unsigned int instanceNum;
}

Behind this, I'd have static arrays of several value types.
Mostly POD types.
But also a few derived types, particularly a "List" type.

I'd like to be able to make lists of valRef instances.
I'd like each instance to act like a C++ reference to a value in a specific type array.

This would allow a hierarchy of lists to be instantiated that contain references to mixed types, including POD and List types.

A sequence of valRef instances of List type would create a path from the root to any sub-list.
But each valRef provides direct access to a specific List or value reference.

I tried to do this years ago and concluded that it couldn't be done without support for functions with a variable return type.

I think now that I might be able to eliminate the typNum element and use typed instances of the valRef structure to associate each value with the associated array.

It seems that there are now more resources available.
I've found many examples on the internet of clever techniques using templates and classes, such as a nested proxy class, etc. But I can't quite piece them together.

Standard templates, Booch libraries, vectors and most other standard components are NOT useful for my needs, because they use dynamic allocation and destruction too freely. Even if I override the new and delete operators to use a managed memory pool, the variety of memory sizes will lead to fragmentation.

Does any of this make sense to anyone?
If so, are you willing to share some suggestions?
Thanks in advance for any help.

[helios]

Here's what I understand in OO terms:
You want a Listable type with a get_member(int) member that gives you the nth member of the object (for the sake of simplicity, we'll assume that all subclasses of Listable are final, without subclasses of their own). So, for example,

class A : public Listable{
    int a;
    double b;
    std::string c;
    Listable *d;
};

//...

Listable *l = new A;
l->get_member(2);

The last call should somehow return a pointer or whatever to ((A *)l)->c.
Finally, you can traverse the object hierarchy by chaining calls:

l->get_member(3)->get_member(2) /* etc. */

Ignoring what you've said about dynamic allocation, is this interpretation correct?

Even if I override the new and delete operators to use a managed memory pool, the variety of memory sizes will lead to fragmentation.

You'll only get fragmentation if you're allocating and deallocating objects. It's trivial to write a perfect allocator if it assumes that no object will ever be deallocated.
On the other hand, if you both allocate and deallocate, fragmentation is inevitable.

[NorseMN]

helios,
Thanks for your response.
I think I need to provide more clarification and some code fragments.
I am considering something like this:

template<class T, size_t SIZE>
class DataTyp
{
private:
static T Data[SIZE];
static const size_t size = SIZE;
static U16 cnt = 0;
U16 num;
...
T& operator[] (size_t i);
const T& operator[] (size_t i) const;
...


This would be instantiated for each data type in my application, including a list type.
A front-end editor allows all allocations of each data value to be known in advance, so the SIZE of the Data arrays for each type is known and they can be statically allocated.

The only non-static data member is "U16 num", so each declaration of a DataTyp value would effectively be just 16 bits.
Each DataTyp instance is associated with the the static Data array member of it's class, so it should be possible to make the DataTyp instance act as a reference to an element of the array.

There are obvious flaws in this, and I may already be too far down a bad path (again), so maybe I need to broaden the picture (once more).

I want to define function block interfaces as hierarchical lists. (e.g. Inputs list and Outputs list)
Each function block added to an application registers its interface with a central data manger that controls external access to the master hierarchy. It also adds an "Update function" to a "Process Manager" list.
An "Application Builder" tool (PC application) supports editing of interconnections
between items in the hierarchy. (an output signal from one function can share the same DataTyp instance as the input of another function. That is, both have the same internal "num" value. Or, they can share an entire list of values (potentially with sub-lists).

Regarding dynamic memory allocation:
My explanation was brief and I expected questions.
Most of this will be static allocation. But there will be some need for dynamic allocations.
Deallocation is not used.
Instead, allocation is from a memory pool and is limited to specific sized blocks.
Rather than free memory, it's placed on a "Free List" which is checked first when memory is allocated. (One free list for each size.)

[helios]

What do you gain from having everything statically allocated that you can't get by overloading new and using a simple object layout with pointers? Like I said, writing a perfect allocator that assumes no deallocations is trivial, even for objects of heterogeneous types.

Alternatively, if you're generating code from metadata (that's what that front-end editor you mentioned does, right?), you could generate a routine that allocates a big chunk of memory and initializes pointers manually. E.g.

auto big_chunk = (char *)malloc(known_size);
Node *root = (Node *)big_chunk;
root->left = (Node *)(big_chunk + 12);
root->right = (Node *)(big_chunk + 24);
root->left->left = (Node *)(big_chunk + 100);
//etc.

return root;

[NorseMN]

It seems I must again step up to a higher level of description.

Perhaps first, I should explain the target usage:
This is intended for use in hard real-time embedded control software used on off-road vehicles with hydrostatic transmissions. Each application runs repeatedly every millisecond or two. Obviously safety and reliability are crucial. It's necessary to encapsulate the complexity and present a simple interface that is as bullet-proof as possible. Vehicles are moving towards IoT connectivity, so data security is of increasing importance.

In general, many people get nervous about dynamic memory allocation for these types of applications. It's possible to justify some, but it's best to minimize it where possible.

We do not have a typical operating system. Only an RTOS kernel. And the application program is restricted to a single thread with a fixed update interval. There is no heap for dynamic memory allocation. Some use is made of memory pools with a fixed allocation size, such as for communications buffers.

Controller resources are limited and seem always to be less than needed. So it's critical to optimize memory use and execution speed.


Here's more detail about what I'm hoping to accomplish:

1) Describe a "function block" interface in the form of a hierarchical list.
Individual lists are effectively specified by some form of scripting such as:

List myList("tagName1")
Item myItem("tagName2")
myList AddItem(myItem)
List otherList("tagName3")
myList AddItem(otherList)

Each List controls access to its data (and sub-lists). Each list item (data value or sub-list) is accessed only through its parent list. Most of the code to manage the hierarchy is shared by an embedded application, a PC "Application Builder" and a PC "Service Interface" application.

My original question was about statically allocated arrays of values of specific types. The lists described here are all references to the values allocated in those arrays, including values of type List.

2) Add function blocks to an application (using the Application Builder) by selecting them from libraries. The interface of each block is added to a "Data Manager" and an "Update" function is added to a "Process Manager", which is also a hierarchical list that effectively specifies the execution sequence of all functions.

A list of Update functions is easy, because all are "void Update(void)". No function arguments or return values are needed because the function's local values are all referenced in the data hierarchy.

The organization of data into a hierarchy allows the Application Builder program to display the interconnections of any function and provide multiple browser windows focused on different parts of the hierarchy. Connections are examined or changed by drag-and-drop. Constants can be substituted for values and values can be tagged for backup in nonvolatile memory (in the embedded application).

The PC Application Builder allows configuration of access rights as well as specification of I/O connections. Input 1 of Block A references the same value as Output 2 of Block B. The blocks can even share whole sub-sets of data. For example, four instances of a function block might be related to four wheels of a vehicle. When the blocks are added to the application, a list of parameter values is deleted from the interfaces of three blocks and replaced by a reference to the fourth list. (Potential issue: which data is allocated by a function block and which by the interface?)

Once the pattern is established, the definition of an application is reduced simply to data... and of course, the individual functions. Since the function blocks all come from libraries, it also takes only data to identify them.

3) When an application is running in an embedded controller, the Data Manager provides access to all interface values in the application and can present them, via a PC Service Tool, much as Windows Explorer presents folders and files on a hard drive. (FYI: Communication with external devices is via CAN bus.)

My original thoughts were to use dynamic allocation and even write the "script-like" instructions (example above) as straight C++ object allocations and member function calls. But since I will need a PC front-end application anyway, and will have all information available at compile time, it seems like static allocation is possible. Part of the configuration that's done with the Application Builder is to specify any potential for dynamic addition of some feature.

All of this leads to an ability to reuse software and track where specific functions are used. Only versioned, documented, tested functions, that are selected from a library, can be used. Complete sub-systems of functions can be saved and reused. Each embedded application has its own local library for "interstitial" functions that support interconnections, such as (C = A + B) to make a function input from the sum of two function outputs. The local functions can also be highly complex, and have their own documentation.

I hope you're finding this interesting and are willing to contribute some further thoughts. If I'm trying to "design a perpetual motion machine", please let me know.

[helios]

I figured it'd be an embedded system, although this is the first time I've seen C++ used in an actual real-time application.

The lists described here are all references to the values allocated in those arrays, including values of type List.

This sentence makes no sense to me. Is this what you meant to say?
"The lists described here are all lists of references to the values allocated in those arrays. The values in those arrays may include values of type List."
This sounds somewhat like what I wrote above with Listable. You have an abstract type Listable that behaves like a sequence (i.e. has length and can be indexed) and contains elements of heterogeneous types.

The organization of data into a hierarchy allows the Application Builder program to display the interconnections of any function and provide multiple browser windows focused on different parts of the hierarchy.

I believe I've been following up to this point. I don't see how you put the interfaces of the function blocks in a hierarchy. Take for example the expression for the quadratic formula: (-b +- sqrt(b^2 - 4*a*c)) / (2*a). Translated into function block language, that could be expressed as

input[b]                     -> invert_sign   -> temp[0]
input[b]                     -> square        -> temp[1]
(4, input[a])                -> multiply      -> temp[2]
(temp[2], input[c])          -> multiply      -> temp[3]
(temp[1], temp[3])           -> subtract      -> temp[4]
temp[4]                      -> sqrt          -> temp[5]
(temp[0], temp[5])           -> plus_or_minus -> (temp[6], temp[7])
(2, input[a])                -> multiply      -> temp[8]
(temp[6], temp[7], temp[8])  -> double_divide -> (result[0], result[1])

So, by this example, the interfaces would be input[a], input[b], input[c], temp[0] through temp[8], result[0], and result[1]. How does that fit into a hierarchy?

The PC Application Builder allows configuration of access rights as well as specification of I/O connections.

Access rights? I assume that has nothing to do with the actual computation described by the interconnection of function blocks.

Potential issue: which data is allocated by a function block and which by the interface?

Well, presumably no data is allocated by an interface. An interface is just a list of labeled values.

Thus far, you haven't said anything that eliminates the solution I mentioned earlier. If so desired, dynamic allocation can be prevented:

static char *big_chunk[known_size];
Node *root = (Node *)big_chunk;
root->left = (Node *)(big_chunk + 12);
root->right = (Node *)(big_chunk + 24);
root->left->left = (Node *)(big_chunk + 100);
//etc.

return root;

The initialization routine can also be avoided if the address of big_chunk is knowable at compile time (by filling the static buffer with valid pointers).

[dhayden]

It sounds to me like you need an abstract Component class with a virtual Update() method, probably a toHTML() method to generate HTML to display on a web page, etc. Then you have a List class that is itself a Component. It contains a list of pointers to Components. The Component provides all the interface functionality that you need. Then you can derive classes for the individual things that get updated/monitored.

[NorseMN]

Yes this is for embedded systems programming, where it's historically unusual to use C++. But "embedded systems" covers a broad range of applications. Some segments have embraced C++ for many years. Others still prohibit it. My primary goal is to use templates, rather than maintain a set of handcrafted modules for each data type. Depending on how things work out, it might be possible to use C++ more extensively.

I'm happy to see any interest in my issues and I thank you for your responses. I hope the novelty of this endeavor keeps you interested.

After reading the prior response from Helios, I realized that I needed to broaden the description of my concept. I (foolishly) entered it as a new topic with with (Part 2) appended to the same topic title.

Fortunately, a response from TheIdeasMan straightened me out. So I'll try to move forward from here. But it might help if you find and read the (Part 2) posting. It shows some example code that I got to run and poses some questions.

As I expected, my world differs vastly from the world of the typical C++ forum member. Let me see if I can translate. I'll start with the quadratic equation example from Helios. If this were expressed as a function:

 int QuadFunc(int a, int b, int c)
{
     return (-b +- sqrt(b^2 - 4*a*c)) / (2*a)
}

This function is wrapped by code that adapts it to my "Data Manager" concept.
Assume that a code generator has statically allocated some resources, such as:

DataTyp<int> ArrayInt[4];    // Allocation of int data.
DataTyp<List> ArrayList[4];    // Allocation of List data.

List Root;    // Effectively a reference to ArrayList[0].
List QuadInterface;    // Effectively a reference to ArrayList[1].
List Inputs;    // ref to ArrayList[2].   Referenced by QuadInterface[0].
List Outputs;    // ref to ArrayList[3].  Referenced by QuadInterface[1].

ItemRef a;    // ref to ArrayInt[0].   Referenced by Inputs[0].
ItemRef b;    // ref to ArrayInt[1].   Referenced by Inputs[1].
ItemRef c;    // ref to ArrayInt[2].   Referenced by Inputs[2].
ItemRef result;    // ref to ArrayInt[3].   Referenced by Outputs[0]. 

The code generator also creates a wrapper function, such as:

void QuadWrap(ItemRef r)     // called with r = QuadInterface.
{
    r.Inputs.result = QuadFunc(r.Inputs.a, r.Inputs.b, r.Inputs.c);
}

Clearly, the above example is just pseudo code.
The the term "reference" is used loosely here. Not necessarily the specific C++ meaning.

My comment about allocation by the interface was misleading.
The actual allocated values in the above example are all in the two "DataTyp" arrays.
These arrays are allocated by a code generator that accounts for all interfaces in an application.
This was clearly not obvious in my prior post. (Sorry about that.)
At the time, I was considering whether data might be allocated locally in the wrapper interface code.
After composing the above example, it seems like that might not be necessary.
To do that, I'd need a DataTyp<int*> array to reference a pointer to an int allocated outside the DataTyp<int> array.
There are likely many cases I've not yet considered. So I'm keeping an open mind.

It might be useful if static data, allocated within the wrapped function, can be accessed through the Data Manager hierarchy. If so, it would be necessary for the wrapper to copy them to a list of output values.
That means a duplication of storage and a waste of memory.

In outline form, the interface to the QuadWrap example function is:

Root
  QuadInterface
    Inputs
      a
      b
      c
    Outputs
      result

The Root] list is actually part of the application, which includes QuadInterface as an item.
There would also be a Process Manager with a hierarchical list of function pointers.
DataTyp<List> ArrayFunc[1]; // Allocation of a List of function pointers.
In this example, ArrayFunc[0] points to [b]void QuadWrap(ItemRef r).

This concept also requires two Windows applications that are much more conventional.
- Application Builder
Selects functions from libraries, interconnects interfaces and sets execution sequence.
Generates the code for the embedded controller.

- Service Tool
Connects to a running embedded application.
Allows user to browse the hierarchical data for observation, logging and editing.

These applications can use conventional C++ with few limitations.
But... the more code they share the better.
I expect that code for iterating the hierarchy values can be common to the PC and embedded applications.

It's possible to use a "path" to any item in the hierarchy, from the root list.
For example: Root\QuadInterface\Outputs\result.
Equivalently, this is a sequence of List subscripts: ArrayList[0] \ ArrayList[1] \ ArrayList[3] \ ArrayInt[3].
A path composed of text labels is used to initially access a list or list element.
Access is managed by the List class, which controls access to its elements.
Once access to any path endpoint is established, further access is direct, using <typ>[num].
This provides a direct reference to the data allocated in the array of a specified type.
In the embedded application, the path is simply a sequence of numbers: {0,1,3,3}.

As I mentioned in my (Part 2) topic, I originally planned to reference an allocated value by {typeNumber, instanceNumber }. (The ItemRef type in the above example.) But I found no way (short of a switch block) to select an array using typeNumber.
I think now that I might get by with a typed value that contains only instanceNumber. The type would associate it with the correct array of allocated values through template generated function overloading.

This should be more than enough to generate some new questions.
I don't expect anyone to "do my homework".
But questions, suggestions and sanity checks are greatly appreciated.
Just describing this to others (who can understand it) is an excellent exercise for me.

[dhayden]

I think you're making this far too complicated.

How will you explain all of this to a new developer? How long will it take for them to understand what you've done?

Using templates in an embedded system runs the risk of code bloat: you may end up with lots of instantiations of the code when a small change could reduce it to a few.

Keep it simple. Isn't there an easier way to do this?

[NorseMN]

Maybe the scope of my concept is just too broad to explain. But I'll give it another try.

I'm trying to create a system with an IDE that allows low skilled users to select function blocks from libraries and arrange them to create an embedded application. Actually, any skill level user can make a basic outline of an application that identifies the major components. This outline acts as a specification for the software. Most often, a higher skilled programmer is involved before the software is finished. They use the same system to fill-in lower level function blocks that are beyond the scope of specified features. The higher skill level required to fill-in the details is related more to application domain knowledge than to programming skill.

WARNING, Marketing pitch: Ultimately, the software is literally built directly from the detailed specification.

One goal is to maximize re-use of tested and documented function blocks. These function blocks are each written independently by various people and potentially in several languages. Typical languages are C, or a proprietary graphical language, or a family of industrial languages under the IEC 61131-3 standard. (The best known product supporting this standard is called CODESYS.) Ultimately, it all turns into generated C code.

Many customers have legacy software, proven in use, that could be placed in function wrappers that adapt their interface to fit into this system. Each wrapped function block is then added to a library.

An IDE application running on a PC allows the user to select blocks and add them to the application. The interface of each block is specified in an outline format. As each block is added to the application, its interface is added to a master outline and its "Update" function is added to a "Process List".

The IDE allows the user to drag-and-drop interface values from one point to another in the hierarchy to make connections. The user also controls the placement of the Update functions within the Process List. This controls the execution sequence. (e.g. functions that read input signals run before functions that calculate output commands.) The Process List is hierarchical so that sub-lists of function blocks can be re-used as easily as individual function blocks. The entire list of functions is executed once per "update". An update interval is typically 1 to 10 ms, and includes time for system functions to run. (Hard real time.)

When all is arranged satisfactorily, the IDE generates the code for the application program. It also writes information (such as text names of Lists and Signals) to external files. The files are shared with a Service Tool application that also runs on a PC. This tool communicates with the embedded program through a "Data Manager" that provides access to the hierarchy of values that comprise the interfaces of the function blocks. The external text files can be translated into different languages so the presentation of data by the Service Tool can be customized for different countries. The Data Manager is "system code" that's linked into every application. It's effectively an iterator of the hierarchy of data.

The only developers who would work on this are the ones that create it in the first place. And of course, anyone who maintains and enhances it, because we all know that software is never done. Think of this more as development of an IDE and a code generator. This is NOT something that end users would modify, or even be able to see.

Right now, I'm trying to attack it from the perspective of the code that would be generated and compiled to run in an embedded controller. I'd like to hand-craft a small example program and verify that I can build it with the GCC compiler version used with our controllers, and get it to run. This will help me evaluate what works. I must also consider how the Application Builder and Service Tool programs will work and how the code generator will work.

I think it would help a lot if someone looks at the code I posted separately under the title List of generic references to mixed types (Part 2) and answer the questions I asked there. (Yes. It was a mistake to enter that as a separate post. Sorry about that.)

Here's a link: http://www.cplusplus.com/forum/general/196380/#msg943199