]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/tools/build/src/engine/modules/order.cpp
38209b889db412fcd2459b4168adb93c08a8898f
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)
10 #include "../object.h"
11 #include "../jam_strings.h"
12 #include "../variable.h"
15 /* Use quite klugy approach: when we add order dependency from 'a' to 'b', just
16 * append 'b' to of value of variable 'a'.
18 LIST
* add_pair( FRAME
* frame
, int flags
)
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
);
29 /* Given a list and a value, returns position of that value in the list, or -1
32 int list_index( LIST
* list
, OBJECT
* value
)
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
) )
43 enum colors
{ white
, gray
, black
};
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
50 void do_ts( int * * graph
, int current_vertex
, int * colors
, int * * result_ptr
55 colors
[ current_vertex
] = gray
;
56 for ( i
= 0; graph
[ current_vertex
][ i
] != -1; ++i
)
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
67 colors
[ current_vertex
] = black
;
68 **result_ptr
= current_vertex
;
73 void topological_sort( int * * graph
, int num_vertices
, int * result
)
76 int * colors
= ( int * )BJAM_CALLOC( num_vertices
, sizeof( int ) );
77 for ( i
= 0; i
< num_vertices
; ++i
)
80 for ( i
= num_vertices
- 1; i
>= 0; --i
)
81 if ( colors
[ i
] == white
)
82 do_ts( graph
, i
, colors
, &result
);
88 LIST
* order( FRAME
* frame
, int flags
)
90 LIST
* arg
= lol_get( frame
->args
, 0 );
93 LISTITER iter
= list_begin( arg
);
94 LISTITER
const end
= list_end( arg
);
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'.
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 ) );
103 for ( src
= 0; iter
!= end
; iter
= list_next( iter
), ++src
)
105 /* For all objects this one depends upon, add elements to 'graph'. */
106 LIST
* dependencies
= var_get( frame
->module
, list_item( iter
) );
108 LISTITER dep_iter
= list_begin( dependencies
);
109 LISTITER
const dep_end
= list_end( dependencies
);
111 graph
[ src
] = ( int * )BJAM_CALLOC( list_length( dependencies
) + 1,
113 for ( ; dep_iter
!= dep_end
; dep_iter
= list_next( dep_iter
) )
115 int const dst
= list_index( arg
, list_item( dep_iter
) );
117 graph
[ src
][ index
++ ] = dst
;
119 graph
[ src
][ index
] = -1;
122 topological_sort( graph
, length
, order
);
125 int index
= length
- 1;
126 for ( ; index
>= 0; --index
)
129 LISTITER iter
= list_begin( arg
);
130 for ( i
= 0; i
< order
[ index
]; ++i
, iter
= list_next( iter
) );
131 result
= list_push_back( result
, object_copy( list_item( iter
) ) );
138 for ( i
= 0; i
< length
; ++i
)
139 BJAM_FREE( graph
[ i
] );
151 char const * args
[] = { "first", "second", 0 };
152 declare_native_rule( "class@order", "add-pair", args
, add_pair
, 1 );
156 char const * args
[] = { "objects", "*", 0 };
157 declare_native_rule( "class@order", "order", args
, order
, 1 );