c - 设计问题 : Implementing a two way lookup table in C

Question

我想实现一个双向查找表。MAC 地址 --> MAC 地址

表示可以使用一个键访问上游侧的值。并且在下游侧，可以使用值来访问键。

内存是一个约束，所以我不能使用两个哈希表，我期待使用哈希表的相同节点进行上游和下游查找。

运行时也是一个约束，因此只有哈希表策略才有效。

语言是一个约束，所以我只能使用 C 语言(所以不能使用 C++ Boost bimap)

请就如何实现这一目标分享您的想法。提前致谢。

Answer 1

正如您所建议的，您可以对上游和下游存储桶使用相同的节点。它不会为您节省大量资金(肯定少于 2 倍)，但任何事情都有帮助。

struct bucket {
  struct bucket *next_upstream;
  struct bucket *next_downstream;
  char upstream_mac[6];
  char downstream_mac[6];
}
struct bucket **upstream_table = malloc(sizeof(struct bucket*) * N);
struct bucket **downstream_table = malloc(sizeof(struct bucket*) * N);
void insert(char *upstream_mac, char *downstream_mac) {
  struct bucket *b = malloc(sizeof(*b));
  memcpy(b->upstream_mac, upstream_mac, 6);
  memcpy(b->downstream_mac, downstream_mac, 6);
  int uh = hash(upstream_mac);
  int dh = hash(downstream_mac);
  b->next_upstream = upstream_table[uh];
  upstream_table[uh] = b;
  b->next_downstream = downstream_table[dh];
  downstream_tbale[dh] = b;
}