diff --git a/dealer.h b/dealer.h --- a/dealer.h +++ b/dealer.h @@ -47,7 +47,6 @@ class SolverThread; #include "speeds.h" #include "view.h" -#include "patsolve/patsolve.h" #include "KCardDeck" #include "KCardScene" diff --git a/libkcardgame/kcardscene.cpp b/libkcardgame/kcardscene.cpp --- a/libkcardgame/kcardscene.cpp +++ b/libkcardgame/kcardscene.cpp @@ -49,9 +49,6 @@ #include -#define DEBUG_LAYOUT 0 - - namespace { const int cardMoveDuration = 230; @@ -1249,31 +1246,6 @@ { Q_UNUSED( painter ) Q_UNUSED( rect ) - -#if DEBUG_LAYOUT - if ( !d->sizeHasBeenSet || !d->deck ) - return; - - painter->setPen( Qt::yellow ); - painter->drawRect( 0, 0, d->contentSize.width(), d->contentSize.height() ); - - foreach ( const KCardPile * p, piles() ) - { - if ( !p->isVisible() ) - continue; - - QRectF availableRect = multRectSize( d->pileAreas.value( p, QRectF() ), d->deck->cardSize() ); - - QRectF reservedRect( -p->leftPadding(), -p->topPadding(), 1 + p->rightPadding(), 1 + p->bottomPadding() ); - reservedRect = multRectSize( reservedRect, d->deck->cardSize() ); - reservedRect.translate( p->pos() ); - - painter->setPen( Qt::cyan ); - painter->drawRect( availableRect ); - painter->setPen( QPen( Qt::red, 1, Qt::DotLine, Qt::FlatCap ) ); - painter->drawRect( reservedRect ); - } -#endif } diff --git a/patsolve/fortyeightsolver.cpp b/patsolve/fortyeightsolver.cpp --- a/patsolve/fortyeightsolver.cpp +++ b/patsolve/fortyeightsolver.cpp @@ -21,8 +21,10 @@ #include -#define NUM_PILE 8 -#define NUM_DECK 9 +namespace { +constexpr auto NUM_PILE = 8; +constexpr auto NUM_DECK = 9; +} #define PRINT 0 diff --git a/patsolve/freecellsolver.cpp b/patsolve/freecellsolver.cpp --- a/patsolve/freecellsolver.cpp +++ b/patsolve/freecellsolver.cpp @@ -23,10 +23,12 @@ /* Some macros used in get_possible_moves(). */ -/* The following macro implements +/* The following function implements (Same_suit ? (suit(a) == suit(b)) : (color(a) != color(b))) */ -#define suitable(a, b) ((((a) ^ (b)) & PS_COLOR) == PS_COLOR) +namespace { + constexpr bool suitable(const card_t a, const card_t b) {return ((a ^ b) & PS_COLOR) == PS_COLOR; } +} /* Statistics. */ @@ -89,7 +91,9 @@ possible moves, but few productive ones. Note that we also prioritize positions when they are added to the queue. */ -#define NNEED 8 +namespace { + constexpr auto NNEED = 8; +} void FreecellSolver::prioritize(MOVE *mp0, int n) { diff --git a/patsolve/idiotsolver.cpp b/patsolve/idiotsolver.cpp --- a/patsolve/idiotsolver.cpp +++ b/patsolve/idiotsolver.cpp @@ -296,7 +296,7 @@ if ( Wlen[pile] == 0 ) return false; for ( int i = 0; i < 4; ++i ) - Q_ASSERT( Wp[i] = &W[i][Wlen[i] - 1] ); + Q_ASSERT( Wp[i] == &W[i][Wlen[i] - 1] ); return ( ( Wlen[0] && higher( *Wp[pile], *Wp[0] ) ) || ( Wlen[1] && higher( *Wp[pile], *Wp[1] ) ) || ( Wlen[2] && higher( *Wp[pile], *Wp[2] ) ) || diff --git a/patsolve/memory.h b/patsolve/memory.h --- a/patsolve/memory.h +++ b/patsolve/memory.h @@ -92,7 +92,12 @@ }; -#define new_array( type, size ) ( type* )MemoryManager::allocate_memory( ( size )*sizeof( type ) ); -#define mm_allocate( type ) ( type* )MemoryManager::allocate_memory( sizeof( type ) ); +template +T* mm_new_array(const size_t size) { + return static_cast(MemoryManager::allocate_memory(size * sizeof(T))); +} + +template +T* mm_allocate() {return static_cast(MemoryManager::allocate_memory(sizeof(T)));} #endif // MEMORY_H diff --git a/patsolve/memory.cpp b/patsolve/memory.cpp --- a/patsolve/memory.cpp +++ b/patsolve/memory.cpp @@ -115,7 +115,7 @@ /* If we didn't find it, make a new one and add it to the list. */ if (tl == nullptr) { - tl = mm_allocate(TREELIST); + tl = mm_allocate(); if (tl == nullptr) { return nullptr; } @@ -138,11 +138,11 @@ { BLOCK *b; - b = mm_allocate(BLOCK); + b = mm_allocate(); if (b == nullptr) { return nullptr; } - b->block = new_array(quint8, BLOCKSIZE); + b->block = mm_new_array(BLOCKSIZE); if (b->block == nullptr) { MemoryManager::free_ptr(b); return nullptr; diff --git a/patsolve/patsolve.h b/patsolve/patsolve.h --- a/patsolve/patsolve.h +++ b/patsolve/patsolve.h @@ -80,7 +80,6 @@ Solver(); virtual ~Solver(); ExitStatus patsolve( int max_positions = -1, bool debug = false); - bool recursive(POSITION *pos = nullptr); virtual void translate_layout() = 0; bool m_shouldEnd; QMutex endMutex; @@ -141,13 +140,13 @@ POSITION *Freepos; -#define MAXMOVES 64 /* > max # moves from any position */ + static constexpr auto MAXMOVES = 64; /* > max # moves from any position */ MOVE Possible[MAXMOVES]; MemoryManager *mm; ExitStatus Status; /* win, lose, or fail */ -#define NQUEUES 127 + static constexpr auto NQUEUES = 127; POSITION *Qhead[NQUEUES]; /* separate queue for each priority */ int Maxq; @@ -163,22 +162,23 @@ /* Misc. */ -#define PS_DIAMOND 0x00 /* red */ -#define PS_CLUB 0x10 /* black */ -#define PS_HEART 0x20 /* red */ -#define PS_SPADE 0x30 /* black */ -#define PS_BLACK 0x10 -#define PS_COLOR 0x10 /* black if set */ -#define PS_SUIT 0x30 /* mask both suit bits */ - -#define NONE 0 -#define PS_ACE 1 -#define PS_KING 13 - -#define RANK(card) ((card) & 0xF) -#define SUIT(card) (( (card) >> 4 ) & 3) -#define COLOR(card) ((card) & PS_COLOR) -#define DOWN(card) ((card) & ( 1 << 7 ) ) +constexpr card_t PS_DIAMOND = 0x00; /* red */ +constexpr card_t PS_CLUB = 0x10; /* black */ +constexpr card_t PS_HEART = 0x20; /* red */ +constexpr card_t PS_SPADE = 0x30; /* black */ +constexpr card_t PS_BLACK = 0x10; +constexpr card_t PS_COLOR = 0x10; /* black if set */ +constexpr card_t PS_SUIT = 0x30; /* mask both suit bits */ + +constexpr card_t NONE = 0; +constexpr card_t PS_ACE = 1; +constexpr card_t PS_KING = 13; + +constexpr card_t RANK(card_t card) {return card & 0xF;} +constexpr card_t SUIT(card_t card) {return (card >> 4 ) & 3;} + +constexpr card_t COLOR(card_t card) {return card & PS_COLOR;} +constexpr card_t DOWN(card_t card) {return (card) & ( 1 << 7 );} extern long all_moves; diff --git a/patsolve/patsolve.cpp b/patsolve/patsolve.cpp --- a/patsolve/patsolve.cpp +++ b/patsolve/patsolve.cpp @@ -42,30 +42,15 @@ /* This is a 32 bit FNV hash. For more information, see http://www.isthe.com/chongo/tech/comp/fnv/index.html */ -#define FNV1_32_INIT 0x811C9DC5 -#define FNV_32_PRIME 0x01000193 - -#define fnv_hash(x, hash) (((hash) * FNV_32_PRIME) ^ (x)) - -/* Hash a buffer. */ - -static inline quint32 fnv_hash_buf(quint8 *s, int len) -{ - int i; - quint32 h; - - h = FNV1_32_INIT; - for (i = 0; i < len; i++) { - h = fnv_hash(*s++, h); - } - - return h; -} +namespace { +constexpr qint32 FNV_32_PRIME = 0x01000193; // FIXME: move into fnv_hash once we depend on C++14 +constexpr qint32 fnv_hash(qint32 x, qint32 hash) {return (hash * FNV_32_PRIME) ^ x;} /* Hash a 0 terminated string. */ -static inline quint32 fnv_hash_str(quint8 *s) +quint32 fnv_hash_str(const quint8 *s) { + constexpr qint32 FNV1_32_INIT = 0x811C9DC5; quint32 h; h = FNV1_32_INIT; @@ -75,6 +60,8 @@ return h; } +} + /* Hash a pile. */ @@ -89,140 +76,6 @@ Wpilenum[w] = -1; } -#define MAXDEPTH 400 - -bool Solver::recursive(POSITION *parent) -{ - int i, alln, a, numout = 0; - - if ( parent == nullptr ) { - init(); - recu_pos.clear(); - delete Stack; - Stack = new POSITION[MAXDEPTH]; - memset( Stack, 0, sizeof( POSITION ) * MAXDEPTH ); - } - - /* Fill in the Possible array. */ - - alln = get_possible_moves(&a, &numout); - assert(alln < MAXMOVES); - - if (alln == 0) { - if ( isWon() ) { - Status = SolutionExists; - Q_ASSERT(parent); // it just is never called with a won game - win(parent); - return true; - } - return false; - } - - /* Prioritize these moves. Automoves don't get queued, so they - don't need a priority. */ - - if (!a) { - prioritize(Possible, alln); - } - - /* Now copy to safe storage and return. Non-auto moves out get put - at the end. Queueing them isn't a good idea because they are still - good moves, even if they didn't pass the automove test. So we still - do the recursive solve() on them, but only after queueing the other - moves. */ - - if ( parent && parent->depth >= MAXDEPTH - 2 ) - return false; - - MOVE *mp0 = new_array(MOVE, alln+1); - if (mp0 == nullptr) { - return false; - } - MOVE *mp = mp0; - for (i = 0; i < alln; ++i) { - if (Possible[i].card_index != -1) { - *mp = Possible[i]; /* struct copy */ - mp++; - } - } - mp->card_index = -1; - ++alln; - - bool fit = false; - for (mp = mp0; mp->card_index != -1; ++mp) { - - int depth = 0; - if (parent != nullptr) - depth = parent->depth + 1; - - make_move(mp); - - /* Calculate indices for the new piles. */ - pilesort(); - - /* See if this is a new position. */ - - Total_generated++; - POSITION *pos = &Stack[depth]; - pos->queue = nullptr; - pos->parent = parent; - pos->node = pack_position(); - quint8 *key = (quint8 *)pos->node + sizeof(TREE); -#if 0 - qint32 hash = fnv_hash_buf(key, mm->Pilebytes); - if ( recu_pos.contains( hash ) ) - { - undo_move( mp ); - mm->give_back_block( (quint8 *)pos->node ); - continue; - } - recu_pos[hash] = true; -#else - for ( int i = 0; i < depth; ++i ) - { - quint8 *tkey = (quint8 *)Stack[i].node + sizeof(TREE); - if ( !memcmp( key, tkey, mm->Pilebytes ) ) - { - key = nullptr; - break; - } - } - if ( !key ) - { - undo_move( mp ); - mm->give_back_block( (quint8 *)pos->node ); - continue; - } -#endif - Total_positions++; - if ( Total_positions % 10000 == 0 ) { - //qDebug() << "positions" << Total_positions; - } - - pos->move = *mp; /* struct copy */ - pos->cluster = 0; - pos->depth = depth; - pos->nchild = 0; - - bool ret = recursive(pos); - fit |= ret; - undo_move(mp); - mm->give_back_block( (quint8 *)pos->node ); - if ( ret ) - break; - } - - MemoryManager::free_array(mp0, alln); - - if ( parent == nullptr ) { - printf( "Total %ld\n", Total_generated ); - delete [] Stack; - Stack = nullptr; - } - return fit; -} - - /* Generate an array of the moves we can make from this position. */ MOVE *Solver::get_moves(int *nmoves) @@ -270,7 +123,7 @@ do the recursive solve() on them, but only after queueing the other moves. */ - mp = mp0 = new_array(MOVE, n); + mp = mp0 = mm_new_array(n); if (mp == nullptr) { return nullptr; } @@ -468,7 +321,7 @@ //printf("Winning in %d moves.\n", nmoves); - mpp0 = new_array(MOVE *, nmoves); + mpp0 = mm_new_array(nmoves); if (mpp0 == nullptr) { Status = UnableToDetermineSolvability; return; /* how sad, so close... */ @@ -556,13 +409,13 @@ //qDebug() << "out of piles"; return -1; } - l = mm_allocate(BUCKETLIST); + l = mm_allocate(); if (l == nullptr) { Status = UnableToDetermineSolvability; //qDebug() << "out of buckets"; return -1; } - l->pile = new_array(quint8, Wlen[w] + 1); + l->pile = mm_new_array(Wlen[w] + 1); if (l->pile == nullptr) { Status = UnableToDetermineSolvability; MemoryManager::free_ptr(l);