内存C中的IP查找表

我目前正在尝试使用libpcap和各种C应用程序并尝试完成以下操作。在程序初始化时，我想从文件加载IP并将它们存储在内存中。当我收到一些数据包详细信息进行处理时，我想将IP与加载到内存中的IP集进行比较。 在C中实现此功能的最佳方法/数据结构是什么？我需要适应列表增长和高效匹配，所以我觉得简单的查找数组将是一个错误的解决方案。救命？     
2019-11-01 4 条评论
分享

没有找到相关结果

    已邀请:

    悲帽慑彤电

    绝对最少量的工作，对于真正体面的性能，可能只是使用一个
    uint32_t
    数组。 加载数据时，将每个IP丢入阵列，使用
    realloc()
    根据需要增长。请记住使用理智的增长模式，每次耗尽时将分配的长度加倍是常见的，并且可能会很好地工作。 加载后，使用简单的
    http://linux.die.net/man/3/qsort
    调用对数组进行排序。 然后，您可以使用
    bsearch()
    快速搜索阵列。 由于这只使用标准函数，因此代码非常小，因此易于理解和快速编写。没有依赖关系，没有花时间追逐理智的库，或者编写自己的高级数据结构。但由于它使用二进制搜索，因此速度非常快。     
    2019-11-01 0 0
    分享

    鞘垒飘

    好吧，大概你不会在运行时删除IP，只是添加。如果列表没有变得庞大，那么对它进行排序确实没有什么大的收获。 考虑到这两个事实，我可能只是将它们全部放在一个（大小的）数组中，并在需要时进行线性搜索。跟踪数组中数据结束的位置，在那里添加新条目将是一件小事。 如果这太慢了，你可以开发一个哈希表。它需要根据IP映射的典型内容进行调整，以避免发生冲突（并且开发和调试，因为C在标准中没有哈希值）。有点PITA，但应该可行。 我不打算介于两者之间（可能是使用二进制搜索查找）。如果你对速度感到绝望，那你也可以一路走下去。     
    2019-11-01 0 0
    分享

    祁澈盘哼颗

    如果您的表中可能有IP地址，则很大程度上取决于数字。 对于较小的数字，平衡的二叉树（例如，AVL树）应该相当好地工作。它有相当大的开销（每个节点2个指针），但只要节点数量很少，它可能不是一个问题（除非你的目标是一个内存受限的系统）。您还可以使用混合，其中单个节点在阵列中存储多达N个IP地址。通过半精心选择N，可以减少指针开销，并提高缓存使用率。 如果你可能超过10K左右，那么考虑使用trie可能是值得的。 如果你可能有一个非常大的数字，你可以考虑使用一个简单的bitset，每个IP地址一位。 编辑：我应该补充一点，它还可以取决于与查找相比的插入/删除频率。我发现在许多情况下有用的一个混合结构是从一个已排序的主数组开始，然后在添加项目时将它们保存在一个未排序的单独数组中。当/如果辅助数组太大，则对其进行排序并与主数组合并。     
    2019-11-01 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.03634786605835