For my current implementation of a linked list, I have the user of the "library" manage all memory themselves, from node allocation, to data allocation, the user is in charge. I think this is a good thing, because it lets the user decide where things are in memory, while the data structure library itself just organizes the data for the user. The data could be anywhere, including the stack if the user needs it to be. But this approach does make things a bit difficult. Creation and deletion of elements is somewhat tedious, having to allocate/free nodes by hand each time. Clearing the list is also difficult, since the memory needs to be freed as the list is cleared, something the library can't do.
Is this a good idea? Or am I chasing a fool's errand?
Is this a good idea? Or am I chasing a fool's errand?
Edited by sudo459
on
Reason: Initial post
One way to give control over allocations to the user is to have an "intrusive" linked list. You define a struct Node{Node* next, prev;} and the user code adds that as a field to every object that wants to be in a linked list (one for every linked list it wants to be in).
Then your linked list library only needs to know about the Node fields in the objects in the list and some macro or template magic lets the user code get back the actual object pointer from the Node pointer.
Then your linked list library only needs to know about the Node fields in the objects in the list and some macro or template magic lets the user code get back the actual object pointer from the Node pointer.
I often that the intrusive approach that rachetfreak mentioned is the simplest. It can consume extra memory if the user has a list of Foos, a red-black tree of Foos, etc, since Foo now has to have a struct list_head, struct rb_node, etc. in it, but that's really not that bad of a trade-off for the simplicity. If it comes down to it, users can work around those sorts of problems with clever memory tricks. Linus Torvalds agrees, as Linux is the most popular example of this approach. You can find the implementation here, and there are many explanations of it on the internet. A good one is found in Linux Kernel Development, if you're into books.
To give more detailed information, we would need to see your exact use case.
To give more detailed information, we would need to see your exact use case.
Another way is to let the user provide a custom allocator if they want to. Your link list functions would allocate the nodes by calling the user allocator. The payload would still be allocated and freed by the user.
1 2 3 4 5 6 7 8 9 10 | /* If the user wants a custom allocator they define: */ #define link_list_alloc( size, allocator_data ) user_alloc( allocator_data, size ) #define link_list_free( pointer, allocator_data ) user_free( allocator_data, pointer ) /* allocator_data is a void* the user can use to pass "context" to the allocator. */ /* Otherwise use the default: */ #ifndef link_list_alloc #define link_list_alloc( size, allocator_data ) malloc( size ) #define link_list_free( pointer, allocator_data ) free( pointer ) #endif |
This is actually the method I ended up deciding on. It seems easiest for at least how I want to use it. I think the "intrusive" method is interesting but well, I think a separate structure still works best for me. But thank you rationalcoder for the suggestion of the book, thats sure to be an interesting read!