Lock all cells in the end so sorters finish pending operations.

[funnysort.git] / funnysort.c

/* funnysort.c */

/* remove the next line to enable asserts */
#define NDEBUG

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <stdbool.h>
#include <signal.h>

#include "congl.h"

#define WIDTH 50
#define HEIGHT 30
#define NCYCLES 1000000
#define SLEEP_TIME 0
#define SORTER_MOVE_TRIES 100
#define FREE_PER_ITEM 50
#define NSORTERS 5

typedef enum {A=0, EMPTY, SORTER} item_t;

struct board_s {
    unsigned int width;
    unsigned int height;
    bool size_valid;
    item_t **surface;
        pthread_mutex_t **lock;
    bool surface_valid;
};
typedef struct board_s board_t;

struct sorter_s {
        unsigned int column;
        unsigned int line;
};
typedef struct sorter_s sorter_t;

void count_item (board_t *, item_t *, unsigned int *);
void drop_item (unsigned int, unsigned int, board_t *, item_t *);
void erase_board (board_t *);
void fetch_item(unsigned int, unsigned int, item_t *);
void finish_board(board_t *);
void move_sorter (board_t *, sorter_t *);
void peek_item (unsigned int, unsigned int, board_t *, item_t *);
void pick_item (unsigned int, unsigned int, board_t *, item_t *);
void poke_item (unsigned int, unsigned int, board_t *, item_t);
void print_board (board_t *);
void print_item (unsigned int, unsigned int, item_t);
void print_mutexes (board_t *board);
void *launch_sorter (void *);
void setup_board(board_t *);

/* Erase the output medium. */
void erase_board (board_t *board)
{
        conglReset();
        conglClearScreen();
        conglMoveCursor(1, 1);
}

void move_sorter(board_t *board, sorter_t *sorter)
{
        /* sorter current position was locked before calling this function */

        assert(sorter != NULL);
        assert(sorter->column < WIDTH);
        assert(sorter->line < HEIGHT);

        int h, v;
        unsigned int newline, newcolumn;
        unsigned int ncycles;
        item_t item, sorter_item;

        ncycles = 0;
        do {
                /* Select random displacement. */
                h = random()%3 - 1;
                v = random()%3 - 1;

                newline = (sorter->line + (h+HEIGHT)) % HEIGHT;
                newcolumn = (sorter->column + (v+WIDTH)) % WIDTH;

                /* Do not try to move to current position */
                if ((newline != sorter->line) && (newcolumn != sorter->column)) {
                        /* lock position to where the sorter may move */
                        pthread_mutex_lock((board->lock)[newline]+newcolumn);
                        peek_item(newline, newcolumn, board, &item);
                        if (item != EMPTY) {
                                /* unlock if position if not available */
                                pthread_mutex_unlock((board->lock)[newline]+newcolumn);
                        }
                }
                ++ncycles;
        } while ((item != EMPTY) && (ncycles < SORTER_MOVE_TRIES));

        /* If sorter failed to move, respawn in random position */
        while (item != EMPTY) {
                newline = random()%HEIGHT;
                newcolumn = random()%WIDTH;

                /* Do not try to move to current position */
                if ((newline != sorter->line) && (newcolumn != sorter->column)) {
                        /* lock position to where the sorter may move */
                        pthread_mutex_lock((board->lock)[newline]+newcolumn);
                        peek_item(newline, newcolumn, board, &item);
                        if (item != EMPTY) {
                                /* unlock if position if not available */
                                pthread_mutex_unlock((board->lock)[newline]+newcolumn);
                        }
                }
        }

        /* Update board. */

        /* Don't reset the item if sorter just droped one. */
        /* If an item was droped, it will be different from SORTER. */
        peek_item(sorter->line, sorter->column, board, &sorter_item);
        if (sorter_item == SORTER) {
                poke_item (sorter->line, sorter->column, board, EMPTY);
        }
        poke_item(newline, newcolumn, board, SORTER);
        sorter->line = newline;
        sorter->column = newcolumn;

        pthread_mutex_unlock((board->lock)[newline]+newcolumn);

        assert(sorter->column < WIDTH);
        assert(sorter->line < HEIGHT);
}

void *launch_sorter (void *board)
{
        int itera;
        item_t item;
        unsigned int line;
        unsigned int column;
        sorter_t sorter;

        /* Place sorter in some free position. */ 
        do {
                line = random()%HEIGHT;
                column = random()%WIDTH;
                peek_item(line, column, board, &item);
        } while (item != EMPTY);
        poke_item(line, column, board, SORTER);
        sorter.line = line;
        sorter.column = column;

        for (itera = 0; itera <= NCYCLES; ++itera) {
        //for (itera = 0; 0==0; ++itera) {
                do {
                        move_sorter(board, &sorter);
                        pick_item(sorter.line, sorter.column, board, &item);

                        usleep(SLEEP_TIME);
                } while (item == EMPTY);

                /* because the sorter allways moves, if it drops the item it will not
                 * remain on the top of it */
                while (item != EMPTY) {
                        line = sorter.line;
                        column = sorter.column;

                        // Because the sorter may drop an item, it's current position must
                        // be locked until after it moves.
                        pthread_mutex_lock((((board_t *)board)->lock)[line]+column);
                        drop_item(sorter.line, sorter.column, board, &item);
                        move_sorter(board, &sorter);
                        pthread_mutex_unlock((((board_t *)board)->lock)[line]+column);

                        usleep(SLEEP_TIME);
                }

                /* leave the premisses */
                //for (r = 0; (r < 10); ++r) {
                //      move(board, sorter);
                //}
        }

        return NULL;
}

