Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge__export.h =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge__export.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge__export.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,12 @@ +#pragma once + +#include "edge__tshell.h" + +#include "node__tshell.h" + +struct graph$edge$$Edge { + struct graph$node$$Node$$shell *nodes[2]; + struct graph$edge$$Other$$shell o; +}; + +struct graph$edge$$Edge$$shell graph$edge$$create_edge(struct graph$node$$Node$$shell *first, struct graph$node$$Node$$shell *second); Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge__impl.c =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge__impl.c (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge__impl.c (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,12 @@ +#include "edge__export.h" + +#include "node__export.h" + +struct graph$edge$$Other {}; + +struct graph$edge$$Edge$$shell graph$edge$$create_edge(struct graph$node$$Node$$shell *first, struct graph$node$$Node$$shell *second) { + struct graph$edge$$Edge$$shell e; + (*(struct graph$edge$$Edge*)&e).nodes[0] = first; + (*(struct graph$edge$$Edge*)&e).nodes[1] = second; + return e; +} Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge__tshell.h =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge__tshell.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge__tshell.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,9 @@ +#pragma once + +// [[size 16, align 8]] +struct graph$edge$$Edge$$shell { + double contents[2]; // just to fill space, not used +}; + +// [[size 0, align 1]] +struct graph$edge$$Other$$shell {}; Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge_picker__export.h =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge_picker__export.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge_picker__export.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,10 @@ +#pragma once + +#include "edge_picker__tshell.h" + +#include "edge__tshell.h" +#include "node__tshell.h" + +struct graph$edge_picker$$Controller$$shell graph$edge_picker$$get_controller(); + +struct graph$node$$Node$$shell *graph$edge_picker$$pick_next(struct graph$edge_picker$$Controller$$shell *c, struct graph$node$$Node$$shell *n); Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge_picker__impl.c =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge_picker__impl.c (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge_picker__impl.c (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,18 @@ +#include "edge_picker__export.h" + +#include "edge__export.h" +#include "node__export.h" + +#include + +struct graph$edge_picker$$Controller {}; + +struct graph$edge_picker$$Controller$$shell graph$edge_picker$$get_controller() { + return (*(struct graph$edge_picker$$Controller$$shell*)&(struct graph$edge_picker$$Controller){}); +} + +struct graph$node$$Node$$shell *graph$edge_picker$$pick_next(struct graph$edge_picker$$Controller$$shell *c, struct graph$node$$Node$$shell *n) { + if (((struct graph$node$$Node*)n)->num_edges == 0) return NULL; + struct graph$edge$$Edge$$shell *e = ((struct graph$node$$Node*)n)->edges[rand() % ((struct graph$node$$Node*)n)->num_edges]; + return ((struct graph$node$$Node*)((struct graph$edge$$Edge*)e)->nodes[0]) == ((struct graph$node$$Node*)n) ? ((struct graph$edge$$Edge*)e)->nodes[1] : ((struct graph$edge$$Edge*)e)->nodes[0]; +} Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge_picker__tshell.h =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge_picker__tshell.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/edge_picker__tshell.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,4 @@ +#pragma once + +// [[size 0, align 1]] +struct graph$edge_picker$$Controller$$shell {}; Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/node__export.h =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/node__export.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/node__export.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,17 @@ +#pragma once + +#include "node__tshell.h" + +#include "edge__tshell.h" +#include "edge_picker__tshell.h" + +// Note: constant max_edges_per_node expanded here +struct graph$node$$Node { + int num_edges; + struct graph$edge$$Edge$$shell *edges[100]; + struct graph$node$$Other$$shell o; +}; + +int graph$node$$add_edge(struct graph$node$$Node$$shell *n, struct graph$edge$$Edge$$shell *e); + +int graph$node$$random_search(struct graph$node$$Node$$shell *start, struct graph$node$$Node$$shell *end, int steps_left); Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/node__impl.c =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/node__impl.c (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/node__impl.c (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,37 @@ +#include "node__export.h" + +#include "edge__export.h" +#include "edge_picker__export.h" + +#include + +// move constants to top +const int graph$node$$max_edges_per_node = 100; +const int graph$node$$continue_rate = 2; + +// also move function declarations (of those not already in `node__export.h`) to top +int graph$node$$random_search$$mangle(struct graph$node$$Node$$shell *start, struct graph$node$$Node$$shell *end, int *steps_left); + +int graph$node$$add_edge(struct graph$node$$Node$$shell *n, struct graph$edge$$Edge$$shell *e) { + if (((struct graph$node$$Node*)n)->num_edges >= graph$node$$max_edges_per_node) exit(2); + ((struct graph$node$$Node*)n)->edges[((struct graph$node$$Node*)n)->num_edges++] = e; + return 1; +} + +int graph$node$$random_search(struct graph$node$$Node$$shell *start, struct graph$node$$Node$$shell *end, int steps_left) { + while (steps_left > 0) { + int result = graph$node$$random_search$$mangle(start, end, &steps_left); + if (result != 0) return result; + } + return 0; +} + +int graph$node$$random_search$$mangle(struct graph$node$$Node$$shell *start, struct graph$node$$Node$$shell *end, int *steps_left) { + if (start == end) return 1; + (*steps_left)--; + if (rand() % graph$node$$continue_rate == 0) return 0; + struct graph$edge_picker$$Controller$$shell c = graph$edge_picker$$get_controller(); + struct graph$node$$Node$$shell *n = graph$edge_picker$$pick_next(&c, start); + if (n == NULL) return 0; + return graph$node$$random_search$$mangle(n, end, steps_left); +} Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/node__tshell.h =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/node__tshell.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/graph/node__tshell.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,9 @@ +#pragma once + +// [[size 808, align 8]] +struct graph$node$$Node$$shell { + double contents[101]; // just to fill space, not used +}; + +// [[size 0, align 1]] +struct graph$node$$Other$$shell {}; Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/graph__export.h =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/graph__export.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/graph__export.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,21 @@ +#pragma once + +#include "graph__tshell.h" + +#include "graph/node__tshell.h" +#include "graph/edge__tshell.h" + +struct graph$$Graph { + struct graph$node$$Node$$shell *nodes; + struct graph$edge$$Edge$$shell *edges; + int num_nodes; + int num_edges; +}; + +struct graph$$Graph$$shell graph$$create_rand_graph(int num_nodes, int num_edges); + +struct graph$node$$Node$$shell *graph$$grab_random_node(struct graph$$Graph$$shell *g); + +int graph$$path_found(struct graph$node$$Node$$shell *first, struct graph$node$$Node$$shell *second); + +int graph$$destroy_graph(struct graph$$Graph$$shell *g); Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/graph__impl.c =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/graph__impl.c (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/graph__impl.c (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,38 @@ +#include "graph__export.h" + +#include "graph/node__export.h" +#include "graph/edge__export.h" + +#include + +// move constants to top +const int graph$$max_steps_to_walk = 1000; + +struct graph$$Graph$$shell graph$$create_rand_graph(int num_nodes, int num_edges) { + struct graph$$Graph$$shell g; + (*(struct graph$$Graph*)&g).num_nodes = num_nodes; + (*(struct graph$$Graph*)&g).num_edges = num_edges; + (*(struct graph$$Graph*)&g).nodes = (struct graph$node$$Node$$shell *) calloc(num_nodes, sizeof(struct graph$node$$Node$$shell)); + (*(struct graph$$Graph*)&g).edges = (struct graph$edge$$Edge$$shell *) calloc(num_edges, sizeof(struct graph$edge$$Edge$$shell)); + for (int i=0; inodes[rand() % ((struct graph$$Graph*)g)->num_nodes]; +} + +int graph$$path_found(struct graph$node$$Node$$shell *first, struct graph$node$$Node$$shell *second) { + return graph$node$$random_search(first, second, graph$$max_steps_to_walk); +} + +int graph$$destroy_graph(struct graph$$Graph$$shell *g) { + free(((struct graph$$Graph*)g)->nodes); + free(((struct graph$$Graph*)g)->edges); + return 0; +} Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/graph__tshell.h =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/graph__tshell.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/graph__tshell.h (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,6 @@ +#pragma once + +// [[size 24, align 8]] +struct graph$$Graph$$shell { + double contents[3]; // just to fill space, not used +}; Index: doc/proposals/modules-alvin/examples/graph/5_tweaking/main__impl.c =================================================================== --- doc/proposals/modules-alvin/examples/graph/5_tweaking/main__impl.c (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) +++ doc/proposals/modules-alvin/examples/graph/5_tweaking/main__impl.c (revision 7640ff5c2bfadbdbf25492ac84ec6e5be20a4989) @@ -0,0 +1,83 @@ +// Graph searching algorithm testing script + +#include "graph__export.h" + +#include +#include +#include + +void print_usage() { + printf("Usage: program_name [-n num_iter] [-s seed] [-N num_nodes] [-E num_edges] [-c num_checks] [-h]\n"); + printf("Options:\n"); + printf(" -n num_iter Number of graphs to run on\n"); + printf(" -s seed Seed for random number generator\n"); + printf(" -N num_nodes Number of nodes in generated graph\n"); + printf(" -E num_edges Number of edges in generated graph\n"); + printf(" -c num_checks Number of times to check graph for paths\n"); + printf(" -h Display this help message\n"); +} + +struct Arg { + int num_iter, seed, num_nodes, num_edges, num_checks; +}; + +struct Arg process_args(int argc, char *argv[]) { + int opt; + struct Arg args; + args.num_iter = 10; + args.seed = 0; + args.num_nodes = 100; + args.num_edges = 100; + args.num_checks = 10; + + // Parse command line options + while ((opt = getopt(argc, argv, "n:s:N:E:c:h")) != -1) { + switch (opt) { + case 'n': + args.num_iter = atoi(optarg); + break; + case 's': + args.seed = atoi(optarg); + break; + case 'N': + args.num_nodes = atoi(optarg); + break; + case 'E': + args.num_edges = atoi(optarg); + break; + case 'c': + args.num_checks = atoi(optarg); + break; + case 'h': + print_usage(); // Print usage information + exit(0); + case '?': + // Handle unknown options + fprintf(stderr, "Unknown option: -%c\n", optopt); + print_usage(); + exit(1); + default: + print_usage(); + exit(1); + } + } + return args; +} + +int main(int argc, char *argv[]) { + struct Arg args = process_args(argc, argv); + int total_paths = 0; + srand(args.seed); + for (int i=0; i