GIDForums  

Go Back   GIDForums > Computer Programming Forums > C Programming Language
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
 
 
Thread Tools Search this Thread Rating: Thread Rating: 7 votes, 4.14 average.
  #1  
Old 02-Feb-2005, 09:13
bravetanveer bravetanveer is offline
New Member
 
Join Date: Jan 2005
Posts: 11
bravetanveer is on a distinguished road

2D arrays:dynamic allocation and freeing


hi all,

The way to dynamically allocate a 2D array is :

CPP / C++ / C Code:
int a(*)[5];

a=(int (*)[5])malloc(sizeof(int)*5);

This will create array of pointer to arrays.

We can access elements as a 2D array
a[1][1] with access particular element.



Question:
1.
After allocating space for pointers, is it not the case that i need to allocate space for the array they are pointing to?, as we usually do for a pointer to point to array of elements.

2.
Is my way of freeing ok

CPP / C++ / C Code:
for(i=0;i<5;i++)
free(a[i]);

Because it will free the pointers , what about the elements associated with those pointers.
Last edited by LuciWiz : 02-Feb-2005 at 11:06. Reason: Please insert your C code between [c] & [/c] tags
  #2  
Old 02-Feb-2005, 10:09
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,160
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold
If the size is known at compile time; you don't need to allocate anything; let the compiler take care of it (no malloc(), no free())

CPP / C++ / C Code:
 int a[5][5];

..
..
  a[i][j] = xxx;
..
..


Now, if you want a 2D array of int, and the dimensions are not known at compile time, here's a way to do it.

Suppose we want an array[size_x][size_y] of int, where size_x and size_y are variables.

The "array" name will be a "pointer to a pointer to an int"

1. Allocate memory for size_x pointers to int. The address returned by malloc() will be the "array".

2. For each of the pointers, allocate memory for size_y ints.

Then address the individual elements with array[][] notation.

3. Free the memory allocated for the ints.

4. Free the memory allocated for the pointers.

Here's an example (I have given size_x and size_y specific values for purposes of illustration, but these could be obtained from user input or from other program calculations, or whatever.)

CPP / C++ / C Code:

/* illustration of dynamically allocated 2D array */
#include <stdio.h>
#include <stdlib.h>

int main()
{
  int i; /* general purpose variable used for loop index */
  int j; /* general purpose variable used for loop index */

  int **a;     /* this is the array name */
  int size_x; /* this variable will be used for the first  dimension */
  int size_y; /* this variable will be used for the second dimension */

  /* suppose we want an array of int: a[5][3] */
  size_x = 5;
  size_y = 3;

  /*  allocate storage for an array of pointers */
  a = malloc(size_x * sizeof(int *));

  /* for each pointer, allocate storage for an array of ints */
  for (i = 0; i < size_x; i++) {
    a[i] = malloc(size_y * sizeof(int));
  }

  /* just for kicks, show the addresses (note: not all sequential) */
  /* assign an arbitrary value to each element        */
  for (i = 0; i < size_x; i++) {
    for (j = 0; j < size_y; j++) {
      printf("&a[%d][%d] = %p\n", i, j, &a[i][j]); /* show the addresses */
      a[i][j] = i * size_y + j; /* just some unique number for each element */
    }
    printf ("\n");
  }

  /* now show the contents that were assigned */
  for (i = 0; i < size_x; i++) {
    for (j = 0; j < size_y; j++) {
      printf("a[%d][%d] = %2d\n", i, j, a[i][j]);
    }
    printf ("\n");
  }

  /* now for each pointer, free its array of ints */
  for (i = 0; i < size_y; i++) {
    free(a[i]);
  }
  /* now free the array of pointers */
  free(a);

  return 0;
}

(Remember: always free() everything that you got from malloc(), but never anything else.)

C++ Programmers: Do the same, but use new and delete instead of malloc() and free().


Regards,

Dave
Last edited by davekw7x : 02-Feb-2005 at 11:03.
  #3  
Old 03-Feb-2005, 08:50
bravetanveer bravetanveer is offline
New Member
 
Join Date: Jan 2005
Posts: 11
bravetanveer is on a distinguished road

one more question on freeing


Thanks for that code. It ran and more important i got good idea about dynamic allocation of 2D arrays.

One more question:

malloc return NULL if it is not able to allocate the memory we want.

Is there any way to know whether the memory allocated is freed or not.
What can be the check we can make for that?
  #4  
