benchmarks/towers/towers_main.c

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