/* Try to pick an item. Don't pick other sorters :) */
void pick_item (unsigned int line, unsigned int column, board_t *board, item_t *item)
{
        assert (board != NULL);
        assert (board->size_valid);
        assert (board->surface_valid);
        assert (line < board->height);
        assert (column < board->width);
        assert (item != NULL);
        assert (*item == EMPTY);

        int newline, newcolumn;
        item_t newitem;
        int h, v; /* h: horizontal; v: vertical */

        for (h = -1; (h <= 1) && (*item == EMPTY); ++h) {
                for (v = -1; (v <= 1) && (*item == EMPTY); ++v) {
                        /* newline and newcolumn need to be allawys positive */
                        newline = (line+(h+HEIGHT))%HEIGHT;
                        newcolumn = (column+(v+WIDTH))%WIDTH;

                        /* Don't check current position because it is already locked */
                        if ((h != 0) && (v != 0)) {
                                pthread_mutex_lock((board->lock)[newline]+newcolumn);
                                peek_item(newline, newcolumn, board, &newitem);
                                if((newitem != EMPTY) && (newitem != SORTER)) {
                                        *item = newitem;
                                        poke_item(newline, newcolumn, board, EMPTY);
                                        /* we have the item */
                                }
                                pthread_mutex_unlock((board->lock)[newline]+newcolumn);
                        }
                }
        }

        /* we either pick an item or leave it as it is */
        assert ((*item == newitem) || (*item == EMPTY));
        assert (*item != SORTER);
}

/* Try to drop one item. The item needs to be droped in a position adjacent to
 * a similar item.
 */
void drop_item (unsigned int line, unsigned int column, board_t *board, item_t *item)
{
        assert (board != NULL);
        assert (board->size_valid);
        assert (board->surface_valid);
        assert (line < board->height);
        assert (column < board->width);
        assert (item != NULL);
        assert (*item != EMPTY);
        assert (*item != SORTER);

        int newline, newcolumn;
        int h, v; /* h: horizontal, v: vertical */
        item_t newitem;

        for (h = -1; (h <= 1) && (*item != EMPTY); ++h) {
                for (v = -1; (v <= 1) && (*item != EMPTY); ++v) {
                        /* newline and newcolumn need to be allawys positive */
                        newline = (line+h+HEIGHT)%HEIGHT;
                        newcolumn = (column+v+WIDTH)%WIDTH;

                        /* Don't check current position because it is already locked */
                        if ((h != 0) && (v != 0)) {
                                pthread_mutex_lock((board->lock)[newline]+newcolumn);
                                peek_item(newline, newcolumn, board, &newitem);
                                if(newitem == *item) {
                                        poke_item(line, column, board, newitem);
                                        *item = EMPTY;
                                        /* and the item is down */
                                }
                                pthread_mutex_unlock((board->lock)[newline]+newcolumn);
                        }
                }
        }
}

/* Print the base of the board, without any items. */
void print_board(board_t *board)
{
        assert(board->size_valid);
        assert(board->surface_valid);

        conglClearScreen();
        conglMoveCursor(1, 1);
}

void print_item(unsigned int line, unsigned int column, item_t item)
{
        struct properties_s {
                conglColor_t bg;
                conglColor_t fg;
                char symbol;
        };
        typedef struct properties_s properties_t;

        properties_t properties[] = {
                {congl_magenta, congl_white, ' '},
                {congl_green, congl_white, ' '},
                {congl_black, congl_white, ' '}
        //{'i'}, {'f'}, {'s'}
        };

        properties_t p;

        p = properties[item];
        conglDrawCharFull(line+1, column+1, p.symbol, p.fg, p.bg);

        //printf("%c: %d,%d\n", p.symbol, column, line);
}

/* Read an item from the board. */
void peek_item (unsigned int line, unsigned int column, board_t *board, item_t *item)
{
        assert(board != NULL);
        assert(board->size_valid);
        assert(board->surface_valid);
        assert(line < board->height);
        assert(column < board->width);
        assert(item != NULL);

        *item = board->surface[line][column];
        
        assert(*item == board->surface[line][column]);
}

/* Write an item in position (column,line) of the board. At the same time update
 * any output medium.
 */
