Dynamically Allocated Multi-Dimensional Arrays

Discussion in 'C Programming' started by bwaichu@yahoo.com, Sep 2, 2006.

  1. Guest

    Is my understanding of the allocation of these correct?

    I used fixed sized allocations for the example below, so I realize
    there is some optimization that can be done to those.

    I would like to use these in a linked list for something else I am
    working on, but I want to make sure my understanding of the concept is
    correct.

    For example, from the code below string[0][0] would equal 'h' after
    the copy, right?

    The one area where I am not quite certain about is freeing these.

    Another area where I am uncertain is how to keep track of the sizes
    of all the allocations.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <err.h>

    int
    main(void) {


    char **string;

    string = malloc(20 * sizeof(char *));
    if (string == NULL)
    errx(1, "malloc failed");
    string[0] = malloc(80 * sizeof(char));

    if (string[0] == NULL)
    errx(1, "malloc failed");
    string[1] = malloc(80 * sizeof(char));

    if (string[1] == NULL)
    errx(1, "malloc failed");

    strlcpy(string[0], "hello", 80);
    strlcpy(string[1], "world", 80);

    printf("%s %s\n", string[0], string[1]);

    free(string[0]);
    free(string[1]);
    free(string);

    exit(EXIT_SUCCESS);
    }
     
    , Sep 2, 2006
    #1
    1. Advertising

  2. Guest

    wrote:
    > Is my understanding of the allocation of these correct?


    Upon first examination, this all looks ok. I don't know what errx()
    is, but I assume its defined in err.h in your environment.

    > I used fixed sized allocations for the example below, so I realize
    > there is some optimization that can be done to those.
    >
    > I would like to use these in a linked list for something else I am
    > working on, but I want to make sure my understanding of the concept is
    > correct.


    A linked list uses individual allocations that are joined up in
    sequence by link pointers. What you are doing is collecting them into
    an array of strings. That's a different thing (when handled correctly,
    the array strategy usually works out better, BTW).

    > For example, from the code below string[0][0] would equal 'h' after
    > the copy, right?


    Yes.

    > The one area where I am not quite certain about is freeing these.


    You did it correctly. You freed the inner stuff then the outer stuff.
    In absence of other copies of the pointers, you have to do it that way
    (just because the outer stuff is the only thing with references to the
    inner stuff, and that data becomes invalidated as soon as you free it).

    > Another area where I am uncertain is how to keep track of the sizes
    > of all the allocations.


    Aha! And there's the rub! C gives you *NO* direct mechanisms for
    dealing with this. You have to track them yourself, typically through
    implicit or specific runtime tracking support.

    The strategies and implementations for doing this are varied and can be
    convoluted; its hard to recommend one over the other without more
    information about your scenario. If you are just interested in a
    simple strategy, I will again refer you to my string library (
    http://bstring.sf.net/ ) as it contains an array of strings as one of
    the types it supports.

    > #include <stdio.h>
    > #include <stdlib.h>
    > #include <string.h>
    > #include <err.h>
    >
    > int
    > main(void) {
    > char **string;
    >
    > string = malloc(20 * sizeof(char *));
    > if (string == NULL)
    > errx(1, "malloc failed");
    > string[0] = malloc(80 * sizeof(char));
    >
    > if (string[0] == NULL)
    > errx(1, "malloc failed");
    > string[1] = malloc(80 * sizeof(char));
    >
    > if (string[1] == NULL)
    > errx(1, "malloc failed");
    >
    > strlcpy(string[0], "hello", 80);
    > strlcpy(string[1], "world", 80);
    >
    > printf("%s %s\n", string[0], string[1]);
    >
    > free(string[0]);
    > free(string[1]);
    > free(string);
    >
    > exit(EXIT_SUCCESS);
    > }


    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
     
    , Sep 2, 2006
    #2
    1. Advertising

  3. writes:
    > wrote:
    >> Is my understanding of the allocation of these correct?

    >
    > Upon first examination, this all looks ok. I don't know what errx()
    > is, but I assume its defined in err.h in your environment.
    >
    >> I used fixed sized allocations for the example below, so I realize
    >> there is some optimization that can be done to those.
    >>
    >> I would like to use these in a linked list for something else I am
    >> working on, but I want to make sure my understanding of the concept is
    >> correct.

    >
    > A linked list uses individual allocations that are joined up in
    > sequence by link pointers. What you are doing is collecting them into
    > an array of strings. That's a different thing (when handled correctly,
    > the array strategy usually works out better, BTW).

    [...]

    One should be careful about the phrase "array of strings".

    In C, a string is a data format, not a data type. Specifically, a
    "string" is "a contiguous sequence of characters terminated by and
    including the first null character" (C99 7.1.1p1).

    What you have in your program is an array of pointers to strings. (A
    "pointer to string" is actually a pointer to its first character, but
    the standard specifically defines a "pointer to a string" as "a
    pointer to its initial (lowest addressed) character".)

    You could have had an array of arrays of char (also known as a
    two-dimensional array) where each row happens to contain a string, and
    called that an "array of strings".

    Arrays and pointers in C can be confusing (which is why there's an
    entire section of the FAQ devoted to them). Keeping terminology
    strictly correct isn't just pedantry; it can be vital to a proper
    understanding of how things actually work.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Sep 2, 2006
    #3
  4. Guest

    wrote:

    > A linked list uses individual allocations that are joined up in
    > sequence by link pointers. What you are doing is collecting them into
    > an array of strings. That's a different thing (when handled correctly,
    > the array strategy usually works out better, BTW).


    But I can have a structure that contains an element that is allocated.

    struct node {

    char **string;
    struct node *next;
    };

    The string would be allocated for each node and populated. The
    weakness
    is that each node point need not be contiguous as an array would be.

    The weakness still remains in having to do overhead to keep a count of
    all
    the allocation sizes. The only advantage of allocating them is that I
    allocate
    memory as I need it, rather than allocating it all at once in the
    beginning.

    At this point I am exploring different ways to store and manipulate
    data.
     
    , Sep 2, 2006
    #4
  5. Guest

    wrote:
    > wrote:
    > > A linked list uses individual allocations that are joined up in
    > > sequence by link pointers. What you are doing is collecting them into
    > > an array of strings. That's a different thing (when handled correctly,
    > > the array strategy usually works out better, BTW).

    >
    > But I can have a structure that contains an element that is allocated.
    >
    > struct node {
    > char **string;
    > struct node *next;
    > };


    You probably mean:

    struct node {
    char * string;
    struct node * next;
    }

    But another possibility is

    struct node {
    struct node * next;
    char string[1]; /* struct hack */
    };

    Where you use malloc (offsetof (struct node, string) + BUFF_LENGTH) to
    allocate each node. In this way you amortize the overhead of the node
    allocation with that of the string allocation.

    > The string would be allocated for each node and populated. The
    > weakness is that each node point need not be contiguous as an
    > array would be.


    Correct.

    > The weakness still remains in having to do overhead to keep a count of
    > all the allocation sizes.


    Well, if you don't care about performance, you can always make minimum
    assumptions and constantly perform reallocs all the time. I.e., always
    realloc the array to have exactly the length of the string plus one
    characters in it. In this way, you can "know" the size since it will
    always be one more than the length of the string.

    > [...] The only advantage of allocating them is that I
    > allocate memory as I need it, rather than allocating it all at once in the
    > beginning.
    >
    > At this point I am exploring different ways to store and manipulate
    > data.


    As well you should. If you do enough research into it you're going end
    up with the only strategy that makes sense: http://bstring.sf.net/

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
     
    , Sep 2, 2006
    #5
  6. On 1 Sep 2006 20:18:30 -0700, "" <>
    wrote:

    >
    >But I can have a structure that contains an element that is allocated.
    >
    >struct node {
    >
    > char **string;


    char *string;

    > struct node *next;
    >};
    >
    >The string would be allocated for each node and populated. The
    >weakness
    >is that each node point need not be contiguous as an array would be.


    It's not much of a weakness and my actually be a benefit.

    With an array, accessing the n-th entry is a simple
    calculation. With a linked list, you must walk the list which is not
    difficult but usually more time consuming.

    As you note below, memory allocation is different between the
    array approach and a linked list one. On a system with fragmented
    memory, the allocation for the latter may be succeed (as many times as
    you need) while allocation for the former fails on the first try.

    Also note that with an array, all the strings would be the
    same size. If your strings have widely varying lengths, this might
    consume too much memory.

    >
    >The weakness still remains in having to do overhead to keep a count of
    >all
    >the allocation sizes. The only advantage of allocating them is that I


    Add another member to your structure:
    size_t size;

    >allocate
    >memory as I need it, rather than allocating it all at once in the
    >beginning.
    >
    >At this point I am exploring different ways to store and manipulate
    >data.


    There are other options. Your original code had an allocated array of
    pointers, each pointing to an allocated string. Since pointers don't
    consume much memory, you may choose to define the array of pointers
    and allocate space only for the strings themselves (assuming you know
    the maximum number of strings you will ever need).


    Remove del for email
     
    Barry Schwarz, Sep 2, 2006
    #6
  7. Guest

    Barry Schwarz wrote:

    > There are other options. Your original code had an allocated array of
    > pointers, each pointing to an allocated string. Since pointers don't
    > consume much memory, you may choose to define the array of pointers
    > and allocate space only for the strings themselves (assuming you know
    > the maximum number of strings you will ever need).


    So instead of allocating the "array" with malloc or calloc. I would
    do something like this:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <err.h>

    int
    main(void) {

    char *string[20] ={0};

    string[0] = calloc(80, sizeof(char));
    if (string[0] == NULL)
    errx(1, "calloc failed");
    strlcpy(string[0], "hello", 80);
    printf("%s\n", string[0]);
    free(string[0]);
    exit(0);
    }

    So what other options do I have?
     
    , Sep 3, 2006
    #7
    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. Alf P. Steinbach
    Replies:
    0
    Views:
    439
    Alf P. Steinbach
    Aug 18, 2003
  2. John Harrison
    Replies:
    4
    Views:
    6,931
    Default User
    Aug 19, 2003
  3. Replies:
    5
    Views:
    625
    Matt Wharton
    Dec 9, 2004
  4. Serpent
    Replies:
    7
    Views:
    461
    Chris Torek
    Mar 17, 2007
  5. Wirianto Djunaidi
    Replies:
    2
    Views:
    204
    Wirianto Djunaidi
    Apr 29, 2008
Loading...

Share This Page