Dynamically Allocated Multi-Dimensional Arrays

[bwaichu]

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

[websnarf]

bw*****@yahoo.com 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/

[Keith Thompson]

we******@gmail.com writes:

bw*****@yahoo.com 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) ks***@mib.org <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.

[bwaichu]

we******@gmail.com 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.

[websnarf]

bw*****@yahoo.com wrote:

we******@gmail.com 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/

[Barry Schwarz]

On 1 Sep 2006 20:18:30 -0700, "bw*****@yahoo.com" <bw*****@yahoo.com>
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

[bwaichu]

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?