]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /* Copyright 2004. Vladimir Prus |
2 | * Distributed under the Boost Software License, Version 1.0. | |
3 | * (See accompanying file LICENSE_1_0.txt or copy at | |
4 | * http://www.boost.org/LICENSE_1_0.txt) | |
5 | */ | |
6 | ||
7 | #include "../lists.h" | |
8 | #include "../mem.h" | |
9 | #include "../native.h" | |
10 | #include "../object.h" | |
f67539c2 | 11 | #include "../jam_strings.h" |
7c673cae FG |
12 | #include "../variable.h" |
13 | ||
14 | ||
15 | /* Use quite klugy approach: when we add order dependency from 'a' to 'b', just | |
16 | * append 'b' to of value of variable 'a'. | |
17 | */ | |
18 | LIST * add_pair( FRAME * frame, int flags ) | |
19 | { | |
20 | LIST * arg = lol_get( frame->args, 0 ); | |
21 | LISTITER iter = list_begin( arg ); | |
22 | LISTITER const end = list_end( arg ); | |
23 | var_set( frame->module, list_item( iter ), list_copy_range( arg, list_next( | |
24 | iter ), end ), VAR_APPEND ); | |
25 | return L0; | |
26 | } | |
27 | ||
28 | ||
29 | /* Given a list and a value, returns position of that value in the list, or -1 | |
30 | * if not found. | |
31 | */ | |
32 | int list_index( LIST * list, OBJECT * value ) | |
33 | { | |
34 | int result = 0; | |
35 | LISTITER iter = list_begin( list ); | |
36 | LISTITER const end = list_end( list ); | |
37 | for ( ; iter != end; iter = list_next( iter ), ++result ) | |
38 | if ( object_equal( list_item( iter ), value ) ) | |
39 | return result; | |
40 | return -1; | |
41 | } | |
42 | ||
43 | enum colors { white, gray, black }; | |
44 | ||
45 | ||
46 | /* Main routine for topological sort. Calls itself recursively on all adjacent | |
47 | * vertices which were not yet visited. After that, 'current_vertex' is added to | |
48 | * '*result_ptr'. | |
49 | */ | |
50 | void do_ts( int * * graph, int current_vertex, int * colors, int * * result_ptr | |
51 | ) | |
52 | { | |
53 | int i; | |
54 | ||
55 | colors[ current_vertex ] = gray; | |
56 | for ( i = 0; graph[ current_vertex ][ i ] != -1; ++i ) | |
57 | { | |
58 | int adjacent_vertex = graph[ current_vertex ][ i ]; | |
59 | if ( colors[ adjacent_vertex ] == white ) | |
60 | do_ts( graph, adjacent_vertex, colors, result_ptr ); | |
61 | /* The vertex is either black, in which case we do not have to do | |
62 | * anything, or gray, in which case we have a loop. If we have a loop, | |
63 | * it is not clear what useful diagnostic we can emit, so we emit | |
64 | * nothing. | |
65 | */ | |
66 | } | |
67 | colors[ current_vertex ] = black; | |
68 | **result_ptr = current_vertex; | |
69 | ( *result_ptr )++; | |
70 | } | |
71 | ||
72 | ||
73 | void topological_sort( int * * graph, int num_vertices, int * result ) | |
74 | { | |
75 | int i; | |
76 | int * colors = ( int * )BJAM_CALLOC( num_vertices, sizeof( int ) ); | |
77 | for ( i = 0; i < num_vertices; ++i ) | |
78 | colors[ i ] = white; | |
79 | ||
80 | for ( i = num_vertices - 1; i >= 0; --i ) | |
81 | if ( colors[ i ] == white ) | |
82 | do_ts( graph, i, colors, &result ); | |
83 | ||
84 | BJAM_FREE( colors ); | |
85 | } | |
86 | ||
87 | ||
88 | LIST * order( FRAME * frame, int flags ) | |
89 | { | |
90 | LIST * arg = lol_get( frame->args, 0 ); | |
91 | LIST * result = L0; | |
92 | int src; | |
93 | LISTITER iter = list_begin( arg ); | |
94 | LISTITER const end = list_end( arg ); | |
95 | ||
96 | /* We need to create a graph of order dependencies between the passed | |
97 | * objects. We assume there are no duplicates passed to 'add_pair'. | |
98 | */ | |
99 | int length = list_length( arg ); | |
100 | int * * graph = ( int * * )BJAM_CALLOC( length, sizeof( int * ) ); | |
101 | int * order = ( int * )BJAM_MALLOC( ( length + 1 ) * sizeof( int ) ); | |
102 | ||
103 | for ( src = 0; iter != end; iter = list_next( iter ), ++src ) | |
104 | { | |
105 | /* For all objects this one depends upon, add elements to 'graph'. */ | |
106 | LIST * dependencies = var_get( frame->module, list_item( iter ) ); | |
107 | int index = 0; | |
108 | LISTITER dep_iter = list_begin( dependencies ); | |
109 | LISTITER const dep_end = list_end( dependencies ); | |
110 | ||
111 | graph[ src ] = ( int * )BJAM_CALLOC( list_length( dependencies ) + 1, | |
112 | sizeof( int ) ); | |
113 | for ( ; dep_iter != dep_end; dep_iter = list_next( dep_iter ) ) | |
114 | { | |
115 | int const dst = list_index( arg, list_item( dep_iter ) ); | |
116 | if ( dst != -1 ) | |
117 | graph[ src ][ index++ ] = dst; | |
118 | } | |
119 | graph[ src ][ index ] = -1; | |
120 | } | |
121 | ||
122 | topological_sort( graph, length, order ); | |
123 | ||
124 | { | |
125 | int index = length - 1; | |
126 | for ( ; index >= 0; --index ) | |
127 | { | |
128 | int i; | |
129 | LISTITER iter = list_begin( arg ); | |
7c673cae FG |
130 | for ( i = 0; i < order[ index ]; ++i, iter = list_next( iter ) ); |
131 | result = list_push_back( result, object_copy( list_item( iter ) ) ); | |
132 | } | |
133 | } | |
134 | ||
135 | /* Clean up */ | |
136 | { | |
137 | int i; | |
138 | for ( i = 0; i < length; ++i ) | |
139 | BJAM_FREE( graph[ i ] ); | |
140 | BJAM_FREE( graph ); | |
141 | BJAM_FREE( order ); | |
142 | } | |
143 | ||
144 | return result; | |
145 | } | |
146 | ||
147 | ||
148 | void init_order() | |
149 | { | |
150 | { | |
151 | char const * args[] = { "first", "second", 0 }; | |
152 | declare_native_rule( "class@order", "add-pair", args, add_pair, 1 ); | |
153 | } | |
154 | ||
155 | { | |
156 | char const * args[] = { "objects", "*", 0 }; | |
157 | declare_native_rule( "class@order", "order", args, order, 1 ); | |
158 | } | |
159 | } |