digitalmars.D.learn - Correctly implementing a bidirectional range on a linked list?
- Gary Willoughby (12/12) Jul 06 2015 How do you correctly implement a bidirectional range on a linked
- Alex Parrill (10/17) Jul 06 2015 This is why modifying a sequence while iterating over it is
- anonymous (16/28) Jul 06 2015 There's no requirement for a range to stay valid when the
- anonymous (3/6) Jul 06 2015 Looks like I messed up the URL. Here's the right one:
- Jonathan M Davis via Digitalmars-d-learn (20/24) Jul 07 2015 This is why you almost never use @trusted on templated functions. You sh...
- Gary Willoughby (2/32) Jul 07 2015 Thanks for the advice.
How do you correctly implement a bidirectional range on a linked list? I have a linked list implementation and I've added a range interface to it but after a while I've realized it not quite right. The problem is when I call the save method of the forward range interface I don't get a copy I only get another view to the same state. So when i remove nodes from the original list the range becomes invalid. How can you implement such a range over a type whose state is accessed via pointers? Here's my implementation: https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d#L533
Jul 06 2015
On Monday, 6 July 2015 at 20:50:19 UTC, Gary Willoughby wrote:The problem is when I call the save method of the forward range interface I don't get a copy I only get another view to the same state. So when i remove nodes from the original list the range becomes invalid.This is why modifying a sequence while iterating over it is generally forbidden; there's no good way to make it work. You could duplicate the entire list for each range, but that's expensive for the usual case of simply reading the list. Forward ranges don't require that ranges be independent of the data they iterate over [1]:Saving a range is not duplicating it; in the example above, r1 and r2 still refer to the same underlying data. They just navigate that data independently.IMO your implementation is fine. [1]: http://dlang.org/phobos/std_range_primitives.html#isForwardRange
Jul 06 2015
On Monday, 6 July 2015 at 20:50:19 UTC, Gary Willoughby wrote:How do you correctly implement a bidirectional range on a linked list? I have a linked list implementation and I've added a range interface to it but after a while I've realized it not quite right. The problem is when I call the save method of the forward range interface I don't get a copy I only get another view to the same state. So when i remove nodes from the original list the range becomes invalid. How can you implement such a range over a type whose state is accessed via pointers? Here's my implementation: https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d#L533There's no requirement for a range to stay valid when the underlying container changes. std.container defines "stable" variants of the various insertion and removal operations. They promise not to invalidate any ranges. When the unstable variants are used, it's to be expected that ranges are invalidated. To make your removal methods stable, it may be enough to not free the removed node. That is, don't do this: https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection There's a doubly linked list in phobos: std.container.dlist; maybe look how things are done there: https://github.com/D-Programming-Language/phobos/blob/master/std/container/dlist.d Off topic: I think ` trusted:` is horrible. It's easy to forget that you're in a trusted environment when editing things later. And even worse, you're trusting everything that's passed through template parameters.
Jul 06 2015
On Monday, 6 July 2015 at 21:58:31 UTC, anonymous wrote:To make your removal methods stable, it may be enough to not free the removed node. That is, don't do this: https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collectionLooks like I messed up the URL. Here's the right one: https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d#L205-L206
Jul 06 2015
On Monday, July 06, 2015 21:58:30 anonymous via Digitalmars-d-learn wrote:Off topic: I think ` trusted:` is horrible. It's easy to forget that you're in a trusted environment when editing things later. And even worse, you're trusting everything that's passed through template parameters.This is why you almost never use trusted on templated functions. You should _never_ mark anything with trusted unless you can guarantee that it's actually safe. safe is inferred for templated functions, so unless you're doing system operations in a templated function, there is no need for trusted, and if you are doing system operations, then they need to be segregated in a way that you can mark that section of code as trusted and guarantee that it's safe regardless of what the template argument is. But you should _never_ mark code as trusted if it involves calling functions that you can't guarantee are safe, which almost always means that you should not mark code which calls functions on template arguments as trusted. That being said, trusted is very much a necessity in certain types of code, so it would be really bad if we didn't have it. But if you're marking much code as trusted, or if you're marking templated code as trusted, then you really need to be examining what you're doing. Very little code should need to be marked as trusted, and every time that it is, you need to be able to absolutely guarantee that it's actually safe in spite of the system operations that you're doing in that code. - Jonathan M Davis
Jul 07 2015
On Tuesday, 7 July 2015 at 09:35:12 UTC, Jonathan M Davis wrote:This is why you almost never use trusted on templated functions. You should _never_ mark anything with trusted unless you can guarantee that it's actually safe. safe is inferred for templated functions, so unless you're doing system operations in a templated function, there is no need for trusted, and if you are doing system operations, then they need to be segregated in a way that you can mark that section of code as trusted and guarantee that it's safe regardless of what the template argument is. But you should _never_ mark code as trusted if it involves calling functions that you can't guarantee are safe, which almost always means that you should not mark code which calls functions on template arguments as trusted. That being said, trusted is very much a necessity in certain types of code, so it would be really bad if we didn't have it. But if you're marking much code as trusted, or if you're marking templated code as trusted, then you really need to be examining what you're doing. Very little code should need to be marked as trusted, and every time that it is, you need to be able to absolutely guarantee that it's actually safe in spite of the system operations that you're doing in that code. - Jonathan M DavisThanks for the advice.
Jul 07 2015