index

fork-machine

(this describes the implementation of my fork extension for XFree86)

the program is a simulation of a 'machine'. The machine can be thought of as a Mealy (deterministic) finite state automaton.

The state of the automaton is a composition (i.e. product) of a 'state' (of the machine), a (top-bound limited) queue of undecided events and (upper bound limited) time. It's the time since the first event on the queue. This is the event we want to decide if it is meant to be forked (as a modifier), or not.

The machine accepts (one at a time) events, possibly changes the state, enqueues the event, and virtually increases the time, and sometimes outputs an event decided to be either unchanged or forked. The event is always the first in the queue.

states' description

normal
only a forkable key Press can get us out of this state, into Suspect. Otherwise copy input to output immediately. So, here we distinguish these cases:
suspect
i.e. a forkable key is pressed, and we have to decide. Here we wait either for a time overall-limit, or another key press. Key releases (of keys pressed before the suspected/forkable one) are 'passed' immediately.
verify
another key was pressed. Now just verify if it wasn't just an error. So we wait for either: overall-limit, overlap limit, or the release of the suspected key. All event are enqueued.
activated/deactivated
we decide for the fork (or not). This state is a signal to the external code, to take the queue, and replay the events once again to a reset machine.

When we output a Release, we have to output that of the forked ...

i implemented it in C++, so i could finally start to understand that langauge. I like its stricter type checking wrt C (compilers).

Here some bookmarks on implementing FSA in C++:

Updated: 2005-12-22 Home / Index Agenzia matrimoniale Maruska google rev