1 // See LICENSE for license details.
3 //**************************************************************************
4 // Towers of Hanoi benchmark
5 //--------------------------------------------------------------------------
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.
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.
23 // This is the number of discs in the puzzle.
27 //--------------------------------------------------------------------------
28 // List data structure and functions
42 struct List g_nodeFreeList
;
43 struct Node g_nodePool
[NUM_DISCS
];
45 int list_getSize( struct List
* list
)
50 void list_init( struct List
* list
)
56 void list_push( struct List
* list
, int val
)
60 // Pop the next free node off the free list
61 newNode
= g_nodeFreeList
.head
;
62 g_nodeFreeList
.head
= g_nodeFreeList
.head
->next
;
64 // Push the new node onto the given list
65 newNode
->next
= list
->head
;
69 list
->head
->val
= val
;
76 int list_pop( struct List
* list
)
78 struct Node
* freedNode
;
81 // Get the value from the->head of given list
82 val
= list
->head
->val
;
84 // Pop the head node off the given list
85 freedNode
= list
->head
;
86 list
->head
= list
->head
->next
;
88 // Push the freed node onto the free list
89 freedNode
->next
= g_nodeFreeList
.head
;
90 g_nodeFreeList
.head
= freedNode
;
98 void list_clear( struct List
* list
)
100 while ( list_getSize(list
) > 0 )
104 //--------------------------------------------------------------------------
105 // Tower data structure and functions
116 void towers_init( struct Towers
* this, int n
)
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
);
132 void towers_clear( struct Towers
* this )
135 list_clear( &(this->pegA
) );
136 list_clear( &(this->pegB
) );
137 list_clear( &(this->pegC
) );
139 towers_init( this, this->numDiscs
);
144 void towers_print( struct Towers
* this )
150 for ( i
= 0; i
< ((this->numDiscs
)-list_getSize(&(this->pegA
))); i
++ )
152 for ( ptr
= this->pegA
.head
; ptr
!= 0; ptr
= ptr
->next
)
153 printf( "%d ", ptr
->val
);
156 for ( i
= 0; i
< ((this->numDiscs
)-list_getSize(&(this->pegB
))); i
++ )
158 for ( ptr
= this->pegB
.head
; ptr
!= 0; ptr
= ptr
->next
)
159 printf( "%d ", ptr
->val
);
162 for ( i
= 0; i
< ((this->numDiscs
)-list_getSize(&(this->pegC
))); i
++ )
164 for ( ptr
= this->pegC
.head
; ptr
!= 0; ptr
= ptr
->next
)
165 printf( "%d ", ptr
->val
);
171 void towers_solve_h( struct Towers
* this, int n
,
172 struct List
* startPeg
,
173 struct List
* tempPeg
,
174 struct List
* destPeg
)
182 val
= list_pop(startPeg
);
183 list_push(destPeg
,val
);
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
);
194 void towers_solve( struct Towers
* this )
196 towers_solve_h( this, this->numDiscs
, &(this->pegA
), &(this->pegB
), &(this->pegC
) );
199 int towers_verify( struct Towers
* this )
204 if ( list_getSize(&this->pegA
) != 0 ) {
206 printf( "ERROR: Peg A is not empty!\n" );
211 if ( list_getSize(&this->pegB
) != 0 ) {
213 printf( "ERROR: Peg B is not empty!\n" );
218 if ( list_getSize(&this->pegC
) != this->numDiscs
) {
220 printf( " ERROR: Expected %d discs but found only %d discs!\n", \
221 this->numDiscs
, list_getSize(&this->pegC
) );
226 for ( ptr
= this->pegC
.head
; ptr
!= 0; ptr
= ptr
->next
) {
228 if ( ptr
->val
!= numDiscs
) {
230 printf( " ERROR: Expecting disc %d on peg C but found disc %d instead!\n", \
231 numDiscs
, ptr
->val
);
237 if ( this->numMoves
!= ((1 << this->numDiscs
) - 1) ) {
239 printf( " ERROR: Expecting %d num moves but found %d instead!\n", \
240 ((1 << this->numDiscs
) - 1), this->numMoves
);
248 //--------------------------------------------------------------------------
251 int main( int argc
, char* argv
[] )
253 struct Towers towers
;
256 // Initialize free list
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
;
268 towers_init( &towers
, NUM_DISCS
);
270 // If needed we preallocate everything in the caches
273 towers_solve( &towers
);
278 towers_clear( &towers
);
280 towers_solve( &towers
);
283 // Print out the results
286 towers_print( &towers
);
290 return towers_verify( &towers
);