3 /* remove the next line to enable asserts */
18 #define NCYCLES 1000000
20 #define SORTER_MOVE_TRIES 100
21 #define FREE_PER_ITEM 50
24 typedef enum {A
=0, EMPTY
, SORTER
} item_t
;
31 pthread_mutex_t
**lock
;
34 typedef struct board_s board_t
;
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 *launch_sorter (void *);
54 void setup_board(board_t
*);
56 /* Erase the output medium. */
57 void erase_board (board_t
*board
)
63 void move_sorter(board_t
*board
, sorter_t
*sorter
)
65 assert(sorter
!= NULL
);
66 assert(sorter
->column
< WIDTH
);
67 assert(sorter
->line
< HEIGHT
);
70 unsigned int newline
, newcolumn
;
72 item_t item
, sorter_item
;
76 /* Select random displacement. */
80 newline
= (sorter
->line
+ (h
+HEIGHT
)) % HEIGHT
;
81 newcolumn
= (sorter
->column
+ (v
+WIDTH
)) % WIDTH
;
83 peek_item(newline
, newcolumn
, board
, &item
);
85 } while ((item
!= EMPTY
) && (ncycles
< SORTER_MOVE_TRIES
));
87 /* If sorter failed to move, respawn in random position */
88 if (ncycles
== SORTER_MOVE_TRIES
) {
90 newline
= random()%HEIGHT
;
91 newcolumn
= random()%WIDTH
;
92 peek_item(newline
, newcolumn
, board
, &item
);
93 } while (item
!= EMPTY
);
98 /* Don't reset the item if sorter just droped one. */
99 /* If an item was droped, it will be different of SORTER. */
100 peek_item(sorter
->line
, sorter
->column
, board
, &sorter_item
);
101 if (sorter_item
== SORTER
) {
102 poke_item (sorter
->line
, sorter
->column
, board
, EMPTY
);
104 poke_item(newline
, newcolumn
, board
, SORTER
);
105 sorter
->line
= newline
;
106 sorter
->column
= newcolumn
;
108 assert(sorter
->column
< WIDTH
);
109 assert(sorter
->line
< HEIGHT
);
112 void *launch_sorter (void *board
)
120 /* Place sorter in some free position. */
122 line
= random()%HEIGHT
;
123 column
= random()%WIDTH
;
124 peek_item(line
, column
, board
, &item
);
125 } while (item
!= EMPTY
);
126 poke_item(line
, column
, board
, SORTER
);
128 sorter
.column
= column
;
130 for (itera
= 0; itera
<= NCYCLES
; ++itera
) {
131 //for (itera = 0; 0==0; ++itera) {
133 move_sorter(board
, &sorter
);
134 pick_item(sorter
.line
, sorter
.column
, board
, &item
);
136 } while (item
== EMPTY
);
138 /* because the sorter allways moves, if it drops the item it will not
139 * remain on the top of it */
140 while (item
!= EMPTY
) {
141 drop_item(sorter
.line
, sorter
.column
, board
, &item
);
142 move_sorter(board
, &sorter
);
146 /* leave the premisses */
147 //for (r = 0; (r < 10); ++r) {
148 // move(board, sorter);
155 /* Try to pick an item. Don't pick other sorters :) */
156 void pick_item (unsigned int line
, unsigned int column
, board_t
*board
, item_t
*item
)
158 assert (board
!= NULL
);
159 assert (board
->size_valid
);
160 assert (board
->surface_valid
);
161 assert (line
< board
->height
);
162 assert (column
< board
->width
);
163 assert (item
!= NULL
);
164 assert (*item
== EMPTY
);
166 int newline
, newcolumn
;
168 int h
, v
; /* h: horizontal; v: vertical */
170 for (h
= -1; (h
<= 1) && (*item
== EMPTY
); ++h
) {
171 for (v
= -1; (v
<= 1) && (*item
== EMPTY
); ++v
) {
172 /* newline and newcolumn need to be allawys positive */
173 newline
= (line
+(h
+HEIGHT
))%HEIGHT
;
174 newcolumn
= (column
+(v
+WIDTH
))%WIDTH
;
176 pthread_mutex_lock(board
->lock
[newline
]+newcolumn
);
177 peek_item(newline
, newcolumn
, board
, &newitem
);
178 if((newitem
!= EMPTY
) && (newitem
!= SORTER
)) {
180 poke_item(newline
, newcolumn
, board
, EMPTY
);
181 /* we have the item */
183 pthread_mutex_unlock(board
->lock
[newline
]+newcolumn
);
187 /* we either pick an item or leave it as it is */
188 assert ((*item
== newitem
) || (*item
== EMPTY
));
189 assert (*item
!= SORTER
);
192 /* Try to drop one item. The item needs to be droped in a position adjacent to
195 void drop_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
);
204 assert (*item
!= SORTER
);
206 int newline
, newcolumn
;
207 int h
, v
; /* h: horizontal, v: vertical */
210 for (h
= -1; (h
<= 1) && (*item
!= EMPTY
); ++h
) {
211 for (v
= -1; (v
<= 1) && (*item
!= EMPTY
); ++v
) {
212 /* newline and newcolumn need to be allawys positive */
213 newline
= (line
+h
+HEIGHT
)%HEIGHT
;
214 newcolumn
= (column
+v
+WIDTH
)%WIDTH
;
216 pthread_mutex_lock(board
->lock
[newline
]+newcolumn
);
217 peek_item(newline
, newcolumn
, board
, &newitem
);
218 if(newitem
== *item
) {
219 poke_item(line
, column
, board
, newitem
);
221 /* and the item is down */
223 pthread_mutex_unlock(board
->lock
[newline
]+newcolumn
);
228 /* Print the base of the board, without any items. */
229 void print_board(board_t
*board
)
231 assert(board
->size_valid
);
232 assert(board
->surface_valid
);
235 conglMoveCursor(1, 1);
238 void print_item(unsigned int line
, unsigned int column
, item_t item
)
240 struct properties_s
{
245 typedef struct properties_s properties_t
;
247 properties_t properties
[] = {
248 {congl_magenta
, congl_white
, ' '},
249 {congl_green
, congl_white
, ' '},
250 {congl_black
, congl_white
, ' '}
251 //{'i'}, {'f'}, {'s'}
256 p
= properties
[item
];
257 conglDrawCharFull(line
+1, column
+1, p
.symbol
, p
.fg
, p
.bg
);
259 //printf("%c: %d,%d\n", p.symbol, column, line);
262 /* Read an item from the board. */
263 void peek_item (unsigned int line
, unsigned int column
, board_t
*board
, item_t
*item
)
265 assert(board
!= NULL
);
266 assert(board
->size_valid
);
267 assert(board
->surface_valid
);
268 assert(line
< board
->height
);
269 assert(column
< board
->width
);
270 assert(item
!= NULL
);
272 *item
= board
->surface
[line
][column
];
274 assert(*item
== board
->surface
[line
][column
]);
277 /* Write an item in position (column,line) of the board. At the same time update
280 void poke_item (unsigned int line
, unsigned int column
, board_t
*board
, item_t item
)
282 assert(board
!= NULL
);
283 assert(board
->size_valid
);
284 assert(board
->surface_valid
);
285 assert(line
< board
->height
);
286 assert(column
< board
->width
);
288 board
->surface
[line
][column
] = item
;
290 print_item (line
, column
, item
);
292 assert(board
->surface
[line
][column
] == item
);
295 /* Fetch an item from somewhere. The purpose of this functin is to allow the
296 * user to load one pattern every time the program runs. For now all items are
299 void fetch_item(unsigned int line
, unsigned int column
, item_t
*item
)
301 assert(item
!= NULL
);
305 /* generate one block in every FREE_PER_ITEM board cells */
306 number
= random()%FREE_PER_ITEM
;
316 void setup_board(board_t
*board
)
318 assert (board
->size_valid
);
319 assert (!board
->surface_valid
);
321 unsigned int column
, line
;
324 //printf("Preparing board.\n");
326 /* allocate space for the board */
327 board
->surface
= calloc (board
->height
, sizeof(board
->surface
));
328 board
->lock
= calloc (board
->height
, sizeof(board
->lock
));
329 if (board
->surface
== NULL
) {
330 perror("board_setup");
333 if (board
->lock
== NULL
) {
334 perror("board_setup");
337 for (line
= 0; line
< board
->height
; ++line
) {
338 board
->surface
[line
] = calloc (board
->width
, sizeof(item_t
));
339 board
->lock
[line
] = calloc (board
->width
, sizeof(pthread_mutex_t
));
340 if (board
->surface
[line
] == NULL
) {
341 perror("board_setup");
344 if (board
->lock
[line
] == NULL
) {
345 perror("board_setup");
349 board
->surface_valid
= true;
351 //printf("Printing board.\n");
353 //printf("Board printed.\n");
355 /* fill the board with initial values */
356 for (line
= 0; line
< board
->height
; ++line
) {
357 for (column
= 0; column
< board
->width
; ++column
) {
358 fetch_item(line
, column
, &item
);
359 poke_item(line
, column
, board
, item
);
360 pthread_mutex_init(board
->lock
[line
]+column
, NULL
);
364 assert (board
->surface_valid
);
367 void finish_board (board_t
*board
)
369 assert (board
->surface_valid
);
373 for (line
= 0; line
< board
->height
; ++line
) {
374 free (board
->surface
[line
]);
375 free (board
->lock
[line
]);
377 free (board
->surface
);
379 board
->surface_valid
= false;
383 assert (!board
->surface_valid
);
386 void count_items(board_t
*board
, item_t
*item
, unsigned int *nitems
)
388 assert (board
!= NULL
);
389 assert (item
!= NULL
);
390 assert (nitems
!= NULL
);
392 unsigned int line
, column
;
397 for (line
= 0; line
< board
->height
; ++line
) {
398 for (column
= 0; column
< board
->width
; ++column
) {
399 peek_item(line
, column
, board
, &this_item
);
400 if (this_item
== *item
) count
++;
407 int main (int argc
, char *argv
[])
410 unsigned int nitems_begin
, nitems_finish
;
411 pthread_attr_t thread_attributes
;
412 pthread_t sorter
[NSORTERS
];
417 board
.height
= HEIGHT
;
418 board
.size_valid
= true;
419 board
.surface_valid
= false;
421 /* intialize random number generator */
422 srandom((unsigned int)time(NULL
));
424 setup_board (&board
);
428 count_items(&board
, &item
, &nitems_begin
);
431 pthread_attr_init(&thread_attributes
);
432 for (n
= 0; n
< NSORTERS
; ++n
) {
433 pthread_create(sorter
+n
, &thread_attributes
, launch_sorter
, (void *)(&board
));
436 /* wait for keypress (return) */
440 count_items(&board
, &item
, &nitems_finish
);
442 /* make shure the sorters didn't ate items (they can have one with
444 assert((nitems_begin
- nitems_finish
) <= NSORTERS
);
446 for (n
= 0; n
< NSORTERS
; ++n
) {
447 pthread_cancel(sorter
[n
]);
450 finish_board (&board
);
452 printf("All good.\n");