aboutsummaryrefslogtreecommitdiff
path: root/src/solvers/h48/thread.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/solvers/h48/thread.h')
-rw-r--r--src/solvers/h48/thread.h301
1 files changed, 0 insertions, 301 deletions
diff --git a/src/solvers/h48/thread.h b/src/solvers/h48/thread.h
deleted file mode 100644
index fb5ccbc..0000000
--- a/src/solvers/h48/thread.h
+++ /dev/null
@@ -1,301 +0,0 @@
1#include <stdatomic.h>
2
3#define MAX_QUEUE_SIZE 244
4#define BFS_DEPTH 2
5typedef struct {
6 dfsarg_solveh48_t tasks[MAX_QUEUE_SIZE];
7 int front;
8 int rear;
9 int tasks_count;
10 int active;
11 pthread_mutex_t mutex;
12 pthread_cond_t cond;
13 pthread_cond_t active_cond;
14 atomic_bool terminate;
15} task_queue_t;
16
17STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *, task_queue_t *);
18STATIC void init_queue(task_queue_t *);
19STATIC void submit_task(task_queue_t *, dfsarg_solveh48_t);
20STATIC void copy_queue(task_queue_t *, task_queue_t *, int, int64_t *);
21STATIC void *start_thread(void *);
22STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t *, task_queue_t *);
23STATIC int64_t solve_h48_single(dfsarg_solveh48_t *, task_queue_t *);
24STATIC int64_t solve_h48_parent(cube_t, int8_t, int8_t, int8_t, const void *, char *);
25
26STATIC void
27solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq)
28{
29 pthread_mutex_lock(&tq->mutex);
30 int strl = 0;
31 uint8_t invertedpremoves[MAXLEN];
32 char *solution = *arg->nextsol;
33
34 strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol);
35 *arg->nextsol += strl;
36
37 if (arg->npremoves)
38 {
39 **arg->nextsol = ' ';
40 (*arg->nextsol)++;
41
42 invertmoves(arg->premoves, arg->npremoves, invertedpremoves);
43 strl = writemoves(invertedpremoves, arg->npremoves, *arg->nextsol);
44 *arg->nextsol += strl;
45 }
46 LOG("Solution found: %s\n", solution);
47
48 **arg->nextsol = '\n';
49 (*arg->nextsol)++;
50 (*arg->nsols)++;
51 pthread_mutex_unlock(&tq->mutex);
52}
53
54STATIC void
55init_queue(task_queue_t *queue)
56{
57 queue->front = 0;
58 queue->rear = 0;
59 queue->tasks_count = 0;
60 queue->active = 0;
61 queue->terminate = ATOMIC_VAR_INIT(false);
62 pthread_mutex_init(&queue->mutex, NULL);
63 pthread_cond_init(&queue->cond, NULL);
64 pthread_cond_init(&queue->active_cond, NULL);
65}
66
67STATIC void
68submit_task(task_queue_t *queue, dfsarg_solveh48_t task)
69{
70 pthread_mutex_lock(&queue->mutex);
71 queue->tasks[queue->rear] = task;
72 queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
73 queue->tasks_count++;
74 pthread_cond_broadcast(&queue->cond);
75 pthread_mutex_unlock(&queue->mutex);
76}
77
78STATIC void
79copy_queue(task_queue_t *src, task_queue_t *dest, int depth, int64_t *nsols)
80{
81 pthread_mutex_lock(&dest->mutex);
82 for (int i = src->front; i != src->rear; i = (i + 1) % MAX_QUEUE_SIZE)
83 {
84 dest->tasks[i] = src->tasks[i];
85 dest->tasks[i].depth = depth;
86 }
87 dest->front = src->front;
88 dest->rear = src->rear;
89 dest->tasks_count = src->tasks_count;
90 pthread_cond_broadcast(&dest->cond);
91 pthread_mutex_unlock(&dest->mutex);
92}
93
94STATIC void *
95start_thread(void *arg)
96{
97 task_queue_t *queue = (task_queue_t *)arg;
98 while (1) {
99 pthread_mutex_lock(&queue->mutex);
100 while (queue->tasks_count == 0 && !queue->terminate) {
101 pthread_cond_wait(&queue->cond, &queue->mutex);
102 }
103 if (queue->tasks_count == 0 && queue->terminate) {
104 pthread_mutex_unlock(&queue->mutex);
105 break;
106 }
107
108 if (queue->tasks_count > 0) {
109 dfsarg_solveh48_t task = queue->tasks[queue->front];
110 queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
111 queue->tasks_count--;
112 queue->active++;
113 pthread_mutex_unlock(&queue->mutex);
114
115 solve_h48_single(&task, queue);
116
117 pthread_mutex_lock(&queue->mutex);
118 queue->active--;
119
120 if(queue->tasks_count == 0 && queue->active == 0)
121 pthread_cond_signal(&queue->active_cond);
122 }
123 pthread_mutex_unlock(&queue->mutex);
124 }
125 return NULL;
126}
127
128STATIC int64_t
129solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq)
130{
131 dfsarg_solveh48_t queue[MAX_QUEUE_SIZE];
132 int front = 0, rear = 0;
133 dfsarg_solveh48_t nextarg;
134 int depth = 0;
135 int nodes_at_current_depth = 1;
136 int nodes_at_next_depth = 0;
137 queue[rear++] = *arg_zero;
138
139 dfsarg_solveh48_t task_pool[MAX_QUEUE_SIZE];
140
141 while (front < rear){
142 dfsarg_solveh48_t arg = queue[front++];
143 nodes_at_current_depth--;
144
145 if (*arg.nsols == arg.maxsolutions)
146 return 1;
147
148 if (issolved(arg.cube)){
149 if (arg.nmoves + arg.npremoves != arg.depth)
150 continue;
151 solve_h48_appendsolution(&arg);
152 continue;
153 }
154
155 arg.nissbranch = MM_NORMAL;
156 uint32_t allowed = allowednextmove_h48(arg.moves, arg.nmoves, arg.nissbranch);
157
158 for (uint8_t m = 0; m < 18; m++){
159 if (allowed & (1 << m)){
160 nextarg = arg;
161 nextarg.nmoves = arg.nmoves + 1;
162 nextarg.moves[arg.nmoves] = m;
163 nextarg.cube = move(arg.cube, m);
164 nextarg.inverse = premove(arg.inverse, m);
165
166 if (nextarg.nmoves == BFS_DEPTH){
167 dfsarg_solveh48_t *task = &task_pool[rear % MAX_QUEUE_SIZE];
168 *task = nextarg;
169 submit_task(tq, *task);
170 } else {
171 queue[rear++] = nextarg;
172 nodes_at_next_depth++;
173 }
174 }
175 }
176 if (nodes_at_current_depth == 0){
177 nodes_at_current_depth = nodes_at_next_depth;
178 nodes_at_next_depth = 0;
179 LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", *nextarg.nsols, depth++);
180 }
181 if (depth == BFS_DEPTH) return 0;
182 }
183 return 1;
184}
185
186STATIC int64_t
187solve_h48_single(dfsarg_solveh48_t *arg, task_queue_t *tq)
188{
189 dfsarg_solveh48_t nextarg;
190 int64_t ret;
191 uint8_t m;
192
193 if (*arg->nsols == arg->maxsolutions)
194 return 0;
195
196 if (solve_h48_stop(arg))
197 return 0;
198
199 if (issolved(arg->cube)){
200 if (arg->nmoves + arg->npremoves != arg->depth)
201 return 0;
202 solve_h48_appendsolution_thread(arg, tq);
203 return 1;
204 }
205
206 nextarg = *arg;
207 ret = 0;
208 uint32_t allowed;
209 if (arg->nissbranch & MM_INVERSE){
210 allowed = allowednextmove_h48(arg->premoves, arg->npremoves, arg->nissbranch);
211 for (m = 0; m < 18; m++){
212 if (allowed & (1 << m)){
213 nextarg.npremoves = arg->npremoves + 1;
214 nextarg.premoves[arg->npremoves] = m;
215 nextarg.inverse = move(arg->inverse, m);
216 nextarg.cube = premove(arg->cube, m);
217 ret += solve_h48_single(&nextarg, tq);
218 }
219 }
220 } else {
221 allowed = allowednextmove_h48(arg->moves, arg->nmoves, arg->nissbranch);
222 for (m = 0; m < 18; m++){
223 if (allowed & (1 << m)){
224 nextarg.nmoves = arg->nmoves + 1;
225 nextarg.moves[arg->nmoves] = m;
226 nextarg.cube = move(arg->cube, m);
227 nextarg.inverse = premove(arg->inverse, m);
228 ret += solve_h48_single(&nextarg, tq);
229 }
230 }
231 }
232 return ret;
233}
234
235STATIC int64_t
236solve_h48_parent(
237 cube_t cube,
238 int8_t minmoves,
239 int8_t maxmoves,
240 int8_t maxsolutions,
241 const void *data,
242 char *solutions)
243{
244 int64_t nsols = 0;
245 int p_depth = 0;
246 dfsarg_solveh48_t arg;
247 tableinfo_t info;
248 pthread_t threads[THREADS];
249
250 if (!readtableinfo_n(data, 2, &info)){
251 LOG("solve_h48: error reading table\n");
252 return 0;
253 }
254
255 arg = (dfsarg_solveh48_t){
256 .cube = cube,
257 .inverse = inverse(cube),
258 .nsols = &nsols,
259 .maxsolutions = maxsolutions,
260 .h = info.h48h,
261 .k = info.bits,
262 .cocsepdata = get_cocsepdata_ptr(data),
263 .h48data = get_h48data_ptr(data),
264 .nextsol = &solutions};
265
266 task_queue_t q;
267 init_queue(&q);
268 if (solve_h48_bfs(&arg, &q))
269 return nsols;
270
271 task_queue_t nq;
272 init_queue(&nq);
273
274 for (int i = 0; i < THREADS; i++){
275 pthread_create(&threads[i], NULL, &start_thread, &nq);
276 }
277
278 nsols = 0;
279 for (p_depth = minmoves > BFS_DEPTH ? minmoves : BFS_DEPTH;
280 p_depth <= maxmoves && nsols < maxsolutions;
281 p_depth++)
282 {
283 LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", nsols, p_depth);
284 copy_queue(&q, &nq, p_depth, &nsols);
285
286 pthread_mutex_lock(&nq.mutex);
287 while (nq.active > 0 || nq.tasks_count > 0)
288 pthread_cond_wait(&nq.active_cond, &nq.mutex);
289 pthread_mutex_unlock(&nq.mutex);
290 }
291
292 atomic_store(&nq.terminate, true);
293 pthread_cond_broadcast(&nq.cond);
294
295 for (int i = 0; i < THREADS; i++){
296 pthread_join(threads[i], NULL);
297 }
298 **arg.nextsol = '\0';
299 (*arg.nextsol)++;
300 return nsols;
301}

Generated with cgit - Back to sebastiano.tronto.net