问题描述
所以我的问题基本上与这个问题相同，但在C语言中所以我没有模板等.我有一个带有分配值的枚举类型，所以它不是连续的.然后我想根据情况来调用一堆函数，所有函数都具有相同的参数.这是针对嵌入式系统的，因此速度和内存都很重要.理想情况下，我将定义一个数组并将值指向函数指针，然后在处理程序函数中，我只在特定的数组位置调用函数指针.
So my problem is basically the same as this question but in C so I don't have templates, etc. I have an enum type with assigned values so it is not continuous. Then I want to call a bunch of functions based on which enum is the case, all the functions have the same arguments. This is for an embedded system so speed and ram are both important. Ideally, I would define an array and point the values to function pointers, then in the handler function, I just call the function pointer at a specific array location.
麻烦的是我的枚举已分配值.例如，当我有20个函数，并且分配给vlaue的值最大为0xA000时，就坐在那里有很多空字节.
The trouble is my enum has assigned values. For example when I have 20 functions with the largest assigned vlaue 0xA000, then this is a lot of empty bytes just sitting there.
还有其他方法可以优雅地处理此问题而又无需维护大型开关盒吗?
Is there any other way to handle this gracefully without the trouble of maintaining a large switch case?
更新
使问题更加清楚.用法在I2C通信的从属端.我有多个使用不同命令的通道.例如，假设我的枚举是以下内容，其中该命令是根据I2C消息中到达的前两个字节定义的.
To make the problem a little more clear. The usage is on the slave side of I2C communication. I have multiple channels with different commands. For example, assume my enum is the following where the command is defined based on the first two bytes that arrive in I2C message.
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不是问题，我可以简单地执行以下操作:
As suggested in the comment and mentioned in the question, if ram was not an issue I could simply do the following:
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);
}
这种方法的麻烦之处在于，现在，如果枚举值是 uint16_t 并被隔开(出于设计目的)，则 sm_func 的每个成员都具有4个字节，那么这可以吹得很快.
The trouble with this approach is that each member of sm_func has 4 bytes, now if when the enum values are uint16_t and are spaced out (for design purposes), then this can blow really fast.
推荐答案
switch/case 就像通过表进行线性搜索以查找表索引一样.
A switch/case is like a linear search through a table to find a table index.
我们想要的东西采用传入的两个字节的代码值(例如"code")(可以是任意的)并将其转换为线性表索引/指针.
What we want is something that takes the incoming two byte code value (e.g. "code") [which can be arbitrary] and convert this to a linear table index/pointer.
有可能提出一种精心设计的多表查询，该查询例如将最左边的半字节作为零级"索引.桌子.然后，下一个最左边的数字是第二级表的索引.这类似于虚拟内存页表的设置方式.
It might be possible to come up with an elaborate multitable lookup that (e.g.) takes the leftmost nibble as an index into the "zero level" table. Then, the next leftmost digit is an index into a second level table. This is similar to how virtual memory page tables are set up.
但是，这可能很复杂，尽管速度很快，但可能会占用更多内存.
However, this can be complex and, although fast, it might use more memory.
使用虚拟函数表方法，我们将代码以及所需的任何函数指针放入vtable条目中.
With a virtual function table approach, we put the code into the vtable entry, along with any function pointers we need.
如果表格已排序，我们可以使用二进制搜索找到正确的表格条目.下面，我使用二进制搜索将输入的代码转换为表索引/指针.
If the table is sorted, we can use a binary search to find the correct table entry. Below, I used a binary search to translate an incoming code into a table index/pointer.
此功能的速度(例如下面的 vtblfind )是其关键所在.二进制搜索为 fast 和 general .但是，有可能设计出更快的专用功能
The speed of this function (e.g. vtblfind below) is the crux of it. The binary search is fast and general. But, it may be possible to devise a specialized function that is faster
以下是说明二进制搜索方法的代码:
Here's some code that illustrates the binary search approach:
#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;
}
更新:
聪明的编译器可能能够将一些测试组合到范围内或进行其他一些窥孔优化，例如条件移动".(例如 cmovne ).
A smart compiler might be able to combine some tests into ranges or some other peephole optimizations, such as "conditional move" (e.g. cmovne).
但是，它仍然是线性"的.搜索:如果有N个案例，则需要进行N个比较，设置，跳转.
But, it's still a "linear" search: If you have N cases, you need to do N compares, sets, jumps.
编译器必须选择一个顺序，而编译器可以对其进行重新排序，但通常不这样做，因为按照源顺序的要求，它遵循该顺序.原因是，如果您有一个最典型的案例90％，您(程序员)会把它放在第一位，因为您想要要首先进行测试.
The compiler has to pick an order and the compiler can reorder them but usually doesn't because, to be true to the source order, it follows it. The reason is, that, if you have a case that is 90% most typical, you [the programmer] put that first, because you want that to be tested first.
如果将开关重新编码为 if/else 阶梯，则将强制执行该命令.您希望开关具有相同的行为.
If you recoded the switch as an if/else ladder, you'd be forcing the order. You'd want the same behavior for your switch.
如果是连续(例如， 1、2、3、4，...，N )案件[或几乎如此]，编译器可以构建一个跳转表并对其进行索引.将设为常数[O(1)]时间.对于某些特定的 switch 序列，我 看到有编译器执行此操作.
If the cases were contiguous (e.g. 1, 2, 3, 4, ..., N) [or nearly so], the compiler could build a jump table and index into it. That would be constant [O(1)] time. For certain specialized switch sequences, I have seen a compiler do this.
不幸的是，这是我们没有在这里-OP问题的全部要点.
Unfortunately, that is what we don't have here--the whole point of OP's question.
这是一个基于 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 ]反汇编[带有 -O2 ].仍然有 6 cmp 条指令，这与六个 case 语句相同:
Here's the [x86_64] disassembly [with -O2]. There are still six cmp instructions, which is the same as the six case statements:
0000000000000000 <funcfind>:
0: 66 81 ff a3 01 cmp $0x1a3,%di
5: 74 31 je 38 <L00>
7: 76 37 jbe 40 <L02>
9: b8 00 00 00 00 mov $0x0,%eax
e: 66 81 ff 20 02 cmp $0x220,%di
13: 74 28 je 3d <L01>
15: b8 00 00 00 00 mov $0x0,%eax
1a: 66 81 ff 30 02 cmp $0x230,%di
1f: 74 1c je 3d <L01>
21: 66 81 ff 10 02 cmp $0x210,%di
26: ba 00 00 00 00 mov $0x0,%edx
2b: b8 00 00 00 00 mov $0x0,%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 $0x0,%eax
3d:L01 c3 retq
3e: 66 90 xchg %ax,%ax
40:L02 b8 00 00 00 00 mov $0x0,%eax
45: 66 81 ff 10 01 cmp $0x110,%di
4a: 74 f1 je 3d <L01>
4c: 66 81 ff 20 01 cmp $0x120,%di
51: ba 00 00 00 00 mov $0x0,%edx
56: b8 00 00 00 00 mov $0x0,%eax
5b: 48 0f 45 c2 cmovne %rdx,%rax
5f: c3 retq
更新#2:
是的，考虑到两个字节的密钥"，这大约是最快的.你有.它不会散列"太好了(任何体面的散列算法都会更慢-见下文).
Yes, this is about the fastest, given the two byte "key" you have. It doesn't "hash" too well [any decent hash algorithm would be slower--see below].
Ah， python ... [就我个人而言，我更喜欢 perl ，但又是一个话题，也许;-)].
Ah, python ... [Personally, I prefer perl, but a topic for another time, perhaps ;-)].
您所说的 python 字典是 perl 称为哈希"的东西.[aka"associative array"].
What you're talking about with a python dictionary is what perl calls a "hash" [aka "associative array"].
将其引为索引，欺骗性地看起来像是一个O(1)操作(基于语法)，但是更多的是底层(这是我们在使用时必须谈论的层级) c ].
Indexing into it, deceptively looks like an O(1) operation [based on the syntax], but, it's much more under the hood [which is the level we have to talk about when using c].
两个字节的密钥不会从哈希中获得太多好处.因此，让我们考虑一个任意长度的缓冲区(例如字符串).
A two byte key doesn't benefit too much from a hash. So, let's consider an arbitrary length buffer (e.g. a string).
我们计算一个[32位]哈希值.对于固定的常量字符串， perl/python 编译器可以在编译时计算哈希值.
We compute a [32 bit] hash value. For fixed constant strings, the perl/python compiler could compute the hash value at compile time.
无论哪种方式，我们都使用哈希值(以哈希桶数为模)来索引哈希表，以获取子列表的地址.我们必须遍历该列表才能在实际键上找到匹配项.
Either way, we use the hash value (modulo the number of hash buckets) to index into a hash table to get the address of a sub-list. We have to traverse that list to find a match on the actual key.
子列表通常是一个单链接列表.因此，我们必须遍历这一点.
The sub-list is typically a singly [or doubly] linked list. So, we have to traverse that.
或者，子列表可以是排序数组，我们可以使用二进制搜索.或者，它可能是一棵平衡的树(例如一棵红色/黑色的树).但是，在一般情况下，这些问题更为严重.
Or, the sub-list could be a sorted array and we could use a binary search. Or, it could be a balanced tree (e.g. a red/black tree). But, these are more problematic in the general case.
这是对我的原始代码的重写，该代码根据字符串/长度找到描述符.为简便起见，仅具有搜索"功能.代码[并且不是插入/更新/删除].
Here's a rewrite of my original code that finds the descriptor based on a string/length. For brevity, this only has the "search" code [and not insert/update/delete].
请注意，我正在使用的 strhash 函数是perl实际哈希函数的抄录. python 将使用类似的内容.给定搜索的执行时间将与 python 或 perl :
Note that the strhash function I'm using is a ripoff of perl's actual hash function. python will use something similar. The execution time for a given search will be on par with either python or 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:
开关或二进制搜索不使用冲突解决.那只是用于字符串示例.
Either the switch or the binary search doesn't use collision resolution. That was just for the string example.
经验法则是线性搜索最多20个项目，二进制搜索较大的项目.
The rule of thumb is linear search for up to ~20 items and binary search for larger.
使用端口号的确切列表，可以获取智能"端口号.定位器.也就是说，可能是基于MSB然后是LSB的2级查找.或者，基于特定于实际端口号的技巧，使某些结构紧凑但速度很快.
With the exact list of port numbers, it's possible to get a "smart" locator. That is, maybe a 2 level lookup based on MSB and then LSB. Or, something compact but fast based on tricks that are specific to the actual port numbers.
由于需要进行速度/空间折衷，因此必须进行测量/基准测试才能找到最佳组合.
Because you've got a speed/space tradeoff, you'll have to measure/benchmark to find the optimal mix.
我的一般规则是:如果无法测量，就无法调整
正如我[和其他人]所提到的，与 switch 相比，表的运行速度和内存占用空间差不多.由于处理器指令缓存上的负载较小，因此该表甚至可能更快.
As I [and others] have mentioned, a table would be just about as fast and with a smaller memory footprint than a switch. The table might even be faster due to the smaller loading on the processor instruction cache.
开关不能很好地缩放.如果您有一百万个类型，那么该表将很明显.如果您有两个，则 switch 很明显.每当我不得不做出 switch vs. table决定时，基于多种因素，我通常会发现table方法是赢家.YMMV.
The switch doesn't scale too well. If you had a million types, the table would be obvious. If you had two, the switch would be obvious. Whenever I've had to make a switch vs. table decision, I've usually found the table approach to be the winner based on several factors. YMMV.
对于二进制搜索，如果您不想手工对列表进行排序，则可以在初始化过程中使用(例如) qsort 调用.
For the binary search, if you don't want to have to have the list sorted by hand, you could just use (e.g.) a qsort call during initialization.
如果您决定按从最高到最低的频率对表格进行排序，那么线性搜索将是最好的.
If you decide to order the table by highest-to-lowest frequency, a linear search would be the best.
另一种方法是缓存".最常发现/使用的条目中的条目"(也称为记忆").如果有缓存命中，请使用它.如果不是这样，则慢速"表示慢".路径(即二进制搜索)可以使用.缓存替换可以基于LRU或频率.
Another method would be a "cache" of the most frequently found/used entries (aka "memoization"). If there is a cache hit, use it. If not, the "slow" path (i.e. binary search) can be used. The cache replacement can be based on either LRU or frequency.
请考虑一个多步骤设计过程.您可以从二进制搜索实现开始.这可能是最佳的整体空间/速度折衷.
Consider a multistep design process. You could start with the binary search implementation. It's probably the best overall space/speed tradeoff.
开始工作.用它来收集频率数据和基准值.查看是否存在模式(例如portA后面总是portB).收集的数据可以帮助您为您的用例提供最佳解决方案.
Get it working. Use that to collect frequency data and benchmark values. See if there is a pattern (e.g. portA is always followed by portB). The data collected could help guide you to a more optimal solution for your use case.
以下是说明缓存方法的代码:
Here's some code that illustrates the cache approach:
#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;
}
这篇关于c中具有分配值的枚举的静态查找表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！