summaryrefslogtreecommitdiff
path: root/jam-files/engine/modules/order.c
diff options
context:
space:
mode:
authorKenneth Heafield <github@kheafield.com>2012-05-12 14:01:52 -0400
committerKenneth Heafield <github@kheafield.com>2012-05-12 14:01:52 -0400
commit3faecf9a00512dcbc8712c4bca9adae72fb64410 (patch)
tree9761b50d12f81a675fb7cbc663ceebad15079f78 /jam-files/engine/modules/order.c
parentc806a8fff63043f63773874986301f2822a2b552 (diff)
Give in and copy bjam into cdec source code
Diffstat (limited to 'jam-files/engine/modules/order.c')
-rw-r--r--jam-files/engine/modules/order.c144
1 files changed, 144 insertions, 0 deletions
diff --git a/jam-files/engine/modules/order.c b/jam-files/engine/modules/order.c
new file mode 100644
index 00000000..d77943a7
--- /dev/null
+++ b/jam-files/engine/modules/order.c
@@ -0,0 +1,144 @@
+/* Copyright Vladimir Prus 2004. 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 "../native.h"
+#include "../lists.h"
+#include "../strings.h"
+#include "../newstr.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( PARSE *parse, FRAME *frame )
+{
+ LIST* arg = lol_get( frame->args, 0 );
+
+ var_set(arg->string, list_copy(0, arg->next), 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, const char* value)
+{
+ int result = 0;
+ for(; list; list = list->next, ++result) {
+ if (strcmp(list->string, value) == 0)
+ return result;
+ }
+ return -1;
+}
+
+enum colors { white, gray, black };
+
+/* Main routite of 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 don't have to do
+ anything, a gray, in which case we have a loop. If we have a loop,
+ it's 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 = 0; i < num_vertices; ++i)
+ if (colors[i] == white)
+ do_ts(graph, i, colors, &result);
+
+ BJAM_FREE(colors);
+}
+
+LIST *order( PARSE *parse, FRAME *frame )
+{
+ LIST* arg = lol_get( frame->args, 0 );
+ LIST* tmp;
+ LIST* result = 0;
+ int src;
+
+ /* We need to create a graph of order dependencies between
+ the passed objects. We assume that 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(tmp = arg, src = 0; tmp; tmp = tmp->next, ++src) {
+ /* For all object this one depend upon, add elements
+ to 'graph' */
+ LIST* dependencies = var_get(tmp->string);
+ int index = 0;
+
+ graph[src] = (int*)BJAM_CALLOC(list_length(dependencies)+1, sizeof(int));
+ for(; dependencies; dependencies = dependencies->next) {
+ int dst = list_index(arg, dependencies->string);
+ 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;
+ tmp = arg;
+ for (i = 0; i < order[index]; ++i, tmp = tmp->next);
+ result = list_new(result, tmp->string);
+ }
+ }
+
+ /* 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* args[] = { "first", "second", 0 };
+ declare_native_rule("class@order", "add-pair", args, add_pair, 1);
+ }
+
+ {
+ char* args[] = { "objects", "*", 0 };
+ declare_native_rule("class@order", "order", args, order, 1);
+ }
+
+
+}