c - 关于我的模块化代码在 C 中使用 void* 作为动态数据类型的几个问题

Question

几天前我发布了this question每个人都建议我使用 void*，我就这样做了。我认为其中一些人还指出了一些我需要注意的事情，但我不确定它们到底是什么。但是，我遇到了一些问题......

我不会发布我所有的代码，因为它相当大，相反，我会发布我认为重要的东西，希望足以让你帮助我。

我的哈希表结构是这样的:

typedef void * HashKey;
typedef void * HashValue;

typedef struct sHashItem {
    HashKey key;
    HashValue value;

    char status;
} HashItem;

typedef struct sHashTable {
    HashItem *items;

    int count;
    float load;
    int size;

    Bool (*compare)(HashKey, HashKey);
    unsigned (*hash)(void *);
} HashTable;

我的插入函数的签名如下:

Bool hashInsert(HashTable * const table, HashKey key, HashValue value);

在该函数内的某个位置，当我在哈希表中找到一个空闲存储桶时，我会执行以下操作:

table->items[index].key = key;
table->items[index].value = value;
table->items[index].status = USED;
table->load = ++table->count / (float)table->size;

所有这些都带来了一些问题:

1) 正如您在上面看到的，我只是将空闲存储桶的每个键/值对设置为作为键/值 hashInsert 函数传递的同一指针论据。这提出了一个问题，您可能已经注意到了......例如，执行如下操作:

char str[50];
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)5);
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)3);

如果输入是“KeyA”，然后是“KeyB”，则两者都将“KeyB”作为存储桶键。同样的事情适用于值，而不仅仅是键，因为它们基本上是相同的类型，因为我希望我的代码对于任何数据类型都完全模块化。

我该如何解决这个问题？

我的第一个想法是使用 strdup(str) 并将其传递给 hashInsert 函数。这样就解决了问题。由于这是在主代码中处理的，因此我也可以轻松地使用 malloc() 来处理我需要作为值传递的任何其他数据类型(键可能始终是字符串或整数) .

但是这个解决方案提出了另一个问题......

2) 我应该如何释放分配的内存？当然，它是由“主程序员”而不是“哈希表模块程序员”分配的，所以“主程序员”应该在主代码中释放它，对吗？然而，对我来说，这看起来不太像模块化代码。

我的代码还有一个hashDestroy函数，用于释放所有分配的内存。但是我怎样才能使用这个函数来释放所有东西呢？我不能只是迭代每个键/值并对它们使用free()，因为也许其中一些键/值一开始就没有被任何程序员malloc'd而且我不需要释放它们。

如何找出我的 hashDestroy 必须释放哪些内容以及不应该释放哪些内容？

3) 最后，我想我也可以把这个问题放在一起......在第一点中，我的建议是使用 strdup() 或 malloc 来“修复”该特定问题(同时引入另一个问题)，但这对我来说看起来也不是很模块化。这种内存分配应该在哈希表模块代码中完成，而不是由“主程序员”在主代码中完成。

你建议我如何解决这个问题？我的意思是，数据类型可以是任何类型，虽然使用 strdup() 很有帮助，但它只适用于字符串。如果我需要为某些特定结构或只是一个 int 分配内存怎么办？

抱歉，这篇文章很长，但我认为这些问题都是相关的，我需要一些帮助来解决它们，因为我的 C 知识并不是那么极端。我最近才了解 void* 所以...

Answer 1

哇:这需要一些完整的回答。然而，您需要的关键事项之一是您正在处理的任何内容的大小 - 使用 void 指针很好，但您需要知道您正在接收其地址的对象有多大。

[...] everyone suggested me to use void*, which I did. [...]

My hash table structure is like this:

typedef void * HashKey;
typedef void * HashValue;

typedef struct sHashItem {
    HashKey key;
    HashValue value;
    char status;
} HashItem;

typedef struct sHashTable {
    HashItem *items;
    int count;
    float load;
    int size;

    Bool (*compare)(HashKey, HashKey);
    unsigned (*hash)(void *);
} HashTable;

您可能需要 HashItem 中的 size_t key_sz; 和 size_t val_sz; 成员。您的散列函数指针需要知道要散列的 key 有多大。

