/* linkedlist - a singularly linked list
 * Copyright (c) 2002 Michael B. Allen <mba2000 ioplex.com>
 *
 * The MIT License
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 */

#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <errno.h>
#include <stdio.h>

#include "mba/msgno.h"
#include "mba/iterator.h"
#include "mba/allocator.h"
#include "mba/linkedlist.h"

void
linkedlist_print(struct linkedlist *l)
{
	struct node *n = l->first;
	int idx = 0;
	while (n) {
		fprintf(stderr, "list node %d n=%p,data=%p\n", idx, n, n->data);
		n = n->ptr;
		idx++;
	}
}

static void
_cache_remove_by_node(struct linkedlist *l, struct node *n)
{
	struct cache_entry *ce;
	int i;

	for (i = 0; i < CACHE_SIZE; i++) {
		ce = l->cache + i;
		if (ce->ent == n) {
			ce->ent = NULL;
		}
	}
}
static void
_cache_update_by_index(struct linkedlist *l, unsigned int idx, int insert)
{
	struct cache_entry *ce;
	int i;

	for (i = 0; i < CACHE_SIZE; i++) {
		ce = l->cache + i;
		if (ce->ent && ce->idx >= idx) {
			ce->idx += insert ? 1 : -1;
		}
	}
}

int
linkedlist_init(struct linkedlist *l, unsigned int max_size, struct allocator *al)
{
	if (l == NULL) {
		errno = EINVAL;
		PMNO(errno);
		return -1;
	}
	memset(l, 0, sizeof *l);
	l->max_size = max_size == 0 ? INT_MAX : max_size;
	l->al = al;

	return 0;
}
int
linkedlist_deinit(struct linkedlist *l, del_fn data_del, void *context)
{
	int ret = 0;

	if (l) {
		struct node *next = l->first;

		while (next != NULL) {
			struct node *tmp;

			if (data_del) {
				ret += data_del(context, next->data);
			}
			tmp = next;
			next = next->ptr;
			ret += allocator_free(l->al, tmp);
		}
	}

	return ret ? -1 : 0;
}
struct linkedlist *
linkedlist_new(unsigned int max_size, struct allocator *al)
{
	struct linkedlist *l;

	if ((l = allocator_alloc(al, sizeof *l, 0)) == NULL) {
		PMNO(errno);
		return NULL;
	}
	linkedlist_init(l, max_size, al);

	return l;
}
int
linkedlist_del(struct linkedlist *l, del_fn data_del, void *context)
{
	int ret = 0;

	if (l) {
		ret = linkedlist_deinit(l, data_del, context) + allocator_free(l->al, l);
	}

	return ret ? -1 : 0;
}

