1 /*
2 Redistribution and use in source and binary forms, with or without
3 modification, are permitted provided that the following conditions are met:
4
5 * Redistributions of source code must retain the above copyright
6 notice, this list of conditions and the following disclaimer.
7
8 * Redistributions in binary form must reproduce the above copyright
9 notice, this list of conditions and the following disclaimer in the
10 documentation and/or other materials provided with the distribution.
11
12 * Neither the name of "The Computer Language Benchmarks Game" nor the
13 name of "The Computer Language Shootout Benchmarks" nor the names of
14 its contributors may be used to endorse or promote products derived
15 from this software without specific prior written permission.
16
17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 POSSIBILITY OF SUCH DAMAGE.
28 */
29
30 /* The Computer Language Benchmarks Game
31 http://shootout.alioth.debian.org/
32
33 contributed by Michael Barker
34 based on a Java contribution by Luzius Meisser
35
36 convert to C by dualamd
37 */
38
39 #include <stdlib.h>
40 #include <stdio.h>
41 #include <pthread.h>
42
43
44 enum Colour
45 {
46 blue = 0,
47 red = 1,
48 yellow = 2,
49 Invalid = 3
50 };
51
52 const char* ColourName[] = {"blue", "red", "yellow"};
53 const int STACK_SIZE = 32*1024;
54
55 typedef unsigned int BOOL;
56 const BOOL TRUE = 1;
57 const BOOL FALSE = 0;
58
59 int CreatureID = 0;
60
61
doCompliment(enum Colour c1,enum Colour c2)62 enum Colour doCompliment(enum Colour c1, enum Colour c2)
63 {
64 switch (c1)
65 {
66 case blue:
67 switch (c2)
68 {
69 case blue:
70 return blue;
71 case red:
72 return yellow;
73 case yellow:
74 return red;
75 default:
76 goto errlb;
77 }
78 case red:
79 switch (c2)
80 {
81 case blue:
82 return yellow;
83 case red:
84 return red;
85 case yellow:
86 return blue;
87 default:
88 goto errlb;
89 }
90 case yellow:
91 switch (c2)
92 {
93 case blue:
94 return red;
95 case red:
96 return blue;
97 case yellow:
98 return yellow;
99 default:
100 goto errlb;
101 }
102 default:
103 break;
104 }
105
106 errlb:
107 printf("Invalid colour\n");
108 exit( 1 );
109 }
110
111 /* convert integer to number string: 1234 -> "one two three four" */
formatNumber(int n,char * outbuf)112 char* formatNumber(int n, char* outbuf)
113 {
114 int ochar = 0, ichar = 0;
115 int i;
116 char tmp[64];
117
118 const char* NUMBERS[] =
119 {
120 "zero", "one", "two", "three", "four", "five",
121 "six", "seven", "eight", "nine"
122 };
123
124 ichar = sprintf(tmp, "%d", n);
125
126 for (i = 0; i < ichar; i++)
127 ochar += sprintf( outbuf + ochar, " %s", NUMBERS[ tmp[i] - '0' ] );
128
129 return outbuf;
130 }
131
132
133 struct MeetingPlace
134 {
135 pthread_mutex_t mutex;
136 int meetingsLeft;
137 struct Creature* firstCreature;
138 };
139
140 struct Creature
141 {
142 pthread_t ht;
143 pthread_attr_t stack_att;
144
145 struct MeetingPlace* place;
146 int count;
147 int sameCount;
148
149 enum Colour colour;
150 int id;
151
152 BOOL two_met;
153 BOOL sameid;
154 };
155
156
MeetingPlace_Init(struct MeetingPlace * m,int meetings)157 void MeetingPlace_Init(struct MeetingPlace* m, int meetings )
158 {
159 pthread_mutex_init( &m->mutex, 0 );
160 m->meetingsLeft = meetings;
161 m->firstCreature = 0;
162 }
163
164
Meet(struct Creature * cr)165 BOOL Meet( struct Creature* cr)
166 {
167 BOOL retval = TRUE;
168
169 struct MeetingPlace* mp = cr->place;
170 pthread_mutex_lock( &(mp->mutex) );
171
172 if ( mp->meetingsLeft > 0 )
173 {
174 if ( mp->firstCreature == 0 )
175 {
176 cr->two_met = FALSE;
177 mp->firstCreature = cr;
178 }
179 else
180 {
181 struct Creature* first;
182 enum Colour newColour;
183
184 first = mp->firstCreature;
185 newColour = doCompliment( cr->colour, first->colour );
186
187 cr->sameid = cr->id == first->id;
188 cr->colour = newColour;
189 cr->two_met = TRUE;
190
191 first->sameid = cr->sameid;
192 first->colour = newColour;
193 first->two_met = TRUE;
194
195 mp->firstCreature = 0;
196 mp->meetingsLeft--;
197 }
198 }
199 else
200 retval = FALSE;
201
202 pthread_mutex_unlock( &(mp->mutex) );
203 return retval;
204 }
205
206
CreatureThreadRun(void * param)207 void* CreatureThreadRun(void* param)
208 {
209 struct Creature* cr = (struct Creature*)param;
210
211 while (TRUE)
212 {
213 if ( Meet(cr) )
214 {
215 while (cr->two_met == FALSE)
216 sched_yield();
217
218 if (cr->sameid)
219 cr->sameCount++;
220 cr->count++;
221 }
222 else
223 break;
224 }
225
226 return 0;
227 }
228
Creature_Init(struct Creature * cr,struct MeetingPlace * place,enum Colour colour)229 void Creature_Init( struct Creature *cr, struct MeetingPlace* place, enum Colour colour )
230 {
231 cr->place = place;
232 cr->count = cr->sameCount = 0;
233
234 cr->id = ++CreatureID;
235 cr->colour = colour;
236 cr->two_met = FALSE;
237
238 pthread_attr_init( &cr->stack_att );
239 pthread_attr_setstacksize( &cr->stack_att, STACK_SIZE );
240 pthread_create( &cr->ht, &cr->stack_att, &CreatureThreadRun, (void*)(cr) );
241 }
242
243 /* format meeting times of each creature to string */
Creature_getResult(struct Creature * cr,char * str)244 char* Creature_getResult(struct Creature* cr, char* str)
245 {
246 char numstr[256];
247 formatNumber(cr->sameCount, numstr);
248
249 sprintf( str, "%u%s", cr->count, numstr );
250 return str;
251 }
252
253
runGame(int n_meeting,int ncolor,const enum Colour * colours)254 void runGame( int n_meeting, int ncolor, const enum Colour* colours )
255 {
256 int i;
257 int total = 0;
258 char str[256];
259
260 struct MeetingPlace place;
261 struct Creature *creatures = (struct Creature*) calloc( ncolor, sizeof(struct Creature) );
262
263 MeetingPlace_Init( &place, n_meeting );
264
265 /* print initial color of each creature */
266 for (i = 0; i < ncolor; i++)
267 {
268 printf( "%s ", ColourName[ colours[i] ] );
269 Creature_Init( &(creatures[i]), &place, colours[i] );
270 }
271 printf("\n");
272
273 /* wait for them to meet */
274 for (i = 0; i < ncolor; i++)
275 pthread_join( creatures[i].ht, 0 );
276
277 /* print meeting times of each creature */
278 for (i = 0; i < ncolor; i++)
279 {
280 printf( "%s\n", Creature_getResult(&(creatures[i]), str) );
281 total += creatures[i].count;
282 }
283
284 /* print total meeting times, should equal n_meeting */
285 printf( "%s\n\n", formatNumber(total, str) );
286
287 /* cleaup & quit */
288 pthread_mutex_destroy( &place.mutex );
289 free( creatures );
290 }
291
292
printColours(enum Colour c1,enum Colour c2)293 void printColours( enum Colour c1, enum Colour c2 )
294 {
295 printf( "%s + %s -> %s\n",
296 ColourName[c1],
297 ColourName[c2],
298 ColourName[doCompliment(c1, c2)] );
299 }
300
printColoursTable(void)301 void printColoursTable(void)
302 {
303 printColours(blue, blue);
304 printColours(blue, red);
305 printColours(blue, yellow);
306 printColours(red, blue);
307 printColours(red, red);
308 printColours(red, yellow);
309 printColours(yellow, blue);
310 printColours(yellow, red);
311 printColours(yellow, yellow);
312 }
313
main(int argc,char ** argv)314 int main(int argc, char** argv)
315 {
316 int n = (argc == 2) ? atoi(argv[1]) : 600;
317
318 printColoursTable();
319 printf("\n");
320
321 const enum Colour r1[] = { blue, red, yellow };
322 const enum Colour r2[] = { blue, red, yellow,
323 red, yellow, blue,
324 red, yellow, red, blue };
325
326 runGame( n, sizeof(r1) / sizeof(r1[0]), r1 );
327 runGame( n, sizeof(r2) / sizeof(r2[0]), r2 );
328
329 return 0;
330 }
331