/*
 * remove rq from rbtree and fifo.
 */
static void deadline_remove_request(struct request_queue *q, struct request *rq)
{
	struct deadline_data *dd = q->elevator->elevator_data;

	rq_fifo_clear(rq);
	deadline_del_rq_rb(dd, rq);
}

static void
vr_add_request(struct request_queue *q, struct request *rq)
{
struct sio_data *sd = q->elevator->elevator_data;
const int sync = rq_is_sync(rq);
const int data_dir = rq_data_dir(rq);
/*
* We might be deleting our cached next request.
* If so, find its sucessor.
*/

/*
* add rq to rbtree and fifo
*/
static void
vr_add_request(struct request_queue *q, struct request *rq)
struct request *next)
{
struct vr_data *vd = vr_get_data(q);
const int dir = rq_is_sync(rq);
}
/*
* If next expires before rq, assign its expire time to rq
* and move into next position (next will be deleted) in fifo.
*/
if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist)) {
if (time_before(rq_fifo_time(next), rq_fifo_time(rq))) {
list_move(&rq->queuelist, &next->queuelist);
rq_set_fifo_time(rq, rq_fifo_time(next));
}
}

/* Delete next request */
rq_fifo_clear(next);
}

/*  Implement elevator_merge_fn: do nothing for now
    Implement elevator_merged_fn: If larger than predefined bundle size, remove from async queue and add to tail of bundle queue; 
*/
static void flash_merged_request(struct request_queue *q,
				    struct request *req, int type)
{
	struct flash_data *fd = q->elevator->elevator_data;
	// FIXME:
	// const int data_type = !rq_is_sync(req);
	const int data_type = rq_data_dir(req);

	// BUG if req already in bundle queue
	/* FIXME: how to check if a req belong to certain queue? */

	// if req >= bundle_size, delete from async_fifo queue, add tail to bundle queue
	#ifdef DEBUG_FLASH
	printk("req is of size %d after merging\n", req->__data_len);
	#endif

	// only kick req 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 void zen_dispatch(struct zen_data *zdata, struct request *rq)
{
	/* Remove request from list and dispatch it */
	rq_fifo_clear(rq);
	elv_dispatch_add_tail(rq->q, rq);

	/* Increment # of sequential requests */
	zdata->batching++;
}

static inline void
sio_dispatch_request(struct sio_data *sd, struct request *rq)
{
/*
* Remove the request from the fifo list
* and dispatch it.
*/
rq_fifo_clear(rq);
elv_dispatch_add_tail(rq->q, rq);

sd->batched++;
}

/*
 * move request from additional fifo list to dispatch queue.
 */
static inline void
flash_move_to_dispatch(struct flash_data *dd, struct request *rq)
{
	struct request_queue *q = rq->q;

	/* remove rq from its associated fifo queue and reinit */
	rq_fifo_clear(rq);
	elv_dispatch_add_tail(q, rq);
	#ifdef DEBUG_FLASH
	printk("req of size %d is moved to dispatch queue\n", rq->__data_len);
	#endif
}

static inline void tripndroid_dispatch_request(struct tripndroid_data *td, struct request *rq)
{
	/* Dispatch the request */
	rq_fifo_clear(rq);
	elv_dispatch_add_tail(rq->q, rq);

	td->batched++;

	if (rq_data_dir(rq))
		td->starved = 0;
	else
		td->starved++;
}

static void
sio_merged_requests(struct request_queue *q, struct request *rq,
		    struct request *next)
{
	if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist)) {
		if (time_before(rq_fifo_time(next), rq_fifo_time(rq))) {
			list_move(&rq->queuelist, &next->queuelist);
			rq_set_fifo_time(rq, rq_fifo_time(next));
		}
	}

	rq_fifo_clear(next);
}

static inline void
sio_dispatch_request(struct sio_data *sd, struct request *rq)
{
	rq_fifo_clear(rq);
	elv_dispatch_add_tail(rq->q, rq);

	if (rq_data_dir(rq)) {
		sd->starved = 0;
	} else {
		if (!list_empty(&sd->fifo_list[SYNC][WRITE]) || 
				!list_empty(&sd->fifo_list[ASYNC][WRITE]))
			sd->starved++;
	}
}

/* 
   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 void tripndroid_merged_requests(struct request_queue *q, struct request *rq,
		    struct request *next)
{
	/*
	 * If next expires before rq, assign its expire time to rq
	 * and move into next position (next will be deleted) in fifo.
	 */
	if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist)) {
		time_before(next->fifo_time, rq->fifo_time); {
			list_move(&rq->queuelist, &next->queuelist);
			rq->fifo_time = next->fifo_time;
		}
	}

	rq_fifo_clear(next);
}

static inline void
sio_dispatch_request(struct sio_data *sd, struct request *rq)
{
	/* Remove the request from the fifo list and dispatch it. */
	rq_fifo_clear(rq);
	elv_dispatch_add_tail(rq->q, rq);

	sd->batched++;

	if (rq_data_dir(rq)) {
		sd->starved = 0;
	} else {
		if (!list_empty(&sd->fifo_list[SYNC][WRITE]) ||
				!list_empty(&sd->fifo_list[ASYNC][WRITE]))
			sd->starved++;
	}
}

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

void ElvDeadline::deadline_remove_request(request *rq)
{
	rq_fifo_clear(rq);
	deadline_del_rq_rb(rq);
}