#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Posts
    2
    Rep Power
    0

    Question multi dimensional array, memory allocation


    Hi,
    I have a problem which i don't know exactly what it is.. So the subject of the message is also abit confusing..
    I describe a multidimensional (2D) array staticly. I have one of the dimensions large (~200 000) and the other is 3. It is for handling the 3D coordinates of a geometry.
    #define size 200 000
    ...
    double marray[size][3];
    ...
    but i have 10 of this dimensional arrays.

    During compilation there is no error but at runtime i get a segmentation error. ( And when i reduce the size to e.g. 60 000, it compiles and runs normally...
    Is there somehow limitations in C to describing the variables?? How should i handle this?

    Second thing is: In the same program i want to describe these multidimensional arrays dynamically with MALLOC. Since i don't want to copy and paste the same procedure for every array i want to write a function to do this. I wrote this function and call this function from the main function. But it does not work... i think i don't know how to send the **pointer to a function.. I fsomeone has exprience with it, can you please help me...


    #include<stdio.h>
    #include<math.h>
    #include<stdlib.h>
    main()
    {


    int size1=65000,size2=3;
    double **zer;



    createmarray(size1,size2,zer);
    /*
    * ..
    * do whatever i want.....
    * ....
    * */

    freemarray(size1,size2,zer);

    return;
    }


    void createmarray(int size1, int size2, double **xyz)
    {

    int i; // index

    MALLOC(xyz, sizeof(double *) * size2);
    for (i = 0; i < size2; i++) {
    MALLOC(xyz[i], sizeof(double) * size1);
    }
    return;
    }

    void freemaray(int size1, int size2, double **xyz)
    {

    int i; // index

    for (i = 0; i < size2; i++) {
    free(xyz[i]);
    }
    free(xyz);


    return;
    }



    Thanks in advance..
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Jun 2003
    Posts
    705
    Rep Power
    12
    I'm a C++ programmer, so I bite my lip to keep from preaching
    about C++ containers or the problems of C. This I know like my
    signature, though.

    Depending on where you placed it, the "double marray[size][3]"
    where size = 200000 is 4.8 Mbytes. That could have been on the
    stack, which might not be tolerated ;)

    You've already figured out that dynamic allocation is required.

    Think on this; it's just a block of RAM. That multidimensional
    array may be coded [size][3], but with pointers you could even
    reference it as if it were [3][size]. That's not an advantage,
    it's an insight. Take this for example.

    double *marray = (double *) malloc( size * sizeof( double ) * 3);


    It's only a block of ram 3 times the size of a list of doubles
    as long as the value of size. With that, you can reference entries
    in the array in "patches" of 3,

    double x = marray[1];
    double y = marray[2];
    double z = marray[3];


    Ever third entry is an x, every third a y, every third a z.

    If you made a 3dpoint structure, like

    struct point
    {
    double x;
    double y;
    double z;

    };



    Then used the "confusing" (sorry, C++ dude here) pointer things
    you can end up doing in C, this becomes possible.


    point * p= (point *)marray;

    This cast makes marray look like to an array of point structs.

    Now, a double on the PC is usually 8 bytes long, or perhaps
    the compiler thinks in 80 bit doubles, then they're ten.

    The point struct would be the size of 3 doubles. When you "increment"
    the pointer to a double, the memory value under the hood moves
    forward by one double, or 8 bytes (perhaps 10 for an 80 bit float).

    When you increment the value of the struct point pointer, it increments
    the size of a point struct, or 3 doubles. This creates the same effect
    as your array of [size][3].

    For example, marray[p][2] is the same as (pts+p)->z.

    In fact, in the assembler, to compute the address of an entry in that
    2d array, the compiler will make the CPU multiply 3 by the entry in the
    first dimension by the size of the item (a double). That gives the "row"
    position, then adding the second subscript of the array * sizeof double,
    to get the column on that row.

    The struct point does that by always giving you access to x,y and z
    without a recalculation of the row by column position in the array.

    (Now all you seasoned programmers recognize that the cast I suggested may cause problems depending on the memory alignment setting of the compiler. From the standpoint of theory, this is instructive in order to recognize the notion of "overlaying" the struct's layout over the memory occupied by the array of doubles, in order to structure how it's referenced in code, putting things under better control - it's not something you'd want to do in practice, but even MS does stuff LIKE this in it's BITMAPINFO mess - allocates it a one thing, refers to it as another - and they get away with it because the take control of some compiler switches that control memory alignment. By allocated with malloc(sizeof(struct point) * size) instead, things make more sense).



    Now consider this:


    for a single dimension array of doubles,

    double *sarray = malloc( size * sizeof(double) );

    I can reference elements i in the array with;


    double x = sarray[i];

    double y = *(sarray + i);

    Which is actually the same thing, just stated two different ways. Likewise,

    double *marray = malloc( sizeof( double ) * size * 3 );

    Allows me to reference rows and columns in a 2d array of doubles with


    double x = *(marray + (row * 3) + column);


    That is, column being either x, y or z in positions 0,1 or 2 of the row.

    This works because, the malloc is for 3 times the "size" parameter by
    the size of double, and the row * 3 + column is pretty much what the
    compiler does to find

    marray[row][column];


    Then, too

    struct point *pts = (struct point *) malloc( size * sizeof( struct point ));



    Gives you the same thing. Here;

    pts[2].x, pts[2].y and pts.z are one point, instead of marray[p][0], marray[p][1], and marray[p][0], which isn't nearly as meaningful
    to read.

    To more directly address the lower part of your question, though, in order for a function to modify the content of your pointer,
    you need to pass it the address of the pointer. Odd as this seems at first, consider this;



    double *marray = NULL;


    makearray( &marray, size, 3 );

    works if


    void makearray( double **array, int sizerow, int sizecolumn)
    {
    *array = (double *)malloc( whatever );
    }



    Here,the function makearray has a pointer to the double * (not
    a pointer to a double, the pointer to a double pointer), and
    can store something where it points to, a double (or an array of doubles if so allocated).


    In your example, you're declaring a pointer to a double *, then
    passing it to the function which accepts the same, which matches, but the function's pointer is a copy, so any change you make to
    it is local to the function, and isn't witnessed by the calle.

    In C++ we'd use

    void makearray( double *&array)


    This way, changes made to array within the function are retained
    in the caller, but this is a reference, which under the hood is like
    the pointer to an object in the sense that changes to it are made
    such that the calle "sees" the change. For example,

    void func( int &n)
    {
    n = 0;
    }


    The calling code will retain any change to n, just as if it had been a "return" value, because what's passed as a reference.

    In C (assuming you're using a genuine C compiler, not just
    writing in C++ as C), you must use the ** instead.

    Now, the address of a double ** is a double ***.

    For that, C not having references, you need

    void makearray( double ***array);

    the caller would issue makearry( &zer ), and the calle would need
    to use

    *array = (double **)malloc( size......

    to alter the "contents" of the double ** identified by the location
    in array (a double ***), or the address of the double **.


    You correctly recognized, though, that this is now a pointer to
    an array of pointers, to which you applied 200,000 mallocs in a row,
    which is not efficient in case you didn't notice. You could have
    done the same thing in 1 malloc, instead of 200,000.

    You can get there by simply "agreeing" that every 3rd double is an x, every 3rd a y and every third a z. You can seal the agreement on that decision with a struct, or, as we like to do in C++, a class ;).
    Last edited by jasonvene; June 7th, 2003 at 04:38 AM.

IMN logo majestic logo threadwatch logo seochat tools logo