Array of variable length arrays in C

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3060
Joined: Sat May 09, 2009 11:55 pm UTC

Array of variable length arrays in C

Postby Qaanol » Wed May 13, 2015 5:06 pm UTC

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
= 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
= 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?
wee free kings

User avatar
Diemo
Posts: 393
Joined: Mon Dec 03, 2007 8:43 pm UTC

Re: Array of variable length arrays in C

Postby Diemo » Wed May 13, 2015 5:51 pm UTC

Use FORTRAN? :P
In the beginning the Universe was created.
This has made a lot of people very angry and been widely regarded as a bad move.
--Douglas Adams

User avatar
hotaru
Posts: 1042
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Array of variable length arrays in C

Postby hotaru » Wed May 13, 2015 6:36 pm UTC

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

Code: Select all

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3060
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Array of variable length arrays in C

Postby Qaanol » Thu May 14, 2015 12:15 am UTC

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.
wee free kings

User avatar
WanderingLinguist
Posts: 237
Joined: Tue May 22, 2012 5:14 pm UTC
Location: Seoul
Contact:

Re: Array of variable length arrays in C

Postby WanderingLinguist » Thu May 14, 2015 12:20 am UTC

hotaru wrote: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.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6297
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Array of variable length arrays in C

Postby Thesh » Thu May 14, 2015 1:31 am UTC

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.
Summum ius, summa iniuria.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3060
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Array of variable length arrays in C

Postby Qaanol » Thu May 14, 2015 3:56 am UTC

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.
wee free kings

Tub
Posts: 401
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Array of variable length arrays in C

Postby Tub » Fri May 15, 2015 9:28 pm UTC

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
Posts: 2179
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Array of variable length arrays in C

Postby Derek » Fri May 15, 2015 11:47 pm UTC

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

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3060
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Array of variable length arrays in C

Postby Qaanol » Sat May 16, 2015 1:06 am UTC

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.
wee free kings

Tub
Posts: 401
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Array of variable length arrays in C

Postby Tub » Mon May 18, 2015 8:51 am UTC

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 (< 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.
Last edited by Tub on Mon May 18, 2015 4:46 pm UTC, edited 1 time in total.

User avatar
Flumble
Yes Man
Posts: 2075
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Array of variable length arrays in C

Postby Flumble » Mon May 18, 2015 1:58 pm UTC

[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;
}


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests