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);
}
CodePudding user response:
One big problem is that you are hiding pointers behind typedef. This serves one single purpose: to confuse the programmer and everyone else reading the code.
For example t_op **op;
expanded without typedef creates a function pointer of type
typedef const char *(***t_op)(t_stack *, t_stack *);
As you hopefully can tell, that's simply madness. You need to get rid of these typedefs and needless layers of multiple indirection, before you can do anything else.
A sensible typedef
of a function pointer might look like this (it's actually a typedef of a function):
typedef char* t_op (t_stack*, t_stack*);
Which you then use as t_op* op
.
Overall, your program is way too complicated for something that sounds like a fairly trivial task. There shouldn't be any casts anywhere, as another example - all these do is to hide away bugs.
CodePudding user response:
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;
}