/* ARISA - data queue, abstraction layer
 * Copyright (C) 2004 Carl Ritson
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
 */

#include "arisa.h"
#include <unistd.h>
#include <errno.h>

#define DQS_INITIAL_SIZE 18

static dq_ops_t dq_invalid_ops = {
	.magic	= ~DQ_MAGIC
};

static inline dq_t *alloc_dq(dq_ops_t *ops, void *data) {
	dq_t *dq = xalloc(sizeof(dq_t));
	dq->ops = ops;
	dq->data = data;
	return dq;
}

/***
 * Simple Data Queue
 ***/

typedef struct dq_simple_t {
	void	**data;
	int	size;
	int	head;
	int	tail;
} dq_simple_t;


static inline int wrap_ptr(dq_simple_t *dqs, int ptr) {
	ptr = ptr % dqs->size;
	if(ptr < 0)
		return dqs->size - ptr;
	else
		return ptr;
}

static void enlarge_dqs(dq_simple_t *dqs) {
	int new_size = dqs->size * 2;
	if(dqs->head < dqs->tail) {
		dqs->data = xreloc(dqs->data,new_size * sizeof(void *));
	} else {
		// note the ** is very important as offsets are pointers
		// not bytes!
		void **new_data = xalloc(new_size * sizeof(void *));
		memcpy(new_data,dqs->data + dqs->head, 
			(dqs->size - dqs->head) * sizeof(void *));
		memcpy(new_data + dqs->size - dqs->head, dqs->data, 
			dqs->tail * sizeof(void *));
		xfree(dqs->data);
		dqs->data = new_data;
		dqs->tail = (dqs->size - dqs->head) + dqs->tail;
		dqs->head = 0;
	}
	dqs->size = new_size;
}

static void shrink_dqs(dq_simple_t *dqs) {
	int new_size = dqs->size / 2;
	
	if(new_size < DQS_INITIAL_SIZE)
		return;

	if(dqs->head <= dqs->tail) {
		if(new_size < (dqs->tail - dqs->head))
			return;
	} else {
		if(new_size < ((dqs->size - dqs->head) + dqs->tail))
			return;
	}

	if(dqs->head <= dqs->tail) {
		if(dqs->head != 0 && dqs->head != dqs->tail) {
			memmove(dqs->data, dqs->data + dqs->head, dqs->tail - dqs->head);
			dqs->tail = dqs->tail - dqs->head;
			dqs->head = 0;
		}
		dqs->data = xreloc(dqs->data,sizeof(void *) * new_size);
		if(dqs->head == dqs->tail) {
			dqs->head = 0;
			dqs->tail = 0;
		}
	} else {
		// note the ** is very important, as the offsets are pointers
		// not bytes!
		void **new_data = xalloc(sizeof(void *) * new_size);
		memcpy(new_data,dqs->data + dqs->head, 
			(dqs->size - dqs->head) * sizeof(void *));
		memcpy(new_data + (dqs->size - dqs->head), dqs->data, 
			dqs->tail * sizeof(void *));
		xfree(dqs->data);
		dqs->data = new_data;
		dqs->tail = (dqs->size - dqs->head) + dqs->tail;
		dqs->head = 0;
	}

	dqs->size = new_size;
}	

static void _dqs_pushf(dq_simple_t *dqs, void *ptr) {
	if((dqs->head - 1) == dqs->tail)
		enlarge_dqs(dqs);
	dqs->head = wrap_ptr(dqs,dqs->head - 1);
	dqs->data[dqs->head] = ptr;
}
static void dqs_pushf(dq_t *dq, void *ptr) {
	_dqs_pushf((dq_simple_t *)dq->data,ptr);
}

static void _dqs_pushb(dq_simple_t *dqs, void *ptr) {
	int new_tail = wrap_ptr(dqs,dqs->tail + 1);
	if(new_tail == dqs->head) {
		enlarge_dqs(dqs);
		new_tail = wrap_ptr(dqs,dqs->tail + 1);
	}
	dqs->data[dqs->tail] = ptr;
	dqs->tail = new_tail;
	//D("head = %d, tail = %d, ptr = %p",dqs->head,dqs->tail,ptr);
}
static void dqs_pushb(dq_t *dq, void *ptr) {
	_dqs_pushb((dq_simple_t *)dq->data,ptr);
}

static void *_dqs_popf(dq_simple_t *dqs) {
	void *ret;
	if(dqs->head == dqs->tail)
		return NULL;
	ret = dqs->data[dqs->head];
	dqs->head = wrap_ptr(dqs,dqs->head + 1);
	//D("head = %d, tail = %d, ret = %p",dqs->head,dqs->tail,ret);
	if(dqs->head == dqs->tail)
		shrink_dqs(dqs);
	return ret;
}
static void *dqs_popf(dq_t *dq) {
	return _dqs_popf((dq_simple_t *)dq->data);
}

static void *_dqs_popb(dq_simple_t *dqs) {
	void *ret;
	if(dqs->head == dqs->tail)
		return NULL;
	dqs->tail = wrap_ptr(dqs,dqs->tail - 1);
	ret = dqs->data[dqs->tail];
	if(dqs->head == dqs->tail)
		shrink_dqs(dqs);
	return ret;
}
static void *dqs_popb(dq_t *dq) {
	return _dqs_popb((dq_simple_t *)dq->data);
}

static int _dqs_length(dq_simple_t *dqs) {
	if(dqs->head <= dqs->tail)
		return dqs->tail - dqs->head;
	else
		return (dqs->size - dqs->head) + dqs->tail;
}
static int dqs_length(dq_t *dq) {
	return _dqs_length((dq_simple_t *)dq->data);
}

