From: Jeffrey Carter <jrcarter@acm.org>
Subject: Re: List container strawman
Date: Sat, 03 Nov 2001 19:22:14 GMT
Date: 2001-11-03T19:22:14+00:00 [thread overview]
Message-ID: <3BE443DE.574D669C@acm.org> (raw)
In-Reply-To: gyME7.11045$xS6.15364@www.newsranger.com
Ted Dennison wrote:
>
> 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)?
That's right. You don't get 100% confidence, but it's better than the
nothing that most lists provide.
>
> 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.
It's certainly possible that the memory could be reallocated to the same
list, so the dangling reference becomes valid again. I did say *fairly*
foolproof. :)
>
> b) The OS marks that location as not allocated, and issues a segfault (or
> whatever) when you try to access it.
Then you're no worse off than without the check.
> 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.
Let me record my vote against unary operators as primary names. I
probably won't object if they're renames of other subprograms. I suggest
Clear for deleting all Elements in a List; Make_Empty might also be
acceptable.
Finally, what you're calling an iterator is what is usually called a
"position within a list" in discussing lists as an abstraction, and the
manipulation of a list is usually defined in terms of positions. I think
it would make the package easier to understand if it adheres to this
convention: call the type Position and present the operations for
obtaining positions and using them to manipulate a list before the
dequeue- and string-like operations.
--
Jeff Carter
"I fart in your general direction."
Monty Python & the Holy Grail
next prev parent reply other threads:[~2001-11-03 19:22 UTC|newest]
Thread overview: 166+ messages / expand[flat|nested] mbox.gz Atom feed top
2001-11-02 3:56 List container strawman Ted Dennison
2001-11-02 4:20 ` James Rogers
2001-11-02 14:23 ` Ted Dennison
2001-11-02 14:38 ` Preben Randhol
2001-11-02 15:15 ` Larry Kilgallen
2001-11-02 4:35 ` Eric Merritt
2001-11-02 15:46 ` Ted Dennison
2001-11-02 7:28 ` Ehud Lamm
2001-11-02 14:57 ` Marin David Condic
2001-11-02 15:57 ` Francisco Javier Loma Daza
2001-11-02 16:28 ` Marin David Condic
2001-11-02 17:08 ` Ted Dennison
2001-11-02 15:06 ` Ted Dennison
2001-11-02 15:32 ` Marin David Condic
2001-11-02 16:33 ` Ted Dennison
2001-11-02 16:43 ` Marin David Condic
2001-11-02 22:51 ` Jeffrey Carter
2001-11-03 0:24 ` Matthew Heaney
2001-11-03 2:21 ` Jeffrey Carter
2001-11-03 22:51 ` Rosen Trick [List container strawman] Nick Roberts
2001-11-04 13:07 ` Robert Dewar
2001-11-04 17:17 ` Side-Effects in Functions [Rosen Trick] Nick Roberts
2001-11-05 2:46 ` Robert Dewar
2001-11-05 7:26 ` pete
2001-11-05 10:29 ` Dmitry A. Kazakov
2001-11-05 11:19 ` pete
2001-11-05 14:59 ` Dmitry A. Kazakov
2001-11-05 15:21 ` Preben Randhol
2001-11-05 16:04 ` Ted Dennison
2001-11-05 16:33 ` Dmitry A. Kazakov
2001-11-05 17:42 ` Warren W. Gay VE3WWG
2001-11-05 18:11 ` Preben Randhol
2001-11-06 8:38 ` Dmitry A. Kazakov
2001-11-06 9:31 ` tgingold
2001-11-06 0:10 ` Nick Roberts
2001-11-06 9:30 ` Dmitry A. Kazakov
2001-11-06 16:18 ` Lazy Evaluation [Side-Effects in Functions] Nick Roberts
2001-11-07 3:42 ` Robert Dewar
2001-11-07 4:42 ` Darren New
2001-11-07 11:54 ` Robert Dewar
2001-11-07 13:32 ` Florian Weimer
2001-11-07 13:24 ` Jean-Marc Bourguet
2001-11-09 18:06 ` Ted Dennison
2001-11-09 18:27 ` M. A. Alves
2001-11-11 20:13 ` Georg Bauhaus
2001-12-06 17:47 ` Harri J Haataja
2001-11-07 9:28 ` Dmitry A. Kazakov
2001-11-06 20:08 ` Side-Effects in Functions [Rosen Trick] Florian Weimer
2001-11-06 22:48 ` Nick Roberts
2001-11-07 10:46 ` Florian Weimer
2001-11-05 13:56 ` Robert Dewar
2001-11-05 16:08 ` Ted Dennison
2001-11-05 17:44 ` Warren W. Gay VE3WWG
2001-11-05 15:56 ` Ted Dennison
2001-11-05 18:46 ` Nick Roberts
2001-11-08 11:51 ` Georg Bauhaus
2001-11-16 0:31 ` List container strawman Vincent Marciante
2001-11-05 15:10 ` Marin David Condic
2001-11-05 18:31 ` Ted Dennison
2001-11-05 19:09 ` Marin David Condic
2001-11-05 21:23 ` Ted Dennison
2001-11-07 19:27 ` Stephen Leake
2001-11-02 18:11 ` Mark Johnson
2001-11-02 18:46 ` Marin David Condic
2001-11-02 19:21 ` Larry Kilgallen
2001-11-03 22:30 ` Nick Roberts
2001-11-02 16:26 ` Ted Dennison
2001-11-02 16:36 ` Marin David Condic
2001-11-02 19:31 ` Ted Dennison
2001-11-02 17:49 ` Jeffrey Carter
2001-11-08 10:34 ` Ehud Lamm
2001-11-08 18:53 ` Better Finalisation [List container strawman] Nick Roberts
2001-11-09 13:36 ` Robert Dewar
2001-11-09 15:04 ` Florian Weimer
2001-11-10 0:36 ` Nick Roberts
2001-11-09 15:16 ` Ted Dennison
2001-11-09 17:30 ` Better control of assignment Jeffrey Carter
2001-11-10 0:32 ` Nick Roberts
2001-11-10 22:27 ` Jeffrey Carter
2001-11-13 6:36 ` Craig Carey
2001-11-13 6:39 ` Craig Carey
2001-11-13 8:53 ` Craig Carey
2001-11-14 9:42 ` Craig Carey
2001-11-09 14:49 ` List container strawman Ted Dennison
2001-11-09 16:12 ` Ehud Lamm
2001-11-09 17:12 ` Marin David Condic
2001-11-09 18:11 ` Ted Dennison
2001-11-09 18:42 ` Matthew Heaney
2001-11-10 17:54 ` Simon Wright
[not found] ` <3BE29AF4.80804@telepath.com>
2001-11-02 13:14 ` Ted Dennison
2001-11-02 13:31 ` Larry Kilgallen
2001-11-02 15:09 ` Ted Dennison
2001-11-02 15:13 ` Preben Randhol
2001-11-02 20:48 ` David Starner
2001-11-02 22:49 ` Larry Kilgallen
2001-11-02 17:44 ` Jeffrey Carter
2001-11-02 20:07 ` Ted Dennison
2001-11-02 23:19 ` Jeffrey Carter
2001-11-03 6:56 ` Ted Dennison
2001-11-03 19:22 ` Jeffrey Carter [this message]
2001-11-04 18:58 ` Darren New
2001-11-04 19:40 ` Larry Kilgallen
2001-11-04 20:49 ` Darren New
2001-11-07 19:07 ` ramatthews
2001-11-08 0:04 ` Darren New
2001-11-08 4:50 ` Jeffrey Carter
2001-11-08 23:26 ` ramatthews
2001-11-09 18:00 ` Ted Dennison
2001-11-09 18:13 ` Jean-Marc Bourguet
2001-11-09 18:55 ` Ted Dennison
2001-11-10 1:48 ` Nick Roberts
2001-11-10 17:04 ` Ted Dennison
2001-11-10 20:59 ` Nick Roberts
2001-11-10 23:17 ` Larry Hazel
2001-11-11 3:27 ` Nick Roberts
2001-11-12 18:39 ` Darren New
2001-11-13 0:35 ` Nick Roberts
2001-11-10 19:36 ` Ehud Lamm
2001-11-10 20:15 ` Nick Roberts
2001-11-09 19:27 ` Larry Kilgallen
2001-11-09 20:03 ` Stephen Leake
2001-11-09 21:05 ` Ted Dennison
2001-11-09 22:42 ` Larry Kilgallen
2001-11-10 4:52 ` Nick Roberts
2001-11-10 20:24 ` ramatthews
2001-11-05 19:28 ` Ted Dennison
2001-11-05 19:42 ` Jean-Marc Bourguet
2001-11-05 20:40 ` Ted Dennison
2001-11-05 20:24 ` Darren New
2001-11-05 20:45 ` Ted Dennison
2001-11-05 17:21 ` List container strawman; Construct alternatives Stephen Leake
2001-11-03 7:42 ` List container strawman Simon Wright
2001-11-05 14:00 ` Stephen Leake
2001-11-08 11:17 ` Simon Wright
2001-11-13 16:29 ` Stephen Leake
2001-11-13 22:43 ` Jeffrey Carter
2001-11-13 22:48 ` Jeffrey Carter
2001-11-14 3:46 ` Nick Roberts
2001-11-15 10:23 ` Ehud Lamm
2001-11-14 14:50 ` Marin David Condic
2001-11-14 16:53 ` Jeffrey Carter
2001-11-14 17:59 ` Marin David Condic
2001-11-15 3:33 ` Nick Roberts
2001-11-15 15:10 ` Marin David Condic
2001-11-16 1:29 ` Nick Roberts
2001-11-16 16:03 ` Marin David Condic
2001-11-16 20:19 ` Nick Roberts
2001-11-15 18:08 ` Matthew Heaney
2001-11-02 14:49 ` Marin David Condic
2001-11-02 15:15 ` Ted Dennison
2001-11-02 15:37 ` Marin David Condic
2001-11-02 16:49 ` Ted Dennison
2001-11-02 17:09 ` Marin David Condic
2001-11-04 0:10 ` Nick Roberts
2001-11-03 23:41 ` Nick Roberts
2001-11-02 17:02 ` David Botton
2001-11-02 17:55 ` David Botton
2001-11-03 19:22 ` Nick Roberts
2001-11-08 14:57 ` M. A. Alves
2001-11-09 2:00 ` Jeffrey Carter
2001-11-09 18:31 ` Ted Dennison
2001-11-10 19:56 ` Ehud Lamm
-- strict thread matches above, loose matches on Subject: below --
2001-11-02 19:54 Mike Brenner
2001-11-02 21:04 ` Ted Dennison
2001-11-03 8:09 ` Simon Wright
2001-11-03 12:46 ` Simon Wright
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox