On Sun, Mar 02, 2003 at 09:06:02PM +0000, Simon Jenkins wrote:
torbenh(a)gmx.de 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 ?
==============================================================================
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 );
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.
#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...
gsort_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
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...
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...
~ non-audio applications
what are the non-audio requirements ?
#endif /* !GSORT_HIDE_FULL_INTERFACE */
#ifdef __cplusplus
}
#endif
#endif /* GSORT_H_INCLUDED */
--
torben Hohn
http://galan.sourceforge.net -- The graphical Audio language