对于 HashKey 应该是什么，我有两种想法。这部分取决于您如何使用这些东西。看起来像你想要的:

• 鉴于我选择的这一关键值(value)，
• 存储/返回与其关联的数据。

在这种情况下，您可能还需要将哈希值存储在 HashItem 中的某个位置；这是散列函数返回的值 - 显然是一个无符号整数。我不确定 compare 函数(函数指针)上的签名应该是什么；我怀疑它应该采用一对 HashKey-and-size 值，或者可能采用一对 HashItem 指针。

The signature for my insert function goes like this:

Bool hashInsert(HashTable * const table, HashKey key, HashValue value);

And somewhere inside that function, when I find a free bucket in the hash table, I do this:

table->items[index].key = key;
table->items[index].value = value;
table->items[index].status = USED;
table->load = ++table->count / (float)table->size;

All this presents a few problems:

1) As you can see above I'm simply setting each key/value pair of the free bucket to the same pointer passed as the key/value hashInsert function arguments. This presents a problem as you may have already noticed... For instance, doing something like this:

char str[50];
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)5);
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)3);

使用void *的关键是传递地址。在 C 中应该不需要强制转换。您还需要传递事物的大小。因此:

Bool hashInsert(HashTable * const table, HashKey key, size_t key_sz,
                HashValue value, size_t val_sz);

char str[50];
scanf("%s%*c", str);
int value = 5;
hashInsert(t1, str, strlen(str)+1, &value, sizeof(value));

在内部，您将复制数据 - 不使用“strdup()”，因为您不知道其中没有内部 NUL“\0”字节。

And if the input is "KeyA" and then "KeyB", both will have "KeyB" as the buckets keys. The same thing applies to the value and not just the key since they are basically the same type because I want to have my code fully modular, for any data type.

How could I solve this?

您必须定义谁拥有什么，以及容器是否(以及如何)复制数据。在 C++ 中，容器复制它们所存储的任何内容。

My first thought is to use strdup(str) and pass that to the hashInsert function. That would solve the problem. And since this was handled in the main code, I could easily use malloc() too for any other data type I need to pass as the value (the key will probably always be a string or an int).

您不能使用“strdup()”，因为一般来说，值和键都不是字符串。如果它们始终是字符串，为什么使用“void *”而不是“char *”？

您可以决定复制值和键 - 只要您知道大小。

But this solution presents another problem...

2) How should I free this allocated memory? Sure, it was allocated by the "main programmer" and not the "hash table module programmer" so, the "main programmer" should free it in the main code, right? However, that doesn't look much like modular code to me.

My code also has a hashDestroy function, to free all the allocated memory. But how can I use this function to free everything? I can't just iterate over every key/value and use free() on them cause maybe some of them weren't malloc'd by any programmer in the first place and I don't need to free them.

How can I find out which ones my hashDestroy must free and which ones it shouldn't?

你不能。您必须定义一项政策，并且只有当该政策允许您进行销毁时，您才应该这样做。如果你复制所有内容，你就会很轻松。如果你什么都不复制，你就会有一个不同的轻松时光(可以说更容易)，但你的消费者会经历一段 hell 般的时光，因为他们需要一个结构来跟踪他们需要发布的内容 - 也许是一个散列列表......

3) To finish, I guess I can also throw this issue into the mix... In point one, my suggestion was to use strdup() or malloc to "fix" that specific problem (while introducing another) but that also don't look very modular to me. This memory allocation should be done in the hash table module code and not in the main code by the "main programmer".

是的...这基本上是我的建议。

How do you suggest I solve this? I mean, the data types can be anything and while the use of strdup() helps a lot, it only works for strings. What if I need to allocate memory for some specific structure or just an int?

请注意，复制仅进行浅复制。如果您要复制的结构包含指针，则复制代码将仅复制指针，而不复制指向的数据。

因此，通用解决方案需要某种复制功能。您可能必须要求用户提供“释放”功能来释放项目中的内存。您可能需要让用户向您提供已经完全分配的数据。您需要考虑谁拥有搜索函数返回的内容 - 它是否仍在哈希表“中”或已被删除。仔细观察 C++ STL 系统 - 一般而言，它做得非常出色，并且根据它的要求建模您的需求可能是有意义的。但请记住，C++ 有构造函数和析构函数来帮助它。