在 c 中为具有指定值的枚举进行静态查找 table
static lookup table in c for enum with assigned values
所以我的问题基本上与 相同，但在 C 中，所以我没有模板等。我有一个带有赋值的枚举类型，所以它不是连续的。然后我想根据哪个枚举来调用一堆函数，所有函数都有相同的参数。这是针对嵌入式系统的，因此速度和内存都很重要。理想情况下，我会定义一个数组并将值指向函数指针，然后在处理函数中，我只需在特定的数组位置调用函数指针。
问题是我的枚举已经赋值了。例如，当我有 20 个分配了最大 vlaue 0xA000 的函数时，就会有很多空字节就在那里。
有没有其他方法可以优雅地处理这个问题，而无需维护大型 switch case？
更新
为了让问题更清楚一点。用法是在I2C通信的slave端。我有多个具有不同命令的频道。例如，假设我的枚举如下，其中命令是根据 I2C 消息中到达的前两个字节定义的。
typedef enum {
COMMAND_1 = 0x0110,
COMMAND_2 = 0x0120,
COMMAND_x = 0x01A3,
INFO_1 = 0x0210,
INFO_2 = 0x0220,
INFO_3 = 0x0230,
SM_LAST,
} SM_t;
正如评论中所建议和问题中提到的那样，如果 ram 不是问题，我可以简单地执行以下操作：
void (*sm_func[SM_LAST]) (arguments) = {0};
sm_func[COMMAND_1] = command_1_func;
sm_func[COMMAND_2] = command_2_func;
sm_func[COMMAND_x] = command_x_func;
sm_func[INFO_1] = info_1_func;
sm_func[INFO_2] = info_2_func;
sm_func[INFO_3] = info_3_func;
uint8_t handler(uin8_t request[2]) {
uint16_t req = (uint16_t) req;
(*sm_func[req])(arguments);
}
这种方法的问题是 sm_func 的每个成员都有 4 个字节，现在如果枚举值是 uint16_t 并且被隔开（出于设计目的），那么这可能会失败真快。
使用另一层间接将非连续值转换为连续值。
#include <stdlib.h>
enum SM_e {
COMMAND_1 = 0x0110,
COMMAND_2 = 0x0120,
COMMAND_x = 0x01A3,
};
enum SM_idx_e {
SM_IDX_COMMAND_1,
SM_IDX_COMMAND_2,
SM_IDX_COMMAND_x,
SM_IDX_COUNT,
};
// constant expression version
// one place for your "switch"
#define SM_TO_IDX(sm) (size_t)( \
(sm) == COMMAND_1 ? SM_IDX_COMMAND_1 : \
(sm) == COMMAND_2 ? SM_IDX_COMMAND_2 : \
(sm) == COMMAND_x ? SM_IDX_COMMAND_x : \
(size_t)-1 )
// normal version
size_t sm_to_idx(enum SM_e sm) {
size_t r = SM_TO_IDX(sm);
assert(r != (size_t)-1)
return r;
}
void func_handle_command_1(int);
void func_handle_command_2(int);
void func_handle_command_x(int);
static void (*const sm_func[])(int) = {
[SM_TO_IDX(COMMAND_1)] = func_handle_command_1,
[SM_TO_IDX(COMMAND_2)] = func_handle_command_2,
[SM_TO_IDX(COMMAND_x)] = func_handle_command_x,
// etc.
};
uint8_t handler(uin8_t request[2]) {
uint16_t req = (uint16_t)req; // ???
sm_func[sm_to_idx(req)](arguments);
}
A switch/case 就像通过 table 查找 table 索引的线性搜索。
我们想要的是采用传入的两字节代码值（例如“code”）[可以是任意的]并将其转换为线性 table index/pointer.
可能可以想出一个复杂的多table查找，（例如）将最左边的半字节作为“零级”的索引table。然后，下一个最左边的数字是第二层的索引 table。这类似于虚拟内存页面 table 的设置方式。
但是，这可能很复杂，虽然速度很快，但可能会占用更多内存。
使用虚函数 table 方法，我们将代码放入 vtable 条目，连同我们需要的任何函数指针。
如果 table 已排序，我们可以使用二进制搜索找到正确的 table 条目。下面，我使用二进制搜索将传入代码翻译成 table index/pointer.
这个函数的速度（例如下面的vtblfind）是它的症结所在。二进制搜索是 fast 和 general。但是，有可能设计出更快的专用函数
下面是一些说明二进制搜索方法的代码：
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
typedef enum {
COMMAND_1 = 0x0110,
COMMAND_2 = 0x0120,
COMMAND_x = 0x01A3,
INFO_1 = 0x0210,
INFO_2 = 0x0220,
INFO_3 = 0x0230,
#if 0
SM_LAST,
#endif
} SM_t;
typedef struct smctl smctl_t;
typedef void (*smfunc_p)(smctl_t *ctl,void *data);
struct smctl {
SM_t sm_port; // I2C port value
smfunc_p sm_func1; // a function
smfunc_p sm_func2; // another function
smfunc_p sm_func3; // yet another function
};
void command_1_func(smctl_t *,void *);
void command_2_func(smctl_t *,void *);
void command_x_func(smctl_t *,void *);
void info_1_func(smctl_t *,void *);
void info_2_func(smctl_t *,void *);
void info_3_func(smctl_t *,void *);
smctl_t vtable[] = {
{ .sm_port = COMMAND_1, .sm_func1 = command_1_func },
{ .sm_port = COMMAND_2, .sm_func1 = command_2_func },
{ .sm_port = COMMAND_x, .sm_func1 = command_x_func },
{ .sm_port = INFO_1, .sm_func1 = info_1_func },
{ .sm_port = INFO_2, .sm_func1 = info_2_func },
{ .sm_port = INFO_3, .sm_func1 = info_3_func },
};
#define ARRAY_COUNT(_arr) \
(sizeof(_arr) / sizeof(_arr[0]))
smctl_t *
vtblfind(uint16_t port)
{
int pval = port;
int ilo = 0;
int ihi = ARRAY_COUNT(vtable) - 1;
int imid;
int dif;
smctl_t *vptr = NULL;
smctl_t *vret = NULL;
while (ilo <= ihi) {
imid = (ilo + ihi) / 2;
vptr = &vtable[imid];
dif = pval - vptr->sm_port;
if (dif == 0) {
vret = vptr;
break;
}
if (dif < 0)
ihi = imid - 1;
else
ilo = imid + 1;
}
return vret;
}
uint8_t
handler(uint8_t request[2])
{
uint16_t port = *(uint16_t *) request;
smctl_t *vptr;
uint8_t ret = 23;
do {
vptr = vtblfind(port);
if (vptr == NULL) {
printf("handler: unknown request code -- %2.2X\n",port);
break;
}
vptr->sm_func1(vptr,request);
vptr->sm_func2(vptr,request);
} while (0);
return ret;
}
更新：
I think the switch depends on the compiler implementation but mostly, they are not a linear search. A constant time is more usual
智能编译器可能能够将一些测试组合成范围或一些其他窥视孔优化，例如“条件移动”（例如cmovne）。
但是，它仍然是一个“线性”搜索：如果有 N 个案例，则需要进行 N 次比较、设置、跳转。
编译器必须选择一个顺序，编译器可以重新排序它们，但通常不会，因为为了忠实于源顺序，它遵循它。原因是，如果你有一个 90% 最典型的案例，你 [程序员] 把它放在第一位，因为你 想要 先测试它。
如果您将 switch 重新编码为 if/else 阶梯，您将强制执行该顺序。您希望 switch.
具有相同的行为
如果案例是连续的（例如1, 2, 3, 4, ..., N）[或几乎如此]，编译器可以 构建一个跳转 table 并在其中建立索引。 会 是恒定的 [O(1)] 时间。对于某些特殊的 switch 序列，我 已经 看到编译器这样做。
不幸的是，这正是我们所没有的——OP问题的全部要点。
这是一个基于 switch 的函数：
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
typedef enum {
COMMAND_1 = 0x0110,
COMMAND_2 = 0x0120,
COMMAND_x = 0x01A3,
INFO_1 = 0x0210,
INFO_2 = 0x0220,
INFO_3 = 0x0230,
#if 0
SM_LAST,
#endif
} SM_t;
typedef struct smctl smctl_t;
typedef void (*smfunc_p)(smctl_t *ctl,void *data);
struct smctl {
SM_t sm_port; // I2C port value
smfunc_p sm_func1; // a function
smfunc_p sm_func2; // another function
smfunc_p sm_func3; // yet another function
};
void command_1_func(smctl_t *,void *);
void command_2_func(smctl_t *,void *);
void command_x_func(smctl_t *,void *);
void info_1_func(smctl_t *,void *);
void info_2_func(smctl_t *,void *);
void info_3_func(smctl_t *,void *);
smfunc_p
funcfind(uint16_t port)
{
smfunc_p func = NULL;
switch (port) {
case COMMAND_1:
func = command_1_func;
break;
case COMMAND_2:
func = command_2_func;
break;
case COMMAND_x:
func = command_x_func;
break;
case INFO_1:
func = info_1_func;
break;
case INFO_2:
func = info_2_func;
break;
case INFO_3:
func = info_3_func;
break;
default:
func = NULL;
break;
}
return func;
}
uint8_t
handler(uint8_t request[2])
{
uint16_t port = *(uint16_t *) request;
smfunc_p func;
uint8_t ret = 23;
do {
func = funcfind(port);
if (func == NULL) {
printf("handler: unknown request code -- %2.2X\n",port);
break;
}
func(NULL,request);
} while (0);
return ret;
}
这是 [x86_64] 的反汇编 [with -O2]。还有6条cmp条指令，与6条case条语句相同：
0000000000000000 <funcfind>:
0: 66 81 ff a3 01 cmp [=12=]x1a3,%di
5: 74 31 je 38 <L00>
7: 76 37 jbe 40 <L02>
9: b8 00 00 00 00 mov [=12=]x0,%eax
e: 66 81 ff 20 02 cmp [=12=]x220,%di
13: 74 28 je 3d <L01>
15: b8 00 00 00 00 mov [=12=]x0,%eax
1a: 66 81 ff 30 02 cmp [=12=]x230,%di
1f: 74 1c je 3d <L01>
21: 66 81 ff 10 02 cmp [=12=]x210,%di
26: ba 00 00 00 00 mov [=12=]x0,%edx
2b: b8 00 00 00 00 mov [=12=]x0,%eax
30: 48 0f 45 c2 cmovne %rdx,%rax
34: c3 retq
35: 0f 1f 00 nopl (%rax)
38:L00 b8 00 00 00 00 mov [=12=]x0,%eax
3d:L01 c3 retq
3e: 66 90 xchg %ax,%ax
40:L02 b8 00 00 00 00 mov [=12=]x0,%eax
45: 66 81 ff 10 01 cmp [=12=]x110,%di
4a: 74 f1 je 3d <L01>
4c: 66 81 ff 20 01 cmp [=12=]x120,%di
51: ba 00 00 00 00 mov [=12=]x0,%edx
56: b8 00 00 00 00 mov [=12=]x0,%eax
5b: 48 0f 45 c2 cmovne %rdx,%rax
5f: c3 retq
更新#2：
I think this is the best performance that can be achieved using low-level languages (probably faster than higher performance solutions in high-level languages).
是的，考虑到您拥有的两个字节“密钥”，这大约是最快的。它不会很好地“散列”[任何像样的散列算法都会更慢——见下文]。
I was hoping to find something like a python dictionary where the key would be the enum and the value would be function pointer.
啊，python ... [就我个人而言，我更喜欢 perl，但另一个话题，也许 ;-)]。
你所说的 python 字典就是 perl 所谓的“哈希”[又名“关联数组”]。
对其进行索引，欺骗性地 看起来像一个 O(1) 操作 [基于语法]，但是，它在幕后更多 [这是我们所拥有的水平说说什么时候用c].
两字节密钥不会从散列中获益太多。因此，让我们考虑一个任意长度的缓冲区（例如字符串）。
我们计算一个 [32 位] 哈希值。对于固定常量字符串，perl/python 编译器可以在编译时计算哈希值。
无论哪种方式，我们都使用散列值（对散列桶的数量取模）索引到散列中 table 以获得子列表的地址。我们必须遍历该列表以找到与实际键匹配的项。
子列表通常是单[或双]链表。所以，我们必须遍历它。
或者，子列表可以是一个排序数组，我们可以使用二进制搜索。或者，它可以是一棵平衡树（例如 red/black 树）。但是，这些在一般情况下问题更大。
这里重写了我的原始代码，它根据 string/length 查找描述符。为了简洁起见，这只有“搜索”代码[和没有insert/update/delete]。
请注意，我使用的 strhash 函数是对 perl 实际散列函数的抄袭。 python 将使用类似的东西。给定搜索的执行时间将与 python 或 perl:
相当
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
// strhash -- calculate a string hash
uint32_t
strhash(const void *bf,size_t bflen)
{
const uint8_t *bp;
const uint8_t *bfe;
uint32_t hash;
bp = bf;
bfe = bp + bflen;
hash = 0x37FB26C5;
for (; bp < bfe; ++bp) {
hash += *bp;
hash += hash << 10;
hash ^= hash >> 6;
}
hash += hash << 3;
hash ^= hash >> 11;
hash += hash << 15;
return hash;
}
typedef struct smctl smctl_t;
typedef void (*smfunc_p)(smctl_t *ctl,void *data);
struct smctl {
uint32_t sm_hash; // hash value
const uint8_t *sm_key; // key value
size_t sm_keylen; // length of sm_key
smctl_t *sm_next; // pointer to next element on sublist
smfunc_p sm_func1; // a function
smfunc_p sm_func2; // another function
smfunc_p sm_func3; // yet another function
};
// hash table element
typedef struct {
smctl_t *list_head; // head of list
} vlist_t;
// hash table
#define HASHMAX 256
vlist_t hashlist[HASHMAX];
smctl_t *
vtblfind(const void *buf,size_t buflen)
{
uint32_t hash;
smctl_t *ctl;
// get hash value for buffer
hash = strhash(buf,buflen);
// locate hash bucket
vlist_t *vlist = &hashlist[hash % HASHMAX];
// scan hash bucket for match
for (ctl = vlist->list_head; ctl != NULL; ctl = ctl->sm_next) {
// hash values must match
if (hash != ctl->sm_hash)
continue;
// key length must match
if (ctl->sm_keylen != buflen)
continue;
// do compare of key/buffer contents
if (memcmp(ctl->sm_key,buf,buflen) == 0)
break;
}
return ctl;
}
void
test(void)
{
smctl_t *ctl = vtblfind("the quick brown fox",19);
printf("test: ctl=%p\n",ctl);
}
更新#3：
I was hoping that someone has come up with a simple, static, heuristic hashing function for these cases that doesn't need collision resolution etc.
switch 或二进制搜索不使用冲突解决。那只是字符串示例。
I guess for the number of commands I have (around 50)
经验法则是对最多 ~20 个项目进行线性搜索，对更大的项目进行二分搜索。
有了 精确的 端口号列表，就有可能获得“智能”定位器。也就是说，可能是基于 MSB 然后是 LSB 的 2 级查找。或者，一些紧凑但快速的基于特定于实际端口号的技巧。
因为你有 speed/space 权衡，你必须 measure/benchmark 找到最佳组合。
a switch case would be the best way to go for code maintainability. I can put the most commonly used commands on top to save some speed
我的一般规则是：如果你不能测量它，你就不能调整它
正如我 [和其他人] 所提到的，table 与 switch 一样快并且内存占用更少。由于处理器指令缓存上的负载较小，table 甚至可能更快。
switch 缩放 不太好。如果你有一百万种类型，table 将是显而易见的。如果你有两个，switch 会很明显。每当我不得不做出 switch 与 table 的决定时，我通常会发现 table 方法是基于几个因素的赢家。 YMMV.
对于二进制搜索，如果您不想手动对列表进行排序，您可以在初始化期间使用（例如）qsort 调用。
如果您决定按频率从高到低排序 table，线性搜索将是最佳选择。
另一种方法是“缓存”最频繁的 found/used 条目（又名“记忆”）。如果有缓存命中，则使用它。如果不是，则可以使用“慢速”路径（即二进制搜索）。缓存替换可以基于 LRU 或频率。
考虑一个多步骤的设计过程。您可以从二进制搜索实现开始。这可能是总体上最好的 space/speed 权衡。
开始工作。用它来收集频率数据和基准值。查看是否存在某种模式（例如，portA 始终跟在 portB 之后）。收集的数据可以帮助指导您为您的用例找到更优化的解决方案。
下面是一些说明缓存方法的代码：
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
typedef uint32_t u32;
typedef enum {
COMMAND_1 = 0x0110,
COMMAND_2 = 0x0120,
COMMAND_x = 0x01A3,
INFO_1 = 0x0210,
INFO_2 = 0x0220,
INFO_3 = 0x0230,
#if 0
SM_LAST,
#endif
} SM_t;
typedef struct smctl smctl_t;
typedef void (*smfunc_p)(smctl_t *ctl,void *data);
struct smctl {
SM_t sm_port; // I2C port value
u32 sm_freq; // frequency count
smfunc_p sm_func1; // a function
smfunc_p sm_func2; // another function
smfunc_p sm_func3; // yet another function
};
void command_1_func(smctl_t *,void *);
void command_2_func(smctl_t *,void *);
void command_x_func(smctl_t *,void *);
void info_1_func(smctl_t *,void *);
void info_2_func(smctl_t *,void *);
void info_3_func(smctl_t *,void *);
smctl_t vtable[] = {
{ .sm_port = COMMAND_1, .sm_func1 = command_1_func },
{ .sm_port = COMMAND_2, .sm_func1 = command_2_func },
{ .sm_port = COMMAND_x, .sm_func1 = command_x_func },
{ .sm_port = INFO_1, .sm_func1 = info_1_func },
{ .sm_port = INFO_2, .sm_func1 = info_2_func },
{ .sm_port = INFO_3, .sm_func1 = info_3_func },
};
typedef struct {
#if OPT_CASHPORT
SM_t cash_port; // I2C port value
#endif
smctl_t *cash_ctl; // pointer to control
#if OPT_LRU
u32 cash_lru; // temporal value
#endif
} smcash_t;
#define CASHMAX 4
smcash_t cashlist[CASHMAX];
#if OPT_LRU
u32 lrucur; // current LRU
#endif
#define ARRAY_COUNT(_arr) \
(sizeof(_arr) / sizeof(_arr[0]))
smctl_t *
vtblfind(uint16_t port)
{
int pval = port;
int ilo = 0;
int ihi = ARRAY_COUNT(vtable) - 1;
int imid;
int dif;
smctl_t *vptr = NULL;
smctl_t *vret = NULL;
while (ilo <= ihi) {
imid = (ilo + ihi) / 2;
vptr = &vtable[imid];
dif = pval - vptr->sm_port;
if (dif == 0) {
vret = vptr;
break;
}
if (dif < 0)
ihi = imid - 1;
else
ilo = imid + 1;
}
return vret;
}
static inline int
cashcmp(const smcash_t *cash,uint16_t port)
{
int match;
#if OPT_CASHPORT
match = (cash->cash_port == port);
#else
match = (cash->cash_ctl->sm_port == port);
#endif
return match;
}
uint8_t
handler(uint8_t request[2])
{
uint16_t port = *(uint16_t *) request;
smctl_t *vptr = NULL;
smcash_t *cashcur = cashlist;
smcash_t *cashold = cashlist;
smcash_t *cashmatch = NULL;
uint8_t ret = 23;
do {
#if (! OPT_LRU)
u32 oldfreq = cashold->cash_ctl->sm_freq;
#endif
for (; cashcur < &cashlist[CASHMAX]; ++cashcur) {
// get exact match
if (cashcmp(cashcur,port))
cashmatch = cashcur;
// find oldest cache entry
#if OPT_LRU
if (cashcur->cash_lru < lrucur)
cashold = cashcur;
#else
u32 curfreq = cashcur->cash_ctl->sm_freq;
if (curfreq < oldfreq) {
oldfreq = curfreq;
cashold = cashcur;
}
#endif
}
// slow path lookup
if (vptr == NULL)
vptr = vtblfind(port);
if (vptr == NULL) {
printf("handler: unknown request code -- %2.2X\n",port);
break;
}
// update the cache
do {
// no exact match found
if (cashmatch == NULL) {
cashmatch = cashold;
#if OPT_CASHPORT
cashmatch->cash_port = port;
#endif
cashmatch->cash_ctl = vptr;
break;
}
smcash_t tmp = *cashold;
*cashold = *cashmatch;
*cashmatch = tmp;
} while (0);
#if OPT_LRU
cashmatch->cash_lru = ++lrucur;
#endif
vptr->sm_freq += 1;
vptr->sm_func1(vptr,request);
vptr->sm_func2(vptr,request);
} while (0);
return ret;
}
只需进行标准查找 table。 table 大小可能小于 switch 语句中代码的大小。
typedef void (*func) (arguments);
struct entry {
SM_t cmd;
func fp;
} LUT[] = {
{ COMMAND_1, command_1_func },
{ COMMAND_2, command_2_func },
// etc.
};
SM_t cmd_in = (SM_T) request;
func fp = unknown_request_func;
for (int f=0; f < sizeof(LUT) / sizeof(LUT[0]); f++) {
if (cmd_in == LUT[f].cmd) {
fp = LUT[f].fp;
break;
}
}
所以我的问题基本上与
问题是我的枚举已经赋值了。例如，当我有 20 个分配了最大 vlaue 0xA000 的函数时，就会有很多空字节就在那里。
有没有其他方法可以优雅地处理这个问题，而无需维护大型 switch case？
更新
为了让问题更清楚一点。用法是在I2C通信的slave端。我有多个具有不同命令的频道。例如，假设我的枚举如下，其中命令是根据 I2C 消息中到达的前两个字节定义的。
typedef enum {
COMMAND_1 = 0x0110,
COMMAND_2 = 0x0120,
COMMAND_x = 0x01A3,
INFO_1 = 0x0210,
INFO_2 = 0x0220,
INFO_3 = 0x0230,
SM_LAST,
} SM_t;
正如评论中所建议和问题中提到的那样，如果 ram 不是问题，我可以简单地执行以下操作：
void (*sm_func[SM_LAST]) (arguments) = {0};
sm_func[COMMAND_1] = command_1_func;
sm_func[COMMAND_2] = command_2_func;
sm_func[COMMAND_x] = command_x_func;
sm_func[INFO_1] = info_1_func;
sm_func[INFO_2] = info_2_func;
sm_func[INFO_3] = info_3_func;
uint8_t handler(uin8_t request[2]) {
uint16_t req = (uint16_t) req;
(*sm_func[req])(arguments);
}
这种方法的问题是 sm_func 的每个成员都有 4 个字节，现在如果枚举值是 uint16_t 并且被隔开（出于设计目的），那么这可能会失败真快。
使用另一层间接将非连续值转换为连续值。
#include <stdlib.h>
enum SM_e {
COMMAND_1 = 0x0110,
COMMAND_2 = 0x0120,
COMMAND_x = 0x01A3,
};
enum SM_idx_e {
SM_IDX_COMMAND_1,
SM_IDX_COMMAND_2,
SM_IDX_COMMAND_x,
SM_IDX_COUNT,
};
// constant expression version
// one place for your "switch"
#define SM_TO_IDX(sm) (size_t)( \
(sm) == COMMAND_1 ? SM_IDX_COMMAND_1 : \
(sm) == COMMAND_2 ? SM_IDX_COMMAND_2 : \
(sm) == COMMAND_x ? SM_IDX_COMMAND_x : \
(size_t)-1 )
// normal version
size_t sm_to_idx(enum SM_e sm) {
size_t r = SM_TO_IDX(sm);
assert(r != (size_t)-1)
return r;
}
void func_handle_command_1(int);
void func_handle_command_2(int);
void func_handle_command_x(int);
static void (*const sm_func[])(int) = {
[SM_TO_IDX(COMMAND_1)] = func_handle_command_1,
[SM_TO_IDX(COMMAND_2)] = func_handle_command_2,
[SM_TO_IDX(COMMAND_x)] = func_handle_command_x,
// etc.
};
uint8_t handler(uin8_t request[2]) {
uint16_t req = (uint16_t)req; // ???
sm_func[sm_to_idx(req)](arguments);
}
A switch/case 就像通过 table 查找 table 索引的线性搜索。
我们想要的是采用传入的两字节代码值（例如“code”）[可以是任意的]并将其转换为线性 table index/pointer.
可能可以想出一个复杂的多table查找，（例如）将最左边的半字节作为“零级”的索引table。然后，下一个最左边的数字是第二层的索引 table。这类似于虚拟内存页面 table 的设置方式。
但是，这可能很复杂，虽然速度很快，但可能会占用更多内存。
使用虚函数 table 方法，我们将代码放入 vtable 条目，连同我们需要的任何函数指针。
如果 table 已排序，我们可以使用二进制搜索找到正确的 table 条目。下面，我使用二进制搜索将传入代码翻译成 table index/pointer.
这个函数的速度（例如下面的vtblfind）是它的症结所在。二进制搜索是 fast 和 general。但是，有可能设计出更快的专用函数
下面是一些说明二进制搜索方法的代码：
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
typedef enum {
COMMAND_1 = 0x0110,
COMMAND_2 = 0x0120,
COMMAND_x = 0x01A3,
INFO_1 = 0x0210,
INFO_2 = 0x0220,
INFO_3 = 0x0230,
#if 0
SM_LAST,
#endif
} SM_t;
typedef struct smctl smctl_t;
typedef void (*smfunc_p)(smctl_t *ctl,void *data);
struct smctl {
SM_t sm_port; // I2C port value
smfunc_p sm_func1; // a function
smfunc_p sm_func2; // another function
smfunc_p sm_func3; // yet another function
};
void command_1_func(smctl_t *,void *);
void command_2_func(smctl_t *,void *);
void command_x_func(smctl_t *,void *);
void info_1_func(smctl_t *,void *);
void info_2_func(smctl_t *,void *);
void info_3_func(smctl_t *,void *);
smctl_t vtable[] = {
{ .sm_port = COMMAND_1, .sm_func1 = command_1_func },
{ .sm_port = COMMAND_2, .sm_func1 = command_2_func },
{ .sm_port = COMMAND_x, .sm_func1 = command_x_func },
{ .sm_port = INFO_1, .sm_func1 = info_1_func },
{ .sm_port = INFO_2, .sm_func1 = info_2_func },
{ .sm_port = INFO_3, .sm_func1 = info_3_func },
};
#define ARRAY_COUNT(_arr) \
(sizeof(_arr) / sizeof(_arr[0]))
smctl_t *
vtblfind(uint16_t port)
{
int pval = port;
int ilo = 0;
int ihi = ARRAY_COUNT(vtable) - 1;
int imid;
int dif;
smctl_t *vptr = NULL;
smctl_t *vret = NULL;
while (ilo <= ihi) {
imid = (ilo + ihi) / 2;
vptr = &vtable[imid];
dif = pval - vptr->sm_port;
if (dif == 0) {
vret = vptr;
break;
}
if (dif < 0)
ihi = imid - 1;
else
ilo = imid + 1;
}
return vret;
}
uint8_t
handler(uint8_t request[2])
{
uint16_t port = *(uint16_t *) request;
smctl_t *vptr;
uint8_t ret = 23;
do {
vptr = vtblfind(port);
if (vptr == NULL) {
printf("handler: unknown request code -- %2.2X\n",port);
break;
}
vptr->sm_func1(vptr,request);
vptr->sm_func2(vptr,request);
} while (0);
return ret;
}
更新：
I think the switch depends on the compiler implementation but mostly, they are not a linear search. A constant time is more usual
智能编译器可能能够将一些测试组合成范围或一些其他窥视孔优化，例如“条件移动”（例如cmovne）。
但是，它仍然是一个“线性”搜索：如果有 N 个案例，则需要进行 N 次比较、设置、跳转。
编译器必须选择一个顺序，编译器可以重新排序它们，但通常不会，因为为了忠实于源顺序，它遵循它。原因是，如果你有一个 90% 最典型的案例，你 [程序员] 把它放在第一位，因为你 想要 先测试它。
如果您将 switch 重新编码为 if/else 阶梯，您将强制执行该顺序。您希望 switch.
如果案例是连续的（例如1, 2, 3, 4, ..., N）[或几乎如此]，编译器可以 构建一个跳转 table 并在其中建立索引。 会 是恒定的 [O(1)] 时间。对于某些特殊的 switch 序列，我 已经 看到编译器这样做。
不幸的是，这正是我们所没有的——OP问题的全部要点。
这是一个基于 switch 的函数：
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
typedef enum {
COMMAND_1 = 0x0110,
COMMAND_2 = 0x0120,
COMMAND_x = 0x01A3,
INFO_1 = 0x0210,
INFO_2 = 0x0220,
INFO_3 = 0x0230,
#if 0
SM_LAST,
#endif
} SM_t;
typedef struct smctl smctl_t;
typedef void (*smfunc_p)(smctl_t *ctl,void *data);
struct smctl {
SM_t sm_port; // I2C port value
smfunc_p sm_func1; // a function
smfunc_p sm_func2; // another function
smfunc_p sm_func3; // yet another function
};
void command_1_func(smctl_t *,void *);
void command_2_func(smctl_t *,void *);
void command_x_func(smctl_t *,void *);
void info_1_func(smctl_t *,void *);
void info_2_func(smctl_t *,void *);
void info_3_func(smctl_t *,void *);
smfunc_p
funcfind(uint16_t port)
{
smfunc_p func = NULL;
switch (port) {
case COMMAND_1:
func = command_1_func;
break;
case COMMAND_2:
func = command_2_func;
break;
case COMMAND_x:
func = command_x_func;
break;
case INFO_1:
func = info_1_func;
break;
case INFO_2:
func = info_2_func;
break;
case INFO_3:
func = info_3_func;
break;
default:
func = NULL;
break;
}
return func;
}
uint8_t
handler(uint8_t request[2])
{
uint16_t port = *(uint16_t *) request;
smfunc_p func;
uint8_t ret = 23;
do {
func = funcfind(port);
if (func == NULL) {
printf("handler: unknown request code -- %2.2X\n",port);
break;
}
func(NULL,request);
} while (0);
return ret;
}
这是 [x86_64] 的反汇编 [with -O2]。还有6条cmp条指令，与6条case条语句相同：
0000000000000000 <funcfind>:
0: 66 81 ff a3 01 cmp [=12=]x1a3,%di
5: 74 31 je 38 <L00>
7: 76 37 jbe 40 <L02>
9: b8 00 00 00 00 mov [=12=]x0,%eax
e: 66 81 ff 20 02 cmp [=12=]x220,%di
13: 74 28 je 3d <L01>
15: b8 00 00 00 00 mov [=12=]x0,%eax
1a: 66 81 ff 30 02 cmp [=12=]x230,%di
1f: 74 1c je 3d <L01>
21: 66 81 ff 10 02 cmp [=12=]x210,%di
26: ba 00 00 00 00 mov [=12=]x0,%edx
2b: b8 00 00 00 00 mov [=12=]x0,%eax
30: 48 0f 45 c2 cmovne %rdx,%rax
34: c3 retq
35: 0f 1f 00 nopl (%rax)
38:L00 b8 00 00 00 00 mov [=12=]x0,%eax
3d:L01 c3 retq
3e: 66 90 xchg %ax,%ax
40:L02 b8 00 00 00 00 mov [=12=]x0,%eax
45: 66 81 ff 10 01 cmp [=12=]x110,%di
4a: 74 f1 je 3d <L01>
4c: 66 81 ff 20 01 cmp [=12=]x120,%di
51: ba 00 00 00 00 mov [=12=]x0,%edx
56: b8 00 00 00 00 mov [=12=]x0,%eax
5b: 48 0f 45 c2 cmovne %rdx,%rax
5f: c3 retq
更新#2：
I think this is the best performance that can be achieved using low-level languages (probably faster than higher performance solutions in high-level languages).
是的，考虑到您拥有的两个字节“密钥”，这大约是最快的。它不会很好地“散列”[任何像样的散列算法都会更慢——见下文]。
I was hoping to find something like a
pythondictionary where the key would be theenumand the value would be function pointer.
啊，python ... [就我个人而言，我更喜欢 perl，但另一个话题，也许 ;-)]。
你所说的 python 字典就是 perl 所谓的“哈希”[又名“关联数组”]。
对其进行索引，欺骗性地 看起来像一个 O(1) 操作 [基于语法]，但是，它在幕后更多 [这是我们所拥有的水平说说什么时候用c].
两字节密钥不会从散列中获益太多。因此，让我们考虑一个任意长度的缓冲区（例如字符串）。
我们计算一个 [32 位] 哈希值。对于固定常量字符串，perl/python 编译器可以在编译时计算哈希值。
无论哪种方式，我们都使用散列值（对散列桶的数量取模）索引到散列中 table 以获得子列表的地址。我们必须遍历该列表以找到与实际键匹配的项。
子列表通常是单[或双]链表。所以，我们必须遍历它。
或者，子列表可以是一个排序数组，我们可以使用二进制搜索。或者，它可以是一棵平衡树（例如 red/black 树）。但是，这些在一般情况下问题更大。
这里重写了我的原始代码，它根据 string/length 查找描述符。为了简洁起见，这只有“搜索”代码[和没有insert/update/delete]。
请注意，我使用的 strhash 函数是对 perl 实际散列函数的抄袭。 python 将使用类似的东西。给定搜索的执行时间将与 python 或 perl:
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
// strhash -- calculate a string hash
uint32_t
strhash(const void *bf,size_t bflen)
{
const uint8_t *bp;
const uint8_t *bfe;
uint32_t hash;
bp = bf;
bfe = bp + bflen;
hash = 0x37FB26C5;
for (; bp < bfe; ++bp) {
hash += *bp;
hash += hash << 10;
hash ^= hash >> 6;
}
hash += hash << 3;
hash ^= hash >> 11;
hash += hash << 15;
return hash;
}
typedef struct smctl smctl_t;
typedef void (*smfunc_p)(smctl_t *ctl,void *data);
struct smctl {
uint32_t sm_hash; // hash value
const uint8_t *sm_key; // key value
size_t sm_keylen; // length of sm_key
smctl_t *sm_next; // pointer to next element on sublist
smfunc_p sm_func1; // a function
smfunc_p sm_func2; // another function
smfunc_p sm_func3; // yet another function
};
// hash table element
typedef struct {
smctl_t *list_head; // head of list
} vlist_t;
// hash table
#define HASHMAX 256
vlist_t hashlist[HASHMAX];
smctl_t *
vtblfind(const void *buf,size_t buflen)
{
uint32_t hash;
smctl_t *ctl;
// get hash value for buffer
hash = strhash(buf,buflen);
// locate hash bucket
vlist_t *vlist = &hashlist[hash % HASHMAX];
// scan hash bucket for match
for (ctl = vlist->list_head; ctl != NULL; ctl = ctl->sm_next) {
// hash values must match
if (hash != ctl->sm_hash)
continue;
// key length must match
if (ctl->sm_keylen != buflen)
continue;
// do compare of key/buffer contents
if (memcmp(ctl->sm_key,buf,buflen) == 0)
break;
}
return ctl;
}
void
test(void)
{
smctl_t *ctl = vtblfind("the quick brown fox",19);
printf("test: ctl=%p\n",ctl);
}
更新#3：
I was hoping that someone has come up with a simple, static, heuristic hashing function for these cases that doesn't need collision resolution etc.
switch 或二进制搜索不使用冲突解决。那只是字符串示例。
I guess for the number of commands I have (around 50)
经验法则是对最多 ~20 个项目进行线性搜索，对更大的项目进行二分搜索。
有了 精确的 端口号列表，就有可能获得“智能”定位器。也就是说，可能是基于 MSB 然后是 LSB 的 2 级查找。或者，一些紧凑但快速的基于特定于实际端口号的技巧。
因为你有 speed/space 权衡，你必须 measure/benchmark 找到最佳组合。
a switch case would be the best way to go for code maintainability. I can put the most commonly used commands on top to save some speed
我的一般规则是：如果你不能测量它，你就不能调整它
正如我 [和其他人] 所提到的，table 与 switch 一样快并且内存占用更少。由于处理器指令缓存上的负载较小，table 甚至可能更快。
switch 缩放 不太好。如果你有一百万种类型，table 将是显而易见的。如果你有两个，switch 会很明显。每当我不得不做出 switch 与 table 的决定时，我通常会发现 table 方法是基于几个因素的赢家。 YMMV.
对于二进制搜索，如果您不想手动对列表进行排序，您可以在初始化期间使用（例如）qsort 调用。
如果您决定按频率从高到低排序 table，线性搜索将是最佳选择。
另一种方法是“缓存”最频繁的 found/used 条目（又名“记忆”）。如果有缓存命中，则使用它。如果不是，则可以使用“慢速”路径（即二进制搜索）。缓存替换可以基于 LRU 或频率。
考虑一个多步骤的设计过程。您可以从二进制搜索实现开始。这可能是总体上最好的 space/speed 权衡。
开始工作。用它来收集频率数据和基准值。查看是否存在某种模式（例如，portA 始终跟在 portB 之后）。收集的数据可以帮助指导您为您的用例找到更优化的解决方案。
下面是一些说明缓存方法的代码：
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
typedef uint32_t u32;
typedef enum {
COMMAND_1 = 0x0110,
COMMAND_2 = 0x0120,
COMMAND_x = 0x01A3,
INFO_1 = 0x0210,
INFO_2 = 0x0220,
INFO_3 = 0x0230,
#if 0
SM_LAST,
#endif
} SM_t;
typedef struct smctl smctl_t;
typedef void (*smfunc_p)(smctl_t *ctl,void *data);
struct smctl {
SM_t sm_port; // I2C port value
u32 sm_freq; // frequency count
smfunc_p sm_func1; // a function
smfunc_p sm_func2; // another function
smfunc_p sm_func3; // yet another function
};
void command_1_func(smctl_t *,void *);
void command_2_func(smctl_t *,void *);
void command_x_func(smctl_t *,void *);
void info_1_func(smctl_t *,void *);
void info_2_func(smctl_t *,void *);
void info_3_func(smctl_t *,void *);
smctl_t vtable[] = {
{ .sm_port = COMMAND_1, .sm_func1 = command_1_func },
{ .sm_port = COMMAND_2, .sm_func1 = command_2_func },
{ .sm_port = COMMAND_x, .sm_func1 = command_x_func },
{ .sm_port = INFO_1, .sm_func1 = info_1_func },
{ .sm_port = INFO_2, .sm_func1 = info_2_func },
{ .sm_port = INFO_3, .sm_func1 = info_3_func },
};
typedef struct {
#if OPT_CASHPORT
SM_t cash_port; // I2C port value
#endif
smctl_t *cash_ctl; // pointer to control
#if OPT_LRU
u32 cash_lru; // temporal value
#endif
} smcash_t;
#define CASHMAX 4
smcash_t cashlist[CASHMAX];
#if OPT_LRU
u32 lrucur; // current LRU
#endif
#define ARRAY_COUNT(_arr) \
(sizeof(_arr) / sizeof(_arr[0]))
smctl_t *
vtblfind(uint16_t port)
{
int pval = port;
int ilo = 0;
int ihi = ARRAY_COUNT(vtable) - 1;
int imid;
int dif;
smctl_t *vptr = NULL;
smctl_t *vret = NULL;
while (ilo <= ihi) {
imid = (ilo + ihi) / 2;
vptr = &vtable[imid];
dif = pval - vptr->sm_port;
if (dif == 0) {
vret = vptr;
break;
}
if (dif < 0)
ihi = imid - 1;
else
ilo = imid + 1;
}
return vret;
}
static inline int
cashcmp(const smcash_t *cash,uint16_t port)
{
int match;
#if OPT_CASHPORT
match = (cash->cash_port == port);
#else
match = (cash->cash_ctl->sm_port == port);
#endif
return match;
}
uint8_t
handler(uint8_t request[2])
{
uint16_t port = *(uint16_t *) request;
smctl_t *vptr = NULL;
smcash_t *cashcur = cashlist;
smcash_t *cashold = cashlist;
smcash_t *cashmatch = NULL;
uint8_t ret = 23;
do {
#if (! OPT_LRU)
u32 oldfreq = cashold->cash_ctl->sm_freq;
#endif
for (; cashcur < &cashlist[CASHMAX]; ++cashcur) {
// get exact match
if (cashcmp(cashcur,port))
cashmatch = cashcur;
// find oldest cache entry
#if OPT_LRU
if (cashcur->cash_lru < lrucur)
cashold = cashcur;
#else
u32 curfreq = cashcur->cash_ctl->sm_freq;
if (curfreq < oldfreq) {
oldfreq = curfreq;
cashold = cashcur;
}
#endif
}
// slow path lookup
if (vptr == NULL)
vptr = vtblfind(port);
if (vptr == NULL) {
printf("handler: unknown request code -- %2.2X\n",port);
break;
}
// update the cache
do {
// no exact match found
if (cashmatch == NULL) {
cashmatch = cashold;
#if OPT_CASHPORT
cashmatch->cash_port = port;
#endif
cashmatch->cash_ctl = vptr;
break;
}
smcash_t tmp = *cashold;
*cashold = *cashmatch;
*cashmatch = tmp;
} while (0);
#if OPT_LRU
cashmatch->cash_lru = ++lrucur;
#endif
vptr->sm_freq += 1;
vptr->sm_func1(vptr,request);
vptr->sm_func2(vptr,request);
} while (0);
return ret;
}
只需进行标准查找 table。 table 大小可能小于 switch 语句中代码的大小。
typedef void (*func) (arguments);
struct entry {
SM_t cmd;
func fp;
} LUT[] = {
{ COMMAND_1, command_1_func },
{ COMMAND_2, command_2_func },
// etc.
};
SM_t cmd_in = (SM_T) request;
func fp = unknown_request_func;
for (int f=0; f < sizeof(LUT) / sizeof(LUT[0]); f++) {
if (cmd_in == LUT[f].cmd) {
fp = LUT[f].fp;
break;
}
}