I am currently writing a C code for a doubly linked list(dll) around which I want to write wrapers for implementing stack, queues etc. instead of writing separate codes for all of them.
I’ll be using void * for making it possible for the doubly linked list to work with any data type. The idea is basically the same as this implementation of stack using pointers in my github.
I am thinking of 2 different designs
- Placing the size of elements alongwith the maintenance data. That would make coding easier but any instance of dll would be able to use only a particular data type.
- Placing the size of element in the nodes. That would make it more general but I have concerns whether this approach would be easier to use?
This is the confusion that I wanted to clear before implementing any particular one. If there is any confusion regarding what I am trying to implement then please ask and I’ll clarify.
7
Let me start by answering your question:
Storing the element size per-node or per-list isn’t going to make the code any more or less complex one way or the other. The only real difference will be that anyone calling to add a node will have to pass a size once or each time, and the amount of storage required for each node may grow by an extra size_t‘s worth of bytes. The tradeoff between using less memory and having less flexibility versus using more memory and having more flexibility is something you’d have to evaluate on a case-by-case basis.
Let me finish by suggesting an alternative:
If you’re implementing this to be general-purpose tools along the lines of the STL or Java’s generic containers, I would suggest taking a completely different tack and not trying to do anything with the pointers you’re given. Just store them in your list and return them as it’s traversed.
Your allocate-and-copy approach goes on the assumption that what’s being stored are simple structures, which has a couple of pitfalls:
-
My structure may have additional pointers to allocated memory. If I’m using your list as primary storage for my data and you take it upon yourself to
free()it when I call yourcleanup()function, there’s no opportunity for me to free any of the additional memory unless I traverse the entire thing beforehand and do my own cleaning up. If that’s going to be the case, I might as well just do a traversal and remove the nodes one at a time. You could work around this by providing a disposal hook, which you’d call anytime you wanted to de-allocate a node. -
The pointer I hand you may not be a pointer to a structure. For example, I may have a large block of memory and want to store a list of place markers or something which involves simply pointing at various places in the block. Your implementation requires that I give you a place to copy data from/to during push, pop and peek operations. I’d have to define another structure with a single member to hold my pointer value. That’s awkward and inconvenient. (You could, however, write a wrapper that does allocate-and-copy and uses the pointers-only implementation.)
8
Perhaps you should take a look at the intrusive linked list implementation used in the Linux kernel. The source can be browsed here.
An intrusive design has the advantage that any type can be placed into a list just by including a list element in the structure definition.
Disadvantages include slightly more cumbersome syntax (a matter of personal preference, of course) and the requirement to include multiple members of the same type when your data needs to go into more than one list.
Intrusive lists are mostly useful when you only need a small number of lists and especially when your module/app are focused on adding and removing nodes from one list. A different design might be more suitable if your code needs to deal with local or disposable lists. The former consideration is true for most uses of lists in the kernel.