/*
 * zen_check_fifo returns 0 if there are no expired requests on the fifo,
 * otherwise it returns the next expired request
 */
static struct request *
zen_check_fifo(struct zen_data *zdata)
{
        struct request *rq_sync = zen_expired_request(zdata, SYNC);
        struct request *rq_async = zen_expired_request(zdata, ASYNC);

        if (rq_async && rq_sync) {
        	if (time_after(rq_fifo_time(rq_async), rq_fifo_time(rq_sync)))
                	return rq_sync;
        } else if (rq_sync) {
                return rq_sync;
	} else if (rq_async) {
		return rq_async;
	}

        return 0;
}

static void
zen_merged_requests(struct request_queue *q, struct request *req,
                    struct request *next)
{
	/*
	 * if next expires before rq, assign its expire time to arq
	 * and move into next position (next will be deleted) in fifo
	 */
	if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
		if (time_before(rq_fifo_time(next), rq_fifo_time(req))) {
			list_move(&req->queuelist, &next->queuelist);
			rq_set_fifo_time(req, rq_fifo_time(next));
		}
	}

	/* next request is gone */
	rq_fifo_clear(next);
}

int ElvDeadline::deadline_check_fifo(int rw)
{
	request *rq = (request *) fifo_list[rw].suc;

	if (Event::Clock() >= rq_fifo_time(rq))
		return 1;

	return 0;
}

/*
 * get the first expired request in direction ddir
 */
static struct request *
zen_expired_request(struct zen_data *zdata, int ddir)
{
        struct request *rq;

        if (list_empty(&zdata->fifo_list[ddir]))
                return NULL;

        rq = rq_entry_fifo(zdata->fifo_list[ddir].next);
        if (time_after_eq(jiffies, rq_fifo_time(rq)))
                return rq;

        return NULL;
}

static struct request *
sio_expired_request(struct sio_data *sd, int sync, int data_dir)
{
struct list_head *list = &sd->fifo_list[sync][data_dir];
struct request *rq;
if (list_empty(list))
return NULL;
/* Retrieve request */
rq = rq_entry_fifo(list->next);
/* Request has expired */
if (time_after_eq(jiffies, rq_fifo_time(rq)))
return rq;
return NULL;
}

/* 
   This function does 3 tasks:
   1 check if next expires before req, is so set expire time of req to be the expire time of next
   2 delete next from async fifo queue
   3 check if merged req size >= bundle_size; if so, delete req from async fifo queue, reinit and insert it to bundle queue
 */
static void
flash_merged_requests(struct request_queue *q, struct request *req,
			 struct request *next)
{
	struct flash_data *fd = q->elevator->elevator_data;
	// const int data_type = !rq_is_sync(req);
	// FIXME:
	const int data_type = rq_data_dir(req);

	/*
	 * if next expires before rq, assign its expire time to rq
	 * and move into next position (next will be deleted) in fifo
	 */
	// TODO: why need to check if async queue is empty here?
	if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
		if (time_before(rq_fifo_time(next), rq_fifo_time(req))) {
			list_move(&req->queuelist, &next->queuelist);
			rq_set_fifo_time(req, rq_fifo_time(next));
		}
	}

	/* delete next */
	rq_fifo_clear(next);
	
	/* task 3 only kick into bundle queue if req is async */
	if(req->__data_len >= fd->bundle_size && data_type == 1)
	{
		/* did both delete and init */
		rq_fifo_clear(req); 
		list_add_tail(&req->queuelist, &fd->bundle_list);
		
		#ifdef DEBUG_FLASH
		printk("req of type %d of size %d is inserted to bundle queue\n", data_type, req->__data_len);
		#endif
	}

}

static struct request *tripndroid_expired_request(struct tripndroid_data *td, int sync, int data_dir)
{
	struct list_head *list = &td->fifo_list[sync][data_dir];
	struct request *rq;

	if (list_empty(list))
		return NULL;

	rq = rq_entry_fifo(list->next);

	if (time_after_eq(jiffies, rq_fifo_time(rq)))
		return rq;

	return NULL;
}

static struct request *
sio_expired_request(struct sio_data *sd, int sync)
{
struct request *rq;

if (list_empty(&sd->fifo_list[sync]))
return NULL;

/* Retrieve request */
rq = rq_entry_fifo(sd->fifo_list[sync].next);

/* Request has expired */
if (time_after(jiffies, rq_fifo_time(rq)))
return rq;

return NULL;
}

/*
 * deadline_check_fifo returns 0 if there are no expired requests on the fifo,
 * 1 otherwise. Requires !list_empty(&fd->fifo_list[data_type])
 */
static inline int deadline_check_fifo(struct flash_data *fd, int ddir)
{
	struct request *rq;
	
	// if no req on given list, return 0: not expire;
	if(list_empty(&fd->fifo_list[ddir]))
		return 0;

	rq = rq_entry_fifo(fd->fifo_list[ddir].next);

	/*
	 * rq is expired!
	 */
	if (time_after(jiffies, rq_fifo_time(rq)))
		return 1;

	return 0;
}