How to declare an array of pointers to multidimensional arrays

Question

// LED definitions for each step
static uint8_t route1Step0LedsOn[] = { 0x30, 0xff };
static uint8_t route1Step0LedsOff[] = { 0x26, 0xff };
static uint8_t route1Step1LedsOn[] = { 0x18, 0x45, 0x21, 0xff };
static uint8_t route1Step2LedsOn[] = { 0x56, 0x33, 0x42, 0x31, 0xff };

// First route (consisting of 3 steps + terminator).
static uint8_t* routeLeds1[][2] =
{
    { route1Step0LedsOff, route1Step0LedsOn },
    { NULL,               route1Step0LedsOn },
    { NULL,               route1Step0LedsOn },
    { NULL,               NULL }
};

// Second route.
static uint8_t* routeLeds2[][2] =
{
    // LED elements not shown, but similar to route 1.
    { NULL,               NULL }
};

// Array of routes.
static ??? routes[] =
{
    NULL,
    routeLeds1,
    routeLeds2,
    NULL
};

I'm not sure of the correct type for routes[].

I'd like to know what the ??? should be?

I'm using a micro controller and MUST use arrays in order to force the arrays into flash memory instead of RAM.

Sorry I don't know what that is. I'm using a micro controller, limited RAM, trying to keep all static constants in flash memory — sixeyes, Jan 26 '12 at 01:41
it's boost implementation of n-dimensional array, should compile with (arduino?) g++ — Anycorn, Jan 26 '12 at 02:28
I've edited the post a second time. Can you tell me what the ??? should be? — sixeyes, Jan 26 '12 at 09:54

Seth Carnegie · Answer 1 · 2012-01-26T01:13:18.463

3

You can't convert arrays to "pointers to pointers... to pointers" because they're dereferenced differently; trying to use a multidimensional array as a "pointer to... pointer" to something will cause undefined behaviour the same way dereferencing an invalid pointer would.

In memory, a "pointer to a pointer..." to an object is represented by

a -> b -> c -> ... -> object

Where a, b, c, ..., and object are in completely different parts of memory. To index a pointer, the pointer is dereferenced.

Arrays, however, are stored in a contiguous memory. For instance, int a[2][2] would be

[0,0][0,1][1,0][1,1]

Indexing a multidimensional array does not dereference a pointer, it changes the arithmetic that is used to calculate the offset from the beginning of the array that the desired value is at. The formula would be

address of array + index₁ * sizeof(first dimension) + index₂ * sizeof(second dimension) + ... + index_n * sizeof(object)

Where sizeof(nth dimension) is the size of all the subdimensions put together. For instance with int a[3][2] which is represented by

[0,0][0,1][1,0][1,1][2,0][2,1]

, the index a[2][1] would be

address of a + 2 * (sizeof(int) * 2) + 1 * sizeof(int)

Which, in C++, would be (char*)a + 16 + 4, the last element of the array.

To solve this problem, you need to use pointers only. You should not (and cannot) be storing multidimensional arrays alongside pointers in the same array.

_{I'm having a hard time putting this all into words; if I'm not making sense, please say so.}

edited Jan 26 '12 at 01:13

answered Jan 26 '12 at 00:57

Seth Carnegie

73,875
22
181
249

I'm not sure my intent was clear. I've edited my original post. I'm interested in having an array of routes, but declaring it is the problem. The code posted works but is ugly. I'm sure there's a way to clean up the syntax. – sixeyes Jan 26 '12 at 01:21
@sixeyes by "work" do you mean it compiles, or it runs (and `routes` is used in the active code)? – Seth Carnegie Jan 26 '12 at 01:24
@sixeyes I'm surprised it runs, maybe the compiler is doing something nonstandard to help you out – Seth Carnegie Jan 26 '12 at 01:28
Well as far as I can see it's very similar to Michael Anderson's code so I would expect it to work. – sixeyes Jan 26 '12 at 01:32
1

@sixeyes no, it's quite different; your `routeLeds1`, when used like `routeLeds1[1][1]` will be like `*(uint8_t*)(routeLeds + 1 + 1)` but his will be `*(*(routeLeds + sizeof(ptr)) + sizeof(ptr))` which are quite different – Seth Carnegie Jan 26 '12 at 01:34
OK. I understand why you're confused with my code. I have to declare the arrays in C syntax but to access them I have to do the calculations myself. So the type for routes[] is actually pretty irrelevant to me since I don't access the array via [] etc, I have to use function calls that access flash memory. However I'd like to remove the cast, so how can I declare routes[] so I don't need to cast the values for routes[]. – sixeyes Jan 26 '12 at 03:11