int
linkedlist_clear(struct linkedlist *l, del_fn data_del, void *context)
{
	if (l) {
		int max_size = l->max_size;
		struct allocator *al = l->al;

		if (linkedlist_deinit(l, data_del, context) == -1) {
			AMSG("");
			return -1;
		}

		linkedlist_init(l, max_size, al);
	}

	return 0;
}
int
linkedlist_add(struct linkedlist *l, const void *data)
{
	struct node *n;

	if (l == NULL) {
		PMNF(errno = EINVAL, ": l=NULL");
		return -1;
	}
	if (l->size == l->max_size) {
		PMNF(errno = ERANGE, ": size=%u,max_size=%u", l->size, l->max_size);
		return -1;
	}
	if ((n = allocator_alloc(l->al, sizeof *n, 0)) == NULL) {
		PMNO(errno);
		return -1;
	}

	n->data = (void *)data;
	n->ptr = NULL;
	if (l->size == 0) {
		l->first = l->last = n;
	} else {
		l->last->ptr = n;
		l->last = n;
	}
	l->size++;

	return 0;
}
int
linkedlist_insert(struct linkedlist *l, unsigned int idx, const void *data)
{
	struct node *n;

	if (l == NULL || data == NULL) {
		PMNF(errno = ERANGE, ": l=%p,data=%p", l, data);
		return -1;
	}
	if (idx > l->size || l->size == l->max_size) {
		PMNF(errno = ERANGE, ": idx=%u,size=%u,max_size=%u", idx, l->size, l->max_size);
		return -1;
	}
	if ((n = allocator_alloc(l->al, sizeof *n, 0)) == NULL) {
		PMNO(errno);
		return -1;
	}
	n->data = (void *)data;
	n->ptr = NULL;
	if (l->size == 0) {
		l->first = l->last = n;
	} else {
		if (idx == 0) {
			n->ptr = l->first;
			l->first = n;
		} else if (idx == l->size) {
			l->last->ptr = n;
			l->last = n;
		} else {
			struct node *tmp;
			unsigned int i;

			tmp = l->first;
			n->ptr = tmp->ptr;
			for (i = 1; i < idx; i++) {
				tmp = tmp->ptr;
				n->ptr = tmp->ptr;
			}
			tmp->ptr = n;
		}
	}
	l->size++;

	_cache_update_by_index(l, idx, 1); /* increment cache entries with larger idx */

	return 0;
}
int
linkedlist_insert_sorted(struct linkedlist *l,
    cmp_fn cmp,
	void *context,
	void **replaced,
	const void *data)
{
	struct node *n, *p;
	int c;
	unsigned int idx;
	int ins = 1;

	if (l == NULL || cmp == NULL || data == NULL) {
		PMNF(errno = EINVAL, ": l=%p,cmp=%p,data=%p", l, cmp, data);
		return -1;
	}
	if (l->size == l->max_size) {
		PMNF(errno = ERANGE, ": size=%u,max_size=%u", l->size, l->max_size);
		return -1;
	}
	if ((n = allocator_alloc(l->al, sizeof *n, 0)) == NULL) {
		PMNO(errno);
		return -1;
	}
	n->data = (void *)data;

	idx = 0;
	p = NULL;
	n->ptr = l->first;
	while (n->ptr) {
		c = cmp(data, n->ptr->data, context);
		if (c < 0 || (replaced && c == 0)) {
			if (c == 0) {                             /* replace */
				struct node *rm = n->ptr;
				*replaced = rm->data;
				n->ptr = rm->ptr;
				_cache_remove_by_node(l, rm);
				allocator_free(l->al, rm);
				l->size--;
				ins = 0;
			}
			break;
		}
		p = n->ptr;
		n->ptr = n->ptr->ptr;
		idx++;
	}
	if (p) {
		p->ptr = n;
	} else {
		l->first = n;
	}
	if (n->ptr == NULL) {
		l->last = n;
	}
	l->size++;

	if (ins) {
		_cache_update_by_index(l, idx, 1); /* increment cache entries with larger idx */
	}

	return idx;
}
int
linkedlist_is_empty(const struct linkedlist *l)
{
	return l == NULL || l->size == 0;
}
unsigned int
linkedlist_size(const struct linkedlist *l)
{
	return l == NULL ? 0 : l->size;
}
void
linkedlist_iterate(void *l, iter_t *iter)
{
	if (l && iter) {
		iter->i1 = 0;
	}
}
void *
linkedlist_next(void *l, iter_t *iter)
{
	if (l && iter) {
		struct linkedlist *l0 = l;

		if (iter->i1 >= l0->size) {
			return NULL;
		}
		/* optimized using cache to be O(1) if elements accessed sequentially */
		return linkedlist_get(l0, iter->i1++);
	}

	return NULL;
}
void *
linkedlist_get(struct linkedlist *l, unsigned int idx)
{
	if (l == NULL) {
		errno = EINVAL;
		PMNF(errno, ": l=%p", l);
		return NULL;
	}

	if (idx >= l->size) {
		PMNF(errno = ERANGE, ": idx=%u,size=%u", idx, l->size);
		return NULL;
	}
	if (idx == 0) {
		return l->first->data;
	} else if (idx == l->size - 1) {
		return l->last->data;
	} else {
		unsigned int i, closest_idx = (unsigned int)-1;
		struct cache_entry *ce, *stale = NULL, *closest = NULL;

		for (i = 0; i < CACHE_SIZE && closest_idx; i++) {
			ce = l->cache + i;
			if (ce->ent == NULL) {
				stale = ce;
				continue;
			}
			if (idx >= ce->idx && (idx - ce->idx) < closest_idx) {
				closest_idx = ce->idx;
				closest = ce;
			} else if (stale == NULL) {
				stale = ce;
			}
		}
		if (closest_idx == (unsigned int)-1) {
			struct node *next = l->first;
			ce = stale;
			for (i = 0; i < idx; i++) {
				next = next->ptr;
			}
			ce->idx = i;
			ce->ent = next;
		} else {
			ce = closest;
			while (ce->idx < idx) {
				ce->idx++;
				ce->ent = ce->ent->ptr;
				if (ce->ent == NULL) {
					return NULL;
				}
			}
		}

		return ce->ent->data;
	}
}
void *
linkedlist_get_last(const struct linkedlist *l)
{
	if (l == NULL) {
		PMNF(errno = EINVAL, ": l=%p", l);
		return NULL;
	}
	if (l->size == 0) {
		return NULL;
	}
	return l->last->data;
}
void *
linkedlist_remove(struct linkedlist *l, unsigned int idx)
{
	void *result;
	struct node *tmp;

	if (l == NULL) {
		PMNF(errno = EINVAL, ": l=%p", l);
		return NULL;
	}
	if (idx >= l->size) {
		return NULL;
	}
	if (idx == 0) {
		result = l->first->data;
		tmp = l->first;
		l->first = l->first->ptr;
	} else {
		struct node *n;
		unsigned int i;

		n = l->first;
		for (i = 1; i < idx; i++) {
			n = n->ptr;
		}
		tmp = n->ptr;
		n->ptr = tmp->ptr;
		if (tmp == l->last) {
			l->last = n;
		}
		result = tmp->data;
	}
	_cache_remove_by_node(l, tmp);
	allocator_free(l->al, tmp);
	l->size--;

	_cache_update_by_index(l, idx, 0); /* decrement cache entries with larger idx */

	return result;
}
void *
linkedlist_remove_last(struct linkedlist *l)
{
	void *result;

	if (l == NULL) {
		PMNF(errno = EINVAL, ": l=%p", l);
		return NULL;
	}
	if (l->size == 0) {
		return NULL;
	}
	if (l->size == 1) {
		result = l->first->data;
		_cache_remove_by_node(l, l->first);
		allocator_free(l->al, l->first);
		l->first = l->last = NULL;
	} else {
		struct node *n;

		result = l->last->data;
		n = l->first;
		while (n->ptr != l->last) {
			n = n->ptr;
		}
		_cache_remove_by_node(l, l->last);
		allocator_free(l->al, l->last);
		l->last = n;
		n->ptr = NULL;
	}
	l->size--;

	return result;
}
void *
linkedlist_remove_data(struct linkedlist *l, const void *data)
{
	struct node *tmp;

	if (l == NULL || data == NULL) {
		PMNF(errno = EINVAL, ": l=%p", l);
		return NULL;
	}
	if (l->size == 0) {
		return NULL;
	}
	if (data == l->first->data) {
		tmp = l->first;
		l->first = l->first->ptr;
	} else {
		struct node *n;
		int idx = 1;

		for (n = l->first; n->ptr && n->ptr->data != data; n = n->ptr) {
			idx++;
		}
		if (n->ptr == NULL) {
			return NULL;
		}

		tmp = n->ptr;
		n->ptr = tmp->ptr;
		if (tmp == l->last) {
			l->last = n;
		}

		_cache_update_by_index(l, idx, 0); /* decrement cache entries with larger idx */
	}
	_cache_remove_by_node(l, tmp);
	allocator_free(l->al, tmp);
	l->size--;

	return (void *)data;
}
int
linkedlist_toarray(struct linkedlist *l, void *array[])
{
	struct node *n;
	int i;

	if (l == NULL || array == NULL) {
		PMNF(errno = EINVAL, ": l=%p", l);
		return -1;
	}

	n = l->first;
	for (i = 0; n; i++) {
		array[i] = n->data;
		n = n->ptr;
	}

	return 0;
}