I'm doing a program that sorts a stack of number using two stacks for a school project, and I want to handle the cases where the size of the stack is inferior or egal to 5 by a brute force method, for that I have different structs that contains lookup tables with an array of int arrays representing the order of the numbers (for every possible order), and an array of function pointer arrays containing the corresponding operation sequence to sort them, and each of these structs correspond to a specific array size (2, 3, 4, 5). And to avoid a hugly if forest, I'd like to access them using a while loop with a common struct (t_combi) that has pointers to the different datas, but apparently it doesn't work, I somehow lose the address of my global arrays because I get a segfault (trying to access non allocated data with valgrind) at the first iteration when I compare the orders.
Code:
// brute_force.h
#ifndef BRUTE_FORCE_H
# define BRUTE_FORCE_H
# include "resolver.h"
# define CNT_2 2
# define CNT_3 6
# define CNT_4 24
# define CNT_5 120
typedef struct s_mlx *t_mlxptr;
typedef const char *(*t_op)(t_stack *, t_stack *);
typedef struct s_combi {
int cnt;
int **order;
t_op **op;
} t_combi;
static const struct {
int cnt;
int order[CNT_2][2];
t_op op[CNT_2][2];
} g_2combi = {
.cnt = CNT_2,
.order = {
{0, 1},
{1, 0}
},
.op = {
{NULL},
{sa, NULL}
}
};
static const struct {
int cnt;
int order[CNT_3][3];
t_op op[CNT_3][3];
} g_3combi = {
.cnt = CNT_3,
.order = {
{0, 1, 2},
{0, 2, 1},
{1, 0, 2},
...
},
.op = {
{NULL},
{rra, sa, NULL},
{sa, NULL},
...
}
};
static const struct {
int cnt;
int order[CNT_4][4];
t_op op[CNT_4][7];
} g_4combi = {
.cnt = CNT_4,
.order = {
{0, 1, 2, 3},
{0, 1, 3, 2},
{0, 2, 1, 3},
...
},
.op = {
{NULL},
{pb, rra, sa, pa, NULL},
{ra, sa, rra, NULL},
...
}
};
static const struct {
int cnt;
int order[120][5];
t_op op[120][10];
} g_5combi = {
.cnt = CNT_5,
.order = {
{0, 1, 2, 3, 4},
{0, 1, 2, 4, 3},
{0, 1, 3, 2, 4},
...
},
.op = {
{NULL},
{rra, rra, sa, ra, ra, NULL},
{pb, pb, sa, pa, pa, NULL},
{pb, pb, rra, pa, pa, NULL},
...
}
};
int brute_force(t_mlxptr mlx, t_stack *st[2], t_queue *instr);
#endif
// brute_force.c
#include <brute_force.h>
#include <resolver.h>
bool same_order(const int *a, const int *b, size_t size)
{
size_t i = 0;
while (++i < size)
{
if ((a[i - 1] < a[i] && b[i - 1] > b[i])
|| (a[i - 1] > a[i] && b[i - 1] < b[i]))
return (false);
}
return (true);
}
void apply_instructions(t_mlxptr mlx, t_stack *st[2], t_op *op, t_queue *instr)
{
while (*op)
{
add_op(mlx, *op, st, instr); // function from resolver.h
++op;
}
}
void init_combi(t_combi combi[4])
{
combi[0] = (t_combi) {
.cnt = g_2combi.cnt,
.order = (int**)g_2combi.order,
.op = (t_op **)g_2combi.op
};
combi[1] = (t_combi) {
.cnt = g_3combi.cnt,
.order = (int**)g_3combi.order,
.op = (t_op **)g_3combi.op
};
combi[2] = (t_combi) {
.cnt = g_4combi.cnt,
.order = (int**)g_4combi.order,
.op = (t_op **)g_4combi.op
};
combi[3] = (t_combi) {
.cnt = g_5combi.cnt,
.order = (int**)g_5combi.order,
.op = (t_op **)g_5combi.op
};
}
int brute_force(t_mlxptr mlx, t_stack *st[2], t_queue *instr)
{
const int *const a_raw = stkcbegin(st[ST_A]); // pointer to a int array
const size_t size = stksize(st[ST_A]); // nbcount
int i;
t_combi combi[4];
init_combi(combi);
if (stksorted(st[ST_A]))
return (0);
if (size > 5)
return (1);
i = -1;
while (++i < combi[size - 2].cnt)
{
if (same_order(combi[size - 2].order[i], a_raw, size))
apply_instructions(mlx, st, combi[size - 2].op[i], instr);
}
return (0);
}
The main problem is that you are casting a pointer to an array of some type to a pointer to a pointer of some type. For example, in this code:
void init_combi(t_combi combi[4])
{
combi[0] = (t_combi) {
.cnt = g_2combi.cnt,
.order = (int**)g_2combi.order,
.op = (t_op **)g_2combi.op
};
/* ... */
}
g_2combi.order is 2-dimensional array of int: int [CNT_2][2]. In the initializer, the value is converted to a pointer to its first element. The type of the element is int [2] (array length 2 of int), so the type of the pointer to an element is int (*)[2] (pointer to array length 2 of int). However, the type cast operation is converting it to a pointer to an incompatible type int ** (pointer to pointer to int). combi[0].order[0] should be of type int *, which is not compatible with the underlying object's type: int [2].
Similarly, g_2combi.op is a 2-dimensional array of t_op: t_op [CNT_2][2]. In the initializer, the value is converted to a pointer to its first element of type t_op [2] (array length 2 of t_op), so the pointer is of type t_op (*)[2] (pointer to array length 2 of t_op). The type cast operation is converting the pointer to t_op ** (pointer to pointer to t_op). combi[0].op[0] should be of type t_op *, which is not compatible with the underlying object's type: t_op [2].
One way to solve the problem is to define all the variables g_2combi, g_3combi, etc. to be of the same type t_combi. Keeping everything constant, compound literals could be used to initialize the pointers in g_2combi.order etc. For example:
typedef struct s_combi {
int cnt;
const int * const *order;
const t_op * const *op;
} t_combi;
static const t_combi g_2combi = {
.cnt = CNT_2,
.order = (const int * const []){
(const int []){0, 1},
(const int []){1, 0}
},
.op = (const t_op * const []){
(const t_op []){NULL},
(const t_op []){sa, NULL}
}
};
/* define g_3combi etc. in a similar way to the above. */
void init_combi(t_combi combi[4])
{
combi[0] = g_2combi;
combi[1] = g_3combi;
combi[2] = g_4combi;
combi[3] = g_5combi;
}
(Due to the added constness above, the op parameter of the apply_instruction function would need to be changed from t_op *op to const t_op *op.)