score 1 · Accepted Answer · answered Jan 26 '12 at 18:51

1

Try this:

typedef uint8* Array1; // first column/row
typedef Array1 Array2[2]; // uint* name[2]
typedef Array2* Array3; // get the idea?

// Array of routes.
static Array3 routes[] =
{
    NULL,
    routeLeds1,
    routeLeds2,
    NULL
};

answered Jan 26 '12 at 18:51

Anycorn

50,217
42
167
261

Works a treat. Thanks for the answer. – sixeyes Jan 26 '12 at 22:42

score 0 · Answer 3 · answered Jan 26 '12 at 01:14

0

Your problem is the multidimensional array:

If you need to go the array route, you can just add an extra step:

static uint8_t route1Step0LedsOn[] = { 0x30, 0xff };
static uint8_t* route1Step0[] = { NULL, route1Step0LedsOn };
static uint8_t** routeLeds1[] = { route1Step0 };
static uint8_t*** routes[] =
{
    NULL,
    routeLeds1,
    NULL
};

If some of the arrays are fixed lengths, it may be possible to clean some of this up a little.

But IMO this is getting pretty ugly and could do with some real structs, rather than raw arrays.

answered Jan 26 '12 at 01:14

Michael Anderson

70,661
7
134
187

That's how I originally wrote it, but it was harder to maintain. Sadly none of the arrays are fixed in length. – sixeyes Jan 26 '12 at 01:18
I'm using a micro controller and using structs will use RAM whereas the current form is entirely in Flash memory. – sixeyes Jan 26 '12 at 01:19
@sixeyes are you sure using structs will use RAM? Is that specific to the C++ compiler of the microcontroller you're using? – Seth Carnegie Jan 26 '12 at 01:23
Not certain, but the only way of accessing flash is a byte at a time, so I'd assumed that meant structs would end up in RAM. – sixeyes Jan 26 '12 at 01:25
No, it's 2 bytes. Could the use of a typedef help? – sixeyes Jan 26 '12 at 01:42

score 0 · Answer 4 · answered Jan 26 '12 at 01:40

If you're not tied to ussing arrays for some technical reason, you could change to use a structure like this: (Note if you're using C++11, then the constructors and construction can be made a lot nicer). You'll also need a make_vector helper, of which there are several floating around, if you want a nicer construction.

struct LedList
{
   LedList( const std::vector<uint8_t> & v ) : leds( v ) {}
   std::vector<uint8_t> leds;
};

struct LedStep
{
  LedStep( const & LedList on_, const & LedList off_ ) : on_leds(on_), off_leds(off_) {}
  RouteStepLedList on_leds;
  RouteStepLedList off_leds;
};

struct LedRoute
{
  LedRoute( const std::vector<LedStep> & steps_ ) : steps(steps_) {}
  std::vector<LedStep> steps;
};

struct Route
{
  Route( const std::vector<LedRoute> & routes_ ) : routes(routes_) {}
  std::vector<LedRoute> routes;
};

//All routes
Route r( make_vector<LedRoute>()( 
    //First route
    make_vector<LedStep>()(
      //First step of first route 
      LedStep( 
        make_vector<uint8_t>()( 0x30 ),
        make_vector<uint8_t>()( 0x26 )
      ) )(
      //Second step of first route
      LedStep(
        make_vector<uint8_t>(),
        make_vector<uint8_t>()( 0x18 )( 0x45 )( 0x21 )
      ) )(
      //Third step of first route
      LedStep(
        make_vector<uint8_t>(),
        make_vector<uint8_t>()( 0x56 )( 0x33 )( 0x42 )( 0x31  )
     ) ) ),
     //Second route.
     make_vector<LedStep>()(
       //First step of second route
       LedStep( 
         ...
       ) ) (
       //Second step of second route
      ...
);

Sadly no STL and I'm tied to using arrays in order to keep them in flash. In fact I have to stick extra keywords in the actual code to place the arrays in flash memory. — sixeyes, Jan 26 '12 at 01:45

How to declare an array of pointers to multidimensional arrays

4 Answers4