/*
 * elevator noop
 */
#include <linux/blkdev.h>
#include <linux/elevator.h>
#include <linux/bio.h>
#include <linux/module.h>
#include <linux/init.h>


struct noop_data{
    struct list_head queue;
    unsigned long last_request; //last request dispatched
};

//elevator_merge_req_fn
static void noop_merged_requests(struct request_queue *q, struct request *rq,
                 struct request *next)
{
    list_del_init(&next->queuelist);
}

/*
//elevator_dispatch_fn
static int noop_dispatch(struct request_queue *q, int force)
{
        printk("*** Begining dispatch_fn ***\n");
        printk("jiffies: %lu\n", jiffies);

        return noop_dispatch2(q, force);

    struct noop_data *nd = q->elevator->elevator_data;

    if (!list_empty(&nd->queue)) {
        struct request *rq;
        rq = list_entry(nd->queue.next, struct request, queuelist);

        printk("Request at sector %lu dispatched.\n", rq->sector);
        list_del_init(&rq->queuelist);
        elv_dispatch_sort(q, rq);

        printk("*** Ending dispatch_fn ***\n\n");
        return 1;
    }

    printk("Request queue empty\n");
    printk("*** Ending dispatch_fn ***\n\n");
    return 0;
}
*/

/*
//elevator_add_req_fn
static void noop_add_request(struct request_queue *q, struct request *rq)
{
    printk("Add. . .\n-\n-\n-\n-\n-\n-\n-\n-\n-\n");
    struct noop_data *nd = q->elevator->elevator_data;

    list_add_tail(&rq->queuelist, &nd->queue);
}*/


//elevator_queue_empty_fn
static int noop_queue_empty(struct request_queue *q)
{
    struct noop_data *nd = q->elevator->elevator_data;

    return list_empty(&nd->queue);
}

//elevator_former_req_fn
static struct request *
noop_former_request(struct request_queue *q, struct request *rq)
{
    struct noop_data *nd = q->elevator->elevator_data;

    if (rq->queuelist.prev == &nd->queue)
        return NULL;
    return list_entry(rq->queuelist.prev, struct request, queuelist);
}

//elevator_latter_req_fn
static struct request *
noop_latter_request(struct request_queue *q, struct request *rq)
{
    struct noop_data *nd = q->elevator->elevator_data;

    if (rq->queuelist.next == &nd->queue)
        return NULL;
    return list_entry(rq->queuelist.next, struct request, queuelist);
}

static void *noop_init_queue(struct request_queue *q)
{
    printk("Initializing. . .\n-\n-\n-\n-\n-\n-\n-\n-\n-\n");
    struct noop_data *nd;

    nd = kmalloc_node(sizeof(*nd), GFP_KERNEL, q->node);
    if (!nd)
        return NULL;
    INIT_LIST_HEAD(&nd->queue);
    nd->last_request = 0;
    return nd;
}

static void noop_exit_queue(struct elevator_queue *e)
{
    struct noop_data *nd = e->elevator_data;

    BUG_ON(!list_empty(&nd->queue));
    kfree(nd);
}

//===================================================================
//===================================================================
//Note: request queue is to be sorted by location of request

static int greater2(struct request *x, unsigned long y){
    //unsigned long s1 = (unsigned long) blk_rq_pos(x);
    //unsigned long s2 = (unsigned long) blk_rq_pos(y);

    unsigned long s1 = (unsigned long)(x->sector);
    unsigned long s2 = y;

    if (s1 > s2)
        return 1;

    return 0;
}


static int greater(struct request *x, struct request *y){
    //unsigned long s1 = (unsigned long) blk_rq_pos(x);
    //unsigned long s2 = (unsigned long) blk_rq_pos(y);

    unsigned long s1 = (unsigned long)(x->sector);
    unsigned long s2 = (unsigned long)(y->sector);

    if (s1 > s2)
        return 1;

    return 0;
}

static unsigned long seek_dist(unsigned long x, struct request *y){
    //unsigned long s1 = (unsigned long) blk_rq_pos(x);
    //unsigned long s2 = (unsigned long) blk_rq_pos(y);

    if(y == NULL)
        return ULONG_MAX;

    unsigned long s1 = x;
    unsigned long s2 = (unsigned long)(y->sector);

    if (s1 > s2)
        return s1-s2;

    else
        return s2-s1;
}


