1 | // Parallel abstract graph traverser. Contributed by Bjarne Knudsen. |
---|
2 | |
---|
3 | #ifndef __traverser_h__ |
---|
4 | #define __traverser_h__ |
---|
5 | |
---|
6 | /* |
---|
7 | This file defines a Traverser interface. A Traverser can be used for |
---|
8 | going through an underlying structure of states. At each state, |
---|
9 | there is a number of next states. Moving the traverser to a next |
---|
10 | state changes its internal state. |
---|
11 | |
---|
12 | When constructing a Traverser, it should be in the start state |
---|
13 | (i.e. it should have no previous states). The traversal is over when |
---|
14 | there are no more next states. |
---|
15 | |
---|
16 | The state space should be a directed acyclic graph, so several |
---|
17 | previous states to a given state are allowed. There may be any |
---|
18 | number of end points, but only one start point. |
---|
19 | |
---|
20 | When traversing in a multi threaded fashion, each Traverser receives |
---|
21 | some of the collected information. It is up to the user of this |
---|
22 | interface to join that information when the traversal is done. |
---|
23 | */ |
---|
24 | namespace gfan{ |
---|
25 | |
---|
26 | class Traverser |
---|
27 | { |
---|
28 | public: |
---|
29 | bool aborting; // Added by Anders |
---|
30 | void abort(){aborting=true;} // Added by Anders |
---|
31 | Traverser():aborting(false){} // Added by Anders |
---|
32 | // Virtual destructor |
---|
33 | virtual ~Traverser( void ) {}; |
---|
34 | |
---|
35 | // Get the number of next states. |
---|
36 | virtual int getEdgeCountNext( void ) = 0; |
---|
37 | |
---|
38 | // The return value is the index for moving to the same previous |
---|
39 | // state again. The indexing of the previous state can be arbitrary, |
---|
40 | // but zero should be one of the previous index values. The |
---|
41 | // collect_info parameter will be true once for every edge in the |
---|
42 | // state graph during the traversal. This allows te traverser to |
---|
43 | // collect information along its edges. |
---|
44 | virtual int moveToNext( int index, |
---|
45 | bool collect_info ) = 0; |
---|
46 | |
---|
47 | // Go back to a previous state. Due to the return value of |
---|
48 | // moveToNext(), the state will be unchanged after calling |
---|
49 | // movetoPrev(moveToNext(index)) with a legal next index. |
---|
50 | virtual void moveToPrev( int index ) = 0; |
---|
51 | |
---|
52 | // This function will be called once for every state in a traversal. |
---|
53 | virtual void collectInfo( void ) = 0; |
---|
54 | |
---|
55 | // Function for printing the state to cout for debug purposes. |
---|
56 | virtual void printState( void ) = 0; |
---|
57 | }; |
---|
58 | |
---|
59 | // Traverse a structure in a single threaded way. The traverser should |
---|
60 | // be in the start state. The traverser may not be in the start state |
---|
61 | // when this function returns. |
---|
62 | void traverse_simple( Traverser* traverser ); |
---|
63 | |
---|
64 | // Traverse a structure using several traversers in several |
---|
65 | // threads. The traversers should all be in the start state. Several |
---|
66 | // traversers may go through the same state, but collectInfo() is only |
---|
67 | // called once for each state. The traversers may not be in the start |
---|
68 | // state when this function returns. |
---|
69 | void traverse_threaded( Traverser** traverser, |
---|
70 | int count, |
---|
71 | int step_count ); |
---|
72 | |
---|
73 | } |
---|
74 | #endif // __traverser_h__ |
---|