Array of variable length arrays in C

[Qaanol]

I have a C project (actually Objective-C, but my question is about C) where I need to store a 2D array in contiguous memory. The numbers of rows and columns are known only at runtime, not at compile time.

One approach is to declare a flat 1D array and manually index into it:

Code: Select all

int *v;                                  // At global scope
v = malloc(nrows * ncols * sizeof(int)); // In a function
v[row*ncols + col];                      // Somewhere else 

But that is annoying and error-prone. What I’m currently doing is declaring a pointer to an incomplete array type and casting it before use:

Code: Select all

int (*v)[];                              // At global scope
v = malloc(nrows * sizeof(int[ncols]));  // In a function
int (*x)[ncols] = v;                     // Somewhere else
x[row][col]; 

This is much clearer to use. It would be nice if I could declare it as

Code: Select all

int (*v)[ncols];                         // At global scope
 

But that’s impossible because ncols does not have a value at the time of the declaration. However, the value of ncols never changes after it is set (it is a local variable in an Objective-C class, which is set on init and never changed), so it would be nice if I could make the cast “automatic”.

I could create a macro, or even a macro function, as:

Code: Select all

// At global scope
#define cast_v ((int(*)[ncols])v)
#define cast(A) ((int(*)[ncols])A)

// Somewhere else
cast_v[row][col];
cast(v)[row][col]; 

But those just seem hacky. Is there a better solution?

[Diemo]

Use FORTRAN?

[hotaru]

if ncols never changes once it's set, why not put the declaration after ncols is set?

[Qaanol]

Because both the array and ncols are member variables of an Objective-C class. They both have to be declared in the definition of the class, but they aren’t given values until the init method for instances of that class.

[WanderingLinguist]

if ncols never changes once it's set, why not put the declaration after ncols is set?

I don't think that works at global scope.

If it was C++, it would be easier. I don't know of any clean way to accomplish this in C. I guess you could have accessor functions to get/set an array element? (This also gets you bounds checking if you want it). There's a small performance hit which may or may not matter depending on what you're doing with the array. Personally, if performance isn't an issue, I'd go with get/set functions. (Even if performance is an issue, you can always inline them or change them to macros in the release build, and you still get the benefit of bounds checking). Again, it kind of depends what you're using it for.

[Thesh]

Yes, that is the way to do it. Create a struct with three properties: ncols, nrows, and items, where items is a pointer, and then have getter/setter functions to access the elements by column and row indexes.

[Qaanol]

Thanks. My Objective-C class is essentially playing the role of such a struct, so I’ll just stick with casting the incomplete array pointer before use.

[Tub]

IMHO your first example is the cleanest way to do it. It may be a bit redundant to write, but it's a LOT easier to read, understand and verify than the second. I'm also pretty sure that the compiler has more optimization potential when presented with clear indexing rules instead of elaborate pointer arithmetic.


I'm working on a project that needs to pass dynamically sized 2D-arrays to openCL kernels (which are C only, no C++ features). A kernel looks somewhat like this:

Code: Select all

__kernel void do_stuff(int *foo_data, int foo_width, int foo_height, int *bar_data, int bar_width, int bar_height) {
  // now do something with the arrays
} 

Lacking C++ features, all solutions will be ugly, but we settled on using a macro.

Code: Select all

#define R(n,x,y) n ## _data[(y) * n ## _width + (x)]

R(foo, x, y) = R(bar, y, x)
// expands to
foo_data[y * foo_width + x] = bar_data[x * bar_width + y]
 

Needless to say, you shouldn't use such a macro in any global scope, but it's probably ok to use for the implementation of an internal data structure, if you think that repeatedly typing out the formula for 1d indexing is error prone. Then again, are you typing out the indexing formula more than twice? You'd only need to implement get(x,y) and set(x,y,value) and then use those for everything else.

[Derek]

EDIT: Nevermind, I realize my solution doesn't work because VLAs only work in function scope in C.

[Qaanol]

Thanks Tub, I liked the incomplete array type because it requires a cast to access the array elements. But if you’re right about direct access to a flat array being faster, I can work with that.

[Tub]

If performance is going to be the deciding factor, then implement both and do some benchmarks.

All I can tell you is that I tried a few times to "help" the compiler by replacing indexing arithmetic with pointer tricks, but all I managed to do was to confuse the compiler into producing less optimized code.


btw, because I just stumbled upon the code, JavaScript doesn't have any 2d-arrays^[1], so I implemented something similar for a little game I wrote.

Code: Select all

    function TwoDArr(width, height) {
        this.width = width;
        this.height = height;
        this.cells = width*height;
        this.data = [];
        this.clear(false);
    }

    TwoDArr.prototype.clear = function(value) {
        for (var i=0;i<this.cells;i++)
            this.data[i] = value;
    }

    TwoDArr.prototype.set = function(x, y, value) {
        this.data[y*this.width + x] = value;
    }

    TwoDArr.prototype.get = function(x, y) {
        return this.data[y*this.width + x];
    }

    TwoDArr.prototype.getSafe = function(x, y, _default) {
        if (x < 0 || y < 0 || x >= this.width || y >= this.height)
            return _default;
        return this.get(x, y);
    }

    // ... other helper methods

    // count occurrences of a certain value within a rectangle, specified by center and radius.
    // implemented without accessing this.data[] directly.
    TwoDArr.prototype.countInRect = function(cx, cy, radius, comparevalue) {
        var count = 0;
        var rect = {
            x1: cx-radius+1,
            y1: cy-radius+1,
            x2: cx+radius-1,
            y2: cy+radius-1
        }
        for (var x=rect.x1;x<=rect.x2;x++) {
            for (var y=rect.y1;y<=rect.y2;y++) {
                if (this.get(x, y) == comparevalue)
                    count++;
            }
        }
        return count;
    }
 

It has a few more helper functions, but the important thing is that the indexing formula is used in no more than two locations. I don't think it's as "annoying and error-prone" as you assume once you accept that you want to use a get() and a set() method to access elements.

Basing it on a 1d array also makes location agnostic code like clear() easy to write, and as an added bonus it'll automatically traverse the memory in a cache-friendly way.


[1] /edit: as Flumble below me pointed out, in JavaScript you can have an array of objects with each of those objects being another array, but that has an entirely different set of problems. For the use cases in my game, mapping to a 1D array seemed the least painful approach. And, considering that this topic is about simulating a dynamic 2D array with a 1D array, I thought the code may be relevant, even if in another language.

[Flumble]

[edit] Hey, this isn't the fleeting thoughts topic [/edit]

How do you mean Javascript doesn't have 2D-arrays? It's true that you can't enforce the size without helper functions (or using typed arrays), but you can easily make an array of arrays:

Code: Select all

/**
  * Array.create(sizesArray, optional initialValue, optional callback,
  *    optional thisArg)
  */
Array.create = function(sizesArray, initialValue, callback, thisArg) {
   if (sizesArray.length == 0)
      return callback ? callback.call(thisArg || this, initialValue) : initialValue;

   var array = new Array(sizesArray.shift());
   
   for (var i = 0; i < array.length; ++i) //.map and .forEach won't work
      array[i] = Array.create(sizesArray.slice(), initialValue, callback, thisArg);

   return array;
}