4 Mar
2003
4 Mar
'03
10:13 a.m.
On Mon, Mar 03, 2003 at 08:36:04PM +0000, Simon Jenkins wrote:
oh i missed that one :)
Remembering that this version of the proposal presumes a pure C interface to
a C++/STL implementation...
ah yes i forgot that..
then the interface is fine with me...
Its worth pointing out here that the full interface is completely
non-interoperable
with the quick interface. You use one or the other. The full interface
is the "real"
interface to the library. The quick interface lets you sort your own
graphs without
getting "sucked in" to the library's model.
ok... you could state this clearer with your defines:
#ifdef GSORT_QUICK
quick_interface()
#else
full_interface()
#endif
The question about pointers vs IDs really applied to the quick interface
only. Those
pointers (or IDs) in the quick interface were the app's own values,
whereas a
gsort_handle is the library's handle on one of its internal classes.
ok now i get get it...
always forgetting STL :)
lets see how it would look with the C++ wrapper for my objects..
You lose! I only have a hazy cloud of ideas concerning this. :)
typedef rettype? (*gsort_callback)( void *Data, (CGraphObject * | Generator *)? );
There's "inplace replace" where a node writes its output over the
top of
its input
buffer to reduce the cache hit, but that's not a property of the node but an
opportunity for optimisation of the sort order so that the app can reuse
buffers.
This aspect of inplace is equivalent to your request that the library
tell you what
your temporary vars are. I avoided the issue in amble by letting the
compiler
work it out for me, but I think the library really is going to have to
do this by
itself. Time to dig out those old compiler volumes and remember how its
done.
i had some thoughts on the traversal but i think i wont be catching
up with you...
at least i think i know how to fix davids sort now.
But it involves detecting all cycles in the not directed
graph... and using this information to find joins and splits of
there is one cycle in the above graph...
traversal to notinplace2 would stop at notinplace1 because
cycle context changed. function would return ptr to notinplace1.
traversal to inplace1 equivalent...
now both calls returned notinplace1 and that is where the search
shall continue....
well the description is somewhat clunky but code would follow....
how do i detect the cycles ?
this is a popular algorithm i guess... any pointers ?
is it possible to do that O(n) ?
i dont get that... please explain more...
Yes. You'd always be editing and navigating the unexpanded, heirarchical
graph.
(Though "expand" would be an available editing operation). It would only be
expanded internally to the library during a sort, this wouldn't overwrite or
flatten the heirarchical representation.
cool very nice thing...
i hope i can fit this into galan somehow...
this asks for another component...
I'm trying to think about the most general model, at least at this
stage. It might
become unmanageably complex and need to be stripped back. OTOH its
possible that a
whole lot of complexity could suddenly disappear behind a simple abstaction.
would be nice...
what is the most general model ?
That sort of thing, yes.
Not so interesting for audio. "Pull" is the right way to do it if
you've got
feedback. By analysing backwards from the outputs you detect the
unavoidable sources of feedback and deal with them one at a time. You
never introduce any avoidable latency at all, or at least you shouldn't.
"Push" works for graphs without cycles and it practically sorts itself.
The trouble is that it encounters any feedback at its destination, rather
than at its source.
Insertion order is a non-sort, executing everything in the order in which
it was entered into the list of nodes. Useless unless the app or its user
already know the exact execution order required, or if they really don't
care.
why should this app use gsort ?
ah... for the graph... ok...
torbenh(a)gmx.de wrote:
i could build a C++ wrapper around my generator class
inheriting from CGraphObject:
it now looks like this:
struct GeneratorClass {
char *name; /* human-readable name - and also
tag for save/load, so MUST be unique */
/* Event inputs */
gint in_count;
char **in_names;
AEvent_handler_t *in_handlers;
/* Event outputs */
gint out_count;
char **out_names;
/* Signal inputs */
gint in_sig_count;
InputSignalDescriptor *in_sigs;
/* Signal outputs */
gint out_sig_count;
OutputSignalDescriptor *out_sigs;
/* Control descriptors */
ControlDescriptor *controls;
int numcontrols;
/* Instance methods */
int (*initialize_instance)(Generator *g);
void (*destroy_instance)(Generator *g);
AGenerator_pickle_t unpickle_instance;
AGenerator_pickle_t pickle_instance;
};
struct Generator {
GeneratorClass *klass;
char *name;
/* Links to other Generators */
GList **in_events; /* array of GLists of EventLinks */
GList **out_events;
GList **in_signals;
GList **out_signals;
/* Sample caching for multiple (realtime) reads */
/* note that we don't cache randomaccess signal generators */
SAMPLETIME last_sampletime;
SAMPLE **last_buffers;
int *last_buflens;
gboolean *last_results;
/* Controls */
GList *controls;
/* per-class data */
void *data;
};
would convert to :
class CGraphGeneratorObject : public CGraphObject {
Generator *g;
public:
cppGenerator( GeneratorClass *klass, string name ) {
g=gen_new_generator( klass, name );
}
cppGenerator( ObjectStoreItem *item ) {
g = gen_unpickle( item );
}
~cppGenerator( ) {
gen_kill_generator( g );
}
EventLink *link( int is_signal, cppGenerator *src, int src_q, cppGenerator *dst, int
dst_q ) {
return gen_link( is_signal, src, src_q, dst, dst_q );
}
// I would rather use this one but galan does not:
EventLink *link( is_signal, Input *i, Output *o );
// hmmm unlink does not match here (any idea?)
ObjectStoreItem *pickle( ObjectStore *db ) {
gen_pickle( g, db );
}
// think i must describe the lists etc by
// inheriting from list<T> or something...
}
On Sun, Mar 02, 2003 at 09:06:02PM +0000, Simon
Jenkins wrote:
You've already spotted the obvious place, later on, where a graph can be
used as a node.
This is where the C++ functionality is actually touched (or, at least,
is prodded at with
handles) by the application. Internal to the library, and so less
relevant to this API, there
might be cause to build a little heirarchy starting with "CGraphObject".
torbenh(a)gmx.de wrote:
me too... but as you stated: you're the graph sort head :)
ok ... now to the API...
Here's my thinking so far, modulo some of your comments
(I'll need to think a bit more about some other of your comments,
eg what you need for galan)
/*============================================================================
File: gsort.h
==============================================================================
Purpose: C interface to gsort library
Project: gsort library
Tabs: 4
Version: proposal.0.0.1
Comments: Very rough draft, doesn't compile.
This version presumes a C++/STL implementation completely
hidden
behind a C API, but that hasn't been decided yet. Alternatives
could be:
an implementation that exposes enough internal data
structures for
apps to manipulate graphs directly rather than solely via
the API.
(Problem with this is that the implementation needs inheritance
which would have to be "hand rolled" in C, were it to be exposed
to the application.)
where do you use inheritance ?
>>==============================================================================
>>Copyright (c) Simon Jenkins 2003 licence to be decided (GPL/LGPL/dual?)
>>============================================================================*/
dont know...
>>
>>and some minimal customisation of the sort...
>> GSORT_QIF_LATE_AS_POSSIBLE
>> GSORT_QIF_EARLY_AS_POSSIBLE
>> (2 flags because default is don't care)
>> GSORT_QIF_FEEDBACK_WELCOME
>> GSORT_QIF_FEEDBACK_UNWELCOME
>> (2 flags because default is don't care)
>> GSORT_QIF_INCLUDE_IF_UNCONNECTED */
ok... nice...
>
>gsort_error
>gsort_Q_AddConnect( void *SNode, uint SOut, void *DNode, uint DOut );
>
Whoops! That should say:
gsort_Q_AddConnect( void *SNode, uint SOut, void *DNode, uint DIn );
gsort_error
gsort_Q_SortGraph( void );
void *
gsort_Q_GetNextNode( void );
/* after calling gsort_Q_SortGraph, call this repeatedly to get the
execution order. Returns 0 when finished. Self resetting so if you need to
be told twice, just start calling it again. */
hmmm... i would like to have this a list or is this not a list internally ?
#endif /*
!GSORT_HIDE_QUICK_INTERFACE */
/*===============
FULL INTERFACE:
=================
The full interface is for apps with heavyweight graph sorting
requirements ie
they need some or all of the following functionality:
~ multiple, persistent, modifiable graphs
~ nodes with changing numbers of inputs and outputs
~ graphs-within-graphs
~ customiseable sorting
~ more information about the execution order, eg about feedback loops
~ serialisation of graphs
yes...
It is
possible, but not obligatory, for an app to use gsort to hold the
sole
representation of its graph(s) when using the full interface.
this is nice...
graphs-within-graph functionality is accessed
simply by passing a graph
handle into a function that expects a node handle. These never turn up in
the execution list, but the stuff inside them does (works recursively with
sub-sub-graphs etc as well) */
nice idea... i begin to understand why you want ids...
but a void * is a unique id also ... needs a smarter hash function than an
ID
but no more i think.
Whether or not to use void* as the type for gsort_handle is an
implementation
issue. Whatever the underlying type, its just a "gsort_handle" so far as
the app is
concerned. Its got to be something that can be passed and returned by
value in a
C function call, and it might be nice if 0 could represent a failed
allocation.
ok...
#ifndef
GSORT_HIDE_FULL_INTERFACE
typedef void * gsort_handle;
gsort_error
gsort_Initialise( int InitGraphHandles );
gsort_error
gsort_Cleanup( void );
gsort_handle
gsort_NewGraph( ushort Flags, void *Data, gsort_callback Callback );
/* The callback functions have nothing to do with runtime execution of the
graph. They're for the application to receive - and possibly provide -
information during the sort process. Pass in 0 if you're not bothered.
The Data pointer is for the sole use and convenience of the application.
*/
signature of gsort ?
i bet you know already...
/* question: is a type InputOutput (to express the fact that a node is
going to be doing in-place processing) required? Need to think about
whether/when this might affect sorting decisions */
could be a hint on the Node... (CAN_DO_INPLACE)
thoughts about sort order impact:
notinplace2
/ \
-- notinplace1 < > inplace2
\ /
inplace1
would be optimal if sorted_list = [notinplace1, notinplace2, inplace1,
inplace2]
as inplace1 would destroy output buffer of notinplace1
And then there's "inplace add" where a node mixes its output into a
buffer. This *is* a node property.
You could be telling the library: "generate an implied mixer for me wherever
several outputs meet at the same input. Then optimise it away again wherever
you can use a run_adding node".
Or you could even be telling it: "I want to join connections together in
thin
air, not just at my inputs. These connections are implied mixer nodes but
again, I want them optimised away wherever run_adding is available".
But before tying the library too closely to these particular optimisation
techniques its worth pausing to remember that
node2
/ \
-- node1 < > node4 --
\ /
node3
is also an opportunity to execute node2 and node3 simultaneously :)
oh right to express this the return value should be a tree...
hmm ... (not ?)
which semantics would this have ?
if there was inplace3 parallel to inplace1 we
would have to decide
which one should do the inplace processing...
hmmm... what is better ?
- copy output buffer and do inplace processing for both...
- do inplace only once
this example suggests run_adding()
but if the parallells would be >1 plugin chains run_adding() would be only
used on
the end of the parallel structure...
I think connections should be first class objects:
Editing ~
Suppose you're feeding a load of inputs from a single
output, but you want to unplug from the output and
plug it in elsewhere. Without careful handling, your
relations will disappear in a puff of smoke the moment
you pull the plug! Thats what happened on early
Nord Modular software. They had to fix it.
gsort_error
gsort_Connect( gsort_handle Input, gsort_handle Output );
/* wrong? Connections should be first class objects, not relations? */
why ?
do we have metadata on a connection ?
i believe metadata on a connection can be avoided...
but i am not sure...
Heirarchical Graphs ~
Whenever a connection goes into or out of a sub-graph
you've got 2 connections in the representation which must
become a single connection in the flattened graph. There
can be long chains of these if the "real" nodes are at the
bottom of a deep heirarchy. Again, careful handling
required if the connections are just relations
right is see this...
Connection Properties ~ Expressing things such as
(The library knows that...) Connection A is a feedback path
(The application knows that...) Connection B is yellow
(The sort algorithm for a non-audio application knows that...)
Connection C is part of a clock-tree that is explicitly controlling
the execution order of some of the nodes.
now this is of course a point...
what do you mean with a clock tree ?
gsort_error
gsort_Disconnect( gsort_handle Input, gsort_handle Output );
/* wrong? Connections should be first class objects, not relations? */
/* plus more functions to...
~ customise the sort
~ trigger the sort
~ find out (about) the execution order
~ navigate around the graph (if you're using gsort to hold your sole
representation of the graph you may need these to find out what it says!)
this should be able to return a tree
of unexpanded graphs.
serialise
the graph */
ok... here is the polymorphy beginning...
application needs to use struct Node from gsort.h
this could be also done with
gsort_nodes_foreach( gsort_handle graph, gsort_callback cb, boolean
enter_subgraphs, void *data )
/* ALSO
THINKING HARD ABOUT...
~ non-audio-rate connections eg control signals
David stated that (at least in the XAP model) there would be no difference
for the sort algorithm...
it seems correct to me.
~ higher
level graph editing functions
like automatic connecting ins and outs with same names ?
copy/paste ?
select chain ?
select parallel block ?
~ non-pull
sort semantics eg push/dataflow, insertion order, clocked,
others?
please describe more... sounds interesting...
Clocked is where some connections in and out of nodes are clocks that
control when the node should be executed. There are graphical programming
languages that do this. You can't fully sort it because the execution
order is at least partially determined at runtime.
galan needs this...
i have event handling code in the plugins
these can be triggered by clocks...
if the library would find out these codepaths it would be ideal...
hmm... how should that be returned ?
--
torben Hohn
http://galan.sourceforge.net -- The graphical Audio language