1 // This file is part of Freecell Solver. It is subject to the license terms in
2 // the COPYING.txt file found in the top-level directory of this distribution
3 // and at http://fc-solve.shlomifish.org/docs/distro/COPYING.html . No part of
4 // Freecell Solver, including this file, may be copied, modified, propagated,
5 // or distributed except according to the terms contained in the COPYING file.
6 //
7 // Copyright (c) 2000 Shlomi Fish
8 // instance.h - header file of fcs_instance / fcs_hard_thread /
9 // fcs_soft_thread .
10 #pragma once
11
12 #ifdef __cplusplus
13 extern "C" {
14 #endif
15
16 #include <math.h>
17
18 #include "move.h"
19 #include "freecell-solver/fcs_enums.h"
20 #include "freecell-solver/fcs_user.h"
21 #include "rate_state.h"
22 #include "indirect_buffer.h"
23 #include "rand.h"
24 #include "game_type_params.h"
25
26 #if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBREDBLACK_TREE) || \
27 (defined(INDIRECT_STACK_STATES) && \
28 (FCS_STACK_STORAGE == FCS_STACK_STORAGE_LIBREDBLACK_TREE))
29 #include <redblack.h>
30 #endif
31
32 #if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBAVL2_TREE)
33 #include "fcs_libavl2_state_storage.h"
34 #endif
35
36 #if (FCS_STACK_STORAGE == FCS_STACK_STORAGE_LIBAVL2_TREE)
37 #include "fcs_libavl2_stack_storage.h"
38 #endif
39
40 #if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_TREE) || \
41 (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_HASH) || \
42 (defined(INDIRECT_STACK_STATES) && \
43 ((FCS_STACK_STORAGE == FCS_STACK_STORAGE_GLIB_TREE) || \
44 (FCS_STACK_STORAGE == FCS_STACK_STORAGE_GLIB_HASH)))
45 #include <glib.h>
46 #endif
47
48 #if ((defined(FCS_RCS_STATES) && \
49 (FCS_RCS_CACHE_STORAGE == FCS_RCS_CACHE_STORAGE_JUDY)) || \
50 (FCS_STATE_STORAGE == FCS_STATE_STORAGE_JUDY) || \
51 (defined(INDIRECT_STACK_STATES) && \
52 (FCS_STACK_STORAGE == FCS_STACK_STORAGE_JUDY)))
53 #include <Judy.h>
54 #endif
55
56 #if ((FCS_STATE_STORAGE == FCS_STATE_STORAGE_INTERNAL_HASH) || \
57 (FCS_STACK_STORAGE == FCS_STACK_STORAGE_INTERNAL_HASH))
58 #include "fcs_hash.h"
59 #endif
60
61 #if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GOOGLE_DENSE_HASH) || \
62 (FCS_STACK_STORAGE == FCS_STACK_STORAGE_GOOGLE_DENSE_HASH)
63 #include "google_hash.h"
64 #endif
65
66 #if ((FCS_STATE_STORAGE == FCS_STATE_STORAGE_KAZ_TREE) || \
67 (defined(FCS_RCS_STATES) && \
68 (FCS_RCS_CACHE_STORAGE == FCS_RCS_CACHE_STORAGE_KAZ_TREE)))
69 #include "kaz_tree.h"
70 #endif
71
72 #if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_DB_FILE)
73 #include <db.h>
74 #endif
75
76 #include "pqueue.h"
77 #include "meta_alloc.h"
78
79 // We need 2 chars per card - one for the column_idx and one
80 // for the card_idx.
81 //
82 // We also need it times 13 for each of the ranks.
83 //
84 // We need (4*LOCAL_DECKS_NUM+1) slots to hold the cards plus a
85 // (-1,-1) (= end) padding.
86 #define FCS_POS_BY_RANK_WIDTH (MAX_NUM_DECKS << 3)
87
88 // We don't keep track of kings
89 #define FCS_POS_BY_RANK_LEN (FCS_RANK_KING * FCS_POS_BY_RANK_WIDTH)
90 typedef struct
91 {
92 int8_t col, height;
93 } fcs_pos_by_rank;
94
95 typedef struct
96 {
97 fcs_iters_int num_checked_states;
98 #ifndef FCS_DISABLE_NUM_STORED_STATES
99 fcs_iters_int num_states_in_collection;
100 #endif
101 } fcs_stats;
102
103 #ifndef FCS_DISABLE_SIMPLE_SIMON
104 #define FCS_SS_POS_BY_RANK_WIDTH (FCS_RANK_KING + 1)
105 #define FCS_SS_POS_BY_RANK_LEN (FCS_SS_POS_BY_RANK_WIDTH * 4)
106 #define FCS_BOTH__POS_BY_RANK__SIZE \
107 (max(FCS_SS_POS_BY_RANK_LEN * sizeof(fcs_pos_by_rank), FCS_POS_BY_RANK_LEN))
108 #else
109 #define FCS_BOTH__POS_BY_RANK__SIZE FCS_POS_BY_RANK_LEN
110 #endif
111
112 typedef int8_t fcs__positions_by_rank[FCS_BOTH__POS_BY_RANK__SIZE];
113
114 // This is a linked list item that is used to implement a queue for the BFS
115 // scan.
116 typedef struct fcs_states_linked_list_item_struct
117 {
118 fcs_collectible_state *s;
119 struct fcs_states_linked_list_item_struct *next;
120 } fcs_states_linked_list_item;
121
122 // Declare these structures because they will be used within
123 // fc_solve_instance, and they will contain a pointer to it.
124 struct fc_solve_hard_thread_struct;
125 struct fc_solve_soft_thread_struct;
126 struct fc_solve_instance_struct;
127
128 typedef void (*fc_solve_solve_for_state_move_func)(
129 struct fc_solve_soft_thread_struct *, fcs_kv_state,
130 fcs_derived_states_list *);
131
132 #ifdef FCS_SINGLE_HARD_THREAD
133 #define HT_FIELD(ht, field) (ht)->hard_thread.field
134 #define HT_INSTANCE(hard_thread) (hard_thread)
135 #define INST_HT0(instance) ((instance)->hard_thread)
136 #define NUM_CHECKED_STATES \
137 (HT_INSTANCE(hard_thread)->i__stats.num_checked_states)
138 typedef struct fc_solve_instance_struct fcs_hard_thread;
139 #if (defined(FCS_SINGLE_HARD_THREAD) && defined(FCS_WITH_MOVES))
140 extern void fc_solve_init_soft_thread(fcs_hard_thread *const hard_thread,
141 struct fc_solve_soft_thread_struct *const soft_thread);
142 #endif
143 #else
144 #define HT_FIELD(hard_thread, field) (hard_thread)->field
145 #define HT_INSTANCE(hard_thread) ((hard_thread)->instance)
146 #define INST_HT0(instance) ((instance)->hard_threads[0])
147 #define NUM_CHECKED_STATES HT_FIELD(hard_thread, ht__num_checked_states)
148 typedef struct fc_solve_hard_thread_struct fcs_hard_thread;
149 #endif
150 extern bool fc_solve_check_and_add_state(
151 fcs_hard_thread *, fcs_kv_state *, fcs_kv_state *);
152
153 #if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_HASH)
154 extern guint fc_solve_hash_function(gconstpointer key);
155 #endif
156
157 #ifndef FCS_ZERO_FREECELLS_MODE
158 #include "move_funcs_maps.h"
159 #endif
160
161 // HT_LOOP == hard threads' loop - macros to abstract it.
162 #ifdef FCS_SINGLE_HARD_THREAD
163
164 #define HT_LOOP_START() fcs_hard_thread *const hard_thread = instance;
165
166 #else
167 #define HT_LOOP_START() \
168 fcs_hard_thread *hard_thread = instance->hard_threads; \
169 fcs_hard_thread *const end_hard_thread = \
170 hard_thread + instance->num_hard_threads; \
171 for (; hard_thread < end_hard_thread; ++hard_thread)
172 #endif
173
174 // ST_LOOP == soft threads' loop - macros to abstract it.
175 #define ST_LOOP_START() \
176 fcs_soft_thread *const ht_soft_threads = \
177 HT_FIELD(hard_thread, soft_threads); \
178 fcs_soft_thread *soft_thread = ht_soft_threads; \
179 fcs_soft_thread *const end_soft_thread = \
180 ht_soft_threads + HT_FIELD(hard_thread, num_soft_threads); \
181 for (; soft_thread < end_soft_thread; ++soft_thread)
182 #define MOVES_GROW_BY 16U
183
184 typedef struct
185 {
186 fc_solve_weighting_float weights[FCS_NUM_BEFS_WEIGHTS];
187 } fcs_default_weights;
188 typedef struct
189 {
190 bool should_go_over_stacks;
191 fc_solve_weighting_float max_sequence_move_factor,
192 cards_under_sequences_factor, seqs_over_renegade_cards_factor,
193 depth_factor, num_cards_not_on_parents_factor;
194
195 fc_solve_weighting_float num_cards_out_lookup_table[14];
196 // The BeFS weights of the different BeFS tests. Those
197 // weights determine the commulative priority of the state.
198 fcs_default_weights befs_weights;
199 } fcs_state_weighting;
200
201 typedef enum
202 {
203 FCS_NO_SHUFFLING,
204 FCS_RAND,
205 FCS_WEIGHTING,
206 FCS_PERFORM_ALL_MOVE_FUNCS,
207 } fcs_moves_group_kind;
208
209 typedef union {
210 fc_solve_solve_for_state_move_func f;
211 uint_fast32_t idx;
212 } fcs_move_func;
213
214 typedef struct
215 {
216 fcs_move_func *move_funcs;
217 uint_fast32_t num;
218 fcs_moves_group_kind shuffling_type;
219 fcs_state_weighting weighting;
220 } fcs_moves_group;
221
222 typedef struct
223 {
224 uint_fast32_t num;
225 #ifndef FCS_ZERO_FREECELLS_MODE
226 fcs_moves_group *groups;
227 #endif
228 } fcs_moves_order;
229
230 typedef struct
231 {
232 ssize_t max_depth;
233 fcs_moves_order moves_order;
234 } fcs_by_depth_moves_order;
235
236 #define STRUCT_CLEAR_FLAG(instance, flag) (instance)->flag = false
237 #define STRUCT_TURN_ON_FLAG(instance, flag) (instance)->flag = true
238 #define STRUCT_QUERY_FLAG(instance, flag) ((instance)->flag)
239 #define STRUCT_SET_FLAG_TO(instance, flag, value) (instance)->flag = (value)
240
241 #ifdef FCS_RCS_STATES
242 struct fcs_cache_key_info_struct
243 {
244 const fcs_collectible_state *val_ptr;
245 fcs_state key;
246 // lower_pri and higher_pri form a doubly linked list. pri == priority.
247 struct fcs_cache_key_info_struct *lower_pri, *higher_pri;
248 };
249
250 typedef struct fcs_cache_key_info_struct fcs_cache_key_info;
251
252 typedef struct
253 {
254 #if (FCS_RCS_CACHE_STORAGE == FCS_RCS_CACHE_STORAGE_JUDY)
255 Pvoid_t states_values_to_keys_map;
256 #elif (FCS_RCS_CACHE_STORAGE == FCS_RCS_CACHE_STORAGE_KAZ_TREE)
257 dict_t *kaz_tree;
258 #else
259 #error Unknown FCS_RCS_CACHE_STORAGE
260 #endif
261 compact_allocator states_values_to_keys_allocator;
262 fcs_iters_int count_elements_in_cache, max_num_elements_in_cache;
263
264 fcs_cache_key_info *lowest_pri, *highest_pri, *recycle_bin;
265 } fcs_lru_cache;
266
267 #endif
268
269 #ifndef FCS_WITHOUT_ITER_HANDLER
270 typedef void (*instance_debug_iter_output_func)(
271 void *, fcs_int_limit_t, int, void *, fcs_kv_state *, fcs_int_limit_t);
272 #endif
273
274 typedef struct fc_solve_soft_thread_struct fcs_soft_thread;
275 typedef struct fc_solve_instance_struct fcs_instance;
276
277 typedef uint_fast32_t fastest_type_for_num_soft_threads__unsigned;
278 struct fc_solve_hard_thread_struct
279 {
280 #ifndef FCS_SINGLE_HARD_THREAD
281 fcs_instance *instance;
282 #endif
283
284 struct fc_solve_soft_thread_struct *soft_threads;
285
286 #ifndef FCS_SINGLE_HARD_THREAD
287 // The hard thread count of how many states he checked himself. The
288 // instance num_checked_states can be misleading because other threads
289 // modify it too.
290 //
291 // Thus, the soft thread switching should be done based on this variable
292 fcs_iters_int ht__num_checked_states;
293
294 #endif
295 // The maximal limit for num_checked_states.
296 fcs_iters_int ht__max_num_checked_states;
297
298 // The index for the soft-thread that is currently processed
299 uint_fast32_t st_idx;
300 // This is the mechanism used to allocate memory for stacks, states
301 // and move stacks.
302 compact_allocator allocator;
303
304 #ifdef FCS_WITH_MOVES
305 // This is a move stack that is used and re-used by the
306 // moves functions of this hard thread
307 fcs_move_stack reusable_move_stack;
308 #endif
309
310 // This is a buffer used to temporarily store the stacks of the
311 // duplicated state.
312 DECLARE_IND_BUF_T(indirect_stacks_buffer)
313
314 size_t prelude_num_items;
315 size_t prelude_idx;
316 #ifndef FCS_USE_PRECOMPILED_CMD_LINE_THEME
317 fc_solve_prelude_item *prelude;
318 #else
319 const fc_solve_prelude_item *prelude;
320 #endif
321
322 bool allocated_from_list;
323 fastest_type_for_num_soft_threads__unsigned num_soft_threads;
324
325 // A counter that determines how many of the soft threads that belong
326 // to this hard thread have already finished. If it becomes
327 // num_soft_threads this thread is skipped.
328 fastest_type_for_num_soft_threads__unsigned num_soft_threads_finished;
329
330 #ifndef FCS_USE_PRECOMPILED_CMD_LINE_THEME
331 char *prelude_as_string;
332 #endif
333 };
334
335 typedef struct
336 {
337 int rating_with_index__idx;
338 pq_rating rating;
339 } rating_with_index;
340
341 typedef struct
342 {
343 fcs_collectible_state *state;
344 fcs_derived_states_list derived_states_list;
345 size_t move_func_list_idx;
346 size_t current_state_index;
347 size_t move_func_idx;
348 #ifndef FCS_ZERO_FREECELLS_MODE
349 size_t derived_states_random_indexes_max_size;
350 rating_with_index *derived_states_random_indexes;
351 #endif
352 fcs__positions_by_rank positions_by_rank;
353 } fcs_soft_dfs_stack_item;
354
355 typedef struct
356 {
357 ssize_t max_depth;
358 fcs_moves_order move_funcs;
359 } moves_by_depth_unit;
360
361 typedef struct
362 {
363 size_t num_units;
364 moves_by_depth_unit *by_depth_units;
365 } fcs_moves_by_depth_array;
366
367 typedef enum
368 {
369 FCS_SUPER_METHOD_DFS,
370 FCS_SUPER_METHOD_BEFS_BRFS,
371 #ifndef FCS_DISABLE_PATSOLVE
372 FCS_SUPER_METHOD_PATSOLVE,
373 #endif
374 } fcs_super_method_type;
375
376 struct fc_solve__patsolve_thread_struct;
377 struct fc_solve_soft_thread_struct
378 {
379 fcs_hard_thread *hard_thread;
380
381 // The ID of the soft thread inside the instance. Used for the
382 // state-specific flags.
383 fastest_type_for_num_soft_threads__unsigned id;
384
385 #ifndef FCS_ZERO_FREECELLS_MODE
386 // The moves' order indicates which move funcs to run.
387 struct
388 {
389 size_t num;
390 fcs_by_depth_moves_order *by_depth_moves;
391 } by_depth_moves_order;
392 #endif
393
394 fcs_super_method_type super_method_type;
395
396 struct
397 {
398 struct
399 {
400 // The (temporary) max depth of the Soft-DFS scans)
401 ssize_t dfs_max_depth;
402
403 // Soft-DFS uses a stack of fcs_soft_dfs_stack_item s.
404 //
405 // derived_states_list - a list of states to be checked next.
406 // Not all of them will be checked because it is possible that
407 // future states already visited them.
408 //
409 // current_state_index - the index of the last checked state
410 // in depth i.
411 //
412 // move_func_list_idx - the index of the move list that is
413 // performed. FCS performs each move separately, so
414 // states_to_check and friends will not be overpopulated.
415 //
416 // num_vacant_stacks - the number of unoccpied stacks that
417 // correspond
418 // to solution_states.
419 //
420 // num_vacant_freecells - ditto for the freecells.
421 fcs_soft_dfs_stack_item *soft_dfs_info;
422
423 // The depth of the DFS stacks
424 ssize_t depth;
425
426 fcs_rand_gen rand_gen;
427
428 // The initial seed of this random number generator
429 fcs_rand_gen rand_seed;
430
431 #ifndef FCS_ZERO_FREECELLS_MODE
432 // The moves to be performed in a preprocessed form.
433 fcs_moves_by_depth_array moves_by_depth;
434 #endif
435
436 } soft_dfs;
437 struct
438 {
439 fcs__positions_by_rank befs_positions_by_rank;
440 fcs_move_func *moves_list, *moves_list_end;
441 struct
442 {
443 struct
444 {
445 // A linked list that serves as the queue for the BFS
446 // scan.
447 fcs_states_linked_list_item *bfs_queue;
448 // The last item in the linked list, so new items can be
449 // added at it, thus making it a queue.
450 fcs_states_linked_list_item *bfs_queue_last_item;
451 // A linked list of items that were freed from
452 // the queue and should be reused before allocating new
453 // items.
454 fcs_states_linked_list_item *recycle_bin;
455 } brfs;
456 struct
457 {
458 pri_queue pqueue;
459 fcs_state_weighting weighting;
460 } befs;
461 } meth;
462 // The first state to be checked by the scan. It is a kind of
463 // bootstrap for the algorithm.
464 fcs_collectible_state *first_state_to_check;
465 } befs;
466 } method_specific;
467
468 bool FCS_SOFT_THREAD_IS_FINISHED, FCS_SOFT_THREAD_INITIALIZED,
469 FCS_SOFT_THREAD_IS_A_COMPLETE_SCAN;
470
471 // The numbers of vacant stacks and freecells in the current state - is
472 // read by the move functions in freecell.c .
473 fcs_game_limit num_vacant_stacks, num_vacant_freecells;
474
475 // The number of iterations with which to process this scan
476 fcs_iters_int checked_states_step;
477
478 #ifndef FCS_USE_PRECOMPILED_CMD_LINE_THEME
479 // A string that serves as an identification for the user.
480 char name[FCS_MAX_IDENT_LEN];
481 #endif
482
483 #ifndef FCS_ENABLE_PRUNE__R_TF__UNCOND
484 // Whether pruning should be done.
485 // This variable is temporary - there should be a better pruning
486 // abstraction with several optional prunes.
487 bool enable_pruning;
488 #endif
489
490 #ifndef FCS_DISABLE_PATSOLVE
491 // The patsolve soft_thread that is associated with this soft_thread.
492 struct fc_solve__patsolve_thread_struct *pats_scan;
493 #endif
494 // Differentiates between SOFT_DFS and RANDOM_DFS.
495 bool master_to_randomize;
496 bool is_befs;
497 #ifdef FCS_WITH_MOVES
498 bool is_optimize_scan;
499 #endif
500 };
501
502 struct fc_solve_instance_struct
503 {
504 // The parameters of the game - see the declaration of fcs_game_type_params_t .
505 #ifndef FCS_FREECELL_ONLY
506 fcs_game_type_params game_params;
507 #ifndef FCS_DISABLE_PATSOLVE
508 fcs_card game_variant_suit_mask;
509 fcs_card game_variant_desired_suit_value;
510 #endif
511 #endif
512
513 fcs_stats i__stats;
514 #ifndef FCS_WITHOUT_MAX_NUM_STATES
515 // Limit for the maximal number of checked states.
516 // max_num_checked_states is useful because it can limit the amount of
517 // consumed memory (and time).
518 //
519 // This is the effective number that enables the process to work without
520 // checking if it's zero.
521 //
522 // Normally should be used instead.
523 fcs_iters_int effective_max_num_checked_states;
524 #endif
525 #ifndef FCS_DISABLE_NUM_STORED_STATES
526 fcs_iters_int effective_max_num_states_in_collection;
527 #ifndef FCS_WITHOUT_TRIM_MAX_STORED_STATES
528 fcs_iters_int effective_trim_states_in_collection_from;
529 #endif
530 #endif
531 fcs_seq_cards_power_type initial_cards_under_sequences_value;
532 // tree is the balanced binary tree that is used to store and index
533 // the checked states.
534 #if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBREDBLACK_TREE)
535 struct rbtree *tree;
536 #elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_JUDY)
537 Pvoid_t judy_array;
538 #elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBAVL2_TREE)
539 fcs_libavl2_states_tree_table *tree;
540 #elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_TREE)
541 GTree *tree;
542 #elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_KAZ_TREE)
543 dict_t *tree;
544 #elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_HASH)
545 GHashTable *hash;
546 #elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INTERNAL_HASH)
547 hash_table hash;
548 #elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GOOGLE_DENSE_HASH)
549 fcs_states_google_hash_handle hash;
550 #elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_DB_FILE)
551 DB *db;
552 #endif
553
554 #if defined(INDIRECT_STACK_STATES)
555 // The storage mechanism for the stacks
556 #if (FCS_STACK_STORAGE == FCS_STACK_STORAGE_INTERNAL_HASH)
557 hash_table stacks_hash;
558 #elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_LIBAVL2_TREE)
559 fcs_libavl2_stacks_tree_table *stacks_tree;
560 #elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_LIBREDBLACK_TREE)
561 struct rbtree *stacks_tree;
562 #elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_GLIB_TREE)
563 GTree *stacks_tree;
564 #elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_GLIB_HASH)
565 GHashTable *stacks_hash;
566 #elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_GOOGLE_DENSE_HASH)
567 fcs_columns_google_hash_handle stacks_hash;
568 #elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_JUDY)
569 Pvoid_t stacks_judy_array;
570 #else
571 #error FCS_STACK_STORAGE is not set to a good value.
572 #endif
573 #endif
574
575 fcs_collectible_state *list_of_vacant_states;
576
577 #ifndef FCS_HARD_CODE_CALC_REAL_DEPTH_AS_FALSE
578 bool FCS_RUNTIME_CALC_REAL_DEPTH;
579 #endif
580 #ifndef FCS_HARD_CODE_REPARENT_STATES_AS_FALSE
581 bool FCS_RUNTIME_TO_REPARENT_STATES_REAL;
582 #endif
583 #ifndef FCS_HARD_CODE_SCANS_SYNERGY_AS_TRUE
584 bool FCS_RUNTIME_SCANS_SYNERGY;
585 #endif
586 #ifndef FCS_HARD_CODE_REPARENT_STATES_AS_FALSE
587 bool FCS_RUNTIME_TO_REPARENT_STATES_PROTO;
588 #endif
589 #ifdef FCS_WITH_MOVES
590 bool FCS_RUNTIME_OPTIMIZE_SOLUTION_PATH, FCS_RUNTIME_IN_OPTIMIZATION_THREAD,
591 FCS_RUNTIME_OPT_TESTS_ORDER_WAS_SET;
592 #endif
593
594 // This is the number of states in the state collection.
595 // It gives a rough estimate of the memory occupied by the instance.
596 #ifndef FCS_DISABLE_NUM_STORED_STATES
597 #ifndef FCS_WITHOUT_TRIM_MAX_STORED_STATES
598 fcs_iters_int active_num_states_in_collection;
599 #endif
600 #endif
601
602 #ifdef FCS_SINGLE_HARD_THREAD
603 struct fc_solve_hard_thread_struct hard_thread;
604 #ifdef FCS_WITH_MOVES
605 bool is_optimization_st;
606 struct fc_solve_soft_thread_struct optimization_soft_thread;
607 #endif
608 #else
609 uint_fast32_t num_hard_threads;
610 struct fc_solve_hard_thread_struct *hard_threads;
611 // An iterator over the hard threads.
612 fcs_hard_thread *current_hard_thread;
613
614 #ifdef FCS_WITH_MOVES
615 // This is the hard-thread used for the optimization scan.
616 struct fc_solve_hard_thread_struct *optimization_thread;
617 #endif
618 #endif
619
620 // The master moves' order. It is used to initialize all the new
621 // Soft-Threads.
622 fcs_moves_order instance_moves_order;
623
624 // Counts how many of the hard threads that belong
625 // to this instance have already finished. If it becomes
626 // num_hard_threads the instance terminates.
627 uint_fast32_t finished_hard_threads_count;
628
629 #ifdef FCS_WITH_MOVES
630 // The moves for the optimization scan, as specified by the user.
631 fcs_moves_order opt_moves;
632 #endif
633
634 #ifdef FCS_RCS_STATES
635 fcs_lru_cache rcs_states_cache;
636
637 #if ((FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBAVL2_TREE) || \
638 (FCS_STATE_STORAGE == FCS_STATE_STORAGE_KAZ_TREE))
639 fcs_state *tree_new_state_key;
640 fcs_collectible_state *tree_new_state;
641 #endif
642
643 #endif
644
645 #ifndef FCS_WITHOUT_ITER_HANDLER
646 // The debug_iter_output variables provide a programmable way
647 // to debug the algorithm while it is running. This works well for DFS
648 // and Soft-DFS scans but at present support for BeFS and BFS is not
649 // too good, as it's hard to tell which state came from which parent
650 // state.
651 //
652 // debug_iter_output_func is a pointer to the function that performs the
653 // debugging. If NULL, this feature is not used.
654 //
655 // debug_iter_output_context is a user-specified context for it, that
656 // may include data that is not included in the instance structure.
657 //
658 // This feature is used by the "-s" and "-i" flags of fc-solve-debug.
659 instance_debug_iter_output_func debug_iter_output_func;
660 void *debug_iter_output_context;
661 #endif
662
663 fastest_type_for_num_soft_threads__unsigned next_soft_thread_id;
664
665 // This is the initial state
666 fcs_state_keyval_pair state_copy;
667
668 #ifdef FCS_WITH_MOVES
669 // This is the final state that the scan recommends to the interface
670 fcs_collectible_state *final_state;
671
672 // A move stack that contains the moves leading to the solution.
673 //
674 // It is created only after the solution was found by swallowing
675 // all the stacks of each depth.
676 fcs_move_stack solution_moves;
677 #endif
678
679 // The meta allocator - see meta_alloc.h.
680 meta_allocator *meta_alloc;
681
682 #if (defined(FCS_WITH_MOVES) && (!defined(FCS_DISABLE_PATSOLVE)))
683 // The soft_thread that solved the state.
684 //
685 // Needed to trace the patsolve solutions.
686 fcs_soft_thread *solving_soft_thread;
687 #endif
688 #ifndef FCS_DISABLE_PATSOLVE
689 // This is intended to be used by the patsolve scan which is
690 // sensitive to the ordering of the columns/stacks. This is an ugly hack
691 // but hopefully it will work.
692 fcs_state_keyval_pair *initial_non_canonized_state;
693 #endif
694
695 #ifndef FCS_DISABLE_SIMPLE_SIMON
696 // Whether or not this is a Simple Simon-like game.
697 bool is_simple_simon;
698 #endif
699 };
700
701 #define fcs_st_instance(soft_thread) HT_INSTANCE((soft_thread)->hard_thread)
702
703 #define DFS_VAR(soft_thread, var) (soft_thread)->method_specific.soft_dfs.var
704 #define BEFS_VAR(soft_thread, var) \
705 (soft_thread)->method_specific.befs.meth.befs.var
706 #define BEFS_M_VAR(soft_thread, var) (soft_thread)->method_specific.befs.var
707 #define BRFS_VAR(soft_thread, var) \
708 (soft_thread)->method_specific.befs.meth.brfs.var
709
710 // An enum that specifies the meaning of each BeFS weight.
711 #define FCS_BEFS_WEIGHT_CARDS_OUT 0
712 #define FCS_BEFS_WEIGHT_MAX_SEQUENCE_MOVE 1
713 #define FCS_BEFS_WEIGHT_CARDS_UNDER_SEQUENCES 2
714 #define FCS_BEFS_WEIGHT_SEQS_OVER_RENEGADE_CARDS 3
715 #define FCS_BEFS_WEIGHT_DEPTH 4
716 #define FCS_BEFS_WEIGHT_NUM_CARDS_NOT_ON_PARENTS 5
717
718 #ifndef FCS_DISABLE_PATSOLVE
719 #include "pat.h"
720 #endif
721
722 extern fc_solve_solve_process_ret_t fc_solve_befs_or_bfs_do_solve(
723 fcs_soft_thread *const soft_thread);
724
memdup(const void * const src,const size_t my_size)725 static inline void *memdup(const void *const src, const size_t my_size)
726 {
727 void *const dest = malloc(my_size);
728 if (dest == NULL)
729 {
730 return NULL;
731 }
732
733 memcpy(dest, src, my_size);
734
735 return dest;
736 }
737
update_col_cards_under_sequences(const int sequences_are_built_by,const fcs_const_cards_column col,int d)738 static inline int update_col_cards_under_sequences(
739 #ifndef FCS_FREECELL_ONLY
740 const int sequences_are_built_by,
741 #endif
742 const fcs_const_cards_column col,
743 int d // One less than cards_num of col
744 )
745 {
746 fcs_card this_card = fcs_col_get_card(col, d);
747 fcs_card prev_card;
748 for (; (d > 0) && ({
749 prev_card = fcs_col_get_card(col, d - 1);
750 fcs_is_parent_card(this_card, prev_card);
751 });
752 d--, this_card = prev_card)
753 {
754 }
755 return d;
756 }
757
758 extern fcs_collectible_state *fc_solve_sfs_raymond_prune(
759 fcs_soft_thread *, fcs_kv_state);
760
761 #ifdef FCS_RCS_STATES
762 fcs_state *fc_solve_lookup_state_key_from_val(
763 fcs_instance *instance, const fcs_collectible_state *orig_ptr_state_val);
764
765 extern int fc_solve_compare_lru_cache_keys(const void *, const void *, void *);
766
767 #endif
768
769 extern void fc_solve_soft_thread_init_befs_or_bfs(
770 fcs_soft_thread *const soft_thread);
771
772 extern void fc_solve_free_soft_thread_by_depth_move_array(
773 fcs_soft_thread *const soft_thread);
774
moves_order_dup(fcs_moves_order * const orig)775 static inline fcs_moves_order moves_order_dup(fcs_moves_order *const orig)
776 {
777 const_SLOT(num, orig);
778 fcs_moves_order ret = (fcs_moves_order){.num = num,
779 #ifndef FCS_ZERO_FREECELLS_MODE
780 .groups = memdup(
781 orig->groups, sizeof(orig->groups[0]) *
782 ((num & (~(MOVES_GROW_BY - 1))) + MOVES_GROW_BY))
783 #endif
784 };
785 #ifndef FCS_ZERO_FREECELLS_MODE
786 for (size_t i = 0; i < num; ++i)
787 {
788 ret.groups[i].move_funcs = memdup(ret.groups[i].move_funcs,
789 sizeof(ret.groups[i].move_funcs[0]) *
790 ((ret.groups[i].num & (~(MOVES_GROW_BY - 1))) + MOVES_GROW_BY));
791 }
792 #endif
793
794 return ret;
795 }
796
797 extern fcs_soft_thread *fc_solve_new_soft_thread(
798 fcs_hard_thread *const hard_thread);
799
800 // This is the commmon code from fc_solve_instance__init_hard_thread() and
801 // recycle_hard_thread()
fc_solve_reset_hard_thread(fcs_hard_thread * const hard_thread)802 static inline void fc_solve_reset_hard_thread(
803 fcs_hard_thread *const hard_thread)
804 {
805 #ifndef FCS_SINGLE_HARD_THREAD
806 HT_FIELD(hard_thread, ht__num_checked_states) = 0;
807 #endif
808 HT_FIELD(hard_thread, ht__max_num_checked_states) = FCS_ITERS_INT_MAX;
809 HT_FIELD(hard_thread, num_soft_threads_finished) = 0;
810 }
811
fc_solve_reset_soft_thread(fcs_soft_thread * const soft_thread)812 static inline void fc_solve_reset_soft_thread(
813 fcs_soft_thread *const soft_thread)
814 {
815 STRUCT_CLEAR_FLAG(soft_thread, FCS_SOFT_THREAD_IS_FINISHED);
816 STRUCT_CLEAR_FLAG(soft_thread, FCS_SOFT_THREAD_INITIALIZED);
817 }
818
819 typedef enum
820 {
821 FOREACH_SOFT_THREAD_CLEAN_SOFT_DFS,
822 FOREACH_SOFT_THREAD_FREE_INSTANCE,
823 FOREACH_SOFT_THREAD_ACCUM_TESTS_ORDER,
824 FOREACH_SOFT_THREAD_DETERMINE_SCAN_COMPLETENESS
825 } foreach_st_callback_choice;
826
827 extern void fc_solve_foreach_soft_thread(fcs_instance *const instance,
828 const foreach_st_callback_choice callback_choice, void *const context);
829
moves_order__free(fcs_moves_order * moves_order)830 static inline void moves_order__free(fcs_moves_order *moves_order)
831 {
832 #ifndef FCS_ZERO_FREECELLS_MODE
833 const_SLOT(groups, moves_order);
834 const_SLOT(num, moves_order);
835 for (size_t group_idx = 0; group_idx < num; ++group_idx)
836 {
837 free(groups[group_idx].move_funcs);
838 }
839 free(groups);
840 moves_order->groups = NULL;
841 #endif
842 moves_order->num = 0;
843 }
844
845 #define MOVE_FUNC_ARGS \
846 fcs_soft_thread *const soft_thread GCC_UNUSED, \
847 fcs_kv_state raw_state_raw GCC_UNUSED, \
848 fcs_derived_states_list *const derived_states_list GCC_UNUSED
849
850 #define DECLARE_MOVE_FUNCTION(name) extern void name(MOVE_FUNC_ARGS)
851 #define DECLARE_PURE_MOVE_FUNCTION(name) extern void name(MOVE_FUNC_ARGS)
852
853 #ifndef FCS_HARD_CODE_CALC_REAL_DEPTH_AS_FALSE
fcs_get_calc_real_depth(const fcs_instance * const instance)854 static inline bool fcs_get_calc_real_depth(const fcs_instance *const instance)
855 {
856 return STRUCT_QUERY_FLAG(instance, FCS_RUNTIME_CALC_REAL_DEPTH);
857 }
858 #endif
859
860 #ifdef FCS_WITH_MOVES
861 extern void fc_solve_trace_solution(fcs_instance *const instance);
862 #endif
863 #ifdef __cplusplus
864 }
865 #endif
866