//selects request closes to the last dispatched request
static int noop_dispatch(struct request_queue *q, int force){
    printk("*** Begining dispatch_fn *** \n");
    printk("jiffies: %lu\n", jiffies);

    struct noop_data *nd = q->elevator->elevator_data;
   unsigned long last_rq = nd->last_request;

    if (list_empty(&nd->queue)) {
        printk("Request queue empty.\n");
        printk("*** Ending dispatch_fn *** \n\n");
        return 0;
    }

    struct list_head *pos;
    struct request *curr;
    struct request *prev = NULL;

    //iterate through request queue
    list_for_each(pos, nd->queue.next) {
        curr = list_entry(pos, struct request, queuelist);

        //This if statement comes into effect at the spot in the queue
        //that the most recently dispatched request would be. The closest
        //element is either the current one or the one before it.

        //Note: the greater function is a comparison of request locations
        //I'm not sure how to implement this.
        if (greater2(curr, last_rq)) {
            //seek_dist would be a numerical approximation of the
            //distance between two requests.  I still need to implement this.
            unsigned long dist1 = seek_dist(last_rq, curr);
            unsigned long dist2 = seek_dist(last_rq, prev);

            if (dist1 < dist2) {
                printk("Request at sector: %lu dispatched.\n",
                 (unsigned long)(curr->sector));

                nd->last_request = curr->sector;
                list_del_init(&curr->queuelist);
                elv_dispatch_sort(q, curr);
            }
            else {
                printk("Request at sector: %lu dispatched.\n",
                 (unsigned long)(prev->sector));

                nd->last_request = prev->sector;
                list_del_init(&prev->queuelist);
                elv_dispatch_sort(q, prev);
            }
            printk("*** Ending dispatch_fn *** \n\n");
            return 1;
        }
        prev = curr;
    }
    printk("Request at sector: %lu dispatched.\n",
        (unsigned long)(prev->sector));

    nd->last_request = prev->sector;
    list_del_init(&prev->queuelist);
    elv_dispatch_sort(q, prev);

    return 1;
}


//add the request to the queue in the correct sorted location
static void noop_add_request(struct request_queue *q, struct request *rq) {
    struct noop_data *nd = q->elevator->elevator_data;
    printk("*** Beginning request_add_fn ***\n");
    printk("Request at sector %lu added.\n",
        (unsigned long)(rq->sector));

    printk("\tjiffies: %lu\n", jiffies);

    if (list_empty(&nd->queue)) {
        list_add_tail(&rq->queuelist, &nd->queue);
        printk("At spot 0\n");
        printk("*** Ending request_add_fn ***\n\n");
        return;
    }

    struct list_head *pos;
    struct request *curr;

    //same general principle as the list_for_each call in dispatch
    int i = 0;
    list_for_each(pos, nd->queue.next) {
        curr = list_entry(pos, struct request, queuelist);
        if (greater(curr, rq)){
            list_add_tail(&rq->queuelist, &curr->queuelist);
            printk("At spot %d\n", i);
            printk("*** Ending request_add_fn ***\n\n");
            return;
        }
        i++;
    }
}


//==========================================================================

static struct elevator_type elevator_noop = {
    .ops = {
        .elevator_merge_req_fn      = noop_merged_requests,
        .elevator_dispatch_fn       = noop_dispatch,
        .elevator_add_req_fn        = noop_add_request,
        .elevator_queue_empty_fn    = noop_queue_empty,
        .elevator_former_req_fn     = noop_former_request,
        .elevator_latter_req_fn     = noop_latter_request,
        .elevator_init_fn       = noop_init_queue,
        .elevator_exit_fn       = noop_exit_queue,
        //elevator_merge_fn
        //elevator_remove_req_fn
        //elevator_set_req_fn
        //elevator_put_req_fn
    },
    .elevator_name = "anticipatory",
    .elevator_owner = THIS_MODULE,
};

static int __init noop_init(void)
{
    elv_register(&elevator_noop);

    return 0;
}

static void __exit noop_exit(void)
{
    elv_unregister(&elevator_noop);
}

module_init(noop_init);
module_exit(noop_exit);


MODULE_AUTHOR("Jens Axboe");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("No-op IO scheduler");