在 C 中有一个指向多个不同大小的 LUT 的数组

Question

我正在为一个学校项目做一个使用两个堆栈对一堆数字进行排序的程序，我想通过蛮力方法处理堆栈大小低于或等于 5 的情况，为此，我有不同的结构，其中包含查找表，其中包含一个表示数字顺序的 int 数组数组（对于每个可能的顺序），以及一个函数指针数组数组，其中包含对它们进行排序的相应操作序列，以及这些结构中的每一个对应于特定的数组大小（2、3、4、5）。为了避免巨大的 if 森林，我想使用带有指向不同数据的指针的通用结构 (t_combi) 的 while 循环来访问它们，但显然它不起作用，我以某种方式丢失了全局数组的地址，因为在比较订单时的第一次迭代中出现段错误（尝试使用 valgrind 访问未分配的数据）。

代码：

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

Answer 1

一个大问题是您将指针隐藏在 typedef 后面。这只有一个目的：混淆程序员和其他阅读代码的人。

例如 t_op **op; 不带 typedef 的扩展创建一个类型为

的函数指针

typedef const char      *(***t_op)(t_stack *, t_stack *);

如您所料，这简直是疯了。在你可以做任何其他事情之前，你需要摆脱这些 typedef 和不必要的多重间接层。

一个合理的 typedef 函数指针可能看起来像这样（它实际上是一个函数的 typedef）：

typedef char* t_op (t_stack*, t_stack*);

然后您将其用作 t_op* op。

总的来说，您的程序方式太复杂了，无法完成听起来相当微不足道的任务。任何地方都不应该有任何演员表，另一个例子 - 所有这些都是为了隐藏错误。

Answer 2

主要问题是您将指向某种类型数组的指针转换为指向某种类型指针的指针。例如，在这段代码中：

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 是 int: int [CNT_2][2] 的二维数组。在初始化器中，该值被转换为指向其第一个元素的指针。元素的类型是int [2]（int的数组长度2），所以指向元素的指针的类型是int (*)[2]（指向int的数组长度2的指针).但是，类型转换操作将其转换为指向不兼容类型 int ** 的指针（指向指向 int 的指针）。 combi[0].order[0] 应该是 int * 类型，它与底层对象的类型不兼容：int [2].

同理，g_2combi.op是t_op的二维数组：t_op [CNT_2][2]。在初始化器中，该值被转换为指向其第一个类型为 t_op [2] 的元素的指针（t_op 的数组长度 2），因此该指针的类型为 t_op (*)[2]（指向数组长度的指针t_op 中的 2 个）。类型转换操作将指针转换为 t_op **（指向指向 t_op 的指针）。 combi[0].op[0] 应该是 t_op * 类型，它与底层对象的类型不兼容：t_op [2].

解决该问题的一种方法是将所有变量g_2combi、g_3combi等定义为同一类型t_combi。保持一切不变，compound literals 可用于初始化 g_2combi.order 等中的指针。例如：

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

(由于上面添加了constness，apply_instruction函数的op参数需要从t_op *op改为const t_op *op .)

在 C 中有一个指向多个不同大小的 LUT 的数组

Having an array that points to multiple LUT with different sizes in C

c

pointers

lookup-tables

segmentation-fault