void poke_item (unsigned int line, unsigned int column, board_t *board, item_t item)
{
        assert(board != NULL);
        assert(board->size_valid);
        assert(board->surface_valid);
        assert(line < board->height);
        assert(column < board->width);

        board->surface[line][column] = item;

        print_item (line, column, item);

        assert(board->surface[line][column] == item);
}

/* Fetch an item from somewhere. The purpose of this functin is to allow the
 * user to load one pattern every time the program runs. For now all items are
 * random (sort of).
 */
void fetch_item(unsigned int line, unsigned int column, item_t *item)
{
        assert(item != NULL);

        int number;
        
        /* generate one block in every FREE_PER_ITEM board cells */
        number = random()%FREE_PER_ITEM;
        switch (number) {
                case 0:
                        *item = A;
                        break;
                default:
                        *item = EMPTY;
                        break;
        }
}
void setup_board(board_t *board)
{
    assert (board->size_valid);
        assert (!board->surface_valid);

        unsigned int column, line;
        item_t item;

        //printf("Preparing board.\n");

        /* allocate space for the board */
        board->surface = (item_t **)calloc (board->height, sizeof(board->surface));
        board->lock = (pthread_mutex_t **)calloc (board->height, sizeof(board->lock));
        if (board->surface == NULL) {
                perror("board_setup");
                return;
        }
        if (board->lock == NULL) {
                perror("board_setup");
                return;
        }
        for (line = 0; line < board->height; ++line) {
                board->surface[line] = (item_t *)calloc (board->width, sizeof(item_t));
                board->lock[line] = (pthread_mutex_t *)calloc (board->width, sizeof(pthread_mutex_t));
                if (board->surface[line] == NULL) {
                        perror("board_setup");
                        return;
                }
                if (board->lock[line] == NULL) {
                        perror("board_setup");
                        return;
                }
        }
        board->surface_valid = true;

        //printf("Printing board.\n");
        print_board(board);
        //printf("Board printed.\n");

        /* fill the board with initial values */
        for (line = 0; line < board->height; ++line) {
                for (column = 0; column < board->width; ++column) {
                        fetch_item(line, column, &item);
                        poke_item(line, column, board, item);
                        pthread_mutex_init((board->lock)[line]+column, NULL);
                }
        }

    assert (board->surface_valid);
}

void finish_board (board_t *board)
{
        assert (board->surface_valid);

        int line;

        for (line = 0; line < board->height; ++line) {
                free (board->surface[line]);
                free (board->lock[line]);
        }
        free (board->surface);
        free (board->lock);
        board->surface_valid = false;

        erase_board(board);

        assert (!board->surface_valid);
}

void count_items(board_t *board, item_t *item, unsigned int *nitems)
{
        assert (board != NULL);
        assert (item != NULL);
        assert (nitems != NULL);

        unsigned int line, column;
        item_t this_item;
        unsigned int count;

        count = 0;
        for (line = 0; line < board->height; ++line) {
                for (column = 0; column < board->width; ++column) {
                        peek_item(line, column, board, &this_item);
                        if (this_item == *item) count++;
                }
        }
        
        *nitems = count;
}

void print_mutexes(board_t *board)
{
        int line, column;

        for (line = 0; line < board->height; ++line) {
                for (column = 0; column < board->width; ++column) {
                        print_item(line, column, board->surface[line][column]);
                        if (pthread_mutex_trylock((board->lock)[line]+column) == 0) {
                                printf("U");
                        } else {
                                printf("L");
                        }
                }
        }
}

int main (int argc, char *argv[])
{
    board_t board;
        unsigned int nitems_begin, nitems_finish;
        pthread_attr_t thread_attributes;
        pthread_t sorter[NSORTERS];
        item_t item;
        unsigned int n;
        unsigned int line, column;

    board.width = WIDTH;
    board.height = HEIGHT;
    board.size_valid = true;
        board.surface_valid = false;

        /* intialize random number generator */
        srandom((unsigned int)time(NULL));

        setup_board (&board);
        sleep(1);

        item = A;
        count_items(&board, &item, &nitems_begin);

        /* launch sorters */
        pthread_attr_init(&thread_attributes);
        for (n = 0; n < NSORTERS; ++n) {
                pthread_create(sorter+n, &thread_attributes, launch_sorter, (void *)(&board));
        }
        
        /* wait for keypress (return) */
        getchar();

        count_items(&board, &item, &nitems_finish);
        //print_mutexes(&board);

        /* make shure the sorters didn't ate items (they can have one with
         * themselves) */
        assert((nitems_begin - nitems_finish) <= NSORTERS);

        /* lock the board so sorters finish any pending operation */
        for (line = 0; line < board.height; ++line) {
                for (column = 0; column < board.width; ++column) {
                        pthread_mutex_lock((board.lock)[line]+column);
                }
        }

        for (n = 0; n < NSORTERS; ++n) {
                pthread_cancel(sorter[n]);
        }

        finish_board (&board);

        printf("All good.\n");

        exit(0);
}