[crossfire] safe/common item stack/inventory iteration?

[Mark Wedel]

Bernd Edler wrote:

> 
> If we are sure tmp will not be destroyed in some uncontrollable recursive
> calls we can avoid bailing out altogether:

  We can't be sure that tmp won't get destroyed.  In the general case, one has 
no real clue what may or may not get destroyed.  And in almost all cases, it is 
a function that is called (or function of a function) that destroys tmp, not the 
function where the for loop itself exists, so the code snippet below won't work.

> 
> 
>       for (tmp = op->inv;tmp != NULL;;) {
>           destroy_me = NULL;
>           {
>            do some work
>            replace destroy_obj(tmp) with destroy_me = tmp;
>            do more work
>           }
>           tmp = tmp->below;
>           if { destroy_me } then destroy_obj(destroy_me);
>       }
> 
> If we want the big and clean solution, we only really kill objects
> afterwards. This costs us one extra pointer per
> object. like ob->destroy_list,
> plus two variables: Destroy_list_first,Destroy_list_last
> As in:
> 
> void mark_for_destruction(object ob) {
>    if ( ob->destroy_list != null ) then return;
>      /* this one is dead already */
>    if ( Destroy_list_first == NULL ) then {
>       Destroy_list_first = ob;
>       Destroy_list_last = ob;
>     }
>    Destroy_list_last->destroy_list = ob;
>    ob->destroy_list = ob;
>      /* self-reference marks end of list  */
>    Destroy_list_last = ob;
>     { remove the object from lists like active,below etc. }
> }

  The problem is that when the object is removed from the active and below 
lists, that is what screws up the pointers.  In the simple case, something like:

  for (tmp=op->inv; tmp; tmp=tmp->below) { ... }

  Fails in the above case if tmp is put on a destroy list, because tmp->below 
now doesn't point to anything meaningful (well, it points to null, which would 
then result in that for loop terminating, which isn't really different than my 
described change).

  This isn't a real simple problem.  As said, the use of the:
for (tmp=op->inv; tmp; tmp=next) {
     next = tmp->below
     ....
}

  Covers the case just fine when tmp is destroyed in the processing.  It doesn't 
cover the case when next is destroyed in the processing, which is what I 
observed in the bug.

  and I could even see in some rare cases where both tmp and next are destroyed 
in the processing, leaving one with really nothing to work with.  Under any 
situation, I can come up with some method that could potentially result in 
things not working.  Storing a pointer to the last object processed, and if 
something is destroyed, walk the last until you get to that object, and then 
resume, doesn't work, because that last processed object could be destroyed.

  Such wide spread changes to objects is much more likely to happen for ground 
spaces than inventory (a spell could in theory destroy 50% of the objects on a 
space for example).

  The only really foolproof way would be to add some flag - something like 
'FLAG_NEEDS_TO_BE_DESTROYED'.  Instead of the object actually getting destroyed, 
that flag is set, and then there is some other function later that goes through 
and cleans these objects up.

  However, that would add a lot of processing time.  It would also require a 
pretty major rewrite.  That is because the logic is generally like:

  remove_object(op) - this removes it from the map/inventory, and clears the 
above/below pointers, etc, so this has to be modified not to actually remove the 
object in question, but instead state it has to be removed.

  free_object(op) - this is what actually returns the memory to the system - 
this can't happen as long as op hasn't been removed.  So the usual case of:

  remove_op(op);
  free_object(op);

  Wouldn't really work - remove_ob would have to mark that the object needs to 
be removed, free_object would have to mark that that object should be freed, and 
then elsewhere, the actual work of removing/freeing those objects would have to 
happen (probably called from the main loop, where we can know that nothing else 
will be messing with those objects).  But even that gets tricky - if an object 
is on top of a button, when that object is removed, button is now triggered, 
which could result in other objects getting destroyed.

  But because those calls are used everywhere, that cleanup routine would have 
to examine _all_ of the objects - and lots of other code would have to be 
modified to be aware of these pending objects (in the for loops above, it would 
need to skip over these, etc).


In any case, what I was thinking about was more trying to make macros so that 
when we find cases of that loop needing different/better processing, it is just 
a matter of updating the macros, not of updating 50 different for loops in the code.