包含其他链表的链表&自由的

发布于 2024-10-17 06:03:15 字数 299 浏览 7 评论 0原文

我有一个通用链表实现,其中包含一个包含 void* 数据的节点结构和一个包含对 head 的引用的列表结构。现在这是我的问题,链表中的节点可能通过其 void* 保存对另一个链表的引用。当我释放包含较小列表的较大列表时,这会导致内存泄漏。所以我想知道是否有一种方法可以检查 void* 是否指向另一个列表,以便我跟踪并释放该列表或仅释放数据。

如果我在结构体的开头添加一个键,一个幻数,我可以通过取消引用 void* 来检查它并找出它是一个列表?

编辑:调用者不会插入由我的函数插入的较小列表,我不希望调用者只处理它们持有指针指向的列表的释放多个列表。

I have a generic linked list implementation with a node struct containing a void* to data and a list struct that holds a reference to head. Now here is my problem a node in the linked list may hold a reference to another linked list via its void*. This causes memory leaks when I free the bigger list containing smaller lists. So I am wondering is there a way to check if the void* is pointing to another list so I follow and free that also or to just data.

If i add a key to the beginning of my struct a magic number that I can check by dereferencing the void* and figure out it is a list?

EDIT: Callers don't insert the smaller lists they are inserted by my functions I do not want the callers to deal with relasing multiple lists just the one they hold a pointer to.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

末蓝 2024-10-24 06:03:15

这个问题实际上取决于谁负责清理列表中的条目。如果您的结构负责清理由 void * 字段引用的内存,那么您手头有一个更大的问题,即给定一个 void * 引用某些任意的内存块,你永远不知道释放它的正确方法是什么。例如,如果您按照 C++ std::vector 实现了动态数组,那么您的 void * 可能会指向一个结构体,该结构体本身包含一个指针,并且您的列表需要知道它必须下降到该结构中才能递归地释放其动态分配的块。您所描述的情况(泄漏嵌套列表)只是这个更普遍问题的一个特例。

另一方面,如果列表不负责清理它存储的 void * 引用的内存,那么您根本不必担心这个问题。

如果您的列表确实具有所有权语义,并且需要清理其中存储的元素的内存,我强烈建议您不要使用幻数来确定是否有嵌套列表。相反,您可能应该让客户端为您提供一个函数指针,其中包含一个释放例程,以在插入列表的元素上运行。这样,您的代码就可以使用用户提供的清理代码来确保清理列表中存储的所有元素。

This question really depends on whose responsibility it is to clean up the entries in the list. If your struct is responsible for cleaning up the memory referenced by the void * fields, then you have a much bigger problem at hand here, namely that given a void * referencing some arbitrary block of memory you can never know what the right way to deallocate it is. For example, if you have an implementation of a dynamic array along the lines of the C++ std::vector, then your void * might point at a struct that itself contains a pointer, and your list will need to know that it has to descend into that struct to recursively free its dynamically-allocated block. The case you're describing, where you're leaking a nested list - is just a special case of this more general issue.

If, on the other hand, the list is not responsible for cleaning up the memory referenced by the void *s it stores, then you shouldn't worry about this problem at all.

If your list does have ownership semantics and is required to clean up the memory for the elements stored in it, I would strongly discourage you from using a magic number to determine whether you have a nested list. Rather, you should probably have the client provide you a function pointer containing a deallocation routine to run on the elements inserted into the list. That way, your code can use the user's provided cleanup code to ensure that any elements stored in the list are cleaned up.

爱,才寂寞 2024-10-24 06:03:15

这不仅仅是您的 void* 可以指向一个列表。它可以指向任何动态分配的内存。

GLib 处理这个问题的方式是,调用者有责任确保释放列表的 void *data 所指向的任何内容。请参阅 http://library。 gnome.org/devel/glib/unstable/glib-Doubly-Linked-Lists.html#g-list-free

另一种方法(GLib 也提供了)是创建一个函数,该函数接受函数指针并在遍历列表时在每个 void *data 上调用该指针。查找g_list_free_full

It's not just that your void* could point to a list. It could point to any dynamically-allocated memory.

The way GLib handles this problem is to say that it's the caller's responsibility to ensure that anything pointed-to by the void *data of a list is freed. See http://library.gnome.org/devel/glib/unstable/glib-Doubly-Linked-Lists.html#g-list-free .

The alternative (which GLib also provides) is to make a function that takes a function pointer and calls that on each void *data as it traverses the list. Look up g_list_free_full.

宫墨修音 2024-10-24 06:03:15

我的建议是,如果可能的话,稍微简化一下事情,并简单地确保一个链表仅包含一种类型的对象。

如果你做不到这一点,我可能会让列表中的每个节点不仅保存一些数据,还保存一个指向知道如何正确释放该类型的项目的函数的指针。不可避免地,在为链表编写特殊代码两周后,您会决定还需要另一个幻数来保存动态数组等。

My advice would be if at all possible to simplify things a bit, and simply ensure that one linked list only holds one type of object.

If you can't do that, I'd probably have each node in the list hold not only some data, but also a pointer to a function that knows how to properly free items of that type. Inevitably, two weeks after you write your special code for a linked list, you'll decide you also need another magic number to be able to hold a dynamic array, etc.

帅气称霸 2024-10-24 06:03:15

要回答“如果我在结构体的开头添加一个键,一个神奇的数字,我可以通过取消引用 void* 来检查它并找出它是一个列表”的智慧是什么?

是的,您可以这样做,但很少有人会推荐这样做。只要真正确定“神奇”值不可能出现,否则就不可能发生。这是一个相当大的要求。您需要考虑您可能还指向什么,以及当表示为无符号整数之类的东西时可能会采用什么值。请记住,如果您决定它是一个列表,您将释放它,因此如果您错了,可能会崩溃。

最简单有效的解决方案是,如果您需要一个节点知道它指向一个列表,请在节点中提供一个标志来说明这一点。

如果您确实希望列表承担释放其所有内容的责任,那么您需要的不仅仅是一个标志,您还需要知道如何执行每个释放。这可能是一个 id 或类似指向释放其内容的函数的指针。

To answer the question of what is the wisdom of "If i add a key to the beginning of my struct a magic number that I can check by dereferencing the void* and figure out it is a list?"

Yes, you can do this, but few would recommend it. Just be really sure that the 'magic' value cannot possibly occur otherwise. That is a pretty big ask. You want to consider what else you might be pointing to and what values it might take when represented as something like an unsigned integer. Remember that if you decide it is a list, you are going to free it and hence will likely crash and burn if you are wrong.

The simplest effective solution is that if you need a Node to know that it points to a list, provide a flag in the node saying so.

If you really want the list to own responsibility for freeing all its contents, you need more than a flag, you need to know how to do each free. That might be an id or something like a pointer to the function which frees its contents.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文