Go Down

Topic: How to specify the size of a class array ? (Read 2483 times) previous topic - next topic

tuxduino

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

Code: [Select]

#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:

Code: [Select]

#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

Code: [Select]
#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:

Code: [Select]

#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 ?

robtillaart

Quote
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 ;)

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
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

tuxduino

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

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.

PaulS

Quote
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.

tuxduino


Quote
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 ;)


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.

PaulS

Quote
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.

Quote
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?

tuxduino


Quote
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.


Quote
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" :) 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.

PaulS

Quote
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.


drone



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 ;)


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

tuxduino

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.

pYro_65

#10
Dec 02, 2012, 03:04 pm Last Edit: Dec 02, 2012, 03:08 pm by pYro_65 Reason: 1
Templates are your best bet, none of the side effects of #defines, a template type is bound to its parameters so consider a class:

Code: [Select]
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
Code: [Select]
template< typename T >
 class Foo{
   public:
     Foo( T t_In );
     T Value( void );
   private:
     T t_Data;
};


lib.cpp
Code: [Select]

 #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

Code: [Select]

//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:

Code: [Select]
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.

tuxduino


Quote
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 :) but in the meantime, do you mean realloc() is "safe", i.e. doesn't have problems like free() ?

WizenedEE



Quote
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 :) 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

tuxduino

@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)
Code: [Select]

#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
Code: [Select]

#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:
Code: [Select]

#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

tuxduino


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).

Go Up