Code logic for sample code.
(P.S. 2011 Aug) It has been several years now since I wrote this code and I find it very difficult to read.
It still runs correctly however.
I suspect that an assembler version of the code would be clearer for many purposes.
A general pattern here is a maze of C routines that call each other but mostly never return.
Each call represents a character moving in its stream from one process node to the next.
This causes the stack to grow and not shrink.
Occasionally a long jump resets the stack, where nothing of value has been kept, to an earlier stack state.
It would be strategic to get the compiler to do tail call optimization but I don’t know how to do so reliaby.
The pattern is much like goto with arguments, and a bit like Actors.
The code is in C but C++ would be better in a few ways.
The node would be replaced by a class instance.
Two types of node are defined: unode and dnode.
dnodes define the next step down stream; a pointer to a dnode
is a place to deliver a character of a stream to its next processing stage.
If d locates a dnode then (d->nsn)(c, d, p); is a non returning invocation that dispatches the character c into the stream denoted by d.
p locates a unode (see below) to invoke when subsequent characters of the stream are needed and can be accomodated.
If p locates a unode then (p->code)(p); causes the next character for that unode to be produced.
unodes implement the pulls referred to in the introduction.
Reentrance & Thread Safety
As long as there are not two threads in the same stream, all is well.
If two nodes point to the same dnode there is a race condition and also an opportunity for two threads to get into the same stream.
The pattern is safe, however, in the interleave test case in main.c, for there is just one thread between the two inputs.
For each body of code that implements some stream function, there is a routine that creates a node of that sort.
Indeed the name of the stream function code is internal to the file and only the creation routine is global.
The name of that routine begins with the letter c in this code.
It typically requires pointers to previously created down stream nodes and any other arguments relevant to the function.
It returns a dnode value for the new node.
The constructors are called in main of the demos.
Sample stream processes
The common structure dnode is found in each of the down stream node structures.
It locates the code for the transformation and also locates the next processing node for the stream.
For each particular processing function a structure is defined whose first field is a dnode
and whose other fields carry any necessary node state as described in the introduction.
To Upper Case
x2uc merely changes lower case letters to upper case and does not otherwise change the stream.
cx2uc takes a dnode pointer and returns another pointer with this transformation prepended.
Tee produces two identical streams in place of one.
A new structure dupS is defined which has an embedded dnode called n, but also includes a variable character cell, s, to store the character to be duplicated, a variable cell, sav, in which to remember the continuation of the input stream, and the constant address of a unode mate, allocated to this stream process, which serves as a point to request the second copy of the character for the second stream.
The dnode located by the mate field is constant and points to dup2
and the dnode for this stream process.
ctee takes two downstream locators (character sinks) and returns a new sink.
Characters sent to the new sink are serially supplied to both of the old sinks.
This code supplies a steady stream of the same character.
crptr takes a dnode (to which to deliver its stream, and returns a unode which may be invoked to turn the stream on.
This takes characters alternately from two inputs and forwards them.
It applies flow control (back pressure) so as not to let one input stream get more than one character ahead of the other.
There are two ideas that might improve this code:
- Don’t pass the continuation in the mainline routines.
Instead keep it in thread local storage.
On some ISAs this might be the difference between tail call optimization or not.
It might also be faster.
- Make subroutines of calling next downstream node or pull.
This would be for clearer code and not performance.
If it doesn’t improve clarity it should not be done.