Introduced range and offset in sorter movement.
[funnysort.git] / funnysort.c
blob06b6fb12713d3c81e8223a79ee761f3e8159b967
1 /* funnysort.c */
3 /* remove the next line to enable asserts */
4 #define NDEBUG
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>
14 #include "congl.h"
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
24 typedef enum {A=0, EMPTY, SORTER} item_t;
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;
34 typedef struct board_s board_t;
36 struct sorter_s {
37 unsigned int column;
38 unsigned int line;
40 typedef struct sorter_s sorter_t;
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 *);
57 /* Erase the output medium. */
58 void erase_board (board_t *board)
60 conglReset();
61 conglClearScreen();
62 conglMoveCursor(1, 1);
65 void move_sorter(board_t *board, sorter_t *sorter)
67 /* sorter current position was locked before calling this function */
69 assert(sorter != NULL);
70 assert(sorter->column < board->width);
71 assert(sorter->line < board->height);
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;
79 // set default values to range and offset of random movement
80 hoffset = -1;
81 hrange = 3;
82 voffset = -1;
83 vrange = 3;
85 ncycles = 0;
86 do {
87 /* Select random displacement. */
88 h = random()%hrange + hoffset;
89 v = random()%vrange + voffset;
91 newline = (sorter->line + (h+board->height)) % board->height;
92 newcolumn = (sorter->column + (v+board->width)) % board->width;
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);
104 ++ncycles;
105 } while ((item != EMPTY) && (ncycles < SORTER_MOVE_TRIES));
107 /* If sorter failed to move, respawn in random position */
108 while (item != EMPTY) {
109 newline = random()%board->height;
110 newcolumn = random()%board->width;
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);
124 /* Update board. */
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);
132 poke_item(newline, newcolumn, board, SORTER);
133 sorter->line = newline;
134 sorter->column = newcolumn;
136 pthread_mutex_unlock((board->lock)[newline]+newcolumn);
138 assert(sorter->column < board->width);
139 assert(sorter->line < board->height);
142 void *launch_sorter (void *board)
144 int itera;
145 item_t item;
146 unsigned int line;
147 unsigned int column;
148 sorter_t sorter;
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;
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);
166 usleep(SLEEP_TIME);
167 } while (item == EMPTY);
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;
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);
182 usleep(SLEEP_TIME);
185 /* leave the premisses */
186 //for (r = 0; (r < 10); ++r) {
187 // move(board, sorter);
191 return NULL;
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)
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);
205 int newline, newcolumn;
206 item_t newitem;
207 int h, v; /* h: horizontal; v: vertical */
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;
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 */
224 pthread_mutex_unlock((board->lock)[newline]+newcolumn);
229 /* we either pick an item or leave it as it is */
230 assert ((*item == newitem) || (*item == EMPTY));
231 assert (*item != SORTER);
234 /* Try to drop one item. The item needs to be droped in a position adjacent to
235 * a similar item.
237 void drop_item (unsigned int line, unsigned int column, board_t *board, item_t *item)
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);
248 int newline, newcolumn;
249 int h, v; /* h: horizontal, v: vertical */
250 item_t newitem;
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;
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 */
267 pthread_mutex_unlock((board->lock)[newline]+newcolumn);
273 /* Print the base of the board, without any items. */
274 void print_board(board_t *board)
276 assert(board->size_valid);
277 assert(board->surface_valid);
279 conglClearScreen();
280 conglMoveCursor(1, 1);
283 void print_item(unsigned int line, unsigned int column, item_t item)
285 struct properties_s {
286 conglColor_t bg;
287 conglColor_t fg;
288 char symbol;
290 typedef struct properties_s properties_t;
292 properties_t properties[] = {
293 {congl_magenta, congl_white, ' '},
294 {congl_green, congl_white, ' '},
295 {congl_black, congl_white, ' '}
296 //{'i'}, {'f'}, {'s'}
299 properties_t p;
301 p = properties[item];
302 conglDrawCharFull(line+1, column+1, p.symbol, p.fg, p.bg);
304 //printf("%c: %d,%d\n", p.symbol, column, line);
307 /* Read an item from the board. */
308 void peek_item (unsigned int line, unsigned int column, board_t *board, item_t *item)
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);
317 *item = board->surface[line][column];
319 assert(*item == board->surface[line][column]);
322 /* Write an item in position (column,line) of the board. At the same time update
323 * any output medium.
325 void poke_item (unsigned int line, unsigned int column, board_t *board, item_t item)
327 assert(board != NULL);
328 assert(board->size_valid);
329 assert(board->surface_valid);
330 assert(line < board->height);
331 assert(column < board->width);
333 board->surface[line][column] = item;
335 print_item (line, column, item);
337 assert(board->surface[line][column] == item);
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).
344 void fetch_item(unsigned int line, unsigned int column, item_t *item)
346 assert(item != NULL);
348 int number;
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;
361 void setup_board(board_t *board)
363 assert (board->size_valid);
364 assert (!board->surface_valid);
366 unsigned int column, line;
367 item_t item;
369 //printf("Preparing board.\n");
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;
378 if (board->lock == NULL) {
379 perror("board_setup");
380 return;
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;
389 if (board->lock[line] == NULL) {
390 perror("board_setup");
391 return;
394 board->surface_valid = true;
396 //printf("Printing board.\n");
397 print_board(board);
398 //printf("Board printed.\n");
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);
409 assert (board->surface_valid);
412 void finish_board (board_t *board)
414 assert (board->surface_valid);
416 int line;
418 for (line = 0; line < board->height; ++line) {
419 free (board->surface[line]);
420 free (board->lock[line]);
422 free (board->surface);
423 free (board->lock);
424 board->surface_valid = false;
426 erase_board(board);
428 assert (!board->surface_valid);
431 void count_items(board_t *board, item_t *item, unsigned int *nitems)
433 assert (board != NULL);
434 assert (item != NULL);
435 assert (nitems != NULL);
437 unsigned int line, column;
438 item_t this_item;
439 unsigned int count;
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++;
449 *nitems = count;
452 void print_mutexes(board_t *board)
454 int line, column;
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");
468 int main (int argc, char *argv[])
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;
478 board.width = WIDTH;
479 board.height = HEIGHT;
480 board.size_valid = true;
481 board.surface_valid = false;
483 /* intialize random number generator */
484 srandom((unsigned int)time(NULL));
486 setup_board (&board);
487 sleep(1);
489 item = A;
490 count_items(&board, &item, &nitems_begin);
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));
498 /* wait for keypress (return) */
499 getchar();
501 count_items(&board, &item, &nitems_finish);
502 //print_mutexes(&board);
504 /* make shure the sorters didn't ate items (they can have one with
505 * themselves) */
506 assert((nitems_begin - nitems_finish) <= NSORTERS);
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);
515 for (n = 0; n < NSORTERS; ++n) {
516 pthread_cancel(sorter[n]);
519 finish_board (&board);
521 printf("All good.\n");
523 exit(0);