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