funnysort.c

   1 /* funnysort.c */
   2
   3 /* remove the next line to enable asserts */
   4 #define NDEBUG
   5
   6 #include <stdio.h>
   7 #include <assert.h>
   8 #include <stdlib.h>
   9 #include <pthread.h>
  10 #include <unistd.h>
  11 #include <stdbool.h>
  12 #include <signal.h>
  13
  14 #include "congl.h"
  15
  16 #define WIDTH 50
  17 #define HEIGHT 30
  18 #define NCYCLES 1000000
  19 #define SLEEP_TIME 0
  20 #define SORTER_MOVE_TRIES 100
  21 #define FREE_PER_ITEM 50
  22 #define NSORTERS 5
  23
  24 typedef enum {A=0, EMPTY, SORTER} item_t;
  25
  26 struct board_s {
  27     unsigned int width;
  28     unsigned int height;
  29     bool size_valid;
  30     item_t **surface;
  31         pthread_mutex_t **lock;
  32     bool surface_valid;
  33 };
  34 typedef struct board_s board_t;
  35
  36 struct sorter_s {
  37         unsigned int column;
  38         unsigned int line;
  39 };
  40 typedef struct sorter_s sorter_t;
  41
  42 void count_item (board_t *, item_t *, unsigned int *);
  43 void drop_item (unsigned int, unsigned int, board_t *, item_t *);
  44 void erase_board (board_t *);
  45 void fetch_item(unsigned int, unsigned int, item_t *);
  46 void finish_board(board_t *);
  47 void move_sorter (board_t *, sorter_t *);
  48 void peek_item (unsigned int, unsigned int, board_t *, item_t *);
  49 void pick_item (unsigned int, unsigned int, board_t *, item_t *);
  50 void poke_item (unsigned int, unsigned int, board_t *, item_t);
  51 void print_board (board_t *);
  52 void print_item (unsigned int, unsigned int, item_t);
  53 void print_mutexes (board_t *board);
  54 void *launch_sorter (void *);
  55 void setup_board(board_t *);
  56
  57 /* Erase the output medium. */
  58 void erase_board (board_t *board)
  59 {
  60         conglReset();
  61         conglClearScreen();
  62         conglMoveCursor(1, 1);
  63 }
  64
  65 void move_sorter(board_t *board, sorter_t *sorter)
  66 {
  67         /* sorter current position was locked before calling this function */
  68
  69         assert(sorter != NULL);
  70         assert(sorter->column < board->width);
  71         assert(sorter->line < board->height);
  72
  73         unsigned int newline, newcolumn;
  74         unsigned int ncycles;
  75         item_t item, sorter_item;
  76         int h, hoffset, hrange;
  77         int v, voffset, vrange;
  78
  79         // set default values to range and offset of random movement
  80         hoffset = -1;
  81         hrange = 3;
  82         voffset = -1;
  83         vrange = 3;
  84
  85         ncycles = 0;
  86         do {
  87                 /* Select random displacement. */
  88                 h = random()%hrange + hoffset;
  89                 v = random()%vrange + voffset;
  90
  91                 newline = (sorter->line + (h+board->height)) % board->height;
  92                 newcolumn = (sorter->column + (v+board->width)) % board->width;
  93
  94                 /* Do not try to move to current position */
  95                 if ((newline != sorter->line) && (newcolumn != sorter->column)) {
  96                         /* lock position to where the sorter may move */
  97                         pthread_mutex_lock((board->lock)[newline]+newcolumn);
  98                         peek_item(newline, newcolumn, board, &item);
  99                         if (item != EMPTY) {
 100                                 /* unlock if position if not available */
 101                                 pthread_mutex_unlock((board->lock)[newline]+newcolumn);
 102                         }
 103                 }
 104                 ++ncycles;
 105         } while ((item != EMPTY) && (ncycles < SORTER_MOVE_TRIES));
 106
 107         /* If sorter failed to move, respawn in random position */
 108         while (item != EMPTY) {
 109                 newline = random()%board->height;
 110                 newcolumn = random()%board->width;
 111
 112                 /* Do not try to move to current position */
 113                 if ((newline != sorter->line) && (newcolumn != sorter->column)) {
 114                         /* lock position to where the sorter may move */
 115                         pthread_mutex_lock((board->lock)[newline]+newcolumn);
 116                         peek_item(newline, newcolumn, board, &item);
 117                         if (item != EMPTY) {
 118                                 /* unlock if position if not available */
 119                                 pthread_mutex_unlock((board->lock)[newline]+newcolumn);
 120                         }
 121                 }
 122         }
 123
 124         /* Update board. */
 125
 126         /* Don't reset the item if sorter just droped one. */
 127         /* If an item was droped, it will be different from SORTER. */
 128         peek_item(sorter->line, sorter->column, board, &sorter_item);
 129         if (sorter_item == SORTER) {
 130                 poke_item (sorter->line, sorter->column, board, EMPTY);
 131         }
 132         poke_item(newline, newcolumn, board, SORTER);
 133         sorter->line = newline;
 134         sorter->column = newcolumn;
 135
 136         pthread_mutex_unlock((board->lock)[newline]+newcolumn);
 137
 138         assert(sorter->column < board->width);
 139         assert(sorter->line < board->height);
 140 }
 141
 142 void *launch_sorter (void *board)
 143 {
 144         int itera;
 145         item_t item;
 146         unsigned int line;
 147         unsigned int column;
 148         sorter_t sorter;
 149
 150         /* Place sorter in some free position. */
 151         do {
 152                 line = random()%((board_t *)board)->height;
 153                 column = random()%((board_t *)board)->width;
 154                 peek_item(line, column, board, &item);
 155         } while (item != EMPTY);
 156         poke_item(line, column, board, SORTER);
 157         sorter.line = line;
 158         sorter.column = column;
 159
 160         for (itera = 0; itera <= NCYCLES; ++itera) {
 161         //for (itera = 0; 0==0; ++itera) {
 162                 do {
 163                         move_sorter(board, &sorter);
 164                         pick_item(sorter.line, sorter.column, board, &item);
 165
 166                         usleep(SLEEP_TIME);
 167                 } while (item == EMPTY);
 168
 169                 /* because the sorter allways moves, if it drops the item it will not
 170                  * remain on the top of it */
 171                 while (item != EMPTY) {
 172                         line = sorter.line;
 173                         column = sorter.column;
 174
 175                         // Because the sorter may drop an item, it's current position must
 176                         // be locked until after it moves.
 177                         pthread_mutex_lock((((board_t *)board)->lock)[line]+column);
 178                         drop_item(sorter.line, sorter.column, board, &item);
 179                         move_sorter(board, &sorter);
 180                         pthread_mutex_unlock((((board_t *)board)->lock)[line]+column);
 181
 182                         usleep(SLEEP_TIME);
 183                 }
 184
 185                 /* leave the premisses */
 186                 //for (r = 0; (r < 10); ++r) {
 187                 //      move(board, sorter);
 188                 //}
 189         }
 190
 191         return NULL;
 192 }
 193
 194 /* Try to pick an item. Don't pick other sorters :) */
 195 void pick_item (unsigned int line, unsigned int column, board_t *board, item_t *item)
 196 {
 197         assert (board != NULL);
 198         assert (board->size_valid);
 199         assert (board->surface_valid);
 200         assert (line < board->height);
 201         assert (column < board->width);
 202         assert (item != NULL);
 203         assert (*item == EMPTY);
 204
 205         int newline, newcolumn;
 206         item_t newitem;
 207         int h, v; /* h: horizontal; v: vertical */
 208
 209         for (h = -1; (h <= 1) && (*item == EMPTY); ++h) {
 210                 for (v = -1; (v <= 1) && (*item == EMPTY); ++v) {
 211                         /* newline and newcolumn need to be allawys positive */
 212                         newline = (line+(h+board->height))%board->height;
 213                         newcolumn = (column+(v+board->width))%board->width;
 214
 215                         /* Don't check current position because it is already locked */
 216                         if ((h != 0) && (v != 0)) {
 217                                 pthread_mutex_lock((board->lock)[newline]+newcolumn);
 218                                 peek_item(newline, newcolumn, board, &newitem);
 219                                 if((newitem != EMPTY) && (newitem != SORTER)) {
 220                                         *item = newitem;
 221                                         poke_item(newline, newcolumn, board, EMPTY);
 222                                         /* we have the item */
 223                                 }
 224                                 pthread_mutex_unlock((board->lock)[newline]+newcolumn);
 225                         }
 226                 }
 227         }
 228
 229         /* we either pick an item or leave it as it is */
 230         assert ((*item == newitem) || (*item == EMPTY));
 231         assert (*item != SORTER);
 232 }
 233
 234 /* Try to drop one item. The item needs to be droped in a position adjacent to
 235  * a similar item.
 236  */
 237 void drop_item (unsigned int line, unsigned int column, board_t *board, item_t *item)
 238 {
 239         assert (board != NULL);
 240         assert (board->size_valid);
 241         assert (board->surface_valid);
 242         assert (line < board->height);
 243         assert (column < board->width);
 244         assert (item != NULL);
 245         assert (*item != EMPTY);
 246         assert (*item != SORTER);
 247
 248         int newline, newcolumn;
 249         int h, v; /* h: horizontal, v: vertical */
 250         item_t newitem;
 251
 252         for (h = -1; (h <= 1) && (*item != EMPTY); ++h) {
 253                 for (v = -1; (v <= 1) && (*item != EMPTY); ++v) {
 254                         /* newline and newcolumn need to be allawys positive */
 255                         newline = (line+h+board->height)%board->height;
 256                         newcolumn = (column+v+board->width)%board->width;
 257
 258                         /* Don't check current position because it is already locked */
 259                         if ((h != 0) && (v != 0)) {
 260                                 pthread_mutex_lock((board->lock)[newline]+newcolumn);
 261                                 peek_item(newline, newcolumn, board, &newitem);
 262                                 if(newitem == *item) {
 263                                         poke_item(line, column, board, newitem);
 264                                         *item = EMPTY;
 265                                         /* and the item is down */
 266                                 }
 267                                 pthread_mutex_unlock((board->lock)[newline]+newcolumn);
 268                         }
 269                 }
 270         }
 271 }
 272
 273 /* Print the base of the board, without any items. */
 274 void print_board(board_t *board)
 275 {
 276         assert(board->size_valid);
 277         assert(board->surface_valid);
 278
 279         conglClearScreen();
 280         conglMoveCursor(1, 1);
 281 }
 282
 283 void print_item(unsigned int line, unsigned int column, item_t item)
 284 {
 285         struct properties_s {
 286                 conglColor_t bg;
 287                 conglColor_t fg;
 288                 char symbol;
 289         };
 290         typedef struct properties_s properties_t;
 291
 292         properties_t properties[] = {
 293                 {congl_magenta, congl_white, ' '},
 294                 {congl_green, congl_white, ' '},
 295                 {congl_black, congl_white, ' '}
 296         //{'i'}, {'f'}, {'s'}
 297         };
 298
 299         properties_t p;
 300
 301         p = properties[item];
 302         conglDrawCharFull(line+1, column+1, p.symbol, p.fg, p.bg);
 303
 304         //printf("%c: %d,%d\n", p.symbol, column, line);
 305 }
 306
 307 /* Read an item from the board. */
 308 void peek_item (unsigned int line, unsigned int column, board_t *board, item_t *item)
 309 {
 310         assert(board != NULL);
 311         assert(board->size_valid);
 312         assert(board->surface_valid);
 313         assert(line < board->height);
 314         assert(column < board->width);
 315         assert(item != NULL);
 316
 317         *item = board->surface[line][column];
 318
 319         assert(*item == board->surface[line][column]);
 320 }
 321
 322 /* Write an item in position (column,line) of the board. At the same time update
 323  * any output medium.
 324  */
 325 void poke_item (unsigned int line, unsigned int column, board_t *board, item_t item)
 326 {
 327         assert(board != NULL);
 328         assert(board->size_valid);
 329         assert(board->surface_valid);
 330         assert(line < board->height);
 331         assert(column < board->width);
 332
 333         board->surface[line][column] = item;
 334
 335         print_item (line, column, item);
 336
 337         assert(board->surface[line][column] == item);
 338 }
 339
 340 /* Fetch an item from somewhere. The purpose of this functin is to allow the
 341  * user to load one pattern every time the program runs. For now all items are
 342  * random (sort of).
 343  */
 344 void fetch_item(unsigned int line, unsigned int column, item_t *item)
 345 {
 346         assert(item != NULL);
 347
 348         int number;
 349
 350         /* generate one block in every FREE_PER_ITEM board cells */
 351         number = random()%FREE_PER_ITEM;
 352         switch (number) {
 353                 case 0:
 354                         *item = A;
 355                         break;
 356                 default:
 357                         *item = EMPTY;
 358                         break;
 359         }
 360 }
 361 void setup_board(board_t *board)
 362 {
 363     assert (board->size_valid);
 364         assert (!board->surface_valid);
 365
 366         unsigned int column, line;
 367         item_t item;
 368
 369         //printf("Preparing board.\n");
 370
 371         /* allocate space for the board */
 372         board->surface = (item_t **)calloc (board->height, sizeof(board->surface));
 373         board->lock = (pthread_mutex_t **)calloc (board->height, sizeof(board->lock));
 374         if (board->surface == NULL) {
 375                 perror("board_setup");
 376                 return;
 377         }
 378         if (board->lock == NULL) {
 379                 perror("board_setup");
 380                 return;
 381         }
 382         for (line = 0; line < board->height; ++line) {
 383                 board->surface[line] = (item_t *)calloc (board->width, sizeof(item_t));
 384                 board->lock[line] = (pthread_mutex_t *)calloc (board->width, sizeof(pthread_mutex_t));
 385                 if (board->surface[line] == NULL) {
 386                         perror("board_setup");
 387                         return;
 388                 }
 389                 if (board->lock[line] == NULL) {
 390                         perror("board_setup");
 391                         return;
 392                 }
 393         }
 394         board->surface_valid = true;
 395
 396         //printf("Printing board.\n");
 397         print_board(board);
 398         //printf("Board printed.\n");
 399
 400         /* fill the board with initial values */
 401         for (line = 0; line < board->height; ++line) {
 402                 for (column = 0; column < board->width; ++column) {
 403                         fetch_item(line, column, &item);
 404                         poke_item(line, column, board, item);
 405                         pthread_mutex_init((board->lock)[line]+column, NULL);
 406                 }
 407         }
 408
 409     assert (board->surface_valid);
 410 }
 411
 412 void finish_board (board_t *board)
 413 {
 414         assert (board->surface_valid);
 415
 416         int line;
 417
 418         for (line = 0; line < board->height; ++line) {
 419                 free (board->surface[line]);
 420                 free (board->lock[line]);
 421         }
 422         free (board->surface);
 423         free (board->lock);
 424         board->surface_valid = false;
 425
 426         erase_board(board);
 427
 428         assert (!board->surface_valid);
 429 }
 430
 431 void count_items(board_t *board, item_t *item, unsigned int *nitems)
 432 {
 433         assert (board != NULL);
 434         assert (item != NULL);
 435         assert (nitems != NULL);
 436
 437         unsigned int line, column;
 438         item_t this_item;
 439         unsigned int count;
 440
 441         count = 0;
 442         for (line = 0; line < board->height; ++line) {
 443                 for (column = 0; column < board->width; ++column) {
 444                         peek_item(line, column, board, &this_item);
 445                         if (this_item == *item) count++;
 446                 }
 447         }
 448
 449         *nitems = count;
 450 }
 451
 452 void print_mutexes(board_t *board)
 453 {
 454         int line, column;
 455
 456         for (line = 0; line < board->height; ++line) {
 457                 for (column = 0; column < board->width; ++column) {
 458                         print_item(line, column, board->surface[line][column]);
 459                         if (pthread_mutex_trylock((board->lock)[line]+column) == 0) {
 460                                 printf("U");
 461                         } else {
 462                                 printf("L");
 463                         }
 464                 }
 465         }
 466 }
 467
 468 int main (int argc, char *argv[])
 469 {
 470     board_t board;
 471         unsigned int nitems_begin, nitems_finish;
 472         pthread_attr_t thread_attributes;
 473         pthread_t sorter[NSORTERS];
 474         item_t item;
 475         unsigned int n;
 476         unsigned int line, column;
 477
 478     board.width = WIDTH;
 479     board.height = HEIGHT;
 480     board.size_valid = true;
 481         board.surface_valid = false;
 482
 483         /* intialize random number generator */
 484         srandom((unsigned int)time(NULL));
 485
 486         setup_board (&board);
 487         sleep(1);
 488
 489         item = A;
 490         count_items(&board, &item, &nitems_begin);
 491
 492         /* launch sorters */
 493         pthread_attr_init(&thread_attributes);
 494         for (n = 0; n < NSORTERS; ++n) {
 495                 pthread_create(sorter+n, &thread_attributes, launch_sorter, (void *)(&board));
 496         }
 497
 498         /* wait for keypress (return) */
 499         getchar();
 500
 501         count_items(&board, &item, &nitems_finish);
 502         //print_mutexes(&board);
 503
 504         /* make shure the sorters didn't ate items (they can have one with
 505          * themselves) */
 506         assert((nitems_begin - nitems_finish) <= NSORTERS);
 507
 508         /* lock the board so sorters finish any pending operation */
 509         for (line = 0; line < board.height; ++line) {
 510                 for (column = 0; column < board.width; ++column) {
 511                         pthread_mutex_lock((board.lock)[line]+column);
 512                 }
 513         }
 514
 515         for (n = 0; n < NSORTERS; ++n) {
 516                 pthread_cancel(sorter[n]);
 517         }
 518
 519         finish_board (&board);
 520
 521         printf("All good.\n");
 522
 523         exit(0);
 524 }
 525