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.
21 #include "util.h"
23 // This is the number of discs in the puzzle.
25 #define NUM_DISCS 7
27 //--------------------------------------------------------------------------
28 // List data structure and functions
30 struct Node
31 {
32 int val;
33 struct Node* next;
34 };
36 struct List
37 {
38 int size;
40 };
42 struct List g_nodeFreeList;
43 struct Node g_nodePool[NUM_DISCS];
45 int list_getSize( struct List* list )
46 {
47 return list->size;
48 }
50 void list_init( struct List* list )
51 {
52 list->size = 0;
54 }
56 void list_push( struct List* list, int val )
57 {
58 struct Node* newNode;
60 // Pop the next free node off the free list
64 // Push the new node onto the given list
68 // Assign the value
71 // Increment size
72 list->size++;
74 }
76 int list_pop( struct List* list )
77 {
78 struct Node* freedNode;
79 int val;
81 // Get the value from the->head of given list
84 // Pop the head node off the given list
88 // Push the freed node onto the free list
92 // Decrement size
93 list->size--;
95 return val;
96 }
98 void list_clear( struct List* list )
99 {
100 while ( list_getSize(list) > 0 )
101 list_pop(list);
102 }
104 //--------------------------------------------------------------------------
105 // Tower data structure and functions
107 struct Towers
108 {
109 int numDiscs;
110 int numMoves;
111 struct List pegA;
112 struct List pegB;
113 struct List pegC;
114 };
116 void towers_init( struct Towers* this, int n )
117 {
118 int i;
120 this->numDiscs = n;
121 this->numMoves = 0;
123 list_init( &(this->pegA) );
124 list_init( &(this->pegB) );
125 list_init( &(this->pegC) );
127 for ( i = 0; i < n; i++ )
128 list_push( &(this->pegA), n-i );
130 }
132 void towers_clear( struct Towers* this )
133 {
135 list_clear( &(this->pegA) );
136 list_clear( &(this->pegB) );
137 list_clear( &(this->pegC) );
139 towers_init( this, this->numDiscs );
141 }
143 #if HOST_DEBUG
144 void towers_print( struct Towers* this )
145 {
146 struct Node* ptr;
147 int i, numElements;
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 );
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 );
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 );
167 printf( "\n" );
168 }
169 #endif
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;
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 }
192 }
194 void towers_solve( struct Towers* this )
195 {
196 towers_solve_h( this, this->numDiscs, &(this->pegA), &(this->pegB), &(this->pegC) );
197 }
199 int towers_verify( struct Towers* this )
200 {
201 struct Node* ptr;
202 int numDiscs = 0;
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 }
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 }
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 }
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 }
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 }
245 return 0;
246 }
248 //--------------------------------------------------------------------------
249 // Main
251 int main( int argc, char* argv[] )
252 {
253 struct Towers towers;
254 int i;
256 // Initialize free list
258 list_init( &g_nodeFreeList );
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 }
268 towers_init( &towers, NUM_DISCS );
270 // If needed we preallocate everything in the caches
272 #if PREALLOCATE
273 towers_solve( &towers );
274 #endif
276 // Solve it
278 towers_clear( &towers );
279 setStats(1);
280 towers_solve( &towers );
281 setStats(0);
283 // Print out the results
285 #if HOST_DEBUG
286 towers_print( &towers );
287 #endif
289 // Check the results