How to specify the size of a class array ?

Hi all,
I have a class that contains an array. Since there's only 2KB of RAM, I don't want that array to be bigger than what's strictly needed, but I don't want to use dynamic allocation either.
Unless the client code supplies the class constructor a pointer to an already allocated array, the class must declare its array size in advance.
If the class is to be used as a library, a reasonable default size must be specified. If a sketch needs more room, one has to modify the library source. Ugly.

Two solutions come to mind: templates and #define.

Using templates

#ifndef _BOARDS_H
#define _BOARDS_H

template <int MAX_BOARD_CNT>
class Boards {
public:
    void addBoard(int boardId) {
        if (_numBoards < MAX_BOARD_CNT - 1) {
            _boardIds[_numBoards] = boardId;
            _numBoards++;
        }
    };
    
    int getMaxBoardCnt() {
        return MAX_BOARD_CNT;
    };
    
    int getNumBoards() {
        return _numBoards;
    };
    
private:
    int _boardIds[MAX_BOARD_CNT];
    int _numBoards;
};

#endif

The client code looks like this:

#include "Boards.h"

Boards<100> boards;

int freeRam () {
    extern int __heap_start, *__brkval; 
    int v; 
    return (int) &v - (__brkval == 0 ? (int) &__heap_start : (int) __brkval); 
};

void setup() {
    Serial.begin(115200);
    Serial.println(boards.getMaxBoardCnt());
    Serial.println(boards.getNumBoards());
    boards.addBoard(5);
    boards.addBoard(10);
    Serial.println(boards.getNumBoards());
    Serial.println(freeRam());
}

void loop() {
}

Using #define

#ifndef _BOARDS_H
#define _BOARDS_H

#ifndef Boards_MAX_BOARD_CNT
#define Boards_MAX_BOARD_CNT 10    // default value
#endif

class Boards {
public:
    static const int MAX_BOARD_CNT = Boards_MAX_BOARD_CNT;
    
    void addBoard(int boardId) {
        if (_numBoards < MAX_BOARD_CNT - 1) {
            _boardIds[_numBoards] = boardId;
            _numBoards++;
        }
    };
    
    int getMaxBoardCnt() {
        return MAX_BOARD_CNT;
    };
    
    int getNumBoards() {
        return _numBoards;
    };
    
private:
    int _boardIds[MAX_BOARD_CNT];
    int _numBoards;
};

#endif

The client code is now:

#define Boards_MAX_BOARD_CNT 100    // if this is omitted, the library hardcoded default value is used
#include "Boards.h"

Boards boards;

int freeRam () {
    extern int __heap_start, *__brkval; 
    int v; 
    return (int) &v - (__brkval == 0 ? (int) &__heap_start : (int) __brkval); 
};

void setup() {
    Serial.begin(115200);
    Serial.println(boards.getMaxBoardCnt());
    Serial.println(boards.getNumBoards());
    boards.addBoard(5);
    boards.addBoard(10);
    Serial.println(boards.getNumBoards());
    Serial.println(freeRam());
}

void loop() {
}

So what ?

With 100 elements, the results are:
template: code size = 2592 bytes, freeRam = 1578
#define: code size = 2592 bytes, freeRam = 1578

The template method perhaps looks more elegant, but I don't like the idea of having to put an entire class - declaration and implementation - inside a single .h file.

There might be other issues that a trivial example doesn't touch...

What do you think ?

I have a class that contains an array. Since there's only 2KB of RAM, I don't want that array to be bigger than what's strictly needed, but I don't want to use dynamic allocation either.
Unless the client code supplies the class constructor a pointer to an already allocated array, the class must declare its array size in advance.
If the class is to be used as a library, a reasonable default size must be specified. If a sketch needs more room, one has to modify the library source. Ugly.

After initialization of the class, will the array grow or not?
Is the max size know at the initialization of the class?
// you could first count the boards, and then initialize the class and add the boards one by one

int _numBoards; ==> uint8_t _numBoards; // 1 byte gained :wink:

what is the range of boardID?

  • does it fit in a byte?
  • can negative values occur?
    ==> uint8_t _boardIds[MAX_BOARD_CNT]; possible? // 50% gained

True, if the absolute maximum of 255 items if acceptable, then having _numBoards declared as byte instead of int makes you gain 1 byte. :wink:

