While restructuring my simple IO multiplexing module I had to solve
a problem that was not completely trivial. It might make an
instructive exercise so I will explain it here.
The problem is that I am iterating over a collection (C array)
that can be modified by the functions called during the iteration.
More specifically, some elements could be removed during the
iteration. I thought the simplest way to do this is to have a
flag that marks the validity of elements in my array. This way,
instead of deleting during the iteration I change a flag and,
during the iteration, I skip flagged elements.
After the iteration, we have to compact the array
to remove flagged elements. My first (mental) try was quadratic
but with some more thought, I found a linear algorithm. I let
you meditate and find it, it's not so hard and pretty nice to
hack (3 lines in my program).