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 |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 12/15/00 PST