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 // state.h - header file for state functions and macros for Freecell Solver
9 #pragma once
10
11 #ifdef __cplusplus
12 extern "C" {
13 #endif
14
15 #include <ctype.h>
16 #include "freecell-solver/fcs_conf.h"
17 #include "freecell-solver/fcs_limit.h"
18
19 #ifdef FCS_WITH_MOVES
20 #include "freecell-solver/fcs_move.h"
21 #endif
22
23 #include "freecell-solver/fcs_enums.h"
24
25 #include "rinutils/rinutils.h"
26 #include "game_type_limit.h"
27
28 #include "internal_move_struct.h"
29 #include "indirect_buffer.h"
30
31 #define FCS_MAX_NUM_STACK_CARDS1 (MAX_NUM_INITIAL_CARDS_IN_A_STACK + 12)
32 #define FCS_MAX_NUM_STACK_CARDS2 (MAX_NUM_DECKS * 52)
33 #if FCS_MAX_NUM_STACK_CARDS1 > FCS_MAX_NUM_STACK_CARDS2
34 #define MAX_NUM_CARDS_IN_A_STACK FCS_MAX_NUM_STACK_CARDS2
35 #else
36 #define MAX_NUM_CARDS_IN_A_STACK FCS_MAX_NUM_STACK_CARDS1
37 #endif
38 #define FCS_CARDS_COL_WIDTH (MAX_NUM_CARDS_IN_A_STACK + 1)
39
40 #ifndef FCS_MAX_NUM_SCANS_BUCKETS
41 #define FCS_MAX_NUM_SCANS_BUCKETS 4
42 #endif
43
44 #define FCS_NUM_SUITS 4
45
46 #define FCS_CHAR_BIT_SIZE_LOG2 3
47 #define MAX_NUM_SCANS (FCS_MAX_NUM_SCANS_BUCKETS * (sizeof(unsigned char) * 8))
48
49 #define is_scan_visited(ptr_state, scan_id) \
50 ((FCS_S_SCAN_VISITED(ptr_state))[(scan_id) >> FCS_CHAR_BIT_SIZE_LOG2] & \
51 (1 << ((scan_id) & ((1 << (FCS_CHAR_BIT_SIZE_LOG2)) - 1))))
52
53 typedef uint_fast16_t stack_i;
54 typedef uint8_t fcs_card;
55 typedef fcs_card *fcs_cards_column;
56 typedef const fcs_card *fcs_const_cards_column;
57 typedef fcs_card fcs_state_foundation;
58
59 #ifdef COMPACT_STATES
60 // Card:
61 // Bits 0-3 - Card Number
62 // Bits 4-5 - Suit
63 typedef struct
64 {
65 fcs_card data[MAX_NUM_STACKS * FCS_CARDS_COL_WIDTH + MAX_NUM_FREECELLS +
66 4 * MAX_NUM_DECKS];
67 } fcs_state;
68
69 // Stack: 0 - Number of cards
70 // 1-19 - Cards
71 // Stacks: stack_num*20 where stack_num >= 0 and
72 // stack_num <= (MAX_NUM_STACKS-1)
73 // Bytes: (MAX_NUM_STACKS*20) to
74 // (MAX_NUM_STACKS*20+MAX_NUM_FREECELLS-1)
75 // are Freecells.
76 // Bytes: (MAX_NUM_STACKS*20+MAX_NUM_FREECELLS) to
77 // MAX_NUM_STACKS*20+MAX_NUM_FREECELLS+3
78 // are Foundations.
79 typedef char fcs_locs_type;
80
81 #define fcs_state_get_col(state, col_idx) \
82 ((state).data + ((col_idx)*FCS_CARDS_COL_WIDTH))
83 #define fcs_freecell_card(state, f) \
84 ((state).data[(MAX_NUM_STACKS * FCS_CARDS_COL_WIDTH) + (f)])
85 #define fcs_foundation_value(state, d) \
86 ((state).data[((MAX_NUM_STACKS * FCS_CARDS_COL_WIDTH) + \
87 MAX_NUM_FREECELLS) + \
88 (d)])
89
90 #elif defined(INDIRECT_STACK_STATES) // #ifdef COMPACT_STATES
91 typedef struct
92 {
93 fcs_cards_column columns[MAX_NUM_STACKS];
94 #if MAX_NUM_FREECELLS > 0
95 fcs_card freecells[MAX_NUM_FREECELLS];
96 #endif
97 fcs_state_foundation foundations[MAX_NUM_DECKS * 4];
98 } fcs_state;
99
100 #define fcs_state_get_col(state, col_idx) ((state).columns[(col_idx)])
101
102 #define fcs_freecell_card(state, f) ((state).freecells[(f)])
103
104 #define fcs_foundation_value(state, d) ((state).foundations[(d)])
105
106 #define fcs_copy_stack(state_key, state_val, idx, buffer) \
107 { \
108 if (!((state_val).stacks_copy_on_write_flags & (1 << idx))) \
109 { \
110 (state_val).stacks_copy_on_write_flags |= (1 << idx); \
111 const_AUTO(copy_stack_col, fcs_state_get_col((state_key), idx)); \
112 memcpy(&buffer[idx << 6], copy_stack_col, \
113 fcs_col_len(copy_stack_col) + 1); \
114 fcs_state_get_col((state_key), idx) = &buffer[idx << 6]; \
115 } \
116 }
117
118 #define fcs_duplicate_state_extra(dest_info) \
119 { \
120 (dest_info).stacks_copy_on_write_flags = 0; \
121 }
122
123 typedef uint8_t fcs_locs_type;
124
125 #else
126 #error Neither COMPACT_STATES nor INDIRECT_STACK_STATES are defined.
127 #endif
128
129 // These are macros or functions that are common to all the _STATES types.
130 #define fcs_increment_foundation(state, foundation_idx) \
131 (++(fcs_foundation_value((state), (foundation_idx))))
132 #define fcs_set_foundation(state, foundation_idx, value) \
133 ((fcs_foundation_value((state), (foundation_idx))) = \
134 (fcs_state_foundation)(value))
135 #define fcs_col_pop_top(col) \
136 (fcs_col_get_card((col), (--fcs_col_len(col))) = fc_solve_empty_card)
137 #define fcs_col_pop_card(col, into) \
138 { \
139 into = fcs_col_get_card((col), (fcs_col_len(col) - 1)); \
140 fcs_col_pop_top(col); \
141 }
142 #define fcs_col_push_card(col, from) \
143 fcs_col_get_card((col), ((fcs_col_len(col))++)) = (from)
144 #define fcs_freecell_is_empty(state, idx) \
145 (fcs_card_is_empty(fcs_freecell_card(state, idx)))
146
147 #if defined(COMPACT_STATES)
148
149 #define fcs_duplicate_state_extra(dest_info)
150 #define fcs_copy_stack(state_key, state_val, idx, buffer)
151
152 #endif
153
154 #define fcs_put_card_in_freecell(state, f, card) \
155 (fcs_freecell_card((state), (f)) = (card))
156
157 #define fcs_empty_freecell(state, f) \
158 fcs_put_card_in_freecell((state), (f), fc_solve_empty_card)
159
160 #define fcs_card_is_empty(card) ((card) == 0)
161 #define fcs_card_is_valid(card) ((card) != 0)
162
fcs_make_card(const fcs_card rank,const fcs_card suit)163 static inline fcs_card fcs_make_card(const fcs_card rank, const fcs_card suit)
164 {
165 return (fcs_card)((((fcs_card)rank) << 2) | ((fcs_card)suit));
166 }
167
168 #define fcs_card2char(c) (c)
169 #define fcs_char2card(c) (c)
170
171 #define fcs_col_len(col) (((col)[0]))
172 #define fcs_col_get_card(col, card_idx) ((col)[(card_idx) + 1])
173 #define fcs_state_col_len(s, i) fcs_col_len(fcs_state_get_col((s), (i)))
174 #define fcs_state_col_is_empty(s, i) (fcs_state_col_len((s), (i)) == 0)
175
176 #define fcs_card_rank(card) ((card) >> 2U)
177 #define fcs_card_suit(card) ((card)&0x03U)
178
fcs_col_get_rank(const fcs_const_cards_column col,const int card_idx)179 static inline fcs_card fcs_col_get_rank(
180 const fcs_const_cards_column col, const int card_idx)
181 {
182 return fcs_card_rank(fcs_col_get_card(col, card_idx));
183 }
184 #define FCS_RANK_KING FCS_MAX_RANK
185 #include "is_king.h"
fcs_card_is_king(const fcs_card card)186 static inline bool fcs_card_is_king(const fcs_card card)
187 {
188 return fc_solve_is_king_buf[(size_t)card];
189 }
190
fcs_col_is_king(const fcs_const_cards_column col,const stack_i card_idx)191 static inline bool fcs_col_is_king(
192 const fcs_const_cards_column col, const stack_i card_idx)
193 {
194 return fcs_card_is_king(fcs_col_get_card(col, card_idx));
195 }
196
197 struct fcs_state_keyval_pair_struct;
198
199 // NOTE: the order of elements here is intended to reduce framgmentation
200 // and memory consumption. Namely:
201 //
202 // 1. Pointers come first.
203 // 2. ints (32-bit on most platform) come next.
204 // 3. chars come next.
205 struct fcs_state_extra_info_struct
206 {
207 #ifdef FCS_RCS_STATES
208 struct fcs_state_extra_info_struct *parent;
209 #else
210 struct fcs_state_keyval_pair_struct *parent;
211 #endif
212 #ifdef FCS_WITH_MOVES
213 fcs_move_stack *moves_to_parent;
214 #endif
215
216 #ifdef FCS_WITH_DEPTH_FIELD
217 int depth;
218 #endif
219
220 #ifndef FCS_WITHOUT_VISITED_ITER
221 // The iteration in which this state was marked as visited
222 fcs_iters_int visited_iter;
223 #endif
224
225 // This is the number of direct children of this state which were not
226 // yet declared as dead ends. Once this counter reaches zero, this
227 // state too is declared as a dead end.
228 //
229 // It was converted to an unsigned short , because it is extremely
230 // unlikely that a state will have more than 64K active children.
231 unsigned short num_active_children;
232
233 // This field contains global, scan-independant flags, which are used
234 // from the FCS_VISITED_* enum below.
235 //
236 // FCS_VISITED_IN_SOLUTION_PATH - indicates that the state is in the
237 // solution path found by the scan. (used by the optimization scan)
238 //
239 // FCS_VISITED_IN_OPTIMIZED_PATH - indicates that the state is in the
240 // optimized solution path which is computed by the optimization scan.
241 //
242 // FCS_VISITED_DEAD_END - indicates that the state does not lead to
243 // anywhere useful, and scans should not examine it in the first place.
244 //
245 // FCS_VISITED_GENERATED_BY_PRUNING - indicates that the state was
246 // generated by pruning, so one can skip calling the pruning function
247 // for it.
248 fcs_game_limit visited;
249
250 // This is a vector of flags - one for each scan. Each indicates whether
251 // its scan has already visited this state
252 unsigned char scan_visited[FCS_MAX_NUM_SCANS_BUCKETS];
253
254 #ifdef INDIRECT_STACK_STATES
255 // A vector of flags that indicates which columns were already copied.
256 int stacks_copy_on_write_flags;
257 #endif
258 };
259
260 typedef struct
261 {
262 // These contain the location of the original columns and freecells
263 // in the permutation of them. They are sorted by the canonization
264 // function.
265 fcs_locs_type stack_locs[MAX_NUM_STACKS];
266 #if MAX_NUM_FREECELLS > 0
267 fcs_locs_type fc_locs[MAX_NUM_FREECELLS];
268 #endif
269 } fcs_state_locs_struct;
270
fc_solve_init_locs(fcs_state_locs_struct * const locs)271 static inline void fc_solve_init_locs(fcs_state_locs_struct *const locs)
272 {
273 for (int i = 0; i < MAX_NUM_STACKS; ++i)
274 {
275 locs->stack_locs[i] = (fcs_locs_type)i;
276 }
277 #if MAX_NUM_FREECELLS > 0
278 for (int i = 0; i < MAX_NUM_FREECELLS; ++i)
279 {
280 locs->fc_locs[i] = (fcs_locs_type)i;
281 }
282 #endif
283 }
284
285 typedef struct fcs_state_extra_info_struct fcs_state_extra_info;
286
287 struct fcs_state_keyval_pair_struct
288 {
289 union {
290 struct
291 {
292 fcs_state s;
293 fcs_state_extra_info info;
294 };
295 struct fcs_state_keyval_pair_struct *next;
296 };
297 };
298
299 typedef struct fcs_state_keyval_pair_struct fcs_state_keyval_pair;
300
301 typedef struct
302 {
303 fcs_state *key;
304 fcs_state_extra_info *val;
305 } fcs_kv_state;
306
FCS_STATE_keyval_pair_to_kv(fcs_state_keyval_pair * const s)307 static inline fcs_kv_state FCS_STATE_keyval_pair_to_kv(
308 fcs_state_keyval_pair *const s)
309 {
310 return (const fcs_kv_state){.key = &(s->s), .val = &(s->info)};
311 }
312
313 // Always the same.
314 #define fcs_duplicate_kv_state(ptr_dest, ptr_src) \
315 { \
316 *((ptr_dest)->key) = *((ptr_src)->key); \
317 *((ptr_dest)->val) = *((ptr_src)->val); \
318 fcs_duplicate_state_extra(*((ptr_dest)->val)); \
319 }
320
321 // This type is the struct that is collectible inside the hash.
322 //
323 // In FCS_RCS_STATES we only collect the extra_info's and the state themselves
324 // are kept in an LRU cache because they can be calculated from the
325 // extra_infos and the original state by applying the moves.
326 #ifdef FCS_RCS_STATES
327 typedef fcs_state_extra_info fcs_collectible_state;
328 #define FCS_S_ACCESSOR(s, field) ((s)->field)
329
330 #define fcs_duplicate_state(x, y) fcs_duplicate_kv_state((x), (y))
331
332 #define FCS_STATE_keyval_pair_to_collectible(s) (&((s)->info))
FCS_STATE_kv_to_collectible(fcs_kv_state * const s)333 static inline fcs_collectible_state *FCS_STATE_kv_to_collectible(
334 fcs_kv_state *const s)
335 {
336 return s->val;
337 }
338
FCS_STATE_collectible_to_kv(fcs_kv_state * const ret,fcs_collectible_state * const s)339 static inline void FCS_STATE_collectible_to_kv(
340 fcs_kv_state *const ret, fcs_collectible_state *const s)
341 {
342 ret->val = s;
343 }
344
345 #else
346
347 typedef fcs_state_keyval_pair fcs_collectible_state;
348
349 #define FCS_S_ACCESSOR(s, field) (((s)->info).field)
350
351 #define fcs_duplicate_state(ptr_dest, ptr_src) \
352 { \
353 *(ptr_dest) = *(ptr_src); \
354 fcs_duplicate_state_extra((ptr_dest)->info); \
355 }
356
357 #define FCS_STATE_keyval_pair_to_collectible(s) (s)
FCS_STATE_kv_to_collectible(fcs_kv_state * const s)358 static inline fcs_collectible_state *FCS_STATE_kv_to_collectible(
359 fcs_kv_state *const s)
360 {
361 return (fcs_collectible_state *)(s->key);
362 }
363
FCS_STATE_collectible_to_kv(fcs_kv_state * const ret,fcs_collectible_state * const s)364 static inline void FCS_STATE_collectible_to_kv(
365 fcs_kv_state *const ret, fcs_collectible_state *const s)
366 {
367 *ret = FCS_STATE_keyval_pair_to_kv(s);
368 }
369
370 #endif
371
372 #define FCS_S_NEXT(s) FCS_S_ACCESSOR(s, parent)
373 #define FCS_S_PARENT(s) FCS_S_ACCESSOR(s, parent)
374 #define FCS_S_NUM_ACTIVE_CHILDREN(s) FCS_S_ACCESSOR(s, num_active_children)
375 #define FCS_S_MOVES_TO_PARENT(s) FCS_S_ACCESSOR(s, moves_to_parent)
376 #define FCS_S_VISITED(s) FCS_S_ACCESSOR(s, visited)
377 #define FCS_S_SCAN_VISITED(s) FCS_S_ACCESSOR(s, scan_visited)
378 #ifdef FCS_WITH_DEPTH_FIELD
379 #define FCS_S_DEPTH(s) FCS_S_ACCESSOR(s, depth)
380 #endif
381 #ifndef FCS_WITHOUT_VISITED_ITER
382 #define FCS_S_VISITED_ITER(s) FCS_S_ACCESSOR(s, visited_iter)
383 #endif
384
385 #define fc_solve_empty_card ((fcs_card)0)
386
387 #ifdef HARD_CODED_NUM_FREECELLS
388 #define PASS_FREECELLS(arg)
389 #define FREECELLS_NUM__VAL HARD_CODED_NUM_FREECELLS
390 #else
391 #define PASS_FREECELLS(arg) , arg
392 #define FREECELLS_NUM__VAL freecells_num
393 #endif
394
395 #define FREECELLS_NUM__ARG PASS_FREECELLS(const size_t freecells_num)
396
397 #ifdef HARD_CODED_NUM_STACKS
398 #define PASS_STACKS(arg)
399 #define STACKS_NUM__VAL HARD_CODED_NUM_STACKS
400 #else
401 #define PASS_STACKS(arg) , arg
402 #define STACKS_NUM__VAL stacks_num
403 #endif
404
405 #define STACKS_NUM__ARG PASS_STACKS(const size_t stacks_num)
406
407 #ifdef HARD_CODED_NUM_DECKS
408 #define PASS_DECKS(arg)
409 #define DECKS_NUM__VAL HARD_CODED_NUM_DECKS
410 #else
411 #define PASS_DECKS(arg) , arg
412 #define DECKS_NUM__VAL decks_num
413 #endif
414
415 #define FREECELLS_AND_STACKS_ARGS() FREECELLS_NUM__ARG STACKS_NUM__ARG
416 #define FREECELLS_STACKS_DECKS__ARGS() \
417 FREECELLS_AND_STACKS_ARGS() PASS_DECKS(const size_t decks_num)
418
419 #define PASS_T(arg) FC_SOLVE__PASS_T(arg)
420
421 extern void fc_solve_canonize_state(
422 fcs_state *const ptr_state_key FREECELLS_AND_STACKS_ARGS());
423
424 void fc_solve_canonize_state_with_locs(fcs_state *const ptr_state_key,
425 fcs_state_locs_struct *const locs FREECELLS_AND_STACKS_ARGS());
426
427 #if (FCS_STATE_STORAGE != FCS_STATE_STORAGE_LIBREDBLACK_TREE)
428 typedef void *fcs_compare_context;
429 #else
430 typedef const void *fcs_compare_context;
431 #endif
432
fc_solve_state_compare(const void * const s1,const void * const s2)433 static inline int fc_solve_state_compare(
434 const void *const s1, const void *const s2)
435 {
436 return memcmp(s1, s2, sizeof(fcs_state));
437 }
438
439 #if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_HASH)
440 extern int fc_solve_state_compare_equal(const void *, const void *);
441 #endif
442 extern int fc_solve_state_compare_with_context(
443 const void *, const void *, fcs_compare_context);
444
445 // Convert an entire card to its user representation.
446 extern void fc_solve_card_stringify(
447 const fcs_card card, char *const str PASS_T(const bool t));
448
449 #ifdef FC_SOLVE__STRICTER_BOARD_PARSING
450 #define FC_SOLVE_MAP_CHAR(c) (c)
451 #else
452 #define FC_SOLVE_MAP_CHAR(c) (toupper(c))
453 #endif
454
455 // This function converts a string containing a suit letter (that is
456 // one of H,S,D,C) into its suit ID.
457 //
458 // The suit letter may come somewhat after the beginning of the string.
fcs_str2suit(const char * suit)459 static inline __attribute__((pure)) fcs_card fcs_str2suit(const char *suit)
460 {
461 while (true)
462 {
463 switch (FC_SOLVE_MAP_CHAR(*suit))
464 {
465 case 'H':
466 case ' ':
467 case '\0':
468 return 0;
469 case 'C':
470 return 1;
471 case 'D':
472 return 2;
473 case 'S':
474 return 3;
475 default:
476 ++suit;
477 }
478 }
479 }
480
481 // This function converts a card number from its user representation
482 // (e.g: "A", "K", "9") to its card number that can be used by the program.
fcs_str2rank(const char * string)483 static inline __attribute__((pure)) fcs_card fcs_str2rank(const char *string)
484 {
485 while (1)
486 {
487 switch (FC_SOLVE_MAP_CHAR(*string))
488 {
489 case '\0':
490 case ' ':
491 case '\t':
492 case '\n':
493 case '\r':
494 return 0;
495 case 'A':
496 return 1;
497 case 'J':
498 return 11;
499 case 'Q':
500 return 12;
501 case 'K':
502 return 13;
503 #ifndef FC_SOLVE__STRICTER_BOARD_PARSING
504 case '1':
505 return (string[1] == '0') ? 10 : 1;
506 #endif
507 case 'T':
508 #ifndef FC_SOLVE__STRICTER_BOARD_PARSING
509 case '0':
510 #endif
511 return 10;
512 case '2':
513 return 2;
514 case '3':
515 return 3;
516 case '4':
517 return 4;
518 case '5':
519 return 5;
520 case '6':
521 return 6;
522 case '7':
523 return 7;
524 case '8':
525 return 8;
526 case '9':
527 return 9;
528 default:
529 ++string;
530 }
531 }
532 }
533 // This function converts an entire card from its string representations
534 // (e.g: "AH", "KS", "8D"), to a fcs_card data type.
fc_solve_card_parse_str(const char * const str)535 static inline __attribute__((pure)) fcs_card fc_solve_card_parse_str(
536 const char *const str)
537 {
538 return fcs_make_card(fcs_str2rank(str), fcs_str2suit(str));
539 }
540
541 #ifdef INDIRECT_STACK_STATES
542 #define fc_solve_state_init(state, stacks_num, indirect_stacks_buffer) \
543 fc_solve_state_init_proto( \
544 state PASS_STACKS(stacks_num), indirect_stacks_buffer)
545 #else
546 #define fc_solve_state_init(state, stacks_num, indirect_stacks_buffer) \
547 fc_solve_state_init_proto(state PASS_STACKS(stacks_num))
548 #endif
549
fc_solve_state_init_proto(fcs_state_keyval_pair * const state STACKS_NUM__ARG GCC_UNUSED IND_BUF_T_PARAM (indirect_stacks_buffer))550 static inline void fc_solve_state_init_proto(fcs_state_keyval_pair *const state
551 STACKS_NUM__ARG GCC_UNUSED IND_BUF_T_PARAM(indirect_stacks_buffer))
552 {
553 memset(&(state->s), 0, sizeof(state->s));
554 #ifdef INDIRECT_STACK_STATES
555 size_t i;
556 for (i = 0; i < STACKS_NUM__VAL; ++i)
557 {
558 memset(state->s.columns[i] = &indirect_stacks_buffer[i << 6], '\0',
559 1 * 52 + 1);
560 }
561 for (; i < MAX_NUM_STACKS; ++i)
562 {
563 state->s.columns[i] = NULL;
564 }
565 #endif
566 state->info.parent = NULL;
567 #ifdef FCS_WITH_MOVES
568 state->info.moves_to_parent = NULL;
569 #endif
570 #ifdef FCS_WITH_DEPTH_FIELD
571 state->info.depth = 0;
572 #endif
573 state->info.visited = 0;
574 #ifndef FCS_WITHOUT_VISITED_ITER
575 state->info.visited_iter = 0;
576 #endif
577 state->info.num_active_children = 0;
578 memset(state->info.scan_visited, '\0', sizeof(state->info.scan_visited));
579 #ifdef INDIRECT_STACK_STATES
580 state->info.stacks_copy_on_write_flags = 0;
581 #endif
582 }
583
584 #ifdef FCS_BREAK_BACKWARD_COMPAT_1
585 #define FCS_PARSE_try_prefix(str, p, p_s) try_str_prefix(str, p)
586 #else
587 #if MAX_NUM_FREECELLS > 0
588 static const char *const fc_solve_freecells_prefixes[] = {
589 "FC:", "Freecells:", "Freecell:", NULL};
590 #endif
591
592 static const char *const fc_solve_foundations_prefixes[] = {"Decks:", "Deck:",
593 "Founds:", "Foundations:", "Foundation:", "Found:", NULL};
594
fc_solve__try_prefixes(const char * const str,const char * const * const prefixes)595 static inline __attribute__((pure)) const char *fc_solve__try_prefixes(
596 const char *const str, const char *const *const prefixes)
597 {
598 for (const char *const *prefix = prefixes; (*prefix); ++prefix)
599 {
600 if (!strncasecmp(str, (*prefix), strlen(*prefix)))
601 {
602 return str + strlen(*prefix);
603 }
604 }
605 return NULL;
606 }
607 #define FCS_PARSE_try_prefix(str, p, p_s) fc_solve__try_prefixes(str, p_s)
608 #endif
609 #if defined(WIN32) && (!defined(HAVE_STRNCASECMP))
610 #ifndef strncasecmp
611 #define strncasecmp(a, b, c) (strnicmp((a), (b), (c)))
612 #endif
613 #endif
614
615 #define fc_solve_initial_user_state_to_c(string, out_state, freecells_num, \
616 stacks_num, decks_num, indirect_stacks_buffer) \
617 fc_solve_initial_user_state_to_c_proto(string, \
618 out_state PASS_FREECELLS(freecells_num) PASS_STACKS(stacks_num) \
619 PASS_DECKS(decks_num) PASS_IND_BUF_T(indirect_stacks_buffer))
620
fc_solve_initial_user_state_to_c_proto(const char * const string,fcs_state_keyval_pair * const out_state FREECELLS_STACKS_DECKS__ARGS ()IND_BUF_T_PARAM (indirect_stacks_buffer))621 static inline bool fc_solve_initial_user_state_to_c_proto(
622 const char *const string,
623 fcs_state_keyval_pair *const out_state FREECELLS_STACKS_DECKS__ARGS()
624 IND_BUF_T_PARAM(indirect_stacks_buffer))
625 {
626 fc_solve_state_init(out_state, STACKS_NUM__VAL, indirect_stacks_buffer);
627 const char *str = string;
628
629 bool first_line = true;
630
631 #define out (out_state->s)
632 // Handle the end of string - shouldn't happen
633 #ifdef FCS_BREAK_BACKWARD_COMPAT_2
634 #define HANDLE_EOS() \
635 { \
636 if ((*str) == '\0') \
637 { \
638 return false; \
639 } \
640 }
641 #else
642 #define HANDLE_EOS() \
643 { \
644 if ((*str) == '\0') \
645 { \
646 goto end_of_loop; \
647 } \
648 }
649 #endif
650
651 size_t s;
652 for (s = 0; s < STACKS_NUM__VAL; ++s)
653 {
654 // Move to the next stack
655 if (!first_line)
656 {
657 while ((*str) != '\n')
658 {
659 HANDLE_EOS();
660 ++str;
661 }
662 ++str;
663 }
664
665 first_line = false;
666
667 #if MAX_NUM_FREECELLS > 0
668 const_AUTO(new_str, FCS_PARSE_try_prefix(str,
669 "Freecells:", fc_solve_freecells_prefixes));
670 if (new_str)
671 {
672 str = new_str;
673 for (size_t c = 0; c < FREECELLS_NUM__VAL; ++c)
674 {
675 fcs_empty_freecell(out, c);
676 }
677 for (size_t c = 0; c < FREECELLS_NUM__VAL; ++c)
678 {
679 if (c != 0)
680 {
681 while (((*str) != ' ') && ((*str) != '\t') &&
682 ((*str) != '\n') && ((*str) != '\r'))
683 {
684 HANDLE_EOS();
685 ++str;
686 }
687 if ((*str == '\n') || (*str == '\r'))
688 {
689 break;
690 }
691 ++str;
692 }
693
694 while ((*str == ' ') || (*str == '\t'))
695 {
696 ++str;
697 }
698 if ((*str == '\r') || (*str == '\n'))
699 break;
700
701 fcs_put_card_in_freecell(out, c,
702 ((*str == '*') || (*str == '-')) ? fc_solve_empty_card : ({
703 const fcs_card rank = fcs_str2rank(str);
704 if (!rank)
705 {
706 return false;
707 }
708 fcs_make_card(rank, fcs_str2suit(str));
709 }));
710 }
711
712 while (*str != '\n')
713 {
714 HANDLE_EOS();
715 ++str;
716 }
717 --s;
718 continue;
719 }
720 #endif
721
722 const_AUTO(new_str2, FCS_PARSE_try_prefix(str, "Foundations:",
723 fc_solve_foundations_prefixes));
724 if (new_str2)
725 {
726 str = new_str2;
727 for (size_t f_idx = 0; f_idx < (DECKS_NUM__VAL << 2); ++f_idx)
728 {
729 fcs_set_foundation(out, f_idx, 0);
730 }
731
732 size_t decks_index[4] = {0, 0, 0, 0};
733 while (1)
734 {
735 while ((*str == ' ') || (*str == '\t'))
736 ++str;
737 if ((*str == '\n') || (*str == '\r'))
738 break;
739 const size_t f_idx = fcs_str2suit(str);
740 ++str;
741 while (*str == '-')
742 ++str;
743 // Workaround for fcs_str2rank's willingness to designate the
744 // string '0' as 10.
745 const int c = ((str[0] == '0') ? 0 : fcs_str2rank(str));
746 while ((*str != ' ') && (*str != '\t') && (*str != '\n') &&
747 (*str != '\r'))
748 {
749 HANDLE_EOS();
750 ++str;
751 }
752
753 fcs_set_foundation(out, ((decks_index[f_idx] << 2) + f_idx), c);
754 if ((++decks_index[f_idx]) >= DECKS_NUM__VAL)
755 {
756 decks_index[f_idx] = 0;
757 }
758 }
759 s--;
760 continue;
761 }
762
763 // Handle columns that start with an initial colon, so we can input
764 // states from -p -t mid-play.
765 if ((*str) == ':')
766 {
767 ++str;
768 }
769
770 var_AUTO(col, fcs_state_get_col(out, s));
771 for (int c = 0; c < MAX_NUM_CARDS_IN_A_STACK; ++c)
772 {
773 // Move to the next card
774 if (c != 0)
775 {
776 while (((*str) != ' ') && ((*str) != '\t') &&
777 ((*str) != '\n') && ((*str) != '\r'))
778 {
779 HANDLE_EOS();
780 ++str;
781 }
782 if ((*str == '\n') || (*str == '\r'))
783 {
784 break;
785 }
786 }
787
788 while ((*str == ' ') || (*str == '\t'))
789 {
790 ++str;
791 }
792 HANDLE_EOS();
793 if ((*str == '\n') || (*str == '\r'))
794 {
795 break;
796 }
797 const_AUTO(my_card, fc_solve_card_parse_str(str));
798 if (!fcs_card_rank(my_card))
799 {
800 return false;
801 }
802 fcs_col_push_card(col, my_card);
803 }
804 #ifndef FCS_BREAK_BACKWARD_COMPAT_2
805 end_of_loop:;
806 #endif
807 }
808
809 #ifdef FCS_BREAK_BACKWARD_COMPAT_2
810 return true;
811 #else
812 return s == STACKS_NUM__VAL;
813 #endif
814 }
815
816 #undef out
817 #undef HANDLE_EOS
818
819 extern void fc_solve_state_as_string(char *output_s,
820 const fcs_state *const state,
821 const fcs_state_locs_struct *const state_locs FREECELLS_STACKS_DECKS__ARGS()
822 FC_SOLVE__PASS_PARSABLE(const bool parseable_output),
823 const bool canonized_order_output PASS_T(const bool display_10_as_t));
824
825 typedef enum
826 {
827 FCS_STATE_VALIDITY__OK = 0,
828 FCS_STATE_VALIDITY__MISSING_CARD = 1,
829 FCS_STATE_VALIDITY__EXTRA_CARD = 2,
830 FCS_STATE_VALIDITY__EMPTY_SLOT = 3,
831 FCS_STATE_VALIDITY__PREMATURE_END_OF_INPUT = 4
832 } state_validity_ret;
833
834 #ifndef FCS_DISABLE_STATE_VALIDITY_CHECK
fc_solve_check_state_validity(const fcs_state_keyval_pair * const state_pair FREECELLS_STACKS_DECKS__ARGS (),fcs_card * const misplaced_card)835 static inline state_validity_ret fc_solve_check_state_validity(
836 const fcs_state_keyval_pair *const state_pair
837 FREECELLS_STACKS_DECKS__ARGS(),
838 fcs_card *const misplaced_card)
839 {
840 size_t card_counts[FCS_NUM_SUITS][FCS_MAX_RANK + 1];
841
842 const fcs_state *const state = &(state_pair->s);
843
844 for (int suit_idx = 0; suit_idx < FCS_NUM_SUITS; suit_idx++)
845 {
846 for (int c = 1; c <= FCS_MAX_RANK; c++)
847 {
848 card_counts[suit_idx][c] = 0;
849 }
850 }
851
852 // Mark the card_counts in the decks
853 for (size_t suit_idx = 0; suit_idx < (DECKS_NUM__VAL << 2); ++suit_idx)
854 {
855 for (int c = 1; c <= fcs_foundation_value(*state, suit_idx); c++)
856 {
857 card_counts[suit_idx % FCS_NUM_SUITS][c]++;
858 }
859 }
860
861 #if MAX_NUM_FREECELLS > 0
862 // Mark the card_counts in the freecells
863 for (size_t f = 0; f < FREECELLS_NUM__VAL; ++f)
864 {
865 const fcs_card card = fcs_freecell_card(*state, f);
866 if (fcs_card_is_valid(card))
867 {
868 card_counts[fcs_card_suit(card)][fcs_card_rank(card)]++;
869 }
870 }
871 #endif
872
873 // Mark the card_counts in the columns
874 for (size_t s = 0; s < STACKS_NUM__VAL; ++s)
875 {
876 const_AUTO(col, fcs_state_get_col(*state, s));
877 const int col_len = fcs_col_len(col);
878 for (int c = 0; c < col_len; c++)
879 {
880 const fcs_card card = fcs_col_get_card(col, c);
881 if (fcs_card_is_empty(card))
882 {
883 *misplaced_card = fc_solve_empty_card;
884 return FCS_STATE_VALIDITY__EMPTY_SLOT;
885 }
886 ++card_counts[fcs_card_suit(card)][fcs_card_rank(card)];
887 }
888 }
889
890 // Now check if there are extra or missing card_counts
891 for (size_t suit_idx = 0; suit_idx < FCS_NUM_SUITS; suit_idx++)
892 {
893 for (size_t rank = 1; rank <= FCS_MAX_RANK; rank++)
894 {
895 if (card_counts[suit_idx][rank] != DECKS_NUM__VAL)
896 {
897 *misplaced_card =
898 fcs_make_card((fcs_card)rank, (fcs_card)suit_idx);
899 return ((card_counts[suit_idx][rank] < DECKS_NUM__VAL)
900 ? FCS_STATE_VALIDITY__MISSING_CARD
901 : FCS_STATE_VALIDITY__EXTRA_CARD);
902 }
903 }
904 }
905
906 return FCS_STATE_VALIDITY__OK;
907 }
908 #endif
909
910 #undef state
911
912 #ifdef __cplusplus
913 }
914 #endif
915
916 enum
917 {
918 FCS_VISITED_IN_SOLUTION_PATH = 0x1,
919 FCS_VISITED_IN_OPTIMIZED_PATH = 0x2,
920 FCS_VISITED_DEAD_END = 0x4,
921 FCS_VISITED_ALL_TESTS_DONE = 0x8,
922 FCS_VISITED_GENERATED_BY_PRUNING = 0x10,
923 };
924
fc_solve_card_compare(const fcs_card c1,const fcs_card c2)925 static inline int fc_solve_card_compare(const fcs_card c1, const fcs_card c2)
926 {
927 return (c1) - (c2);
928 }
929
930 #ifdef INDIRECT_STACK_STATES
fc_solve_stack_compare_for_comparison(const void * const v_s1,const void * const v_s2)931 static inline int fc_solve_stack_compare_for_comparison(
932 const void *const v_s1, const void *const v_s2)
933 {
934 const fcs_card *const s1 = (const fcs_card *const)v_s1;
935 const fcs_card *const s2 = (const fcs_card *const)v_s2;
936
937 {
938 #ifdef __cplusplus
939 using std::min;
940 #endif
941 const int min_len = min(s1[0], s2[0]);
942 for (int a = 1; a <= min_len; a++)
943 {
944 const int ret = fc_solve_card_compare(s1[a], s2[a]);
945 if (ret != 0)
946 {
947 return ret;
948 }
949 }
950 }
951 // The reason I do the stack length comparisons after the card-by-card
952 // comparison is to maintain correspondence with
953 // fcs_stack_compare_for_stack_sort, and with the one card comparison
954 // of the other state representation mechanisms.
955 // For some reason this code is faster than s1[0]-s2[0] */
956 if (s1[0] < s2[0])
957 {
958 return -1;
959 }
960 else if (s1[0] > s2[0])
961 {
962 return 1;
963 }
964 else
965 {
966 return 0;
967 }
968 }
969
fc_solve_stack_compare_for_canonize(const void * const v_s1,const void * const v_s2)970 static inline int fc_solve_stack_compare_for_canonize(
971 const void *const v_s1, const void *const v_s2)
972 {
973 const fcs_card *const s1 = (const fcs_card *const)v_s1;
974 const fcs_card *const s2 = (const fcs_card *const)v_s2;
975
976 {
977 #ifdef __cplusplus
978 using std::min;
979 #endif
980 const int min_len = min(s1[0], s2[0]);
981 if (min_len)
982 {
983 return fc_solve_card_compare(s1[1], s2[1]);
984 }
985 }
986 // The reason I do the stack length comparisons after the card-by-card
987 // comparison is to maintain correspondence with
988 // fcs_stack_compare_for_stack_sort, and with the one card comparison
989 // of the other state representation mechanisms.
990
991 // For some reason this code is faster than s1[0]-s2[0]
992 if (s1[0] < s2[0])
993 {
994 return -1;
995 }
996 else if (s1[0] > s2[0])
997 {
998 return 1;
999 }
1000 else
1001 {
1002 return 0;
1003 }
1004 }
1005 #endif
1006
set_scan_visited(fcs_collectible_state * const ptr_state,const size_t scan_id)1007 static inline void set_scan_visited(
1008 fcs_collectible_state *const ptr_state, const size_t scan_id)
1009 {
1010 (FCS_S_SCAN_VISITED(ptr_state))[scan_id >> FCS_CHAR_BIT_SIZE_LOG2] |=
1011 (1 << ((scan_id) & ((1 << (FCS_CHAR_BIT_SIZE_LOG2)) - 1)));
1012 }
1013
1014 // This macro determines if child can be placed above parent.
1015 //
1016 // The variable sequences_are_built_by has to be initialized to
1017 // the sequences_are_built_by member of the instance.
1018
1019 #ifdef FCS_FREECELL_ONLY
1020
1021 #include "is_parent.h"
fcs_is_parent_card(const fcs_card child,const fcs_card parent)1022 static inline bool fcs_is_parent_card(
1023 const fcs_card child, const fcs_card parent)
1024 {
1025 return fc_solve_is_parent_buf[(size_t)parent][(size_t)child];
1026 }
1027 #define FCS__SEQS_ARE_BUILT_BY_RANK() false
1028
1029 #else
1030
fcs_is_parent_card__helper(const fcs_card child,const fcs_card parent,const int sequences_are_built_by)1031 static inline bool fcs_is_parent_card__helper(const fcs_card child,
1032 const fcs_card parent, const int sequences_are_built_by)
1033 {
1034 return ((fcs_card_rank(child) + 1 == fcs_card_rank(parent)) &&
1035 ((sequences_are_built_by == FCS_SEQ_BUILT_BY_RANK)
1036 ? true
1037 : ((sequences_are_built_by == FCS_SEQ_BUILT_BY_SUIT)
1038 ? (fcs_card_suit(child) == fcs_card_suit(parent))
1039 : ((fcs_card_suit(child) & 0x1) !=
1040 (fcs_card_suit(parent) & 0x1)))));
1041 }
1042 #define fcs_is_parent_card(child, parent) \
1043 fcs_is_parent_card__helper(child, parent, sequences_are_built_by)
1044
1045 #define FCS__SEQS_ARE_BUILT_BY_RANK() \
1046 (sequences_are_built_by == FCS_SEQ_BUILT_BY_RANK)
1047
1048 #endif
1049
1050 #define FCS_STATE__DUP_keyval_pair(dest, src) \
1051 { \
1052 (dest) = (src); \
1053 fcs_duplicate_state_extra((dest).info); \
1054 }
1055
fcs_col_transfer_cards(fcs_cards_column dest_col,fcs_cards_column src_col,const size_t cards_num)1056 static inline void fcs_col_transfer_cards(
1057 fcs_cards_column dest_col, fcs_cards_column src_col, const size_t cards_num)
1058 {
1059 fcs_card *const src_cards_ptr =
1060 &fcs_col_get_card(src_col, (fcs_col_len(src_col) -= cards_num));
1061 const size_t cards_size = (((size_t)cards_num) * sizeof(fcs_card));
1062 memcpy(&fcs_col_get_card(dest_col, fcs_col_len(dest_col)), src_cards_ptr,
1063 cards_size);
1064 fcs_col_len(dest_col) += cards_num;
1065 memset(src_cards_ptr, 0, cards_size);
1066 }
1067
fcs_state_pop_col_card(fcs_state * const state,const stack_i col_idx)1068 static inline fcs_card fcs_state_pop_col_card(
1069 fcs_state *const state, const stack_i col_idx)
1070 {
1071 var_AUTO(col, fcs_state_get_col(*state, col_idx));
1072 fcs_card ret;
1073 fcs_col_pop_card(col, ret);
1074 return ret;
1075 }
1076
fcs_state_pop_col_top(fcs_state * const state,const size_t col_idx)1077 static inline void fcs_state_pop_col_top(
1078 fcs_state *const state, const size_t col_idx)
1079 {
1080 var_AUTO(col, fcs_state_get_col(*state, col_idx));
1081 fcs_col_pop_top(col);
1082 }
1083
fcs_state_push(fcs_state * const state,const size_t col_idx,const fcs_card card)1084 static inline void fcs_state_push(
1085 fcs_state *const state, const size_t col_idx, const fcs_card card)
1086 {
1087 var_AUTO(col, fcs_state_get_col(*state, col_idx));
1088 fcs_col_push_card(col, card);
1089 }
1090