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.
[EMAIL PROTECTED] wrote:
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)
me too... but as you stated: you're the graph sort head :)
/*============================================================================ 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 ?
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".
============================================================================== Copyright (c) Simon Jenkins 2003 licence to be decided (GPL/LGPL/dual?) ============================================================================*/ #ifndef GSORT_H_INCLUDED #define GSORT_H_INCLUDED
#ifndef ushort #define ushort unsigned short #endif
#ifndef uint #define uint unsigned int #endif
#ifdef __cplusplus extern "C" { #endif
typedef int gsort_error;
/*================
QUICK INTERFACE:
================== The quick interface is for apps with lightweight sorting requirements. They've
got a flat graph stored elsewhere in whatever format they use. They want to
describe the graph to the gsort library and be told what order the nodes
should be executed in. They don't need to customise the sort algorithm too
much. They don't need gsort's representation of the graph to persist or be
modifiable or re-sortable: When they modify and resort they'll just re-init
the library, describe the new graph and be told the new execution order */
#ifndef GSORT_HIDE_QUICK_INTERFACE
gsort_error gsort_Q_Initialise( void );
gsort_error gsort_Q_Cleanup( void );
gsort_error
gsort_Q_AddNode( void *Node, uint NumInputs, uint NumOutputs, ushort Flags );
/* is void* Node ok? would int NodeID be better? */
/* the flags privide required information... GSORT_QIF_NODE_IS_ROOT
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 */
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 ?
Remembering that this version of the proposal presumes a pure C interface to a C++/STL implementation...
...The list would be something like an std::list<gsort::CGraphNode> internally,
which is why you can't have it :). But the pointers that gsort_Q_GetNextNode
is returning are your *own* pointers to your *own* data structures. If you
need a list, you can walk once down gsort_Q_GetNextNode linking your own
structures into your own list in whatever way suits you best.
Its worth pointing out here that the full interface is completely non-interoperable#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...
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.
The question about pointers vs IDs really applied to the quick interface only. ThoseIt 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.
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.
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.
You lose! I only have a hazy cloud of ideas concerning this. :)#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...
There's "inplace replace" where a node writes its output over the top of its inputgsort_handle gsort_NewGraph( ushort Flags, void *Data, gsort_callback Callback );
gsort_error gsort_DeleteGraph( gsort_handle Graph );
gsort_handle gsort_NewNode( ushort Flags, void *Data, gsort_callback Callback );
gsort_error gsort_AddNode( gsort_handle Node, gsort_handle Graph );
gsort_error gsort_RemoveNode( gsort_handle Node, gsort_handle Graph );
gsort_error gsort_DeleteNode( gsort_handle Node );
gsort_handle gsort_NewInput( ushort Flags, void *Data, gsort_callback Callback );
gsort_error gsort_AddInput( gsort_handle Input, gsort_handle Node );
gsort_error gsort_RemoveInput( gsort_handle Input, gsort_handle Node );
gsort_error gsort_DeleteInput( gsort_handle Input );
gsort_handle gsort_NewOutput( ushort Flags, void *Data, gsort_callback Callback );
gsort_error gsort_AddOutput( gsort_handle Output, gsort_handle Node );
gsort_error gsort_RemoveOutput( gsort_handle Output, gsort_handle Node );
gsort_error gsort_DeleteOutput( gsort_handle Output );
/* 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
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.
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 --
\ /
node3is also an opportunity to execute node2 and node3 simultaneously :)
I think connections should be first class objects: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...
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...
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.
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
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.
Yes. You'd always be editing and navigating the unexpanded, heirarchical graph.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.
(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.
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 )
I'm trying to think about the most general model, at least at this stage. It might/* 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.
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.
That sort of thing, yes.~ 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...
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.
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.
There aren't any requirements exactly, just the following thoughts:~ non-audio applications
what are the non-audio requirements ?
Other classes of app need to do this kind of stuff: Potential "clients" Other classes of app already do this kind of stuff: Potential solutions
#endif /* !GSORT_HIDE_FULL_INTERFACE */
#ifdef __cplusplus } #endif
#endif /* GSORT_H_INCLUDED */
Simon Jenkins (Bristol, UK)
