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 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" */ 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 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 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 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 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 */ 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 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 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 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 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
