benchmarks/towers/towers_main.c

   1 // See LICENSE for license details.
   2
   3 //**************************************************************************
   4 // Towers of Hanoi benchmark
   5 //--------------------------------------------------------------------------
   6 //
   7 // Towers of Hanoi is a classic puzzle problem. The game consists of
   8 // three pegs and a set of discs. Each disc is a different size, and
   9 // initially all of the discs are on the left most peg with the smallest
  10 // disc on top and the largest disc on the bottom. The goal is to move all
  11 // of the discs onto the right most peg. The catch is that you are only
  12 // allowed to move one disc at a time and you can never place a larger
  13 // disc on top of a smaller disc.
  14 //
  15 // This implementation starts with NUM_DISC discs and uses a recursive
  16 // algorithm to sovel the puzzle.  The smips-gcc toolchain does not support
  17 // system calls so printf's can only be used on a host system, not on the
  18 // smips processor simulator itself. You should not change anything except
  19 // the HOST_DEBUG and PREALLOCATE macros for your timing run.
  20
  21 #include "util.h"
  22
  23 // This is the number of discs in the puzzle.
  24
  25 #define NUM_DISCS  7
  26
  27 //--------------------------------------------------------------------------
  28 // List data structure and functions
  29
  30 struct Node
  31 {
  32   int val;
  33   struct Node* next;
  34 };
  35
  36 struct List
  37 {
  38   int size;
  39   struct Node* head;
  40 };
  41
  42 struct List g_nodeFreeList;
  43 struct Node g_nodePool[NUM_DISCS];
  44
  45 int list_getSize( struct List* list )
  46 {
  47   return list->size;
  48 }
  49
  50 void list_init( struct List* list )
  51 {
  52   list->size = 0;
  53   list->head = 0;
  54 }
  55
  56 void list_push( struct List* list, int val )
  57 {
  58   struct Node* newNode;
  59
  60   // Pop the next free node off the free list
  61   newNode = g_nodeFreeList.head;
  62   g_nodeFreeList.head = g_nodeFreeList.head->next;
  63
  64   // Push the new node onto the given list
  65   newNode->next = list->head;
  66   list->head = newNode;
  67
  68   // Assign the value
  69   list->head->val = val;
  70
  71   // Increment size
  72   list->size++;
  73
  74 }
  75
  76 int list_pop( struct List* list )
  77 {
  78   struct Node* freedNode;
  79   int val;
  80
  81   // Get the value from the->head of given list
  82   val = list->head->val;
  83
  84   // Pop the head node off the given list
  85   freedNode = list->head;
  86   list->head = list->head->next;
  87
  88   // Push the freed node onto the free list
  89   freedNode->next = g_nodeFreeList.head;
  90   g_nodeFreeList.head = freedNode;
  91
  92   // Decrement size
  93   list->size--;
  94
  95   return val;
  96 }
  97
  98 void list_clear( struct List* list )
  99 {
 100   while ( list_getSize(list) > 0 )
 101     list_pop(list);
 102 }
 103
 104 //--------------------------------------------------------------------------
 105 // Tower data structure and functions
 106
 107 struct Towers
 108 {
 109   int numDiscs;
 110   int numMoves;
 111   struct List pegA;
 112   struct List pegB;
 113   struct List pegC;
 114 };
 115
 116 void towers_init( struct Towers* this, int n )
 117 {
 118   int i;
 119
 120   this->numDiscs = n;
 121   this->numMoves = 0;
 122
 123   list_init( &(this->pegA) );
 124   list_init( &(this->pegB) );
 125   list_init( &(this->pegC) );
 126
 127   for ( i = 0; i < n; i++ )
 128     list_push( &(this->pegA), n-i );
 129
 130 }
 131
 132 void towers_clear( struct Towers* this )
 133 {
 134
 135   list_clear( &(this->pegA) );
 136   list_clear( &(this->pegB) );
 137   list_clear( &(this->pegC) );
 138
 139   towers_init( this, this->numDiscs );
 140
 141 }
 142
 143 #if HOST_DEBUG
 144 void towers_print( struct Towers* this )
 145 {
 146   struct Node* ptr;
 147   int i, numElements;
 148
 149   printf( "  pegA: " );
 150   for ( i = 0; i < ((this->numDiscs)-list_getSize(&(this->pegA))); i++ )
 151     printf( ". " );
 152   for ( ptr = this->pegA.head; ptr != 0; ptr = ptr->next )
 153     printf( "%d ", ptr->val );
 154
 155   printf( "  pegB: " );
 156   for ( i = 0; i < ((this->numDiscs)-list_getSize(&(this->pegB))); i++ )
 157     printf( ". " );
 158   for ( ptr = this->pegB.head; ptr != 0; ptr = ptr->next )
 159     printf( "%d ", ptr->val );
 160
 161   printf( "  pegC: " );
 162   for ( i = 0; i < ((this->numDiscs)-list_getSize(&(this->pegC))); i++ )
 163     printf( ". " );
 164   for ( ptr = this->pegC.head; ptr != 0; ptr = ptr->next )
 165     printf( "%d ", ptr->val );
 166
 167   printf( "\n" );
 168 }
 169 #endif
 170
 171 void towers_solve_h( struct Towers* this, int n,
 172                      struct List* startPeg,
 173                      struct List* tempPeg,
 174                      struct List* destPeg )
 175 {
 176   int val;
 177
 178   if ( n == 1 ) {
 179 #if HOST_DEBUG
 180     towers_print(this);
 181 #endif
 182     val = list_pop(startPeg);
 183     list_push(destPeg,val);
 184     this->numMoves++;
 185   }
 186   else {
 187     towers_solve_h( this, n-1, startPeg, destPeg,  tempPeg );
 188     towers_solve_h( this, 1,   startPeg, tempPeg,  destPeg );
 189     towers_solve_h( this, n-1, tempPeg,  startPeg, destPeg );
 190   }
 191
 192 }
 193
 194 void towers_solve( struct Towers* this )
 195 {
 196   towers_solve_h( this, this->numDiscs, &(this->pegA), &(this->pegB), &(this->pegC) );
 197 }
 198
 199 int towers_verify( struct Towers* this )
 200 {
 201   struct Node* ptr;
 202   int numDiscs = 0;
 203
 204   if ( list_getSize(&this->pegA) != 0 ) {
 205 #if HOST_DEBUG
 206     printf( "ERROR: Peg A is not empty!\n" );
 207 #endif
 208     return 2;
 209   }
 210
 211   if ( list_getSize(&this->pegB) != 0 ) {
 212 #if HOST_DEBUG
 213     printf( "ERROR: Peg B is not empty!\n" );
 214 #endif
 215     return 3;
 216   }
 217
 218   if ( list_getSize(&this->pegC) != this->numDiscs ) {
 219 #if HOST_DEBUG
 220     printf( " ERROR: Expected %d discs but found only %d discs!\n", \
 221             this->numDiscs, list_getSize(&this->pegC) );
 222 #endif
 223     return 4;
 224   }
 225
 226   for ( ptr = this->pegC.head; ptr != 0; ptr = ptr->next ) {
 227     numDiscs++;
 228     if ( ptr->val != numDiscs ) {
 229 #if HOST_DEBUG
 230       printf( " ERROR: Expecting disc %d on peg C but found disc %d instead!\n", \
 231               numDiscs, ptr->val );
 232 #endif
 233       return 5;
 234     }
 235   }
 236
 237   if ( this->numMoves != ((1 << this->numDiscs) - 1) ) {
 238 #if HOST_DEBUG
 239     printf( " ERROR: Expecting %d num moves but found %d instead!\n", \
 240             ((1 << this->numDiscs) - 1), this->numMoves );
 241 #endif
 242     return 6;
 243   }
 244
 245   return 0;
 246 }
 247
 248 //--------------------------------------------------------------------------
 249 // Main
 250
 251 int main( int argc, char* argv[] )
 252 {
 253   struct Towers towers;
 254   int i;
 255
 256   // Initialize free list
 257
 258   list_init( &g_nodeFreeList );
 259   g_nodeFreeList.head = &(g_nodePool[0]);
 260   g_nodeFreeList.size = NUM_DISCS;
 261   g_nodePool[NUM_DISCS-1].next = 0;
 262   g_nodePool[NUM_DISCS-1].val = 99;
 263   for ( i = 0; i < (NUM_DISCS-1); i++ ) {
 264     g_nodePool[i].next = &(g_nodePool[i+1]);
 265     g_nodePool[i].val = i;
 266   }
 267
 268   towers_init( &towers, NUM_DISCS );
 269
 270   // If needed we preallocate everything in the caches
 271
 272 #if PREALLOCATE
 273   towers_solve( &towers );
 274 #endif
 275
 276   // Solve it
 277
 278   towers_clear( &towers );
 279   setStats(1);
 280   towers_solve( &towers );
 281   setStats(0);
 282
 283   // Print out the results
 284
 285 #if HOST_DEBUG
 286   towers_print( &towers );
 287 #endif
 288
 289   // Check the results
 290   return towers_verify( &towers );
 291 }
 292