Old 03-Feb-2005, 09:48
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,160
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold
Quote:
Originally Posted by bravetanveer
Thanks for that code. It ran and more important i got good idea about dynamic allocation of 2D arrays.

One more question:

malloc return NULL if it is not able to allocate the memory we want.

Is there any way to know whether the memory allocated is freed or not.
What can be the check we can make for that?

Your question points out a major defect in my example: You (and I) should always check the return value of malloc() to make sure it isn't NULL!

CPP / C++ / C Code:
  a = malloc(size_x * sizeof(int *));
  if (a == NULL) {
    printf("Error: malloc could not allocate %d bytes for a\n", size_x * sizeof(int *));
    return 1;
  }

And do something similar for the malloc() calls for a[ i ].

free() doesn't return anything, so there's nothing to check. (But you should make sure that you call free() with a pointer value given to you by malloc(), results are "undefined" if you call free() with anything else.)

Regards,

Dave

Note for C++ programmers: The standard C++ library function new throws an exception when it runs out of memory; no need to check return values.
  #5  
Old 03-Feb-2005, 10:20
bravetanveer bravetanveer is offline
New Member
 
Join Date: Jan 2005
Posts: 11
bravetanveer is on a distinguished road
Thanks again Dave.

Actually with that, what i wanted to do with
int (*)[5]; mentioned by me in 1st post is:

I was thinking to allocate a hash table, with, separate chaining used to resolve collisions. The example structure is of the type:

CPP / C++ / C Code:
struct  men
{
   int age;
   char *name;
};
struct men men_table(*)[5];

Now with this If i create a hash table then I would allocate this hash table as

CPP / C++ / C Code:
/*To create hash table with size 5 */
men_table=(struct men (*)[5])malloc(sizeof(struct men *) *5);

This will allocate pointer to arrays of structures i.e each pointer will point to a different array.

CPP / C++ / C Code:
for(i=0;i<5;i++)
  men_table[i]=(struct men *) malloc(sizeof(struct men) *cols);

With this i will get a 5 * cols table kind of structure.

So I was not getting how to free this kind of table.

For this kind of concept, if it gives me error like "invalid assignment" in the statement:
CPP / C++ / C Code:
men_table[i]=(struct men *)malloc(sizeof(struct men )*cols); 

So i was not able to understand what was the error in that. And i was also not getting, how should i free that table.
  #6  
Old 03-Feb-2005, 11:52
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,160
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold
Well, I didn't get any farther than this (since it's not valid C or C++ syntax):
CPP / C++ / C Code:
int a(*)[5];

I'll try to take your things one at a time:

If you want an array of struct men with five elements (fixed, not dynamically allocated) this does it:

CPP / C++ / C Code:
  struct  men
  {
     int age;
     char *name;
  };
  struct men mentable[5];

