[Intrusive] List Manipulation and Management
Hi all, I am moderningising/porting some old Pascal code. The code makes extensive use of an intrusive singly-linked structure termed a node. In order to replicate this idiom in C++ I have been investigating the Intrusive library. However, I have several questions about list manipulation and memory management. Firstly, in the code being ported all nodes can be thought of as being heap allocated. The following is extremely common (pseudo-code): Node* afunction(...); [...] Node* tail; link(tail, afunction(...)); This is rather nice as in O(1) you can append a returned list to your current list. However, I am unsure how I would accomplish this in Boost Intrusive. I can not seem to find a way to create the somewhat fragile intrusive::list from just a node (be it singly or doubly linked). The list class also seems to take T& as opposed to T* when pusing to the front/back of the list. My experience of intrusive structure in C was that you'd always take a pointer when adding a new link. Secondly, when dealing with heap allocated items, which need to be deleted, the current code uses a while loop to call each nodes destructor. What is the intrusive equivalent? Of course, I am open to ideas/suggestions about better ways to accomplish the above tasks :) Regards, Freddie.
Am Saturday 26 September 2009 20:18:58 schrieb Freddie Witherden:
Node* afunction(...); [...] Node* tail; link(tail, afunction(...));
This is rather nice as in O(1) you can append a returned list to your current list. However, I am unsure how I would accomplish this in Boost Intrusive.
list.splice(list.end(),otherlist); boost.intrusive represents the nodes as STL-like containers, if you need to port code that handles nodes directly you might be interested in *list_algorithms of boost.intrusive, but I'd recommend using the containers.
Secondly, when dealing with heap allocated items, which need to be deleted, the current code uses a while loop to call each nodes destructor. What is the intrusive equivalent?
clear_and_dispose()
Hi, On 26 Sep 2009, at 23:49, Stefan Strasser wrote:
list.splice(list.end(),otherlist);
boost.intrusive represents the nodes as STL-like containers, if you need to port code that handles nodes directly you might be interested in *list_algorithms of boost.intrusive, but I'd recommend using the containers.
Doesn't splice require otherlist to be a list? This seems to make it somewhat inadequate, as the docs make the list class out to be rather brittle (non-copyable and non-assignable), so returning a list from afunction() is not a option. I guess one can return a pointer to a new- ly allocated list, but that is another pointer to delete and more boilerplate code. I would rather use the containers if at all possible, however, the design seems to be working against me in this scenario.
Secondly, when dealing with heap allocated items, which need to be deleted, the current code uses a while loop to call each nodes destructor. What is the intrusive equivalent?
clear_and_dispose()
Excellent. In the library I am writing/porting it is sometimes necessary to return one of these lists. Naturally, one will want to return a clone of the internal list, however, what would be the nicest way to ensure its disposal? It may be somewhat haphazard to rely on users to call a specific dispose/delete method. Are there any exceptionally neat solutions to this? Regards, Freddie.
Am Sunday 27 September 2009 00:21:52 schrieb Freddie Witherden:
Hi,
On 26 Sep 2009, at 23:49, Stefan Strasser wrote:
list.splice(list.end(),otherlist);
boost.intrusive represents the nodes as STL-like containers, if you need to port code that handles nodes directly you might be interested in *list_algorithms of boost.intrusive, but I'd recommend using the containers.
Doesn't splice require otherlist to be a list? This seems to make it somewhat inadequate, as the docs make the list class out to be rather brittle (non-copyable and non-assignable), so returning a list from afunction() is not a option. I guess one can return a pointer to a new- ly allocated list, but that is another pointer to delete and more boilerplate code.
I would rather use the containers if at all possible, however, the design seems to be working against me in this scenario.
you cannot treat intrusive lists as values that you can return, this is by concept. a single value(more precicely: hook) can only be part of one intrusive list at a time. there are multiple solutions for this, depending on your code. passing the list by reference to the function, passing an back_insert_iterator as OutputIterator etc. see e.g. http://www.cplusplus.com/reference/std/iterator/back_insert_iterator/
Secondly, when dealing with heap allocated items, which need to be deleted, the current code uses a while loop to call each nodes destructor. What is the intrusive equivalent?
clear_and_dispose()
Excellent. In the library I am writing/porting it is sometimes necessary to return one of these lists. Naturally, one will want to return a clone of the internal list, however, what would be the nicest way to ensure its disposal? It may be somewhat haphazard to rely on users to call a specific dispose/delete method. Are there any exceptionally neat solutions to this?
clear_and_dispose calls a dispose function. but it is user supplied and it is possible to remove from the list without disposing, but this is intentional again. depending on your use case again, you could A *a= new A[1000]; { list<...> l; l.push_back(a[500]); //more list calls } delete a; and not worry about disposing while using the list.
you cannot treat intrusive lists as values that you can return, this is by concept. a single value(more precicely: hook) can only be part of one intrusive list at a time. there are multiple solutions for this, depending on your code. passing the list by reference to the function, passing an back_insert_iterator as OutputIterator etc.
This seems like a reasonable solution. It makes sense as well considering that I only intended to insert from either the front or back of the list.
clear_and_dispose calls a dispose function. but it is user supplied and it is possible to remove from the list without disposing, but this is intentional again. depending on your use case again, you could A *a= new A[1000]; { list<...> l; l.push_back(a[500]); //more list calls } delete a;
The node list I was speaking of is actually more of a tree. As some of the node-subclasses have list members themselves (of course, in Pascal it is just Node* childList). So it could be quite difficult to flatten. Regards, Freddie.
participants (2)
-
Freddie Witherden -
Stefan Strasser