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.
  17
  18 #include "util.h"
  19
  20 // This is the number of discs in the puzzle.
  21
  22 #define NUM_DISCS  7
  23
  24 //--------------------------------------------------------------------------
  25 // List data structure and functions
  26
  27 struct Node
  28 {
  29   int val;
  30   struct Node* next;
  31 };
  32
  33 struct List
  34 {
  35   int size;
  36   struct Node* head;
  37 };
  38
  39 struct List g_nodeFreeList;
  40 struct Node g_nodePool[NUM_DISCS];
  41
  42 int list_getSize( struct List* list )
  43 {
  44   return list->size;
  45 }
  46
  47 void list_init( struct List* list )
  48 {
  49   list->size = 0;
  50   list->head = 0;
  51 }
  52
  53 void list_push( struct List* list, int val )
  54 {
  55   struct Node* newNode;
  56
  57   // Pop the next free node off the free list
  58   newNode = g_nodeFreeList.head;
  59   g_nodeFreeList.head = g_nodeFreeList.head->next;
  60
  61   // Push the new node onto the given list
  62   newNode->next = list->head;
  63   list->head = newNode;
  64
  65   // Assign the value
  66   list->head->val = val;
  67
  68   // Increment size
  69   list->size++;
  70
  71 }
  72
  73 int list_pop( struct List* list )
  74 {
  75   struct Node* freedNode;
  76   int val;
  77
  78   // Get the value from the->head of given list
  79   val = list->head->val;
  80
  81   // Pop the head node off the given list
  82   freedNode = list->head;
  83   list->head = list->head->next;
  84
  85   // Push the freed node onto the free list
  86   freedNode->next = g_nodeFreeList.head;
  87   g_nodeFreeList.head = freedNode;
  88
  89   // Decrement size
  90   list->size--;
  91
  92   return val;
  93 }
  94
  95 void list_clear( struct List* list )
  96 {
  97   while ( list_getSize(list) > 0 )
  98     list_pop(list);
  99 }
 100
 101 //--------------------------------------------------------------------------
 102 // Tower data structure and functions
 103
 104 struct Towers
 105 {
 106   int numDiscs;
 107   int numMoves;
 108   struct List pegA;
 109   struct List pegB;
 110   struct List pegC;
 111 };
 112
 113 void towers_init( struct Towers* this, int n )
 114 {
 115   int i;
 116
 117   this->numDiscs = n;
 118   this->numMoves = 0;
 119
 120   list_init( &(this->pegA) );
 121   list_init( &(this->pegB) );
 122   list_init( &(this->pegC) );
 123
 124   for ( i = 0; i < n; i++ )
 125     list_push( &(this->pegA), n-i );
 126
 127 }
 128
 129 void towers_clear( struct Towers* this )
 130 {
 131
 132   list_clear( &(this->pegA) );
 133   list_clear( &(this->pegB) );
 134   list_clear( &(this->pegC) );
 135
 136   towers_init( this, this->numDiscs );
 137
 138 }
 139
 140 void towers_solve_h( struct Towers* this, int n,
 141                      struct List* startPeg,
 142                      struct List* tempPeg,
 143                      struct List* destPeg )
 144 {
 145   int val;
 146
 147   if ( n == 1 ) {
 148     val = list_pop(startPeg);
 149     list_push(destPeg,val);
 150     this->numMoves++;
 151   }
 152   else {
 153     towers_solve_h( this, n-1, startPeg, destPeg,  tempPeg );
 154     towers_solve_h( this, 1,   startPeg, tempPeg,  destPeg );
 155     towers_solve_h( this, n-1, tempPeg,  startPeg, destPeg );
 156   }
 157
 158 }
 159
 160 void towers_solve( struct Towers* this )
 161 {
 162   towers_solve_h( this, this->numDiscs, &(this->pegA), &(this->pegB), &(this->pegC) );
 163 }
 164
 165 int towers_verify( struct Towers* this )
 166 {
 167   struct Node* ptr;
 168   int numDiscs = 0;
 169
 170   if ( list_getSize(&this->pegA) != 0 ) {
 171     return 2;
 172   }
 173
 174   if ( list_getSize(&this->pegB) != 0 ) {
 175     return 3;
 176   }
 177
 178   if ( list_getSize(&this->pegC) != this->numDiscs ) {
 179     return 4;
 180   }
 181
 182   for ( ptr = this->pegC.head; ptr != 0; ptr = ptr->next ) {
 183     numDiscs++;
 184     if ( ptr->val != numDiscs ) {
 185       return 5;
 186     }
 187   }
 188
 189   if ( this->numMoves != ((1 << this->numDiscs) - 1) ) {
 190     return 6;
 191   }
 192
 193   return 0;
 194 }
 195
 196 //--------------------------------------------------------------------------
 197 // Main
 198
 199 int main( int argc, char* argv[] )
 200 {
 201   struct Towers towers;
 202   int i;
 203
 204   // Initialize free list
 205
 206   list_init( &g_nodeFreeList );
 207   g_nodeFreeList.head = &(g_nodePool[0]);
 208   g_nodeFreeList.size = NUM_DISCS;
 209   g_nodePool[NUM_DISCS-1].next = 0;
 210   g_nodePool[NUM_DISCS-1].val = 99;
 211   for ( i = 0; i < (NUM_DISCS-1); i++ ) {
 212     g_nodePool[i].next = &(g_nodePool[i+1]);
 213     g_nodePool[i].val = i;
 214   }
 215
 216   towers_init( &towers, NUM_DISCS );
 217
 218   // If needed we preallocate everything in the caches
 219
 220 #if PREALLOCATE
 221   towers_solve( &towers );
 222 #endif
 223
 224   // Solve it
 225
 226   towers_clear( &towers );
 227   setStats(1);
 228   towers_solve( &towers );
 229   setStats(0);
 230
 231   // Check the results
 232   return towers_verify( &towers );
 233 }
 234