geda-developers team mailing list archive

[Peter TB Brett <peter@xxxxxxxxxxxxx>]

Oops, didn't reply to list...

-------- Original Message --------
Subject: Re: [Geda-developers] [RFC] libgeda data structures and algorithms
Date: Sun, 16 Dec 2012 23:41:06 +0000
From: Peter TB Brett <peter@xxxxxxxxxxxxx>
To: <peter.clifton@xxxxxxxxxxxxxxxxxxxxxxxxx>

On Sun, 16 Dec 2012 23:22:50 +0000, Peter Clifton <pcjc2@xxxxxxxxx> wrote:
> However.. it should provide a decent drop-in r-tree implementation which
> works with libgeda OBJECTs. The implementation is taken directly from
> PCB, but has a number of its functions renamed to fit in with the
> libgeda naming conventions (of the time ofGrr.. every damn  the branch).
> There are then a few patches which make it more libgeda/gschem friendly.
> 

Unfortunately PCB uses an R-tree, rather than an R*-tree.  R*-trees have
quite a lot better performance, especially when there are frequent
insertions and deletions: they make searching faster by ensuring minimal
overlap between nodes.  On the other hand, all of the insertion-related
algorithms are significantly different.

I hadn't thought of using an R-tree in gschem for rendering purposes (I was
more focusing on the connection-tracking stuff), but it would make good
sense.

> It seems every tool ends up inventing their own region / rect type...
> grr.. wish there was a standard here.

Well, partly this is because each library has different ideas of what units
are involved, what precision, how the axes are defined, etc... it doesn't
bother me enough to lose sleep over it. ;-)

>> Unfortunately, this has been stymied by the fact that
>> it's not currently possible to receive a signal when an object is added
>> to or removed from a page.
> 
> You will need that to keep your spatial index (R-Tree, whatever) up to
> date.

Well, initially the spatial index could slot in using a similar system to
the way the current tile system is maintained.  But yes, signals would be
ideal.

> I have a branch / patch for attribute change notification somewhere, and
> I used it to replace the nasty hard-coded checks throughout our code for
> slotting related attributes.
> 
> The reason I never pushed it was that (IIRC) it caused some race / crash
> conditions at close-down time, as it would still be delivering change
> notifications as gschem was winding down and free'ing the page contents.
> Nothing insurmountable, but worth remembering if you grab my patch.

Yes, and I seem to recall that that patch has already cycled through
'master' once.  The problem is that that seemed to me to be the sort of
thing that would be really really easy to construct if we could hook into
signals...!

>> Ideally, we shouldn't expose bare GLists anywhere in the API.  It's too
>> much of a temptation to write code which hacks at the list structures
>> directly rather than to use accessors that ensure consistency is
>> maintained.  I'd like to introduce an EdaObjectIter to be used to
>> iterate over object sets.
> 
> Sounds like a lot of work just to force people to behave. OTOH, it does
> help type safety. I know that I've been undecided between both myself in
> the past, and if we didn't already have this design discussion about
> some interface or other, I'm surprised. (We probably looked at this
> regarding GedaList?)

It doesn't just help type safety -- it's the only way to ensure thread
safety.  You keep a stamp number in each iterator, which allows you to
invalidate the iterator if the structure gets modified through a different
iterator.

>> Safely loading schematics and symbols
>> -------------------------------------
>> We have a big crash bug with the current recursive nature of our
>> schematic file parser [2].  The only sane way to fix it appears to be to
>> resolve and load symbols from the library on a separate pass.
> 
> Is this a good opportunity to make symbols load once, and have one
> in-memory copy, plus a separate "GedaInstanceOfSymbol" data-structure on
> the page?

I agree that that would be nice, and it was something that I was keen to
look into as part of my "new libraries" exercise... need to think about how
embedding would work, though.  It seems a bit silly to keep N copies of a
symbol about that then all need to be explicitly chased up and updated
whenever the library gets updated, especially if we want to do the updates
"live".

>> This might also be a good opportunity to modify the schematic loading
>> logic to support GInputStream from the GIO library.
> 
> I have mixed feelings about GIO (for no good reason), but its probably
> not going away any time soon. Why not.

Changing the new configuration system to use GIO's GFile API actually
solved a couple of issues for me.  Also we're going to want GIO anyway for
GFileMonitor. ;-)

Peter

-- 
Peter Brett <peter@xxxxxxxxxxxxx>
Remote Sensing Research Group
Surrey Space Centre