examples/DispatchLife/DispatchLife.c

   1 /*
   2  * Copyright (c) 2008-2009 Apple Inc.  All rights reserved.
   3  *
   4  * @APPLE_DTS_LICENSE_HEADER_START@
   5  *
   6  * IMPORTANT:  This Apple software is supplied to you by Apple Computer, Inc.
   7  * ("Apple") in consideration of your agreement to the following terms, and your
   8  * use, installation, modification or redistribution of this Apple software
   9  * constitutes acceptance of these terms.  If you do not agree with these terms,
  10  * please do not use, install, modify or redistribute this Apple software.
  11  *
  12  * In consideration of your agreement to abide by the following terms, and
  13  * subject to these terms, Apple grants you a personal, non-exclusive license,
  14  * under Apple's copyrights in this original Apple software (the "Apple Software"),
  15  * to use, reproduce, modify and redistribute the Apple Software, with or without
  16  * modifications, in source and/or binary forms; provided that if you redistribute
  17  * the Apple Software in its entirety and without modifications, you must retain
  18  * this notice and the following text and disclaimers in all such redistributions
  19  * of the Apple Software.  Neither the name, trademarks, service marks or logos of
  20  * Apple Computer, Inc. may be used to endorse or promote products derived from
  21  * the Apple Software without specific prior written permission from Apple.  Except
  22  * as expressly stated in this notice, no other rights or licenses, express or
  23  * implied, are granted by Apple herein, including but not limited to any patent
  24  * rights that may be infringed by your derivative works or by other works in
  25  * which the Apple Software may be incorporated.
  26  *
  27  * The Apple Software is provided by Apple on an "AS IS" basis.  APPLE MAKES NO
  28  * WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION THE IMPLIED
  29  * WARRANTIES OF NON-INFRINGEMENT, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  30  * PURPOSE, REGARDING THE APPLE SOFTWARE OR ITS USE AND OPERATION ALONE OR IN
  31  * COMBINATION WITH YOUR PRODUCTS.
  32  *
  33  * IN NO EVENT SHALL APPLE BE LIABLE FOR ANY SPECIAL, INDIRECT, INCIDENTAL OR
  34  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  35  * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  36  * ARISING IN ANY WAY OUT OF THE USE, REPRODUCTION, MODIFICATION AND/OR
  37  * DISTRIBUTION OF THE APPLE SOFTWARE, HOWEVER CAUSED AND WHETHER UNDER THEORY OF
  38  * CONTRACT, TORT (INCLUDING NEGLIGENCE), STRICT LIABILITY OR OTHERWISE, EVEN IF
  39  * APPLE HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  40  *
  41  * @APPLE_DTS_LICENSE_HEADER_END@
  42  */
  43 /*!
  44         @header Life
  45         An asynchronous variation of Conway's Game of Life implemented with
  46         GCD.  Like the classic version, the game board consists of a grid of
  47         cells that can live, die or multiply by the following rules[1]:
  48
  49             1. Survivals.  Every [living cell] with two or three neighboring
  50             [living cells] survives for the next generation.
  51             2. Deaths. Each [living cell] wiht four or more neighbors dies (is
  52             removed) from overpopulation.  Every [living cell] with one
  53             neighbor or none dies from isolation.
  54             3. Births. Each empty cell adjacent to exactly three neighbors--no
  55             more, no fewer--is a birth cell.  A [living cell] is placed on it
  56             at the next move.
  57
  58         However, unlike the classic version, not all deaths and births occur
  59         simultaneously in a single, synchronous, "move" of the game board.
  60         Instead the rules are applies to each cell independently based on its
  61         observations of the cells around it.
  62
  63         Each cell is backed by a GCD queue which manages the synchronization
  64         of the cells internal state (living or dead).  When a cell's state
  65         changes, a notification in the form of a dispatch_call() of the
  66         cell_needs_update() work function is sent to all adjacent cells so
  67         that the state of those cells may be re-evaluated.
  68
  69         To re-evaluate the state of a cell, a request of the current state of
  70         all adjecent cells is sent in the form of a dispatch_call() of the
  71         _cell_is_alive() work function.  The state of the adjacent cells is
  72         returned to the requestor via the _cell_is_alive_callback() completion
  73         callback.  Once all outstanding completion callbacks have been
  74         received, the cell updates its state according to the aforementioned
  75         rules.  If the application of these rules results in another state
  76         change, the update_cell() notification is once again sent out,
  77         repeating the process.
  78
  79         Due to the highly asynchronous nature of this implementation, the
  80         simulation's results may differ from the classic version for the same
  81         set of initial conditions.  In particular, due to non-deterministic
  82         scheduling factors, the same set of initial condiitions is likely to
  83         produce dramatically different results on subsequent simulations.
  84
  85         [1] Martin Gardner. "MATHEMATICAL GAMES: The fantastic combinations of
  86             John Conway's new solitaire game 'life'" Scientific American 223
  87             (October 1970): 120-123.
  88
  89         @copyright Copyright (c) 2008-2009 Apple Inc.  All rights reserved.
  90         @updated 2009-03-31
  91 */
  92 ////////////////////////////////////////////////////////////////////////////////
  93
  94 // Adjustable parameters
  95 unsigned long grid_x_size = 40;
  96 unsigned long grid_y_size = 20;
  97
  98 int use_curses = 1;
  99
 100 ////////////////////////////////////////////////////////////////////////////////
 101 #include <string.h>
 102 #include <stdlib.h>
 103 #include <stdio.h>
 104 #include <unistd.h>
 105 #include <curses.h>
 106 #include <sys/ioctl.h>
 107 #include <dispatch/dispatch.h>
 108
 109 #define CELL_MAX_NEIGHBORS 8
 110
 111 struct cell {
 112         dispatch_queue_t q;
 113         int alive;
 114         char display;
 115
 116         // tracks whether a update_cell() notification arrived while
 117         // an update was already in progress
 118         int needs_update;
 119         int living_neighbors;
 120         int queries_outstanding;
 121
 122         struct cell* neighbors[CELL_MAX_NEIGHBORS];
 123         char* label;
 124 } __attribute__((aligned(64)));
 125
 126 ////////////////////////////////////////////////////////////////////////////////
 127
 128 /*! @function init_grid
 129         Initializes the grid data structure based on the global variables
 130         grid_x_size and grid_y_size.  Must be called before any calls to
 131         cell_set_alive. */
 132 struct cell* init_grid(size_t grid_x_size, size_t grid_y_size);
 133
 134 /*! @function init_display
 135         Initializes the display subsystem.  Starts a periodic timer to update the
 136         display based on the current contents of the cell grid.
 137  */
 138 void init_display(struct cell* grid);
 139
 140 ////////////////////////////////////////////////////////////////////////////////
 141
 142 // Macro to test whether x,y coordinates are within bounds of the grid
 143 #define GRID_VALID(u,v) (((u) >= 0) && ((v) >= 0) && \
 144                         ((u) < grid_x_size) && ((v) < grid_y_size))
 145 // Macro to translate from 2d grid coordinates to array offest
 146 #define GRID_OFF(u,v) ((v) * grid_x_size + (u))
 147
 148 #if !defined(DISPATCH_LIFE_GL)
 149 int main(int argc, char* argv[]) {
 150
 151         struct ttysize tsz;
 152         int res;
 153
 154         res = ioctl(STDIN_FILENO, TIOCGWINSZ, &tsz);
 155         if (res == 0) {
 156                 grid_x_size = tsz.ts_cols;
 157                 grid_y_size = tsz.ts_lines;
 158         }
 159
 160         int dispflag = 1;
 161         int ch;
 162
 163         while ((ch = getopt(argc, argv, "x:y:q")) != -1) {
 164                 char* endptr;
 165                 switch (ch) {
 166                         case 'x':
 167                                 grid_x_size = strtol(optarg, &endptr, 10);
 168                                 if (grid_x_size < 0 || (endptr && *endptr != 0)) {
 169                                         fprintf(stderr, "life: invalid x size\n");
 170                                         exit(1);
 171                                 }
 172                                 break;
 173                         case 'y':
 174                                 grid_y_size = strtol(optarg, &endptr, 10);
 175                                 if (grid_y_size < 0 || (endptr && *endptr != 0)) {
 176                                         fprintf(stderr, "life: invalid y size\n");
 177                                         exit(1);
 178                                 }
 179                                 break;
 180                         case 'q':
 181                                 dispflag = 0;
 182                                 break;
 183                         case '?':
 184                         default:
 185                                 fprintf(stderr, "usage: life [-q] [-x size] [-y size]\n");
 186                                 fprintf(stderr, "\t-x: grid x size (default is terminal columns)\n");
 187                                 fprintf(stderr, "\t-y: grid y size (default is terminal rows)\n");
 188                                 fprintf(stderr, "\t-q: suppress display output\n");
 189                                 exit(1);
 190                 }
 191         }
 192
 193         struct cell* grid = init_grid(grid_x_size, grid_y_size);
 194
 195         if (dispflag) {
 196                 init_display(grid);
 197                 if (use_curses) {
 198                         initscr(); cbreak(); noecho();
 199                         nonl();
 200                         intrflush(stdscr, FALSE);
 201                         keypad(stdscr, TRUE);
 202                 }
 203         }
 204
 205         dispatch_main();
 206
 207         if (dispflag && use_curses) {
 208                 endwin();
 209         }
 210
 211         return 0;
 212 }
 213 #endif /* defined(DISPATCH_LIFE_GL) */
 214
 215 ////////////////////////////////////////////////////////////////////////////////
 216
 217 static void cell_set_alive(struct cell*, int alive);
 218
 219 /*!     @function update_cell
 220         GCD work function.  Begins the update process for a cell by
 221         sending cell_is_alive() messages with cell_is_alive_callback()
 222         completion callbacks to all adjacent cells.  If an update is already
 223         in progress, simply sets the needs_update flag of the cell. */
 224 static void update_cell(struct cell*);
 225
 226 /*!     @function cell_is_alive_callback
 227         GCD completion callback.  Receives the result from cell_is_alive.  When
 228         all _cell_is_alive_callback() completion callbacks have been received
 229         from an update, recalculates the internal state of the cell.  If the
 230         state changes, sends update_cell() to all adjacent cells. */
 231 static void update_cell_response(struct cell*, int);
 232
 233 ////////////////////////////////////////////////////////////////////////////////
 234
 235 void
 236 foreach_neighbor(struct cell* self, void (^action)(struct cell* other)) {
 237         int i;
 238         for (i = 0; i < CELL_MAX_NEIGHBORS; ++i) {
 239                 struct cell* other = self->neighbors[i];
 240                 if (other) {
 241                         action(other);
 242                 }
 243         }
 244 }
 245
 246
 247 // Change cell state, update the screen, and update neighbors.
 248 void
 249 cell_set_alive(struct cell* self, int alive) {
 250         if (alive == self->alive) return; // nothing to do
 251
 252         dispatch_async(self->q, ^{
 253                 self->alive = alive;
 254                 self->display = (self->alive) ? '#' : ' ';
 255
 256                 foreach_neighbor(self, ^(struct cell* other) {
 257                         dispatch_async(other->q, ^{ update_cell(other); });
 258                 });
 259         });
 260 }
 261
 262 void
 263 update_cell(struct cell* self) {
 264         if (self->queries_outstanding == 0) {
 265                 self->needs_update = 0;
 266                 self->living_neighbors = 0;
 267
 268                 foreach_neighbor(self, ^(struct cell* other) {
 269                         ++self->queries_outstanding;
 270                         dispatch_async(other->q, ^{
 271                                 dispatch_async(self->q, ^{ update_cell_response(self, other->alive); });
 272                         });
 273                 });
 274
 275                 // '.' indicates the cell is not alive but needs an update
 276                 if (!self->alive) self->display = '.';
 277         } else {
 278                 self->needs_update = 1;
 279         }
 280 }
 281
 282 void
 283 update_cell_response(struct cell* self, int response) {
 284         if (response) ++self->living_neighbors;
 285         --self->queries_outstanding;
 286
 287         // when all neighbors have replied with their state,
 288         // recalculate our internal state
 289         if (self->queries_outstanding == 0) {
 290                 const int living_neighbors = self->living_neighbors;
 291                 int alive = self->alive;
 292
 293                 // Conway's Game of Life
 294                 if (living_neighbors < 2 || living_neighbors > 3) {
 295                         alive = 0;
 296                 } else if (living_neighbors == 3) {
 297                         alive = 1;
 298                 }
 299
 300                 // Notify neighbors of state change
 301                 cell_set_alive(self, alive);
 302
 303                 // if a request for an update came in while we were
 304                 // already processing one, kick off the next update
 305                 if (self->needs_update) {
 306                         dispatch_async(self->q, ^{ update_cell(self); });
 307                 } else {
 308                         // otherwise clear the '.' character that was
 309                         // displayed during the update
 310                         if (!self->alive) {
 311                                 self->display = ' ';
 312                         }
 313                 }
 314         }
 315 }
 316
 317 ////////////////////////////////////////////////////////////////////////////////
 318
 319 struct cell*
 320 init_grid(size_t grid_x_size, size_t grid_y_size) {
 321         struct cell* grid = calloc(sizeof(struct cell),grid_x_size*grid_y_size);
 322
 323         int i,j;
 324         for (i = 0; i < grid_x_size; ++i) {
 325                 for (j = 0; j < grid_y_size; ++j) {
 326                         struct cell* ptr = &grid[GRID_OFF(i,j)];
 327
 328                         asprintf(&ptr->label, "x%dy%d", i, j);
 329
 330                         ptr->q = dispatch_queue_create(ptr->label, NULL);
 331                         dispatch_set_target_queue(ptr->q, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0));
 332                         dispatch_queue_set_context(ptr->q, ptr);
 333
 334                         ptr->neighbors[0] = GRID_VALID(i  ,j-1) ?
 335                                 &grid[GRID_OFF(i  ,j-1)] : NULL;        // N
 336                         ptr->neighbors[1] = GRID_VALID(i+1,j-1) ?
 337                                 &grid[GRID_OFF(i+1,j-1)] : NULL;        // NE
 338                         ptr->neighbors[2] = GRID_VALID(i+1,j  ) ?
 339                                 &grid[GRID_OFF(i+1,j  )] : NULL;        // E
 340                         ptr->neighbors[3] = GRID_VALID(i+1,j+1) ?
 341                                 &grid[GRID_OFF(i+1,j+1)] : NULL;        // SE
 342                         ptr->neighbors[4] = GRID_VALID(i  ,j+1) ?
 343                                 &grid[GRID_OFF(i  ,j+1)] : NULL;        // S
 344                         ptr->neighbors[5] = GRID_VALID(i-1,j+1) ?
 345                                 &grid[GRID_OFF(i-1,j+1)] : NULL;        // SW
 346                         ptr->neighbors[6] = GRID_VALID(i-1,j  ) ?
 347                                 &grid[GRID_OFF(i-1,j  )] : NULL;        // W
 348                         ptr->neighbors[7] = GRID_VALID(i-1,j-1) ?
 349                                 &grid[GRID_OFF(i-1,j-1)] : NULL;        // NW
 350                 }
 351         }
 352
 353         srandomdev();
 354         for (i = 0; i < grid_x_size; ++i) {
 355                 for (j = 0; j < grid_y_size; ++j) {
 356                         if (random() & 1) {
 357                                 cell_set_alive(&grid[GRID_OFF(i,j)], 1);
 358                         }
 359                 }
 360         }
 361
 362         return grid;
 363 }
 364
 365 #if defined(DISPATCH_LIFE_GL)
 366 char
 367 get_grid_display_char(struct cell* grid, size_t x, size_t y) {
 368         return grid[GRID_OFF(x,y)].display;
 369 }
 370 #endif /* defined(DISPATCH_LIFE_GL) */
 371
 372 #if !defined(DISPATCH_LIFE_GL)
 373 void
 374 init_display(struct cell* grid)
 375 {
 376         dispatch_source_t timer;
 377
 378         timer = dispatch_source_create(DISPATCH_SOURCE_TYPE_TIMER, 0, 0, dispatch_get_main_queue());
 379         dispatch_source_set_timer(dispatch_time(DISPATCH_TIME_NOW, 0). 10000000, 1000);
 380         dispatch_source_set_event_handler(^{
 381                 int x,y;
 382                 x = 0;
 383                 for (x = 0; x < grid_x_size; ++x) {
 384                         for (y = 0; y < grid_y_size; ++y) {
 385                                 mvaddnstr(y, x, &grid[GRID_OFF(x,y)].display, 1);
 386                         }
 387                 }
 388                 refresh();
 389         });
 390         dispatch_resume(timer);
 391 }
 392 #endif /* defined(DISPATCH_LIFE_GL) */