As for boardId, that was just an example. The actual size of the array elements is irrelevant here. My question was about how to have an array the exact needed size without touching the library source...

The array size is fixed at compile time because I want to avoid new, delete, malloc and friends.

The array size is fixed at compile time because I want to avoid new, delete, malloc and friends.

Why? It seems that either you should expect the user to specify a size, and make the array(s) that size, OR you should allow for dynamic sizing.

The free() function has some issues. You can avoid them by never calling it, or delete. That is, once an object is created, it persists until a reset is done.

PaulS:

The array size is fixed at compile time because I want to avoid new, delete, malloc and friends.

Why? It seems that either you should expect the user to specify a size, and make the array(s) that size, OR you should allow for dynamic sizing.

I want the user to be able to specify a size. At compile time. Dynamic allocation would mean grow the array as elements are add()ed. String is telling us that kind of functionality is not without problems :wink:

PaulS:
The free() function has some issues. You can avoid them by never calling it, or delete. That is, once an object is created, it persists until a reset is done.

That would bring in a third solution: let the user specify a size by passing a value to the constructor, which in turn would malloc() the array but never free() it. IOW, no destructor method.
This would be acceptable if the class was only used to declare global variables. In fact, I'd find using such kind of classes to declare local variables strange.

String is telling us that kind of functionality is not without problems

The problem is that String instances go out of scope, triggering the destructor which calls delete which calls free(), which has a bug.

By not allowing the array to shrink, you avoid those problems.

This would be acceptable if the class was only used to declare global variables. In fact, I'd find using such kind of classes to declare local variables strange.

What kind of boards does your class refer to? Are local instances of them reasonable? For instance, Serial is an instance of the HardwareSerial class. There is only one of them, so having anything other than a global instance doesn't make sense. Does your board differ?

PaulS:

String is telling us that kind of functionality is not without problems

The problem is that String instances go out of scope, triggering the destructor which calls delete which calls free(), which has a bug.

By not allowing the array to shrink, you avoid those problems.

What about growing the array ? Is it safe ?
That would happen when the user would call addBoard() more times than the available slots in the array.

PaulS:

This would be acceptable if the class was only used to declare global variables. In fact, I'd find using such kind of classes to declare local variables strange.

What kind of boards does your class refer to? Are local instances of them reasonable? For instance, Serial is an instance of the HardwareSerial class. There is only one of them, so having anything other than a global instance doesn't make sense. Does your board differ?

Sorry, I should have called them "items" :slight_smile: It was just an example. They could be anything from a byte to user-defined objects.
But yes, the use case I have in mind is about using the class to declare global variables only.

What about growing the array ? Is it safe ?
That would happen when the user would call addBoard() more times than the available slots in the array.

Until all available memory was used, it is safe.

tuxduino:
I want the user to be able to specify a size. At compile time. Dynamic allocation would mean grow the array as elements are add()ed. String is telling us that kind of functionality is not without problems :wink:

A point of note You can't do that with a #define and the Arduino IDE as you intimated earlier. Only the code in your sketch sees the #define, the library is different compilation unit, and does not see it with the standard arduino make process. (Unless of course, you ask them to inline your code in their .ino or something.)

!c

Ouch! You're right. For the #define approach to work, either the whole class must be in a single .h file (as in the template case) or the #define'd constant must be in a separate .h file that has to be included by both the sketch and the class header file.

Templates are your best bet, none of the side effects of #defines, a template type is bound to its parameters so consider a class:

template< int V > struct Foo{ static const int MyNum = V; };

This struct is global, you are guaranteed that "Foo< 5 >::MyNum" is always the same value, no matter what compilation unit. This may not be the clearest example, if MyNum was equal to something else other than V it would still have the same guarantee.

You can also put the class definition in a cpp file, I'll describe below:

lib.h

template< typename T >
  class Foo{
    public:
      Foo( T t_In );
      T Value( void );
    private:
      T t_Data;
};

lib.cpp

  #include "lib.h"

  template< typename T >
    Foo< T >::Foo( T t_In ) : t_Data( t_In ) {}

  template< typename T >
    Foo< T >::Value( void ){ return this->t_Data; }

This set up will lead to a linker error. This error is because the compilation unit cannot see the definition of the template. To fix this you can do two things: instantiate types where the definition is available, or use the the definition rather than the declaration.

