Re: [CODE CONCEPTS] Linked lists / reenterant list iterators

From: Patrick J. Dughi (dughi@IMAXX.NET)
Date: 03/26/98

> > So I was thinking, what would be the SAFEST way to implement linked
> > lists, and to iterate through the list without losing place, when there
> > is the chance that the current, previous, next, or any other item in the
> > list could be removed in mid-iteration....

> The method below with the "dirty" flag would be the best method for this.
> I have used a method before called tombstoning.  It works in the following
> manner:  If you want something to be considered removed from the list, set
> one of the values to a value it won't take on under normal circumstances.
> '-1' is a good value.  If you are trying to read from the list and
> encounter a tombstone, just skip it.  Now, if you are afraid of having to
> many tombstones, just write a procedure to remove tombstones when safe to
> do so.  Otherwise, you can just insert over the top of things that have
> been tombstoned.

        Beat me to it - was going to say - instead of freeing within the
list, just set a value to one that doesn't make sense. The next time you
run through that list, immediately before it, run a cleaning function that
frees up and re-orders the list.


     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     | |

This archive was generated by hypermail 2b30 : 12/15/00 PST