jump/monotonic_queue.c

#include "monotonic_queue.h"

void monotonic_queue_init(struct monotonic_queue *mq,
			  monotonic_queue_cmp cmp)
{
	mq->h = mq->h_min = mq->t = mq->len = 0;
	mq->cmp = cmp;
}

int monotonic_queue_push(struct monotonic_queue *mq, float value)
{
	int t1;

	while (mq->h_min != mq->t && mq->cmp(value, mq->buf[mq->h_min]))
		mq->h_min = (mq->h_min + 1) % MONOTONIC_QUEUE_CAP;

	t1 = (mq->t + 1) % MONOTONIC_QUEUE_CAP;
	if (t1 == mq->h)
		/* over flow */
		return -1;

	mq->len++;
	mq->buf[mq->t] = value;
	mq->t = t1;
	return 0;
}

int monotonic_queue_pop(struct monotonic_queue *mq)
{
	if (mq->h == mq->t)
		/* empty */
		return -1;

	mq->len--;
	if (mq->h == mq->h_min)
		mq->h_min = (mq->h_min + 1) % MONOTONIC_QUEUE_CAP;
	mq->h = (mq->h + 1) % MONOTONIC_QUEUE_CAP;

	return 0;
}

int monotonic_queue_get_min(struct monotonic_queue *mq, float *dest)
{
	if (mq->h == mq->t)
		/* empty */
		return -1;

	*dest = mq->buf[mq->h_min];
	return 0;
}

int monotonic_queue_get_len(struct monotonic_queue *mq)
{
	return mq->len;
}

/* vim: set ts=8 sw=8 sts=8 noet: */