1 files changed, 170 insertions, 23 deletions

diff --git a/src/solve.c b/src/solve.c
index 29f614b..a35a837 100644
--- a/src/solve.c
+++ b/src/solve.c
@@ -8,6 +8,8 @@ static void        dfs_branch(Cube c, Step *s, SolveOptions *os, DfsData *dd);
 static bool        dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd);
 static void        dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
 static bool        dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
+static void *      instance_thread(void *arg);
+static void        multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d);
 
 /* Local functions ***********************************************************/
 
@@ -41,12 +43,24 @@ dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
 static void
 dfs_branch(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
 {
-        Move m, l1 = dd->last1, l2 = dd->last2, *moves = dd->sorted_moves;
+        bool b = false;
+        int i;
+        Move m, l1, l2;
 
-        int i, maxnsol = opts->max_solutions;
+        l1 = dd->last1;
+        l2 = dd->last2;
 
-        for (i = 0; moves[i] != NULLMOVE && dd->sols->len < maxnsol; i++) {
-                m = moves[i];
+        for (i = 0; dd->sorted_moves[i] != NULLMOVE; i++) {
+        /*
+                pthread_mutex_lock(dd->sols_mutex);
+                b = dd->sols->len >= opts->max_solutions;
+                pthread_mutex_unlock(dd->sols_mutex);
+        */
+
+                if (b)
+                        break;
+                        
+                m = dd->sorted_moves[i];
                 if (allowed_next(m, dd)) {
                         dd->last2 = dd->last1;
                         dd->last1 = m;
@@ -68,8 +82,12 @@ dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd)
                 return false;
 
         if (dd->current_alg->len == dd->d) {
-                if (s->is_valid(dd->current_alg) || opts->all)
-                        append_alg(dd->sols, dd->current_alg);
+                if (s->is_valid(dd->current_alg) || opts->all) {
+                        pthread_mutex_lock(dd->sols_mutex);
+                        if (dd->sols->len < opts->max_solutions)
+                                append_alg(dd->sols, dd->current_alg);
+                        pthread_mutex_unlock(dd->sols_mutex);
+                }
 
                 if (opts->verbose)
                         print_alg(dd->current_alg, false);
@@ -103,14 +121,13 @@ dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
 static bool
 dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
 {
+        bool b = false;
+
         CubeTarget ct = {
                 .cube   = c,
                 .target = dd->d - dd->current_alg->len
         };
 
-        if (dd->sols->len >= opts->max_solutions)
-                return true;
-
         dd->lb = s->estimate(ct);
         if (opts->can_niss && !dd->niss)
                 dd->lb = MIN(1, dd->lb);
@@ -118,7 +135,131 @@ dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
         if (dd->current_alg->len + dd->lb > dd->d)
                 return true;
 
-        return false;
+        pthread_mutex_lock(dd->sols_mutex);
+        b = dd->sols->len >= opts->max_solutions;
+        pthread_mutex_unlock(dd->sols_mutex);
+
+        return b;
+}
+
+static void *
+instance_thread(void *arg)
+{
+        bool b;
+        Cube c;
+        ThreadData *td;
+        AlgListNode *node;
+        DfsData dd;
+
+        td = (ThreadData *)arg;
+
+        while (1) {
+                b = false;
+
+                pthread_mutex_lock(td->start_mutex);
+                if ((node = *(td->node)) == NULL)
+                        b = true;
+                else
+                        *(td->node) = (*(td->node))->next;
+                pthread_mutex_unlock(td->start_mutex);
+
+                if (b)
+                        break;
+
+                c = node->alg->inv[0] ?
+                    apply_move(node->alg->move[0], inverse_cube(td->cube)) :
+                    apply_move(node->alg->move[0], td->cube);
+
+                dd.d             = td->depth;
+                dd.m             = 1;
+                dd.niss          = node->alg->inv[0];
+                dd.lb            = -1;
+                dd.last1         = node->alg->move[0];
+                dd.last2         = NULLMOVE;
+                dd.sols          = td->sols;
+                dd.sols_mutex    = td->sols_mutex;
+                dd.current_alg   = new_alg("");
+                append_move(dd.current_alg, node->alg->move[0],
+                            node->alg->inv[0]);
+                dd.sorted_moves  = td->sorted_moves;
+                dd.move_position = td->move_position;
+
+/*
+                pthread_mutex_lock(td->sols_mutex);
+                printf("Starting thread %d with move: ", td->thid);
+                print_alg(dd.current_alg, false);
+                pthread_mutex_unlock(td->sols_mutex);
+*/
+
+                dfs(c, td->step, td->opts, &dd);
+
+                free_alg(dd.current_alg);
+        }
+
+        return NULL;
+}
+
+static void
+multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
+{
+        int i, *move_position;
+        Move *sorted_moves;
+        Alg *alg;
+        AlgList *start;
+        AlgListNode **node;
+        pthread_t t[opts->nthreads];
+        ThreadData td[opts->nthreads];
+        pthread_mutex_t *start_mutex, *sols_mutex;
+
+        move_position = malloc(NMOVES * sizeof(int));
+        sorted_moves  = malloc(NMOVES * sizeof(Move));
+        node  = malloc(sizeof(AlgListNode *));
+        start_mutex = malloc(sizeof(pthread_mutex_t));
+        sols_mutex  = malloc(sizeof(pthread_mutex_t));
+
+        start = new_alglist();
+        pthread_mutex_init(start_mutex, NULL);
+        pthread_mutex_init(sols_mutex,  NULL);
+
+        moveset_to_list(s->moveset, sorted_moves);
+        movelist_to_position(sorted_moves, move_position);
+        for (i = 0; sorted_moves[i] != NULLMOVE; i++) {
+                alg = new_alg("");
+                append_move(alg, sorted_moves[i], false);
+                append_alg(start, alg);
+                if (opts->can_niss) {
+                        alg->inv[0] = true;
+                        append_alg(start, alg);
+                }
+                free_alg(alg);
+        }
+        *node = start->first;
+
+        for (i = 0; i < opts->nthreads; i++) {
+                td[i].thid          = i;
+                td[i].cube          = c;
+                td[i].step          = s;
+                td[i].depth         = d;
+                td[i].sorted_moves  = sorted_moves;
+                td[i].move_position = move_position;
+                td[i].opts          = opts;
+                td[i].start         = start;
+                td[i].node          = node;
+                td[i].sols          = sols;
+                td[i].start_mutex   = start_mutex;
+                td[i].sols_mutex    = sols_mutex;
+                pthread_create(&t[i], NULL, instance_thread, &td[i]);
+        }
+
+        for (i = 0; i < opts->nthreads; i++)
+                pthread_join(t[i], NULL);
+
+        free_alglist(start);
+        free(node);
+        free(start_mutex);
+        free(sols_mutex);
+        free(move_position);
+        free(sorted_moves);
 }
 
 /* Public functions **********************************************************/
@@ -126,11 +267,12 @@ dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
 AlgList *
 solve(Cube cube, Step *step, SolveOptions *opts)
 {
+        int d;
+        AlgList *sols = new_alglist();
         AlgListNode *node;
-        DfsData dd;
         Cube c;
 
-        prepare_step(step, &dd);
+        prepare_step(step);
 
         if (step->detect != NULL)
                 step->pre_trans = step->detect(cube);
@@ -139,24 +281,29 @@ solve(Cube cube, Step *step, SolveOptions *opts)
         if (step->ready != NULL && !step->ready(c)) {
                 fprintf(stderr, "Cube not ready for solving step: ");
                 fprintf(stderr, "%s\n", step->ready_msg);
-                return dd.sols;
+                return sols;
+        }
+
+        if (step->estimate((CubeTarget){.cube = c, .target = 0}) == 0 &&
+            opts->min_moves == 0) {
+                append_alg(sols, new_alg(""));
+                return sols;
         }
 
-        for (dd.d = opts->min_moves;
-             dd.d <= opts->max_moves &&
-                 !(dd.sols->len && opts->optimal_only) &&
-                 dd.sols->len < opts->max_solutions;
-             dd.d++) {
+        for (d = MAX(1, opts->min_moves);
+             d <= opts->max_moves &&
+                 !(sols->len && opts->optimal_only) &&
+                 sols->len < opts->max_solutions;
+             d++) {
                 if (opts->verbose)
                         fprintf(stderr,
                                 "Found %d solutions, searching depth %d...\n",
-                                dd.sols->len, dd.d);
-                dfs(c, step, opts, &dd);
+                                sols->len, d);
+                multidfs(c, step, opts, sols, d);
         }
 
-        for (node = dd.sols->first; node != NULL; node = node->next)
+        for (node = sols->first; node != NULL; node = node->next)
                 transform_alg(inverse_trans(step->pre_trans), node->alg);
 
-        free_alg(dd.current_alg);
-        return dd.sols;
+        return sols;
 }