Re: List container strawman

[Ted Dennison<dennison@telepath.com>]

In article <3BE32A18.18404AD1@boeing.com>, Jeffrey Carter says...
>The technique used by PragmARC.List_Unbounded_Unprotected is that the
>list object contains a pointer to a "mini-node" (a node with no data
>stored in it). This makes insertions and deletions at the beginning and
>end of the list look exactly the same as insertions and deletions in the
>middle, but it also follows that the value of this pointer is unique to
>the list object. Call this value the list ID. Every node in the list
>contains a copy of this ID, as does every Position value generated for
>the list. An operation is not permitted unless the IDs for the list,
>position, and node match. When a node is deleted, its ID is invalidated
>(set to null), and the position used to delete the node is similarly
>invalidated (both its ID and pointer are set to null). If a client makes
>a copy of a Position and uses one to delete a node, he cannot then
>manipulate the deallocated node through the other since it has an
>invalid ID. Easy to implement and fairly foolproof.

So you are saying that you are placing values into the memory before it is
deallocated, in the hopes that any code trying to access it through a stale
pointer will still find that value there (telling it not to use this)?

What if:
a) The memory at that location gets reallocated to something else in the
meantime, which then puts what looks like a valid value in there.

b) The OS marks that location as not allocated, and issues a segfault (or
whatever) when you try to access it.

>Now that I know that this is standard list manipulation, not iteration,
>I'd recommend calling it Delete. It's also a lot simpler to make
>Location in out and invalidate it.

That could be done. "Delete" would also be a natural name for toasting a list,
but then I guess in the current scheme "-" would make more sense for that.

>There should probably be an Update procedure that changes the Element
>stored at a location.

That sounds right.


---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.