内存C中的IP查询表

Question

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

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

Answer 1

为了获得真正像样的性能，绝对最少的工作量可能就是使用一个uint32_t数组。

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

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

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

因为它只使用标准函数，所以它在代码方面非常小，因此易于理解和快速编写。没有依赖关系，也不需要花费时间去寻找合理的库，或者编写自己的更高级别的数据结构。但由于它使用二进制搜索，所以速度会很快。

Answer 2

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

考虑到这两个事实，我可能只会将它们全部丢弃在一个(大小合适的)数组中，并在需要时进行线性搜索。跟踪数组中数据的结束位置，在那里添加新条目将是一件微不足道的事情。

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

我不会为这两者之间的任何事情而烦恼(大概是使用二进制搜索来查找)。如果你真的那么渴望速度，你还不如全力以赴。

Answer 3

这在很大程度上取决于表中可能包含的IP地址的数量。

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

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

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

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