geda-developers team mailing list archive

[Peter Clifton <pcjc2@xxxxxxxxx>]

On Wed, 2012-12-19 at 00:00 +0100, Ivan Stankovic wrote:

> While this is not too verbose, I have a feeling we could do better. More
> troublesome is that it's not obvious how eda_objectset_remove and 
> eda_objectset_iter_next interact. Does eda_objectset_remove automatically
> advances the iterator? Does the iterator get invalidated?

Modifying a set or list whilst iterating over it is always a cause for
concern, and it isn't obvious what the correct behaviour is.


One might reasonably argue that it is useful to iterate over a snapshot
copy of the set, although that might require a few extra API calls to
set up the lifetime / scope of that copy (certainly in C).

As we had the desire for the iterator to be heap-allocated, it would
make the API more burdensome if the iterator structure were to store
anything which couldn't be be automatically disposed of. That means
using C++ magic (I think), to handle the iterator lifecycle, or not
allowing the iterator to contain object references or dynamically
allocated memory.

Yes, we could have a function to free iterator contents, but doing so is
atypical of other iterator APIs, and probably asks for introducing
memory leaks in our code where people forget.


If the remove API actually removes the item immediately (and there is no
temporary refcount held by the iterator being in scope), this means that
after the remove operation, the iterator must not continue need data
just removed from the set (including set meta-data such as the actual
linked list or tree underlying the set). The underlying resources will
just have been free'd, or returned to a memory pool.

Unless removal of set meta-data can be deferred until after the
iteration is complete or we iterate over a snapshot copy (again, giving
lifecvvle / scoping issues), it may mean that the iterator needs to
contain enough data in advance that a call to eda_objectset_iter_next()
or eda_objectset_iter_prev() can return a the correct object without
needing to refer back to the meta-data for the set entry iter currently
(previously?) refers to.

The above might lead to a simplifying assumption, that we cannot allow
more than one active iterator into the set at a time. (If not, the
remove call needs to manage "fixing up" all active iterators, otherwise
it becomes limitless how much data we need to store, or keep referenced
from inside each iterator.)

As our APIs so far (necessarily) expect the iterator structure to be an
opaque structure of known size at compile-time, the size of this will
need to be agreed upon in advance and utilised by all implementations.
This I think, implies that we can't expect to throw great amounts of
data into the iterator to solve our problems.



(Did any of that make any sense.. perhaps it comes across that I've not
had to implement something like this before?)

-- 
Peter Clifton <peter.clifton@xxxxxxxxxxxxxxxxxxxxxxxxx>

Clifton Electronics