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.
Hope this helps,
Wicked
fate.cartel.org 4000
On Wed, 25 Mar 1998, Chris Jacobson wrote:
> 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....
>
> My current system isn't necessarily the safest, simply storing the next
> pointer - what if that NEXT mob gets removed from the list? The regular
> system (I think) either does the same or simply uses ch->next - I don't
> recall offhand.
>
> The SAFEST system, to my knowledge, is using vectors - as implemented in
> Eric Green's FL codebase. Any removal-from-list simply NULLs the current
> vector and sets the "dirty" flag on the master vector structure. During
> iteration, if the current vector is NULL, simply skip it. The vector
> structure stores the number of iterators in use. When an iteration ends,
> it "finishes up" (and decrements the vector structure iterator counter),
> and if the number of iterators is 0 and the vector is marked "dirty",
> calls a function to "rebuild" the vectors.
>
> I'm wondering about other methods people have considered/done. One
> method that a friend suggested is a reenterant list iterator, but he did
> not describe it at all, and I have no information on such a piece of
> code, nor any idea how to go about implementing a safe list iterator... I
> can think of many instances that would mess any list iterator I can think
> of.
>
> - Chris Jacobson
>
>
> +------------------------------------------------------------+
> | Ensure that you have read the CircleMUD Mailing List FAQ: |
> | http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
> +------------------------------------------------------------+
>
+------------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
| http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 12/15/00 PST