static void _dqs_clear(dq_simple_t *dqs, void (*ffunc)(void*)) {
	if(dqs->head == dqs->tail)
		return;
	
	if(ffunc != NULL) {
		int i;
		
		if(dqs->tail > dqs->head) {
			for(i = dqs->head; i < dqs->tail; ++i)
				ffunc(dqs->data[i]);
		} else {
			for(i = dqs->head; i < dqs->size; ++i)
				ffunc(dqs->data[i]);
			for(i = 0; i < dqs->tail; ++i)
				ffunc(dqs->data[i]);
		}
	}

	if(dqs->size > DQS_INITIAL_SIZE) {
		dqs->size = DQS_INITIAL_SIZE;
		dqs->data = xreloc(dqs->data,sizeof(void *) * dqs->size);
	}
	dqs->head = 0;
	dqs->tail = 0;
}
static void dqs_clear(dq_t *dq, void (*ffunc)(void*)) {
	_dqs_clear((dq_simple_t *)dq->data,ffunc);
}

static void _dqs_free(dq_simple_t *dqs, void (*ffunc)(void*)) {
	_dqs_clear(dqs,ffunc);
	xfree(dqs->data);
	xfree(dqs);
}
static void dqs_free(dq_t *dq, void (*ffunc)(void*)) {
	_dqs_free((dq_simple_t *)dq->data,ffunc);
	dq->ops = &dq_invalid_ops;
	xfree(dq);
}

static dq_ops_t dq_simple_ops = {
	.magic		= DQ_MAGIC,
	.pushf		= dqs_pushf,
	.pushb		= dqs_pushb,
	.popf		= dqs_popf,
	.popb		= dqs_popb,
	.length		= dqs_length,
	.clear		= dqs_clear,
	.free		= dqs_free
};

static dq_simple_t *alloc_dq_simple(void) {
	dq_simple_t *dqs = xalloc(sizeof(dq_simple_t));
	dqs->size = DQS_INITIAL_SIZE;
	dqs->data = xalloc(sizeof(void *) * dqs->size);
	dqs->head = 0;
	dqs->tail = 0;
	return dqs;
}

dq_t *dq_alloc_simple(void) {
	dq_simple_t *dqs = alloc_dq_simple();
	return alloc_dq(&dq_simple_ops,dqs);
}

/***
 * Advanced Simple Data Queue
 ***/

typedef struct dq_advanced_t {
	lock_t		lock;
	int		notify_fd;
	dq_simple_t	*dq_simple;
} dq_advanced_t;

static void dqa_notify(dq_advanced_t *dqa) {
	if(dqa->notify_fd != -1) {
		ssize_t ret = write(dqa->notify_fd,"\0",1);
		if(ret == -1 && !(errno == EAGAIN)) {
			if(errno == EINTR) {
				/* try again and don't care 
				   about the return value */
				write(dqa->notify_fd,"\0",1);
			} else {
				/* we don't want further errors */
				// FIXME: is this really the right behavior?
				D("close: %d",dqa->notify_fd);
				close(dqa->notify_fd);
				dqa->notify_fd = -1;
			}
		}
	}
}

#define dqa_push(op) 				\
static void dqa_##op(dq_t *dq, void *ptr) {	\
	dq_advanced_t *dqa = dq->data;		\
						\
	LOCK(dqa);				\
	_dqs_##op(dqa->dq_simple,ptr);		\
	dqa_notify(dqa);			\
	UNLOCK(dqa);				\
}

#define dqa_pop(op)				\
static void *dqa_##op(dq_t *dq) {		\
	dq_advanced_t *dqa = dq->data;		\
	void *ret;				\
						\
	LOCK(dqa);				\
	ret = _dqs_##op(dqa->dq_simple);	\
	UNLOCK(dqa);				\
						\
	return ret;				\
}

dqa_push(pushb)
dqa_push(pushf)
dqa_pop(popb)
dqa_pop(popf)

#undef dqa_push
#undef dqa_pop

static int dqa_length(dq_t *dq) {
	dq_advanced_t *dqa = dq->data;
	int ret;
	
	LOCK(dqa);
	ret =_dqs_length(dqa->dq_simple);
	UNLOCK(dqa);

	return ret;
}

static void dqa_clear(dq_t *dq, void (*ffunc)(void*)) {
	dq_advanced_t *dqa = dq->data;

	LOCK(dqa);
	_dqs_clear(dqa->dq_simple,ffunc);
	UNLOCK(dqa);
}

static void dqa_free(dq_t *dq, void (*ffunc)(void*)) {
	dq_advanced_t *dqa = dq->data;

	LOCK_FREE(&(dqa->lock));
	if(dqa->notify_fd != -1) {
		D("close: %d",dqa->notify_fd);
		close(dqa->notify_fd);
	}
	_dqs_free(dqa->dq_simple,ffunc);
	xfree(dqa);

	dq->ops = &dq_invalid_ops;
	xfree(dq);
}

static dq_ops_t dq_advanced_ops = {
	.magic		= DQ_MAGIC,
	.pushf		= dqa_pushf,
	.pushb		= dqa_pushb,
	.popf		= dqa_popf,
	.popb		= dqa_popb,
	.length		= dqa_length,
	.clear		= dqa_clear,
	.free		= dqa_free
};

dq_t *dq_alloc_advanced(int notify_fd) {
	dq_advanced_t *dqa = xalloc(sizeof(dq_advanced_t));
	LOCK_INIT(&(dqa->lock));
	dqa->notify_fd = notify_fd;
	dqa->dq_simple = alloc_dq_simple();
	return alloc_dq(&dq_advanced_ops,dqa);
}