If you know what range/discrete values/types users may select for the template you can instantiate them directly in the cpp ( lib.cpp ) file

//Add instantiations below definitions in cpp file.
template class Foo< bool >;
template class Foo< char >;
template class Foo< long >;

In your sketch you can include the header file and happily use the template with bool, char, and long however int will cause an error.
This is a basic way of stopping programmers from misusing the library with bad inputs.

The other way is simply include the cpp file instead of the header, solving the missing definition error.

Here is my template array class you can give a try:

template< typename _Type, uint16_t _Len > 
  struct MPLArray{
    enum{ 
      Length = _Len,
      Size = sizeof( _Type ) * _Len,
    };
  _Type& operator[]( uint16_t u_Index ) { return this->t_Data[ u_Index ]; }
  operator _Type*() { return this->t_Data; }
  operator const _Type*() const { return this->t_Data; }
  
  _Type t_Data[ Length ];
};	

void loop(){
  MPLArray< bool, 5 > bb = { true, true, true, false, false };
  bool *bp = bb;
  Serial.print( bb[0] );
  Serial.print( *( bp + 3 ) );
  Serial.print( bb.Length );
  Serial.print( bb.Size );
}

You could also create as a variable in a class, or derive a class from it to inherit the functionality.

PaulS:

What about growing the array ? Is it safe ?
That would happen when the user would call addBoard() more times than the available slots in the array.

Until all available memory was used, it is safe.

I should probably RTFM about this :slight_smile: but in the meantime, do you mean realloc() is "safe", i.e. doesn't have problems like free() ?

tuxduino:

PaulS:

What about growing the array ? Is it safe ?
That would happen when the user would call addBoard() more times than the available slots in the array.

Until all available memory was used, it is safe.

I should probably RTFM about this :slight_smile: but in the meantime, do you mean realloc() is "safe", i.e. doesn't have problems like free() ?

Essentially, with the library bug, it's okay to allocate memory as long as you don't expect it back.

realloc calls free if the new chunk size is smaller

@pYro_65

Thank you for you detailed response and for the code.

Out of curiosity, why a struct instead of a class, and why make everything public ? Just asking...

I modified it a bit, included addItem.

MPLArray (modified)

#ifndef _MPL_ARRAY_H
#define _MPL_ARRAY_H

#include <stddef.h>
#include <stdint.h>

template< typename _Type, uint16_t _MaxCount > 
class MPLArray{
public:
    MPLArray() {
        _count = 0;
    };
    
    void addItem(_Type& newItem, bool* itemAdded = NULL, uint16_t* itemIdx = NULL) {
        if (!isFull()) {
            t_Data[_count] = newItem;
            
            if (itemAdded != NULL) {
                *itemAdded = true;
            }
            
            if (itemIdx!= NULL) {
                *itemIdx = _count;
            }
            
            _count++;
        }
        else {
            *itemAdded = false;
        }
    };
    
    bool isFull() const {
        return _count < _MaxCount;
    };
    
    uint16_t count() const {
        return _count;
    };
    
    uint16_t maxCount() const {
       return _MaxCount;
    }; 
    
    uint16_t size() const {
        return sizeof( _Type ) * _MaxCount;
    };
    
    _Type& operator[]( uint16_t u_Index ) {
        return this->t_Data[ u_Index ];
    };
    
    operator _Type*() {
        return this->t_Data;
    };
    
    operator const _Type*() const {
        return this->t_Data;
    };
    
private:
    _Type t_Data[ _MaxCount ];
    uint16_t _count;
};

#endif

Boards.h

#ifndef _BOARDS_H
#define _BOARDS_H

#include "MPLArray.h"

template <int MAX_BOARD_CNT>
class Boards : public MPLArray<int, MAX_BOARD_CNT> {
public:
    Boards() {};

    void addBoard(int boardId) {
         MPLArray<int, MAX_BOARD_CNT>::addItem(boardId);
    };
    
    // other Boards-specific code...
};

#endif

Main sketch:

#include "Boards.h"

Boards<100> boards;

int freeRam () {
    extern int __heap_start, *__brkval; 
    int v; 
    return (int) &v - (__brkval == 0 ? (int) &__heap_start : (int) __brkval); 
};

