Many changes.

[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 300
#define SLEEP_TIME 0
#define SORTER_MOVE_TRIES 100
#define FREE_PER_ITEM 50
#define NSORTERS 20

typedef enum {A=0, EMPTY} 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;
        item_t item;
};
typedef struct sorter_s sorter_t;

struct sorter_argv_s {
        board_t *board;
        sorter_t *sorter;
};
typedef struct sorter_argv_s sorter_argv_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 *run_sorter (void *);
void setup_board(board_t *);


/******************************************************************************/
/*
 * Output related functions.
 */

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

/* 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);
}

/*
 * Print a graphical representation an item.
 */
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);
}

/*
 * Print a graphical representation of the state of all mutexes.
 */
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");
                        }
                }
        }
}


/******************************************************************************/
/*
 * Sorter related functions.
 */

/*
 * The sorter.
 */
void *run_sorter (void *argv)
{
        int itera;
        sorter_t *sorter;
        board_t *board;

        /*
         * Arguments handling.
         */
        board = ((sorter_argv_t *)argv)->board;
        sorter = ((sorter_argv_t *)argv)->sorter;

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

                        usleep(SLEEP_TIME);
                } while (sorter->item == EMPTY);

                while (sorter->item != EMPTY) {
                        drop_item(sorter->line, sorter->column, board, &(sorter->item));
                        move_sorter(board, sorter);

                        usleep(SLEEP_TIME);
                }

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

        return NULL;
}

/*
 * Move the sorter.
 */
void move_sorter(board_t *board, sorter_t *sorter)
{
        assert(sorter != NULL);
        assert(sorter->column < board->width);
        assert(sorter->line < board->height);

        unsigned int newline, newcolumn;
        int h, hoffset, hrange;
        int v, voffset, vrange;

        /*
         * Set default values to range and offset of random movement.
         */
        hoffset = -1;
        hrange = 3;
        voffset = -1;
        vrange = 3;

        /*
         * Adjust according to sorter position.
         */
        if (sorter->line == 0) {
                voffset = 0;
                vrange--;
        }
        if (sorter->line == (board->height-1)) {
                vrange--;
        }
        if (sorter->column == 0) {      
                hoffset = 0;
                hrange--;
        }
        if (sorter->column == (board->width-1)) {
                hrange--;
        }
        /*
         * Calculate the displacements.
         */
        h = rand()%hrange + hoffset;
        v = rand()%vrange + voffset;

        newline = sorter->line + v;
        newcolumn = sorter->column + h;

        sorter->line = newline;
        sorter->column = newcolumn;

        assert(sorter->line < board->height);
        assert(sorter->column < board->width);
}


/******************************************************************************/
/*
 * Item handling functions.
 */

/*
 * Try to pick an item.
 */
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;
        /*
         * h is for horizontal, v is for vertical.
         */
        int h, hmin, hmax;
        int v, vmin, vmax;

        /*
         * Set default values for parameters
         */
        hmin = -1;
        hmax = 1;
        vmin = -1;
        vmax = 1;

        /*
         * Adjust parameters according to position.
         */
        if (line == 0) vmin = 0;
        if (line == (board->height-1)) vmax = 0;
        if (column == 0) hmin = 0;
        if (column == (board->width-1)) hmax = 0;

        for (h = hmin; (h <= hmax) && (*item == EMPTY); ++h) {
                for (v = vmin; (v <= vmax) && (*item == EMPTY); ++v) {
                        /*
                         * newline and newcolumn need to be allawys positive.
                         */
                        newline = line + v;
                        newcolumn = column + h;

                        pthread_mutex_lock((board->lock)[newline]+newcolumn);
                        peek_item(newline, newcolumn, board, &newitem);
                        if (newitem != EMPTY) {
                                *item = newitem;
                                poke_item(newline, newcolumn, board, EMPTY);
                                /*
                                 * We now 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));
}

/* 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);

        int newline, newcolumn;
        /*
         * h is for horizontal, v is for vertical.
         */
        int h, hmin, hmax;
        int v, vmin, vmax;
        item_t newitem;

        /*
         * Set default values for parameters.
         */
        hmin = -1;
        hmax = 1;
        vmin = -1;
        vmax = 1;

        /*
         * Adjust parameters according to position.
         */
        if (line == 0) vmin = 0;
        if (line == (board->height-1)) vmax = 0;
        if (column == 0) hmin = 0;
        if (column == (board->width-1)) hmax = 0;

        pthread_mutex_lock((board->lock)[line]+column);

        /*
         * Only try to drop if current position is empty.
         */
        peek_item(line, column, board, &newitem);
        if (newitem == EMPTY) {
                for (h = hmin; (h <= hmax) && (*item != EMPTY); ++h) {
                        for (v = vmin; (v <= vmax) && (*item != EMPTY); ++v) {
                                /* newline and newcolumn need to be allawys positive */
                                newline = line + v;
                                newcolumn = column + h;

                                peek_item(newline, newcolumn, board, &newitem);
                                if(newitem == *item) {
                                        poke_item(line, column, board, *item);
                                        *item = EMPTY;
                                        /* and the item is down */
                                }
                        }
                }
        }

        pthread_mutex_unlock((board->lock)[line]+column);
}

/* 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 = rand()%FREE_PER_ITEM;
        switch (number) {
                case 0:
                        *item = A;
                        break;
                default:
                        *item = EMPTY;
                        break;
        }
}

/*
 * Count all items of a specific type.
 */
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;
}


/******************************************************************************/
/* 
 * Board related functions.
 */

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);
}


/******************************************************************************/
int main (int argc, char *argv[])
{
    board_t board;
        unsigned int nitems_begin, nitems_finish;
        pthread_attr_t thread_attributes;
        pthread_t sorter_threads[NSORTERS];
        sorter_t sorters[NSORTERS];
        item_t item;
        unsigned int n;
        unsigned int line, column;
        sorter_argv_t sorters_argv[NSORTERS];

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

        /*
         * Intialize random number generator
         */
        srand((unsigned int)time(NULL));

        setup_board (&board);

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

        /*
         * Launch sorters.
         */
        pthread_attr_init(&thread_attributes);
        for (n = 0; n < NSORTERS; ++n) {
                /*
                 * Initialize sorter parameters.
                 */
                sorters[n].line = rand() % board.height;
                sorters[n].column = rand() % board.width;
                sorters[n].item = EMPTY;

                sorters_argv[n].board = &board;
                sorters_argv[n].sorter = sorters+n;

                pthread_create(sorter_threads+n, &thread_attributes, run_sorter, (void *)(sorters_argv+n));
        }
        
        /*
         * Wait for keypress (return).
         */
        getchar();

        /*
         * 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);
                }
        }

        /*
         * Kill all sorters.
         */
        for (n = 0; n < NSORTERS; ++n) {
                pthread_cancel(sorter_threads[n]);
        }

        //print_mutexes(&board);

        /*
         * Make sure the sorters didn't ate items.
         */
        count_items(&board, &item, &nitems_finish);
        assert(nitems_begin == nitems_finish);

        finish_board (&board);

        printf("All good.\n");

        exit(0);
}