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