c - 内存 C 中的 IP 查找表

Question

我目前正在尝试使用 libpcap 和各种 C 应用程序，并尝试完成以下工作。在程序初始化时，我想从文件中加载 IP 并将它们存储在内存中。当我收到一些要处理的数据包详细信息时，我想将一个 IP 与加载到内存中的一组 IP 进行比较。

在 C 中实现这一点的最佳方式/数据结构是什么？我需要适应列表增长和高效匹配，所以我觉得一个简单的查找数组将是一个错误的解决方案。帮助？

Answer 1

好吧，大概你永远不会在运行时删除 IP，只是添加。如果列表没有变得很大，那么对其进行排序真的不会有太大的收获。

鉴于这两个事实，我可能会将它们全部放入一个（大尺寸）数组中，并在需要时进行线性搜索。跟踪数组中数据的末尾在哪里，在那里添加新条目将是一件小事。

如果这真的太慢，你可以开发一个哈希表。它当然需要根据 IP 映射的典型内容进行调整，以避免冲突（并且开发和调试，因为 C 在标准中没有散列）。有点 PITA，但应该是可行的。

我不会介意中间的任何事情（大概使用二进制搜索进行查找）。如果您对速度如此渴望，那么您不妨一路走下去。

Answer 2

如果您的表中可能有 IP 地址，很大程度上取决于数量。

对于小数字，平衡二叉树（例如，AVL 树）应该工作得相当好。它有相当多的开销（每个节点 2 个指针），但只要节点数量很少，这可能不是什么大问题（除非您的目标是内存受限的系统）。您还可以使用混合，其中单个节点在一个阵列中最多存储 N 个 IP 地址。通过半谨慎地选择 N，这可以减少指针开销，并提高缓存使用率。

如果您可能有超过 10K 左右，则可能值得考虑使用 trie。

如果您可能有一个非常大的数字，您可能会考虑使用一个简单的位集，每个 IP 地址一个位。

编辑：我应该补充一点，与查找相比，它还取决于插入/删除的频率。我发现在许多情况下有用的一种混合结构是从一个已排序的主数组开始，然后随着项目的添加，将它们保存在一个未排序的单独数组中。当/如果辅助数组变得太大时，您对其进行排序并与主数组合并。

Answer 3

对于真正体面的性能，绝对最少的工作量可能是只使用uint32_t.

加载数据时，将每个 IP 放入数组中，realloc()并根据需要使用它来增加它。请记住使用合理的增长模式，每次分配的长度用完时加倍是常见的，并且可能会很好地工作。

加载后，使用简单的http://linux.die.net/man/3/qsort调用对数组进行排序。

然后您可以使用 快速搜索数组bsearch()。

由于这仅使用标准函数，因此它的代码量非常小，因此易于理解和快速编写。没有依赖关系，也没有时间花在寻找健全的库或编写自己的更高级别的数据结构上。但是由于它使用二进制搜索，所以它会非常快。