Dynamically allocating a fixed-size multidimensional array?

Discussion in 'C Programming' started by mx, Apr 16, 2012.

  1. mx

    mx Guest

    Actually, I'm not even sure it's possible to dynamically allocate a
    fixed size one dimensional array.
    So here's the problem:
    I have a type 'board' defined as so:
    typedef char board[8][8]
    and I am supposed to write a function with the following prototype:
    Board *new_board();
    which would require me to use malloc for allocation.
    I've tried many different things that I'd be ashamed to post here but
    have found no solution.
    The problem is that it doesn't seem possible to cast a char* or char**
    to a fixed length array (e.g. char[8] or char[8][8] or board in this case)
    I'll add that this exercise I have been given specifies the 'board' type
    and new_board() function exactly as I have said and I would find a
    workaround if I had the choice.
     
    mx, Apr 16, 2012
    #1
    1. Advertising

  2. mx

    Paul N Guest

    On Apr 16, 8:07 pm, mx <mx@none> wrote:
    > Actually, I'm not even sure it's possible to dynamically allocate a
    > fixed size one dimensional array.
    > So here's the problem:
    > I have a type 'board' defined as so:
    > typedef char board[8][8]
    > and I am supposed to write a function with the following prototype:
    > Board *new_board();
    > which would require me to use malloc for allocation.
    > I've tried many different things that I'd be ashamed to post here but
    > have found no solution.
    > The problem is that it doesn't seem possible to cast a char* or char**
    > to a fixed length array (e.g. char[8] or char[8][8] or board in this case)
    > I'll add that this exercise I have been given specifies the 'board' type
    > and new_board() function exactly as I have said and I would find a
    > workaround if I had the choice.


    malloc returns a void *, there's no need to mess about with char *.

    This works for me:

    #include <stdlib.h>

    typedef char board[8][8];

    board *new_board(void) {
    board *b;

    b = malloc(sizeof(*b));
    return b;
    }

    And it seems to be what you want, though you'll have to decide whether
    to call the type Board or board. And the typedef needs a semicolon.

    Hope that helps.
    Paul.
     
    Paul N, Apr 16, 2012
    #2
    1. Advertising

  3. mx

    mx Guest

    On 04/16/2012 07:23 PM, Paul N wrote:
    > On Apr 16, 8:07 pm, mx<mx@none> wrote:
    >> Actually, I'm not even sure it's possible to dynamically allocate a
    >> fixed size one dimensional array.
    >> So here's the problem:
    >> I have a type 'board' defined as so:
    >> typedef char board[8][8]
    >> and I am supposed to write a function with the following prototype:
    >> Board *new_board();
    >> which would require me to use malloc for allocation.
    >> I've tried many different things that I'd be ashamed to post here but
    >> have found no solution.
    >> The problem is that it doesn't seem possible to cast a char* or char**
    >> to a fixed length array (e.g. char[8] or char[8][8] or board in this case)
    >> I'll add that this exercise I have been given specifies the 'board' type
    >> and new_board() function exactly as I have said and I would find a
    >> workaround if I had the choice.

    >
    > malloc returns a void *, there's no need to mess about with char *.
    >
    > This works for me:
    >
    > #include<stdlib.h>
    >
    > typedef char board[8][8];
    >
    > board *new_board(void) {
    > board *b;
    >
    > b = malloc(sizeof(*b));
    > return b;
    > }
    >
    > And it seems to be what you want, though you'll have to decide whether
    > to call the type Board or board. And the typedef needs a semicolon.
    >
    > Hope that helps.
    > Paul.

    Thank you. I was under the impression that a char[8][8] was not a
    contiguous space and that each b was a pointer to a char[8] that
    needed to be allocated.
     
    mx, Apr 16, 2012
    #3
  4. mx

    James Kuyper Guest

    On 04/16/2012 03:48 PM, mx wrote:
    ....
    > Thank you. I was under the impression that a char[8][8] was not a
    > contiguous space and that each b was a pointer to a char[8] that
    > needed to be allocated.


    A structure like that could be declared in C as follows:
    char (*board[8])[8];

    However, it would be more idiomatic to store 8 pointers to the first
    char of each row, rather than to the entire row:

    char *board[8];

    Either way, it would be a very wasteful way to store 64 chars; each of
    the 8 pointers would, on typical modern machines, take up 4 additional
    bytes. Every access to the array would involve two levels of
    indirection, which is unnecessarily inefficient if the dimensions of the
    array are small and fixed. On the other hand, such a structure would
    make it easy to swap rows: is that something you'll be needing to do
    frequently?
     
    James Kuyper, Apr 16, 2012
    #4
  5. mx

    Joe Pfeiffer Guest

    James Kuyper <> writes:

    > On 04/16/2012 03:48 PM, mx wrote:
    > ...
    >> Thank you. I was under the impression that a char[8][8] was not a
    >> contiguous space and that each b was a pointer to a char[8] that
    >> needed to be allocated.

    >
    > A structure like that could be declared in C as follows:
    > char (*board[8])[8];
    >
    > However, it would be more idiomatic to store 8 pointers to the first
    > char of each row, rather than to the entire row:
    >
    > char *board[8];
    >
    > Either way, it would be a very wasteful way to store 64 chars; each of
    > the 8 pointers would, on typical modern machines, take up 4 additional
    > bytes. Every access to the array would involve two levels of
    > indirection, which is unnecessarily inefficient if the dimensions of the
    > array are small and fixed. On the other hand, such a structure would
    > make it easy to swap rows: is that something you'll be needing to do
    > frequently?


    It's called an Iliffe vector. There have at the very least been
    suggestions that arrays be implemented in exactly that way; the
    wikipedia article claims a bunch of languages (including Java and
    Python) have actually done it.

    If you've got a really, really slow multiplication, it can be a win.
    Not quite sure why it's a win for modern languages, though -- I'd think
    a dope vector would be a better bet.

    None of which has anything to do with C!

    What might have something to do with the OP's homework question, though,
    is the instructor might have asked for it to have been done that way.
    If so, rather than give the answer, I'll just say it can be done with a
    malloc() for the first dimension, and then a bunch of malloc()s for the
    second.
     
    Joe Pfeiffer, Apr 16, 2012
    #5
  6. בת×ריך ×™×•× ×©× ×™,16 ב×פריל 2012 20:07:19 UTC+1, מ×ת mx:
    >
    > I have a type 'board' defined as so:
    > typedef char board[8][8]
    > and I am supposed to write a function with the following prototype:
    > Board *new_board();
    >

    Allocating 2 dimensional arrays gets messy and confusing.

    What you shiuld do is declare a structure

    typedef struct
    {
    char board[8][8];
    } CHESSBOARD;

    Then pass everything around as a CHESSBOARD *. It also means that if you want to tag the board with some extra data, like whether castling is allowed (I think it's not if the king has been in check), ypu can do that easily.
    --
    Play suicide chess. Free game, on my website
    http://www.malcolmmclean.site11.com/www
     
    Malcolm McLean, Apr 16, 2012
    #6
  7. mx

    James Kuyper Guest

    On 04/16/2012 05:12 PM, Joe Pfeiffer wrote:
    > James Kuyper <> writes:
    >
    >> On 04/16/2012 03:48 PM, mx wrote:
    >> ...
    >>> Thank you. I was under the impression that a char[8][8] was not a
    >>> contiguous space and that each b was a pointer to a char[8] that
    >>> needed to be allocated.

    >>
    >> A structure like that could be declared in C as follows:
    >> char (*board[8])[8];
    >>
    >> However, it would be more idiomatic to store 8 pointers to the first
    >> char of each row, rather than to the entire row:
    >>
    >> char *board[8];
    >>
    >> Either way, it would be a very wasteful way to store 64 chars; each of
    >> the 8 pointers would, on typical modern machines, take up 4 additional
    >> bytes. Every access to the array would involve two levels of
    >> indirection, which is unnecessarily inefficient if the dimensions of the
    >> array are small and fixed. On the other hand, such a structure would
    >> make it easy to swap rows: is that something you'll be needing to do
    >> frequently?

    >
    > It's called an Iliffe vector. There have at the very least been
    > suggestions that arrays be implemented in exactly that way; the
    > wikipedia article claims a bunch of languages (including Java and
    > Python) have actually done it.


    There's lots of good reasons for using this technique, in the right
    circumstances. I doubt that an array of char with fixed dimensions of
    8x8 is likely to be one of those circumstances, unless there's a fairly
    common need to quickly swap rows. For an array of that size, the
    benefits of being able to quickly swap rows by swapping pointers are
    likely to be small (they could be negative, depending upon the machine
    architecture), and the costs of using this technique are likely to
    overwhelm those benefits.

    > None of which has anything to do with C!


    How to do it in C is on-topic. Whether it's a good idea to do it in C is
    also on-topic.

    > What might have something to do with the OP's homework question, though,
    > is the instructor might have asked for it to have been done that way.
    > If so, rather than give the answer, I'll just say it can be done with a
    > malloc() for the first dimension, and then a bunch of malloc()s for the
    > second.


    His statement "I was under the impression ..." suggests to me that
    expecting to use such a structure was due to a misunderstanding of how C
    works, on the OP's part. I doubt that it was specified as part of the
    homework problem by the teacher.
     
    James Kuyper, Apr 16, 2012
    #7
  8. On Mon, 16 Apr 2012 14:38:57 -0700 (PDT), Malcolm McLean
    <> wrote:

    >?????? ??? ???, 16 ?????? 2012 20:07:19 UTC+1, ??? mx:
    >>
    >> I have a type 'board' defined as so:
    >> typedef char board[8][8]
    >> and I am supposed to write a function with the following prototype:
    >> Board *new_board();
    >>

    >Allocating 2 dimensional arrays gets messy and confusing.
    >
    >What you shiuld do is declare a structure
    >
    >typedef struct
    >{
    > char board[8][8];
    >} CHESSBOARD;
    >
    >Then pass everything around as a CHESSBOARD *. It also means that if you want to tag the board with some extra data, like
    >whether castling is allowed (I think it's not if the king has been in check), ypu can do that easily.


    Castling is not allowed if either the king or the castle has already
    been moved, if the king is CURRENTLY in check, if there are any pieces
    in the intervening squares, or if any of the squares the king will
    pass over is "under attack" by an opposing piece. As with any move
    involving the king, it cannot end up in check.

    --
    Remove del for email
     
    Barry Schwarz, Apr 17, 2012
    #8
  9. On Mon, 16 Apr 2012 19:07:19 +0000, mx <mx@none> wrote:

    >Actually, I'm not even sure it's possible to dynamically allocate a
    >fixed size one dimensional array.


    Why do you say that. I would guess that well over 90% of the calls to
    malloc are to do exactly that.

    >So here's the problem:
    >I have a type 'board' defined as so:
    >typedef char board[8][8]
    >and I am supposed to write a function with the following prototype:
    >Board *new_board();
    >which would require me to use malloc for allocation.
    >I've tried many different things that I'd be ashamed to post here but
    >have found no solution.


    What problem have you run into using
    board *b_ptr = malloc(sizeof(board));

    >The problem is that it doesn't seem possible to cast a char* or char**


    Since an object of type board does not have type char* or char**, why
    is this even a consideration?

    You can cast an expression of type board to a char* though I don't
    know you would want to. (Some might want to use this char* with
    subscripts 0 through 63 to access the squares on the board but that is
    a questionable (tm) practice.)

    >to a fixed length array (e.g. char[8] or char[8][8] or board in this case)


    While you cannot cast a board*, char*, or char** to an array, you can
    cast it to a pointer to array. Using b_ptr above
    char (*arr_ptr)[8] = (char (*)[8])b_ptr;
    /*actually the cast is unnecessary */
    will let you access the squares of the chess board with
    arr_ptr[j]
    where 0 <= i,j <= 7.

    >I'll add that this exercise I have been given specifies the 'board' type
    >and new_board() function exactly as I have said and I would find a
    >workaround if I had the choice.


    Non-problems don't need workarounds.

    --
    Remove del for email
     
    Barry Schwarz, Apr 17, 2012
    #9
  10. On Mon, 16 Apr 2012 16:19:50 -0700, Barry Schwarz <>
    wrote:

    >On Mon, 16 Apr 2012 19:07:19 +0000, mx <mx@none> wrote:
    >
    >>Actually, I'm not even sure it's possible to dynamically allocate a
    >>fixed size one dimensional array.

    >
    >Why do you say that. I would guess that well over 90% of the calls to
    >malloc are to do exactly that.
    >
    >>So here's the problem:
    >>I have a type 'board' defined as so:
    >>typedef char board[8][8]
    >>and I am supposed to write a function with the following prototype:
    >>Board *new_board();
    >>which would require me to use malloc for allocation.
    >>I've tried many different things that I'd be ashamed to post here but
    >>have found no solution.

    >
    >What problem have you run into using
    > board *b_ptr = malloc(sizeof(board));
    >
    >>The problem is that it doesn't seem possible to cast a char* or char**

    >
    >Since an object of type board does not have type char* or char**, why
    >is this even a consideration?
    >
    >You can cast an expression of type board to a char* though I don't
    >know you would want to. (Some might want to use this char* with
    >subscripts 0 through 63 to access the squares on the board but that is
    >a questionable (tm) practice.)
    >
    >>to a fixed length array (e.g. char[8] or char[8][8] or board in this case)

    >
    >While you cannot cast a board*, char*, or char** to an array, you can
    >cast it to a pointer to array. Using b_ptr above
    > char (*arr_ptr)[8] = (char (*)[8])b_ptr;
    > /*actually the cast is unnecessary */


    Unfortunately, in this case the cast is necessary. It would not be
    necessary when the right hand side has type board, as in
    char (*arr_ptr)[8] = b_ptr[0]; /* or *b_ptr *?

    --
    Remove del for email
     
    Barry Schwarz, Apr 17, 2012
    #10
  11. mx

    Joe keane Guest

    In article <1619465.778.1334612337265.JavaMail.geo-discussion-forums@vbtb5>,
    Malcolm McLean <> wrote:
    >What you shiuld do is declare a structure
    >
    >typedef struct
    >{
    > char board[8][8];
    >} CHESSBOARD;


    indeed

    or not typedef

    struct board
    {
    char board_squares[8][8];
    int board_flags;
    struct board *board_jxt_chain;
    };

    It removes this problem:

    typedef char (*Board)[8];

    typedef char (*Bitmap)[8];

    ...
    *boardp = *bitmapp; // oops probably
     
    Joe keane, Apr 19, 2012
    #11
  12. Joe keaneæ–¼ 2012å¹´4月19日星期四UTC+8上åˆ7時07分28秒寫é“:
    > In article <1619465.778.1334612337265.JavaMail.geo-discussion-forums@vbtb5>,
    > Malcolm McLean <> wrote:
    > >What you shiuld do is declare a structure
    > >
    > >typedef struct
    > >{
    > > char board[8][8];
    > >} CHESSBOARD;

    >
    > indeed
    >
    > or not typedef
    >
    > struct board
    > {
    > char board_squares[8][8];
    > int board_flags;
    > struct board *board_jxt_chain;
    > };
    >
    > It removes this problem:
    >
    > typedef char (*Board)[8];
    >
    > typedef char (*Bitmap)[8];
    >
    > ...
    > *boardp = *bitmapp; // oops probably


    Well, I suggest you can try the following alternative method.

    static char sbuf[64];
    static *char psbuf[8];

    // inthe initial lization
    psbuf[0]=sbuf;
    psbuf[1]=sbuf+8;

    .......
    psbuf[7]=sbuf+56;

    //if it's critical loop unrolling to 1 D is better
     
    88888 Dihedral, Apr 23, 2012
    #12
  13. 88888 Dihedralæ–¼ 2012å¹´4月23日星期一UTC+8上åˆ8時03分46秒寫é“:
    > Joe keaneæ–¼ 2012å¹´4月19日星期四UTC+8上åˆ7時07分28秒寫é“:
    > > In article <1619465.778.1334612337265.JavaMail.geo-discussion-forums@vbtb5>,
    > > Malcolm McLean <> wrote:
    > > >What you shiuld do is declare a structure
    > > >
    > > >typedef struct
    > > >{
    > > > char board[8][8];
    > > >} CHESSBOARD;

    > >
    > > indeed
    > >
    > > or not typedef
    > >
    > > struct board
    > > {
    > > char board_squares[8][8];
    > > int board_flags;
    > > struct board *board_jxt_chain;
    > > };
    > >
    > > It removes this problem:
    > >
    > > typedef char (*Board)[8];
    > >
    > > typedef char (*Bitmap)[8];
    > >
    > > ...
    > > *boardp = *bitmapp; // oops probably

    >
    > Well, I suggest you can try the following alternative method.
    >
    > static char sbuf[64];
    > static *char psbuf[8];
    >
    > // inthe initial lization
    > psbuf[0]=sbuf;
    > psbuf[1]=sbuf+8;
    >
    > ......
    > psbuf[7]=sbuf+56;
    >
    > //if it's critical loop unrolling to 1 D is better
     
    88888 Dihedral, Apr 23, 2012
    #13
  14. mx

    Tim Rentsch Guest

    Paul N <> writes:

    > On Apr 16, 8:07 pm, mx <mx@none> wrote:
    >> Actually, I'm not even sure it's possible to dynamically allocate a
    >> fixed size one dimensional array.
    >> So here's the problem:
    >> I have a type 'board' defined as so:
    >> typedef char board[8][8]
    >> and I am supposed to write a function with the following prototype:
    >> Board *new_board();
    >> which would require me to use malloc for allocation.
    >> I've tried many different things that I'd be ashamed to post here but
    >> have found no solution.
    >> The problem is that it doesn't seem possible to cast a char* or char**
    >> to a fixed length array (e.g. char[8] or char[8][8] or board in this case)
    >> I'll add that this exercise I have been given specifies the 'board' type
    >> and new_board() function exactly as I have said and I would find a
    >> workaround if I had the choice.

    >
    > malloc returns a void *, there's no need to mess about with char *.
    >
    > This works for me:
    >
    > #include <stdlib.h>
    >
    > typedef char board[8][8];
    >
    > board *new_board(void) {
    > board *b;
    >
    > b = malloc(sizeof(*b));
    > return b;
    > }


    Or just:

    board *
    new_board( void ){
    return malloc( sizeof *new_board() );
    }
     
    Tim Rentsch, May 7, 2012
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. dynamically allocating a 2d array

    , Sep 10, 2005, in forum: C Programming
    Replies:
    10
    Views:
    691
    Barry Schwarz
    Sep 13, 2005
  2. Yvad
    Replies:
    8
    Views:
    454
  3. xhunga
    Replies:
    2
    Views:
    396
    xhunga
    Aug 11, 2006
  4. Rakesh Kumar
    Replies:
    5
    Views:
    690
    James Kanze
    Dec 21, 2007
  5. bintom
    Replies:
    7
    Views:
    752
    Ian Collins
    Dec 2, 2010
Loading...

Share This Page