[Freeciv-Dev] Re: list cleaning

[Jason Short <jshort@xxxxxxxxxxxxxx>]

On Tue, 27 Jan 2004, Per I. Mathisen wrote:

> On Tue, 27 Jan 2004, Raimar Falke wrote:

> > This is also a large problem I have with your current lazy-delete patch.
> > It just doesn't feel safe. With an early destruction you can for example
> > catch access to this now dead memory with valgrind. With the lazy
> > approach you can't.
>
> What access? Any data pointed to by the list should be deleted the same
> moment that the list node is marked as 'deleted'. To not do so is a
> separate error.

Per's right.  For instance if you're iterating over a list of units and
one of them dies you both free the unit and delete it from the list.
Under the delayed-deleting the removal from the list is delayed.  But the
unit is still gone.  To the caller there is no visible difference from
what happens now.

However I also don't like delaying the deletion to far.  Doing it in an
end-of-turn loop is ugly, since this removes the clean interface and
forces the calling code to know about the delayed-deletion mechanism.  My
preference would be for:

- At the end of the loop, if any nodes were deleted iterate through and
find+remove them.

- As you're iterating through the loop, when you pass a node that's
deleted remove it.  The current problem, IIRC, is with deleting the
current node since you still need the pointer it provides to get to the
next node.  But at the end of the block when you move on to the next node
you shouldn't need the current node anymore.

Both of these require a very small ammortized overhead - no more than one
extra boolean check per loop iteration.  So efficiency shouldn't be a
concern when compared to the delete-at-end-of-turn mechanism.

jason