diff -r 000000000000 -r 708a3d9c759a librazor/types.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/librazor/types.c	Mon Jun 16 22:35:09 2008 -0400
@@ -0,0 +1,246 @@
+#include <stdlib.h>
+#include <string.h>
+
+#include "types.h"
+
+void
+array_init(struct array *array)
+{
+	memset(array, 0, sizeof *array);
+}
+
+void
+array_release(struct array *array)
+{
+	free(array->data);
+}
+
+void *
+array_add(struct array *array, int size)
+{
+	int alloc;
+	void *data, *p;
+
+	if (array->alloc > 0)
+		alloc = array->alloc;
+	else
+		alloc = 16;
+
+	while (alloc < array->size + size)
+		alloc *= 2;
+
+	if (array->alloc < alloc) {
+		data = realloc(array->data, alloc);
+		if (data == NULL)
+			return 0;
+		array->data = data;
+		array->alloc = alloc;
+	}
+
+	p = array->data + array->size;
+	array->size += size;
+
+	return p;
+}
+
+/* RAZOR_IMMEDIATE and RAZOR_ENTRY_LAST must have the same value */
+#define RAZOR_ENTRY_LAST 0x80
+#define RAZOR_IMMEDIATE  0x80
+#define RAZOR_EMPTY_LIST 0xff
+
+void
+list_set_empty(struct list_head *head)
+{
+	head->list_ptr = ~0;
+	head->flags = RAZOR_EMPTY_LIST;
+}
+
+void
+list_set_ptr(struct list_head *head, uint32_t ptr)
+{
+	head->list_ptr = ptr;
+	head->flags = 0;
+}
+
+void
+list_set_array(struct list_head *head, struct array *pool,
+	       struct array *items, int force_indirect)
+{
+	struct list *p;
+
+	if (!force_indirect) {
+		if (items->size == 0) {
+			list_set_empty(head);
+			return;
+		} else if (items->size == sizeof (uint32_t)) {
+			head->list_ptr = *(uint32_t *) items->data;
+			head->flags = RAZOR_IMMEDIATE;
+			return;
+		}
+	}
+
+	p = array_add(pool, items->size);
+	memcpy(p, items->data, items->size);
+	p[items->size / sizeof *p - 1].flags = RAZOR_ENTRY_LAST;
+	list_set_ptr(head, p - (struct list *) pool->data);
+}
+
+struct list *
+list_first(struct list_head *head, struct array *pool)
+{
+	if (head->flags == RAZOR_EMPTY_LIST)
+		return NULL;
+	else if (head->flags == RAZOR_IMMEDIATE)
+		return (struct list *) head;
+	else
+		return (struct list *) pool->data + head->list_ptr;
+}
+
+struct list *
+list_next(struct list *list)
+{
+	if (list->flags)
+		return NULL;
+	return ++list;
+}
+
+void
+list_remap_pool(struct array *pool, uint32_t *map)
+{
+	struct list *p, *end;
+
+	end = pool->data + pool->size;
+	for (p = pool->data; p < end; p++)
+		p->data = map[p->data];
+}
+
+void
+list_remap_head(struct list_head *head, uint32_t *map)
+{
+	if (head->flags == RAZOR_IMMEDIATE)
+		head->list_ptr = map[head->list_ptr];
+}
+
+
+void
+hashtable_init(struct hashtable *table, struct array *pool)
+{
+	array_init(&table->buckets);
+	table->pool = pool;
+}
+
+void
+hashtable_release(struct hashtable *table)
+{
+	array_release(&table->buckets);
+}
+
+static unsigned int
+hash_string(const char *key)
+{
+	const char *p;
+	unsigned int hash = 0;
+
+	for (p = key; *p; p++)
+		hash = (hash * 617) ^ *p;
+
+	return hash;
+}
+
+uint32_t
+hashtable_lookup(struct hashtable *table, const char *key)
+{
+	unsigned int mask, start, i;
+	uint32_t *b;
+	char *pool;
+
+	pool = table->pool->data;
+	mask = table->buckets.alloc - 1;
+	start = hash_string(key) * sizeof(uint32_t);
+
+	for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
+		b = table->buckets.data + ((start + i) & mask);
+
+		if (*b == 0)
+			return 0;
+
+		if (strcmp(key, &pool[*b]) == 0)
+			return *b;
+	}
+
+	return 0;
+}
+
+static void
+do_insert(struct hashtable *table, uint32_t value)
+{
+	unsigned int mask, start, i;
+	uint32_t *b;
+	const char *key;
+
+	key = (char *) table->pool->data + value;
+	mask = table->buckets.alloc - 1;
+	start = hash_string(key) * sizeof(uint32_t);
+
+	for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
+		b = table->buckets.data + ((start + i) & mask);
+		if (*b == 0) {
+			*b = value;
+			break;
+		}
+	}
+}
+
+static uint32_t
+add_to_string_pool(struct hashtable *table, const char *key)
+{
+	int len;
+	char *p;
+
+	len = strlen(key) + 1;
+	p = array_add(table->pool, len);
+	memcpy(p, key, len);
+
+	return p - (char *) table->pool->data;
+}
+
+uint32_t
+hashtable_insert(struct hashtable *table, const char *key)
+{
+	uint32_t value, *buckets, *b, *end;
+	int alloc;
+
+	alloc = table->buckets.alloc;
+	array_add(&table->buckets, 4 * sizeof *buckets);
+	if (alloc != table->buckets.alloc) {
+		end = table->buckets.data + alloc;
+		memset(end, 0, table->buckets.alloc - alloc);
+		for (b = table->buckets.data; b < end; b++) {
+			value = *b;
+			if (value != 0) {
+				*b = 0;
+				do_insert(table, value);
+			}
+		}
+	}
+
+	value = add_to_string_pool(table, key);
+	do_insert (table, value);
+
+	return value;
+}
+
+uint32_t
+hashtable_tokenize(struct hashtable *table, const char *string)
+{
+	uint32_t token;
+
+	if (string == NULL)
+		string = "";
+
+	token = hashtable_lookup(table, string);
+	if (token != 0)
+		return token;
+
+	return hashtable_insert(table, string);
+}