Robert Jacques Wrote: > On Sat, 06 Mar 2010 21:54:50 -0500, Steven Schveighoffer > <[email protected]> wrote: > > On Sat, 06 Mar 2010 11:19:15 -0500, Robert Jacques <[email protected]> > > wrote: > > > >> On Sat, 06 Mar 2010 08:19:36 -0500, Steven Schveighoffer > >> <[email protected]> wrote: > >>> > >>> How can softRemove not affect iterating ranges? What if the range is > >>> positioned on the element removed? > >> > >> It always affects ranges in so far as the range and container are > >> inconsistent, but that is a problem of softInsert as well. Removing an > >> element from an array doesn't invalidate the underlying range, since > >> the memory is still there. And so long as you're not trying to use free > >> lists, linked-lists, trees, etc. can be written so that the ranges > >> never enter an invalid state. If they happen to be pointing at the > >> removed node, they just end up stopping early. > > > > If my linked list range has two node pointers as the implementation, and > > you remove the end node, it's going to end later, not early. > > A linked list maps to a forward range: so the range simply points to a > single internal node. If you're going to store a pointer to the end, then > you should be using a doubly linked list, not a singly linked list.
How do you know when to stop? A range has a beginning and an ending, otherwise it's an iterator. Whether you store it via a pointer to the last (not-to-be-iterated) node, or via a length, or via a value to compare with for stopping, you have to use something. Or are you asserting the only useful range for a linked list iterates the entire list? Think of it as the equivalent of a slice of an array. > > > Of course, you can get around this by just storing a current node and a > > length, but that may not be what the user is expecting. For example, if > > you did a range of a sorted tree from "a" to "f" and it stops at "n", I > > think that would be extremely unexpected. > > By this logic, any and all forms of mutation, not just insertions and > deletions must not be allowed. Allowed, yes. Not invalidating iterators, no. > > > Stopping early is invalidation also IMO. If your program logic depends > > on iterating over all the elements you originally intended to iterate, > > then we have big problems if they stop early. > > Stopping early is the result of a logical error by the programmer. The > code itself, however, is completely valid. I still fail to see the difference between "soft" operations and non-soft. What does soft guarantee? Give me a concrete definition, an example would help too. > >>> The only two containers that would support softInsert would be linked > >>> list and sorted map/set. Anything else might completely screw up the > >>> iteration. I don't see a lot of "generic" use for it. > >> > >> There's all the containers based upon linked-lists, etc like hashes, > >> stacks, queues and dequeues. > > > > Hashes may be rehashed when inserting, completely invalidating a range > > (possibly the end point will be before the starting point). > > Wouldn't re-hashing necessitate re-allocation? (Thus the range would see a > stale view) God no. If my hash collision solution is linked-list based (which it is in dcollections), why should I reallocate all those nodes? I just rearrange them in a new bucket array. > > > Yes, the others you mentioned will be valid. But I still don't see it > > being more useful than just using documentation to indicate insertion > > will not invalidate ranges. Perhaps I am wrong. > > The difference is that algorithms can document in their template > constraints that they need a container with 'soft' properties. What is the advantage? Why would an algorithm require soft functions? What is an example of such an algorithm? > > >>> Another option is to use a "mutation" field that is checked every > >>> chance by the range. If it changes, then the range is invalidated. > >> > >> The mutation field would have to be a version number to support > >> multiple ranges, and given experience with lock-free algorithms which > >> use a 'tag' in a similar manner, this concept is bug prone and should > >> not be relied upon. It would be better to 'lock' the node or container > >> to topology changes, though this does slow things down and has no > >> conflict resolution: removing a locked node would have to throw an > >> exception. > > > > I was not thinking of multithreaded applications. I don't think it's > > worth making containers by default be multithreaded safe. > > I wasn't thinking of multi-threaded containers. I was trying to point out > that version ids have failed in lock-free containers, where things are > happening on the order of a single atomic op or a context switch. Given > the time a range could go unused in standard code, versioning won't work. Are you trying to say that if you don't use your range for exactly 2^32 mutations, it could mistakenly think the range is still valid? That's a valid, but very very weak point. > > > The mutation index has been used in Tango forever, and I think was in > > Doug Lea's original container implementations. I'm pretty sure it is > > sound in single-threaded uses. > > No it's not. version tags + integer overflow = bug. Doug Lea knew about > the problem and but thought it would never happen in real code. And Bill > Gates thought no one will need more than 640k of ram. They both have been > proven wrong. Overflow != bug. Wrapping completely to the same value == bug, but is so unlikely, it's worth the possibility. -Steve
