/*
 * Copyright (c) 2008 Telappliant Ltd.
 *
 * 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 "timeoutlist.h"

#include <stdlib.h>
#include <assert.h>
#include <string.h>

static unsigned long
tol_hash( char* str )
{
	unsigned long hash = 0;
	int c;

	while( (c = *str++) )
	{
		hash = c + (hash << 6) + (hash << 16) - hash;
	}

	return hash;
}

struct timeoutlist*
tol_new( void )
{
	struct timeoutlist* list;

	list = malloc(sizeof(struct timeoutlist));
	list->start = NULL;
	list->finish = NULL;

	return list;
}

time_t
tol_expiry( struct timeoutlist* list )
{
	assert( list != NULL );

	if( list->start == NULL )
	{
		return 0;
	}

	return list->start->timeout;
}

struct tol_entry*
tol_delete( struct timeoutlist* list )
{
	assert( list != NULL );
	struct tol_entry* start;

	start = list->start;
	free(list);

	return start;
}

/**
 * Insert the entry into the list, ordering based on it's expiry time
 *
 * The list is ordered with items with timeouts nearest to now starting at
 * the front, with later timeouts at the end.
 *
 * @param list Timeout list
 * @param entry The entry to insert
 */
static void
tol_insert( struct timeoutlist* list, struct tol_entry* entry )
{
	struct tol_entry* cmp;

	// No entries in the list - insert as top
	if( list->start == NULL )
	{
		assert( list->finish == NULL );

		entry->prev = NULL;
		entry->next = NULL;
		list->start = entry;
		list->finish = entry;
	} else
	{
		// Loop through list with cmp
		cmp = list->start;
		while( cmp != NULL )
		{
			// If cmp has a later timeout than us, or is at the end
			if( cmp->timeout > entry->timeout || cmp->next == NULL )
			{
				entry->next = cmp->next;
				entry->prev = cmp;
				cmp->next = entry;

				if( cmp == list->finish )
				{
					list->finish = entry;
				}
				break;
			}

			cmp = cmp->next;
		}
	}
}

struct tol_entry*
tol_add( struct timeoutlist* list, char* name, time_t timeout )
{
	struct tol_entry* entry;

	entry = malloc(sizeof(struct tol_entry));
	entry->name = strdup(name);
	entry->hash = tol_hash(name);
	entry->timeout = timeout;

	tol_insert( list, entry );
	
	return entry;
}

void
tol_remove_entry( struct timeoutlist* list, struct tol_entry* entry )
{
	if( entry->prev != NULL )
	{
		entry->prev->next = entry->next;
	} else if( list->start == entry )
	{
		list->start = entry->next;
	}

	if( entry->next != NULL )
	{
		entry->next->prev = entry->prev;
	} else if( list->finish == entry )
	{
		list->finish = entry->prev;
	}
}

struct tol_entry*
tol_delete_entry( struct tol_entry* entry )
{
	struct tol_entry* next;

	assert( entry != NULL );
	assert( entry->name != NULL );

	next = entry->next;

	free( entry->name );
	free( entry );

	return next;
}

struct tol_entry*
tol_search( struct timeoutlist* list, char* name )
{
	struct tol_entry* current;
	unsigned long hash;

	assert( list != NULL );
	assert( name != NULL );
	
	hash = tol_hash(name);

	current = list->start;
	while( current != NULL )
	{
		if( current->hash == hash && strcmp(current->name,name) == 0 )
		{
			break;
		}

		current = current->next;
	}

	return current;
}

void
tol_modify( struct timeoutlist* list, char* name, time_t timeout )
{
	struct tol_entry* entry;

	entry = tol_search( list, name );
	if( entry != NULL )
	{
		tol_remove_entry(list,entry);
		entry->timeout = timeout;
		tol_insert(list, entry);
	}
}

struct tol_entry*
tol_expire( struct timeoutlist* list, time_t expiry )
{
	struct tol_entry* expired_list;
	struct tol_entry* first_expired;
	struct tol_entry* current;

	expired_list = NULL;
	first_expired = NULL;

	current = list->start;
	while( current != NULL )
	{
		if( current->timeout > expiry )
			break;

		tol_remove_entry( list, current );
		
		if( expired_list == NULL )
		{
			current->prev = NULL;
			current->next = NULL;
			expired_list = current;
			first_expired = current;
		} else
		{
			current->prev = expired_list;
			current->next = NULL;
			expired_list->next = current;
			expired_list = current;
		}

		current = current->next;
	}

	return first_expired;
}