基本上我想设置一个 map/hash/idr_type_of_thing 将唯一的 u32 映射到唯一的指针值（在当前映射集中是唯一的）。它的核心是 u32 是 DMA 引擎看到的缓冲区的物理地址，指针是关于该缓冲区的上下文 blob，包含缓冲区本身和有关缓冲区的其他元数据。当我从 DMA 引擎获得一些事件时，它提供了 u32，我想从中找到上下文 blob 以进行进一步处理（如释放 DMA 映射、空闲缓冲区等）。DMA 引擎只能返回 u32 物理地址。是否有一些低开销的快速方案来执行此映射，而无需提出一些运行良好的散列函数？顺便说一句，对于这种类型的映射，有什么好的散列函数可以很好地工作（没有冲突？）？
可以同时存在的映射总数是一些固定的小数字，比如 512。
谢谢。
将指针放入 DMA 内存中，就在实际 DMA 缓冲区之前或之后。（使用哪一个取决于您的对齐要求以及您是否知道 DMA 缓冲区的大小。）
嗯，include/linux/rbtree.h内核当前的红黑树实现似乎是最直观的。（目前在 htmldocs 下没有为此生成任何内容，但也请查看Documentation/rbtree.txt）。二叉树（任何类型）的检索时间为 O(log n)。然而，它目前的形式也有缺点——密钥仍然存储在 blob 中，因此，每次比较密钥时都会触及 blob 的缓存行。如果其他人不先做到这一点，我希望有一天能解决这个问题。
除了这个缺点，红黑树是一种非常有效的算法。
编辑：嗯，实际上我可以想到许多其他缺点，但它现在可能是内核中最好的。如果您对此感到特别不满意，我会在您实施新事物时为您加油！！！