cs350/kern/lib/queue.c

/*
 * Queue of void pointers. See queue.h for details.
 */

#include <types.h>
#include <kern/errno.h>
#include <lib.h>
#include <queue.h>

struct queue {
	int size;
	int nextwrite;	// next element to write to (was head)
	int nextread;	  // next element to read from (was tail)
	void **data;
};

static
int
q_grow(struct queue *q, int targetsize)
{
	void **olddata = q->data;
	int onr = q->nextread;
	int onw = q->nextwrite;
	int osize = q->size;

	int nsize;
	void **ndata;

	int i, result;

	nsize = q->size;
	while (nsize < targetsize) {
		nsize *= 2;
		/* prevent infinite loop */
		KASSERT(nsize > 0);
	}
	ndata = kmalloc(nsize * sizeof(void *));
	if (ndata == NULL) {
		return ENOMEM;
	}
	q->size = nsize;
	q->data = ndata;
	q->nextread = q->nextwrite = 0;
	
	for (i=onr; i!=onw; i = (i+1)%osize) {
		result = q_addtail(q, olddata[i]);
		KASSERT(result==0);
	}
	kfree(olddata);
	return 0;
}

struct queue *
q_create(int size)
{
	struct queue *q = kmalloc(sizeof(struct queue));
	if (q==NULL) {
		return NULL;
	}
	q->size = size;
	q->data = kmalloc(size * sizeof(void *));
	if (q->data==NULL) {
		kfree(q);
		return NULL;
	}
	q->nextread = q->nextwrite = 0;
	return q;
}

int
q_preallocate(struct queue *q, int size)
{
	int result = 0;

	KASSERT(q->size > 0);

	if (size > q->size) {
		result = q_grow(q, size);
	}
	return result;
}

inline
int
q_empty(struct queue *q)
{
	return q->nextwrite == q->nextread;
}

int
q_addtail(struct queue *q, void *ptr)
{
	int nextnext, result;

	KASSERT(q->size > 0);
 
	nextnext = (q->nextwrite+1) % q->size;
	if (nextnext==q->nextread) {
		result = q_grow(q, q->size+1);
		if (result) {
			return result;
		}
		nextnext = (q->nextwrite+1) % q->size;
	}
	q->data[q->nextwrite] = ptr;
	q->nextwrite = nextnext;
	return 0;
}

void *
q_remhead(struct queue *q)
{
	void *ret;

	KASSERT(q->size > 0);

	KASSERT(!q_empty(q));
	ret = q->data[q->nextread];
	q->nextread = (q->nextread+1)%q->size;
	return ret;
}

void
q_destroy(struct queue *q)
{
	KASSERT(q_empty(q));
	kfree(q->data);
	kfree(q);
}

/* These are really intended only for debugging. */
int
q_getstart(struct queue *q)
{
	return q->nextread;
}

int
q_getend(struct queue *q)
{
	return q->nextwrite;
}

int
q_getsize(struct queue *q)
{
	return q->size;
}

void *
q_getguy(struct queue *q, int index)
{
	// note that we don't check to make sure the access isn't in the
	// unused part of the queue space. we probably should.

	KASSERT(index>=0 && index<q->size);
	return q->data[index];
}

void *
q_peek(struct queue *q)
{
	void *ret;

	KASSERT(q);
	KASSERT(q->size > 0);

	if (q_empty(q)) {
    ret = 0;
	} else {
	  ret = q->data[q->nextread];
	}
	return ret;
}

int
q_len(struct queue *theq)
{
	int count = 0;
	int tmp = theq->nextread;
	while (tmp != theq->nextwrite) {
		tmp = (tmp+1) % theq->size;
		count++;
	}
	return count;
}