#ifdef __CSCAN_TEST__
#include <tools.h>

struct buf {
	int id;
	int b_pblkno;
	int b_flags;
	TAILQ_ENTRY(buf) b_act;
};
#endif

struct cscan_queue {
	TAILQ_HEAD(cscanq, buf) queue;
	daddr_t	lastpos;
	struct	buf *select; /* I'm where the head is */
	struct	buf *insert; /* sequential inserts go _after_ me */
};

static __inline void
cscan_init(struct cscan_queue *head)
{
	TAILQ_INIT(&head->queue);
	head->lastpos = 0;
	head->select = NULL;
	head->insert = NULL;
}

static __inline struct buf *
cscan_next(struct cscan_queue *head, struct buf *bp)
{
	struct buf *b = TAILQ_NEXT(bp, b_act);
	if (!b) b = TAILQ_FIRST(&head->queue);
	return b;
}

static __inline struct buf *
cscan_prev(struct cscan_queue *head, struct buf *bp)
{
	struct buf *b = TAILQ_PREV(bp, cscanq, b_act);
	if (!b) b = TAILQ_LAST(&head->queue, cscanq);
	return b;
}

/* not required to remove the cscan_select()ed buffer */
static __inline void
cscan_dequeue(struct cscan_queue *head, struct buf *bp)
{
	if (bp == NULL) return;
	TAILQ_REMOVE(&head->queue, bp, b_act);
	head->lastpos = bp->b_pblkno;
	head->select = cscan_prev(head, bp);
	if (head->insert == bp) head->insert = NULL;
}

static __inline struct buf *
cscan_select(struct cscan_queue *head)
{
	struct buf *bp, *bp0;

	bp = head->select ? cscan_next(head, head->select) /* subtle */
		: TAILQ_FIRST(&head->queue);
	if (!bp) return NULL;

	bp0 = bp;
	do {
		if (bp->b_pblkno > head->lastpos)
			break;
		bp = cscan_next(head, bp);
	} while (bp != bp0);

	head->select = cscan_prev(head, bp);
	return bp;
}

static __inline void
cscan_enqueue(head, bp)
	struct cscan_queue *head;
	struct buf *bp;
{
	struct buf *bq, *bn;

#if 0
	struct buf *bb = 0;
	if (head->insert) { /* optimization */
		if (head->insert->b_pblkno < bp->b_pblkno &&
		    ((bn = cscan_next(head, head->insert)) == NULL ||
		     bn->b_pblkno > bp->b_pblkno))
			bb = head->insert;
	}
#endif

	if (TAILQ_FIRST(&head->queue) == NULL)
		TAILQ_INSERT_TAIL(&head->queue, bp, b_act);
	else if ((bq = TAILQ_FIRST(&head->queue))->b_pblkno > bp->b_pblkno)
		TAILQ_INSERT_BEFORE(bq, bp, b_act);
	else if ((bq = TAILQ_LAST(&head->queue, cscanq))->b_pblkno < bp->b_pblkno)
		TAILQ_INSERT_AFTER(&head->queue, bq, bp, b_act);
	else {
		/* Otherwise, insertion sort */
		for (bq = TAILQ_FIRST(&head->queue), bn = TAILQ_NEXT(bq, b_act);
		     bq && bn;
		     bq = bn, bn = TAILQ_NEXT(bq, b_act)) {
			if (bn->b_pblkno >= bp->b_pblkno)
				break;
		}
		if (bq) TAILQ_INSERT_AFTER(&head->queue, bq, bp, b_act);
		else printf("bug\n");
	}
	head->insert = bp;
}

#ifdef __CSCAN_TEST__
int main(int argc, char *argv[])
{
#define N 10
	struct buf buf[N], *b;
	int i;
	struct cscan_queue q; cscan_init(&q);
	for (i = 0; i < N; i++) {
		bzero(&buf[i], sizeof(struct buf));
		buf[i].b_pblkno = i;
		buf[i].id = i;
	}

	for (i = N-1; i >= 1; i--)
		cscan_enqueue(&q, &buf[i]);

#define P b = cscan_select(&q); printf("xx %d\n", b ? b->id : -1);

	P
	/* cscan_dequeue(&q, &buf[0]); */
	cscan_dequeue(&q, &buf[1]);
	cscan_dequeue(&q, &buf[2]);
	cscan_dequeue(&q, &buf[4]);
	/* cscan_enqueue(&q, &buf[2]); */
	/* cscan_enqueue(&q, &buf[0]); */
	cscan_enqueue(&q, &buf[1]);
	P
	cscan_dequeue(&q, &buf[1]);
	P

	for (i = 0; i < N; i++) {
		b = cscan_select(&q);
		printf("%d\n", b ? b->id : -1);
		if (b) cscan_dequeue(&q, b);
	}
	return 0;
}
#endif

void cscan_fillpos(struct cscan_queue *head, char *s, int sizeperdash)
{
	struct buf *bp;
	TAILQ_FOREACH(bp, &head->queue, b_act) {
		int n = pos(bp)/sizeperdash;
		if (s[n] == '-') s[n] = _id(bproc(bp)->p_pid);
		else s[n] = '+';
	}
}