'How to use dynamic 2d array inside a struct array in C?
What do I want to do?
I'm working on a project on dynamic matrix multiplication. I want to input from the user that on how many matrices, he/she wants to perform multiplication and based on that I want to create a struct something like below:
typedef struct
{
size_t rows, columns;
int table[];
} Matrix;
And after that, check for the validation of the matrices to be multiplied (using very simple maths).
Then create an array of Matrix types and allocate memory to it depending on the number of matrices the user wants to multiply.
+---------------------------------------------------------------------------------------------------+
| +------------------------------+ +---------------------------------------------------------+ |
| | Matrix struct type array | | ..... More arrays depending on the number of matrices. | |
| +------------------------------+ +---------------------------------------------------------+ |
+---------------------------------------------------------------------------------------------------+
Eg. 2 Matrices [2][2] & [2][1]
+----------------> rows <-------------+
| |
| +------------> columns <-----------|--+
| | | |
| | +------------------------+ | | +------------------+
{ { 2, 2, | { { 1, 2 }, { 2, 1 } } | }, { 2, 1, | { { 1 }, { 3 } } | } }
+------------------------+ +------------------+
| |
| |
| |
v v
| 1 2 | | 1 |
| | | |
| 2 1 | | 3 |
Reasons for creating an array of struct type
There is one thing that might seem odd to some of my fellow readers of this question, which is, why I want to make an array of types struct Matrix, instead of creating 2 different objects of the type and performing the multiplication on "user_defined_matrix"->table. Well, the reasons are listed below:
- Scalability, as every constraint is user-defined I want things to be as flexible as possible. One way of thinking about this is, suppose the user wants multiplication between 15 matrices, then you don't want to declare 15 objects of types
struct Matrix. - Accessibility, accessing every matrix would become so easy with the help of for loop.
Now back to the topic, after allocation of memory, I want the user to fill each slot of the matrix and then perform the multiplication on them and generate the result.
What I have done so far
Note: I know that you cannot declare a true 2d VLA inside a struct, you have to first declare a 1d array which later becomes a mangled version of a 2d array and before using it typecast it to a 2d array as shown in this answer.
I have made a true 2d array to store user-inputted rows and columns.
int dimensions[NUMBER_OF_MATRIX][2];
Then using these dimensions, I calculated how much memory I have to allocate.
int total_matrix_size = 0;
for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
{
total_matrix_size += (dimensions[i][0] * dimensions[i][1]);
}
And then use the total_matrix_size to allocate memory to the array of types struct Martix.
Matrix *matrix = malloc(((sizeof *matrix) * NUMBER_OF_MATRIX) + sizeof(int[total_matrix_size]));
After that, I am asking the user to fill the matrix, before filling the matrix I'm typecasting the array to a 2d array with the help of a macro in the code below.
Note: I'll be referring to the below code block many times so for the sake of simplicity, let's name this input block.
#define get_array(arr) \
_Generic((arr), \
Matrix \
: (int(*)[(arr).columns])(arr).table)
for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
{
matrix[i].rows = dimensions[i][0];
matrix[i].columns = dimensions[i][1];
for (uint x = 0; x < matrix[i].rows; x++)
{
for (uint y = 0; y < matrix[i].columns; y++)
{
printf("Enter values of matrix %d a[%dx%d] : ", i + 1, x + 1, y + 1);
scanf("%d", &get_array(matrix[i])[x][y]);
printf("%d\n", get_array(matrix[i])[x][y]); // print statement 1
}
}
}
Then just for testing purposes, I'm printing all the matrices.
Note: I'll be referring to the below code block many times so for the sake of simplicity, let's name this output block.
for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
{
printf("Matrix %d\n", i+1);
for (uint x = 0; x < matrix[i].rows; x++)
{
for (uint y = 0; y < matrix[i].columns; y++)
{
printf("%d ", get_array(matrix[i])[x][y]); // print statement 2
}
printf("\n");
}
}
So, where is the problem?
As you can see I've written 2 exactly the same print statements in the above 2 code blocks, input and output blocks.
printf("%d ", get_array(matrix[i])[x][y]);
But both of them are generating different outputs. Output generated by input block.
Enter the rows of matrix 1 : 2 2
Enter the rows of matrix 2 : 2 2
Enter values of matrix 1 a[1x1] : 1
1
Enter values of matrix 1 a[1x2] : 0
0
Enter values of matrix 1 a[2x1] : 1
1
Enter values of matrix 1 a[2x2] : 0
0
Enter values of matrix 2 a[1x1] : 2
2
Enter values of matrix 2 a[1x2] : 3
3
Enter values of matrix 2 a[2x1] : 2
2
Enter values of matrix 2 a[2x2] : 3
3
Printed everything as expected.
But not the same for output block.
Matrix 1
2 2
2 3
Matrix 2
2 3
2 3
What do I expect from the answers?
Nothing but a deep dive explanation for :
- Why print statement is working in the input block & why not in the output block.
- If this is not the correct way of allocating memory, then what is?
- If my approach is totally wrong then what should it be?
Please keep the format somewhat like this answer.
Here is the whole code
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// TODO Preprocessors
#define get_array(arr) \
_Generic((arr), \
Matrix \
: (int(*)[(arr).columns])(arr).table)
// TODO Custom types
typedef unsigned int uint;
// TODO Structs
typedef struct
{
uint rows, columns;
int table[];
} Matrix;
// TODO Function Declarations
void flushBuffer(void);
int main(void)
{
int NUMBER_OF_MATRIX = 2;
int dimensions[NUMBER_OF_MATRIX][2];
for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
{
printf("Enter the rows of matrix %d : ", i + 1);
scanf("%d %d", &dimensions[i][0], &dimensions[i][1]);
flushBuffer();
}
if (dimensions[0][1] != dimensions[1][0])
{
printf("Matrix multiplication not possible.");
}
else
{
int total_matrix_size = 0;
for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
{
total_matrix_size += (dimensions[i][0] * dimensions[i][1]);
}
Matrix *matrix = malloc(((sizeof *matrix) * NUMBER_OF_MATRIX) + sizeof(int[total_matrix_size]));
for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
{
matrix[i].rows = dimensions[i][0];
matrix[i].columns = dimensions[i][1];
for (uint x = 0; x < matrix[i].rows; x++)
{
for (uint y = 0; y < matrix[i].columns; y++)
{
printf("Enter values of matrix %d a[%dx%d] : ", i + 1, x + 1, y + 1);
scanf("%d", &get_array(matrix[i])[x][y]);
printf("%d\n", get_array(matrix[i])[x][y]);
}
}
}
for (uint i = 0; i < NUMBER_OF_MATRIX; i++)
{
printf("Matrix divider\n");
for (uint x = 0; x < matrix[i].rows; x++)
{
for (uint y = 0; y < matrix[i].columns; y++)
{
printf("%d ", get_array(matrix[i])[x][y]);
}
printf("\n");
}
}
}
return 0;
}
// TODO Function Definitions
void flushBuffer(void)
{
int c;
while ((c = getchar()) != '\n' && c != EOF)
;
}
Solution 1:[1]
I'll start by going straight to the point. I'll get into more details on the specific topics you requested afterwards.
Solution
The issue
In short your theoretical approach to the problem is sound IMO. But the memory management is not being implemented correctly.
What you want to do is have multiple instances of the Matrix structure. That's not what you're getting with the current setup. Specifically:
Matrix *matrix = malloc(((sizeof *matrix) * NUMBER_OF_MATRIX) + sizeof(int[total_matrix_size]));
Here you're allocating enough memory for the NUMBER_OF_MATRIX Matrix instances, sure. But you're doing so to the Matrix type. Given matrix is a pointer to Matrix and sizeof *matrix (or sizeof(Matrix)) is equal to sizeof(int[2]) (1), when you index that array (i.e. do pointer arithmetic) the memory offset increment is of that size.
Let's assume sizeof(int) = 4, NUMBER_OF_MATRIX = 2 and total_matrix_size = 8 (2 2x2 matrices). If matrix is given the memory address 0x0010, &(matrix[1]) will be 0x0018, not 0x0028 (24 bytes offset) as you'd expect.
For more reference on how C handles pointer arithmetic you can refer to this SO answer, and this article, which has a more detailed overview on the topic.
IMO the cleanest way of achieving what you want is to dynamically allocate matrix[i].table individually instead of pre-allocating all the memory you need at once. And that's for a few reasons:
- It'd be much cleaner for other readers and for yourself (less chance of issues like this happening)
- As the total memory you need grows larger and larger it gets more and more difficult for the OS to handle that single allocation because it tries to find a contiguous section of memory. That might or might not be an issue to your application but it's a point to watch in any case. Refer to this article series for a deeper overview on the matter (2)
(1): I'm considering the given example of a struct with only ints. That means no padding will be necessary. If there were members with different types the total size of the struct might be slightly larger than the sum of the sizes of the members due to added padding.
(2): A case can be made that a single allocation is faster than multiple allocations. And that's generally true, given allocating memory has an inherent overhead. Again, this is something you need to consider for your application individually instead of taking a general statement as the truth
Possible Solution
The only reason I can think of for you to keep following this strategy is if you need so due to performance reasons and you want to minimze malloc calls (maybe the platform on which you're working has a heavy penalty for mem allocations). Given that one thing I can suggest to fix your current approach is modifying the get_array macro to something like:
#define get_array(arr, idx) \
_Generic((arr), \
Matrix * \
: (int(*)[(arr)[offset_for_index((arr), (idx))].columns])(arr)[offset_for_index((arr), (idx))].table)
and to define a offset_for_index function (or as a macro, if you wish) such as:
static inline size_t offset_for_index(struct x *arr, size_t idx) {
size_t offset = 0;
for (size_t i = 0; i < idx; ++i) {
offset += (sizeof *arr) + sizeof(int[arr[offset].a * arr[offset].b]);
}
// No need to safeguard because all our struct members are `int`, so
// `offset` will, necessarily, be a multiple of `sizeof *arr`
return offset / sizeof *arr;
}
But that's definitely cumbersome in my opinion. I've declared it inline to try and follow the pattern of avoiding function calls (given you chose to define get_array as a macro). And the function might not even be inlined, unless you strictly force the compiler to do so. More info on inline functions here and here.
Sample usage of this new setup would be as follows:
/* ... */
#define NUMBER_OF_MATRIX 2
#define TOTAL_TABLE_ELEMENTS 8
#define SIZE ((sizeof *a) * NUMBER_OF_MATRIX + sizeof(int[TOTAL_TABLE_ELEMENTS]))
int main() {
Matrix *a = calloc(1, SIZE);
a[offset_for_index(a, 0)].a = 2;
a[offset_for_index(a, 0)].b = 2;
a[offset_for_index(a, 1)].a = 2;
a[offset_for_index(a, 1)].b = 2;
for (size_t i = 0; i < 2; ++i) {
for (size_t j = 0; j < 2; ++j) {
get_array(a, 0)[i][j] = 10 * (i + 1);
get_array(a, 1)[i][j] = -10 * (i + 1);
}
}
// Your output block
for (uint i = 0; i < NUMBER_OF_MATRIX; i++) {
printf("Matrix %d\n", i+1);
size_t idx = offset_for_index(a, i);
for (uint x = 0; x < a[idx].rows; x++) {
for (uint y = 0; y < a[idx].columns; y++) {
printf("%d ", get_array(a, i)[x][y]);
}
printf("\n");
}
}
free(a);
return 0;
}
Why were the print statements working in the input block?
It's not that they were exactly working. You were simply printing what you had just set. What you were doing was pretty much the same as:
/* ... */
int n;
scanf("%d", &n);
pritnf("%d\n", n);
Correct way of allocating memory
"Only a sith deals in absolutes". KENOBI, Obi-Wan.
I'm not particularly fond of restricting approaches by saying something is the right way or something should never be used/done (even goto has its place IMO). That said I won't be the one telling you what is the correct way of allocating memory. But, as I have previously mentioned, given the information I have so far I believe the best approach would be to dynamically allocate memory for the table member. Your struct definition would be updated to:
typedef struct {
uint rows, columns;
int *table;
} Matrix;
and upon setting a new matrix you'd need to allocate memory for table:
Matrix *matrix = malloc((sizeof *matrix) * NUMBER_OF_MATRIX);
for (uint i = 0; i < NUMBER_OF_MATRIX; i++) {
matrix[i].rows = dimensions[i][0];
matrix[i].columns = dimensions[i][1];
matrix[i].table = malloc(sizeof(int) * matrix[i].rows * matrix[i].columns);
for (uint x = 0; x < matrix[i].rows; x++) {
for (uint y = 0; y < matrix[i].columns; y++)
{
printf("Enter values of matrix %d a[%dx%d] : ", i + 1, x + 1, y + 1);
scanf("%d", &get_array(matrix[i])[x][y]);
printf("%d\n", get_array(matrix[i])[x][y]); // print statement 1
// Mind `get_array` here is your original macro!
}
}
}
You'd, obviously, need to free that memory when it was no longer necessary. Say that'd only be the case when your program finished, the following would do the trick:
for (uint i = 0; i < NUMBER_OF_MATRIX; i++) {
free(matrix[i].table);
}
free(matrix);
I'll refrain from answering the last question because I believe I've done it over and over through the sections above. In short, you should consider your specific needs and what you think is more important (maybe a clearer code or maybe a bit -- or a lot -- more performance instead).
I hope this was clarifying and you'll be able to ponder and choose the best way forward for your project. Best regards!
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 |