void setup() {
    Serial.begin(115200);
    Serial.println(boards.maxCount());
    Serial.println(boards.count());
    boards.addBoard(5);
    boards.addBoard(10);
    Serial.println(boards.count());
    Serial.println(freeRam());
}

void loop() {
}

Count = 100

Code size: 2704
Freeram: 1578

WizenedEE:
Essentially, with the library bug, it's okay to allocate memory as long as you don't expect it back.

realloc calls free if the new chunk size is smaller

That would fit my use case, as I don't expect the array to shrink, so probably a malloc() + expand as needed with realloc could be ok.

(I'm thinking about a delItem() method, but that would just "invalidate" an entry or shift everything down 1 position and decrement _count, without shrinking the array).

It's true that using dynamic memory allocation is usually best avoided in embedded systems (see Dynamic Memory Allocation in Critical Embedded Systems | David Crocker's Verification Blog for why). However, allocating dynamic memory using malloc or new in the initialization phase (i.e. in stuff called from setup()) is OK if you never release it.

The template solution is also OK. One issue with using templates in embedded systems is that the code gets replicated each time the template is instantiated, leading to code bloat; but in this case you will only even instantiate the class once, so that doesn't apply.

Have you considered using a linked list instead of an array? That way you don't need to know in advance how many boards there will be. The disadvantage is that you need a little more RAM to store the links.

dc42:
It's true that using dynamic memory allocation is usually best avoided in embedded systems (see Dynamic Memory Allocation in Critical Embedded Systems | David Crocker's Verification Blog for why). However, allocating dynamic memory using malloc or new in the initialization phase (i.e. in stuff called from setup()) is OK if you never release it.

Thank you for that very interesting and informative article.

dc42:
The template solution is also OK. One issue with using templates in embedded systems is that the code gets replicated each time the template is instantiated, leading to code bloat; but in this case you will only even instantiate the class once, so that doesn't apply.

You mean if I instantiate two classes with the same template parameters I have two copies of the same "generated" code ? That's interesting. Going to google a bit about that...

But yes, the idea is to have just one instance of that class per sketch.

dc42:
Have you considered using a linked list instead of an array? That way you don't need to know in advance how many boards there will be. The disadvantage is that you need a little more RAM to store the links.

That's an interesting option. For the use case I'm thinking about I think a statically sized array is a better option though.

  1. Do nothing. Pretend G++ does implement automatic instantiation management. Code written for the Borland model works fine, but each translation unit contains instances of each of the templates it uses. In a large program, this can lead to an unacceptable amount of code duplication.

:astonished:

You mean if I instantiate two classes with the same template parameters I have two copies of the same "generated" code ? That's interesting. Going to google a bit about that...

Nope, standard C++ requires types to be unique, therefore only one definition of code can ever be used to describe a type.

tuxduino:
Template Instantiation (Using the GNU Compiler Collection (GCC))

  1. Do nothing. Pretend G++ does implement automatic instantiation management. Code written for the Borland model works fine, but each translation unit contains instances of each of the templates it uses. In a large program, this can lead to an unacceptable amount of code duplication.

:astonished:

Does not apply here, it is for systems that can have page faults, these models help prevent them. ( page faults can be detrimental to games and such ):

When used with GNU ld version 2.8 or later on an ELF system such as GNU/Linux or Solaris 2, or on Microsoft Windows, G++ supports the Borland model. On other systems, G++ implements neither automatic model.

Only ill formed code will have bloat, there is no reason why common code cannot be placed in a base class and inherited into a non-common template.

The instantiations I posted previously will not increase the size of the program unless you actually use the instantiation, they just allow the compiler to generate object files for the required template types:

template class Foo< bool >;
template class Foo< char >;
template class Foo< long >;

Using initial memory allocation is only of benefit if you require the memory to be un-initialised. Even then a global array/variable is still just as effective.

Out of curiosity, why a struct instead of a class, and why make everything public ? Just asking...

POD/Aggregate types cannot have private or protected members, it makes code easier to read, a one line struct is fairly readable, a class may not be.

C++ is your friend :).

tuxduino:
I want the user to be able to specify a size. At compile time.

I don't see your objection to using malloc then (or new). If it is specified at compile time, you won't change it, therefore you wan't call free() therefore you won't have any problems.

The number of items can be in the constructor (or classname.begin). Then the class allocates exactly the amount of memory it needs, and hangs onto it. No problems.