/*
 * Copyright (c) 2008, Stefan Walter
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *     * Redistributions of source code must retain the above
 *       copyright notice, this list of conditions and the
 *       following disclaimer.
 *     * Redistributions in binary form must reproduce the
 *       above copyright notice, this list of conditions and
 *       the following disclaimer in the documentation and/or
 *       other materials provided with the distribution.
 *     * The names of contributors to this software may not be
 *       used to endorse or promote products derived from this
 *       software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
 * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 */

/*
 * Originally from apache 2.0
 */

/* Copyright 2000-2004 The Apache Software Foundation
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *         http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <sys/types.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>

#include "strset.h"

typedef struct _entry {
	struct _entry* next;
	unsigned int hash;
	char *value;
} entry;

struct _strset {
	entry **array;
	unsigned int count;
	unsigned int max;
};

#define INITIAL_MAX 15 /* tunable == 2^n - 1 */

static entry**
alloc_array (unsigned int max)
{
	void *ret;
	size_t len;

	assert (max);

	len = sizeof (entry*) * (max + 1);
	ret = strset_malloc (len);
	if (ret)
		memset (ret, 0, len);

	return ret;
}

strset*
strset_create (void)
{
	strset *set = strset_malloc (sizeof (strset));
	if (set) {
		memset (set, 0, sizeof (strset));
		set->max = INITIAL_MAX;
		set->array = alloc_array (set->max);
		if (!set->array) {
			strset_free (set);
			set = NULL;
		}
	}

	return set;
}

void
strset_destroy (strset *set)
{
	unsigned int i;
	entry *ent, *next;

	if (!set)
		return;

	/* Free all the entries */
	for (i = 0; i < set->max; ++i) {
		next = NULL;
		for (ent = set->array[i]; ent; ent = next) {
			next = ent->next;

			assert (ent->value);
			strset_free (ent);
		}
	}

	/* Free the set itself */
	strset_free (set->array);
	strset_free (set);
}

static int
expand_array (strset* set)
{
	entry** new_array;
	entry* ent, *next;
	unsigned int new_max, n, i;

	assert (set);
	assert (set->max);
	assert (set->array);

	new_max = set->max * 2 + 1;
	new_array = alloc_array (new_max);

	if(!new_array)
		return 0;

	/* Go through all the entries */
	for (i = 0; i < set->max; ++i) {
		next = NULL;
		for (ent = set->array[i]; ent; ent = next) {
			next = ent->next;

			n = ent->hash & new_max;
			ent->next = new_array[n];
			new_array[n] = ent;
		}
	}

	strset_free (set->array);
	set->array = new_array;
	set->max = new_max;

	return 1;
}

static entry**
find_entry (strset* set, const char *value, int add)
{
	entry **ep, *e;
	const char* p;
	unsigned int hash;
	size_t len;

	assert (set);
	assert (set->max);
	assert (set->array);
	assert (value);

	hash = 0;

	for(p = value; *p; p++)
		hash = hash * 33 + *p;

	/* scan linked list */
	for (ep = &set->array[hash & set->max], e = *ep;
	     e; ep = &e->next, e = *ep)
	{
		if (e->hash == hash && strcmp (e->value, value) == 0)
			break;
	}

	if (e || !add)
		return ep;

	/* Add an entry */
	len = strlen (value);
	e = strset_malloc (sizeof (entry) + len + 1);
	if (e) {
		/* Value data points past end of entry */
		e->value = ((char*)e) + sizeof (entry);
		memcpy (e->value, value, len + 1);

		e->next = NULL;
		e->hash = hash;

		*ep = e;
		++set->count;
	}

	return ep;
}

int
strset_has (strset *set, const char *value)
{
	entry **ep;

	assert (set);

	if (!value)
		return 0;

	ep = find_entry (set, value, 0);
	return ep && *ep ? 1 : 0;
}

int
strset_add (strset *set, const char *value)
{
	entry **ep;

	assert (set);

	if (!value)
		return -1;

	ep = find_entry (set, value, 1);
	if (!ep || !*ep)
		return -1;

        if (set->count > set->max)
        	if (!expand_array (set))
        		return -1;

        return 0;
}

int
strset_remove (strset *set, const char* value)
{
	entry **ep, *old;

	assert (set);

	if (!value)
		return -1;

	ep = find_entry (set, value, 0);
	if (!ep || !*ep)
		return -1;

	old = *ep;
	*ep = (*ep)->next;
	--set->count;
	strset_free (old);
	return 0;
}

unsigned int
strset_size (strset *set)
{
	assert (set);
	return set->count;
}