You now have five structs: mentable[0], mentable[1], mentable[2], mentable[3], and mentable[4]. (But I don't think this is what you want.)

Note that the name memtable will be treated as "pointer to struct men" if it's used in a C language expression (actually it's a const pointer, since you can't change its value.)

You could, maybe, use a typedef for an array of 5 structs to make things look different from this point on, but I would rather get fundamental understanding first, and prettify it later (if appropriate).


If you want to have a dynamically allocated array of pointers to 5-element arrays of struct men:

You need to allocate an array of pointers. Pointers to what? Pointers to (pointers to struct men).


CPP / C++ / C Code:

  struct men **men_table;

  int number_of_arrays;
..
.. /* figure out how many arrays you want, and assign to number_of_arrays */
  /* allocate memory for this many pointers */
  men_table = malloc(number_of_arrays * sizeof(struct men *));
  if (men_table == NULL) {
    printf("can't allocate %d bytes for men_table\n",
        number_of_arrays * sizeof(struct men *));
    return 1;
  }

Now, men_table is a pointer to a (pointer to struct men). You have just allocated a bunch of pointers.

The value of men_table[0] is a pointer to (pointer to struct men)
The value of men_table[1] is a pointer to (pointer to struct men)
...
The value of men_table[number_of_arrays - 1] is a pointer to (pointer to struct men)

So, for each pointer that you have just allocated, you want an array of five struct men:
CPP / C++ / C Code:
  for (i = 0; i < number_of_arrays; i++) {
    men_table[i] = malloc(5 * sizeof(struct men));
    if (men_table[i] == NULL) {
      for (j = 0; j < i; j++) {
        free(men_table[i]);
      }
      free men_table;
      return 1;
    }
  }
  /* now you are ready to access men_table[i][j] */

Recap:

CPP / C++ / C Code:
  struct men *x;

This says that x is a pointer to struct men.
Conceptually, this can be like an array of struct men. It's not the same as an array, but, after memory allocation, for, say 5 pointers, individual structs can be accessed by x[ i ], for i = 0..4;

CPP / C++ / C Code:
  struct men **y

This says that y is a pointer to (pointer to struct men).
So, after memory allocation for, say 10 pointers to (pointer to struct men),
The value of y[0] will be a (pointer to struct men)
The value of y[1] will be a (pointer to struct men)
etc.

Now, from the previous paragraph, y[0] can be considered conceptually to be like an array of struct men (after memory allocation). So y can be considered conceptually to be an array of arrays of struct men (a 2D array of struct men). It's not the same as a 2D array, but the following notation is a fundemantal part of the C language:

y[0][0] is a struct
y[0][1] is a struct
etc.

That is, to dynamically allocate something that can be treated as a 2-D array of structs:

Declare a pointer to pointer, and allocate a bunch of pointers. (This "bunch" will be the first dimension of the 2D array.)

For each of these pointers, allocate several structs. (This "several" will be the second dimension of the 2D array.)

Remember to free() everything that was obtained from malloc().

Regards,

Dave
  #7  
Old 03-Feb-2005, 12:34
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,160
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold
Quote:
Originally Posted by bravetanveer
hi all,

The way to dynamically allocate a 2D array is :

CPP / C++ / C Code:
int a(*)[5];

a=(int (*)[5])malloc(sizeof(int)*5);

From the response on other forum that you posted to:

Quote:

> int a(*)[5];
This is a pointer to an array (not a pointer to a pointer).


No it isn't, it's not anything. It's not valid syntax. Period. Full stop.

Regards,

Dave
  #8  
Old 05-Feb-2005, 02:01
bravetanveer bravetanveer is offline
New Member
 
Join Date: Jan 2005
Posts: 11
bravetanveer is on a distinguished road

where have i found int (*)[5];


This is valid syntax.

Actually, I was going through code for mp3, at that time I found this:

CPP / C++ / C Code:
struct mad_stream
{
       ....
       ....
      unsigned char (*main_data)[MAD_BUFFER_MDLEN];
       ....
};

struct mad_stream *stream;

stream->main_data=(unsigned char (*)[MAD_BUFFER_MDLEN])malloc(MAD_BUFFER_MDLEN);

And this allocates pointers to array of characters i.e. strings. In this array lots of strings can be stored.

Am I wrong with the above statement? If yes, do correct me.
  #9  
Old 05-Feb-2005, 09:30
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,160
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold
If you are not in the mood for my long-winded explanations, scroll to the bottom of this post, where I say, "Your original post had this:"

It's possible that we could have saved some board bandwidth if you had given this code snippet in your original post instead of what you had.

I have tried to give an explanation of one way to handle the problem of dynamically allocated 2D arrays (which was the crux of your original request). Instead of just picking up my example (or anyone else's), this is a good opportunity to learn about C notation regarding "pointers" and "arrays" and "arrays of arrays" and "arrays of pointers" and "pointers to arrays" and "arrays of pointers to arrays", etc.

First: lets look at some notation:

The following allocates a pointer to char, x, then uses malloc() to allocate five bytes (dynamic memory allocation), and sets x = the first byte that is allocated (no need to use a cast on the malloc'ed memory in C):

CPP / C++ / C Code:
char *x;
x = malloc(5);
    /* You must put something here to make sure malloc() didn't return NULL */

For C++, you must use a cast on the malloc'ed memory (Here I use the classic C-style cast, which is valid in C++, but there are other recommended cast constructs.)

CPP / C++ / C Code:
  char *x;
  x = (char *)malloc(5);
    /* You must put something here to make sure malloc() didn't return NULL */

(Note that an "pointer to char" is conceptually similar to "array of char". An "pointer to char" can be used with array notation.)



The following allocates an array of 5 pointers to char. This allocates five pointers; they don't point to anything. (My previous post had an example of a "pointer to a pointer", and allocating memory for the pointers, etc.) I'll try to cover something a little different here.

CPP / C++ / C Code:
unsigned char *main_data[5];

A "array of pointer to char" is conceptually similar to a "pointer to pointer to char" and also to "array of array to char". This can be used with 2D array notation.


The following allocates a pointer to array[5] of char. (Note the difference that the parentheses makes.) This only allocates the pointer; it doesn't point to anything.

CPP / C++ / C Code:
unsigned char (*main_data)[5];

(Note that "pointer to array of char" is conceptually similar to "pointer to pointer to char" and similar to "array of array of char". A "pointer to array of char" can be used with 2D array notation.)



Now to the good stuff of your question

The following defines a struct that has a member that is a pointer to array[5] of char.

CPP / C++ / C Code:
struct mad_stream
{
unsigned char (*main_data)[5];
};


The following allocates memory for a pointer to this type of struct. It only allocates a pointer; the pointer doesn't point to anything.

CPP / C++ / C Code:
  struct mad_stream *stream;

The following allocates storage for a struct, and sets sets the pointer to a block of memory dynamically obtained from malloc():

CPP / C++ / C Code:
  stream = (struct stream *)malloc(sizeof(struct stream));
    /* You must put something here to make sure malloc() didn't return NULL */

  stream->main_data = malloc(5); 
    /* You must put something here to make sure malloc() didn't return NULL */

(Note that the pointer points to a memory block of 5 chars).

For C++, we must use a cast on malloc():

CPP / C++ / C Code:
  stream->main_data=(unsigned char (*)[5])malloc(5);
    /* You must put something here to make sure malloc() didn't return NULL */



Note that (unsigned char(*)[5]) in this expression does not allocate any memory, it is a cast that makes the C++ compiler happy; C++ will not allow implicit casting from the return type of malloc (which is "pointer to void").

(Your example used MAD_BUFFER_MDLEN; I am using an explicit constant, 5, just to keep from unnecessarily cluttering up the landscape.)

Your original post had this:

Quote:
Originally Posted by bravetanveer
The way to dynamically allocate a 2D array is :

CPP / C++ / C Code:
int a(*)[5];

I told you then, and I tell you now: this is invalid syntax. Does your compiler accept it? What compiler?

This, on the other hand is the way to use a cast (not required for C, but necessary for C++):

CPP / C++ / C Code:
  int (*a)[5]; // a is a pointer to an array of 5 ints
  a = (int (*)[5])malloc(10 * sizeof(int *)); //allocate ten pointers



(In all cases, remember that before your program terminates, you must use delete() on all memory obtained from malloc().)

Notice that my examples in this post are not just about 2D arrays, they show what the notation of your program snippet means to me. After things are allocated, 2D array notation can be used.

My previous posts about 2D arrays gave one way to implement 2D arrays; there are other ways, and I invite you to investigate them. Try something. Compile it. Execute it (put stuff into the arrays and read them back, using pointer notation and using array notation). See if it does what you think it should. Scratch your head. Try again. Repeat until completely satisfied.



Regards,

Dave

Richard Feynman's methodology for problem solving:

1. Write down the problem.
2. Think real hard.
3. Write down the solution.

(Quote by Murray Gell-Mann in an interview with the N.Y. Times)
Last edited by davekw7x : 05-Feb-2005 at 10:59.
  #10  
Old 29-Aug-2005, 09:02
ss_jas ss_jas is offline
New Member
 
Join Date: Aug 2005
Posts: 1
ss_jas is on a distinguished road

allocating memory to pointer to an array


CPP / C++ / C Code:
  int (*a)[5]; // a is a pointer to an array of 5 ints
  a = (int (*)[5])malloc(10 * sizeof(int *)); //allocate ten pointers

As we are trying to allocate memory to a pointer to an array, and the requirement is to create multiple such arrays (2D) shouldn't we use the following set of statements:

CPP / C++ / C Code:
  int (*a)[5]; // a is a pointer to an array of 5 ints
  a = (int (*)[5])malloc(10 * sizeof(a[0])); //allocate a block to hold 10 x 5 int

The above code works fine but at termination I get a NULL pointer assignment
Can't make out the reason as the allocated addresses come out to be correct:

CPP / C++ / C Code:
printf ("%u", a+i);

gives memory addresses seperated by a block of sizeof(int)*5
Can someone help!!!
 


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 18:18.


vBulletin, Copyright © 2000 - 2016, Jelsoft Enterprises Ltd.