1 files changed, 276 insertions, 0 deletions
diff --git a/common/strset.c b/common/strset.c
new file mode 100644
index 0000000..801a358
--- /dev/null
+++ b/common/strset.c
@@ -0,0 +1,276 @@
+/*
+ * 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;
+}