funnysort.c

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