c - 哪种数据结构在共享内存场景和快速查找中效果最好

Question

我仍处于项目的概念阶段。尚未开始代码实现。子任务是这样的:

2 进程将从常用的 DLL 请求数据。该 DLL 会将这些数据存储在内存的缓冲区中。如果我只是在 DLL 中实例化一个结构并在其中存储数据，那么每个进程实例将有一个单独的结构，并且数据不会是通用的。所以我需要一个共享内存的实现。现在我的另一个要求是数据中的快速查找时间。我不确定 AVL 树如何存储在共享内存空间中。互联网上是否有可以存储在共享内存空间中的 AVL 树/ HashMap 的实现？另外，这是解决问题的正确方法吗？或者我应该完全使用其他东西？

蒂亚!

Answer 1

这是否是正确的方法取决于多种因素，例如数据的生成成本有多高、进程是否需要就数据进行相互通信等等。这个答案的其余部分假设您确实需要共享内存中的查找结构。

您可以使用任何数据结构，前提是您可以在共享内存空间中为数据和数据结构的内部分配存储空间。这通常意味着您将无法对其使用 malloc，因为每个进程的堆通常保持私有(private)。您将需要自己的自定义分配器。

假设您选择了 AVL 树。这是一个实现它们的库:https://github.com/fbuihuu/libtree 。看起来在这个库中，“内部”AVL 节点数据被侵入地存储在您的“对象”中。 侵入性意味着您在声明对象struct时保留供库使用的字段。因此，只要您使用自定义分配器为共享内存中的对象分配空间，并为根树 struct 分配空间，整个树就应该可供多个进程访问。您只需确保共享内存本身映射到每个进程中的相同地址范围即可。

如果您使用非侵入式 AVL 实现，这意味着每个节点都由一个内部 struct 表示，然后该结构指向包含您的数据、库的单独 struct或者您的实现必须允许您以某种方式指定内部结构的分配器，以便您可以确保空间将在共享内存中分配。

至于如何编写自定义分配器，这实际上取决于您的使用情况和系统。您需要考虑是否需要“调整”共享内存区域的大小，系统是否允许您这样做，您是否只在该区域内分配固定宽度的 block ，或者您需要支持任意长度的 block ，是否可以接受将数据结构分布在多个共享内存区域、进程如何同步和通信等等。如果您走这条路，您应该就该主题提出一个新问题。请务必提及您正在使用的系统(Windows？)以及您的限制。

编辑

只是为了进一步阻止您这样做，除非有必要:例如，如果您的数据生成成本昂贵，但您不关心一旦数据可用，进程是否会构建自己的独立查找结构，例如，您可以让 DLL 将数据写入共享内存中的简单环形缓冲区，其余代码从那里获取数据。构建两棵 AVL 树并不是什么问题，除非它们非常大。

此外，如果您只关心并发性，并且有两个进程并不重要，那么您可以将它们设为一个进程的两个线程。