danw@115: #include <stdlib.h>
danw@115: #include <string.h>
danw@115: 
danw@115: #include "types.h"
danw@115: 
danw@115: void
danw@115: array_init(struct array *array)
danw@115: {
danw@115: 	memset(array, 0, sizeof *array);
danw@115: }
danw@115: 
danw@115: void
danw@115: array_release(struct array *array)
danw@115: {
danw@115: 	free(array->data);
danw@115: }
danw@115: 
danw@115: void *
danw@115: array_add(struct array *array, int size)
danw@115: {
danw@115: 	int alloc;
danw@115: 	void *data, *p;
danw@115: 
danw@115: 	if (array->alloc > 0)
danw@115: 		alloc = array->alloc;
danw@115: 	else
danw@115: 		alloc = 16;
danw@115: 
danw@115: 	while (alloc < array->size + size)
danw@115: 		alloc *= 2;
danw@115: 
danw@115: 	if (array->alloc < alloc) {
danw@115: 		data = realloc(array->data, alloc);
danw@115: 		if (data == NULL)
danw@115: 			return 0;
danw@115: 		array->data = data;
danw@115: 		array->alloc = alloc;
danw@115: 	}
danw@115: 
danw@115: 	p = array->data + array->size;
danw@115: 	array->size += size;
danw@115: 
danw@115: 	return p;
danw@115: }
danw@115: 
danw@116: #define RAZOR_ENTRY_LAST	0x80000000ul
danw@116: #define RAZOR_IMMEDIATE		0x80000000ul
danw@116: #define RAZOR_ENTRY_MASK	0x00fffffful
danw@116: 
danw@116: void
danw@116: list_init(uint32_t *list)
danw@116: {
danw@116: 	*list = ~0;
danw@116: }
danw@116: 
danw@116: void
danw@116: list_set(uint32_t *list, struct array *pool, struct array *items)
danw@116: {
danw@116: 	uint32_t *p;
danw@116: 
danw@116: 	if (items->size == 0) {
danw@116: 		list_init(list);
danw@116: 	} else if (items->size == sizeof (uint32_t)) {
danw@116: 		*list = *(uint32_t *) items->data | RAZOR_IMMEDIATE;
danw@116: 	} else {
danw@116: 		p = array_add(pool, items->size);
danw@116: 		memcpy(p, items->data, items->size);
danw@116: 		p[items->size / sizeof *p - 1] |= RAZOR_ENTRY_LAST;
danw@116: 		*list = p - (uint32_t *) pool->data;
danw@116: 	}
danw@116: }
danw@116: 
danw@116: uint32_t *
danw@116: list_first(uint32_t *list, struct array *pool)
danw@116: {
danw@116: 	if (*list == ~0)
danw@116: 		return NULL;
danw@116: 	else if (*list & RAZOR_IMMEDIATE)
danw@116: 		return list;
danw@116: 	else
danw@116: 		return (uint32_t *) pool->data + (*list & RAZOR_ENTRY_MASK);
danw@116: }
danw@116: 
danw@116: uint32_t *
danw@116: list_next(uint32_t *list)
danw@116: {
danw@116: 	if (*list & ~RAZOR_ENTRY_MASK)
danw@116: 		return NULL;
danw@116: 	return ++list;
danw@116: }
danw@116: 
danw@116: void
danw@116: list_remap_pool(struct array *pool, uint32_t *map)
danw@116: {
danw@116: 	uint32_t *p, *end;
danw@116: 
danw@116: 	end = pool->data + pool->size;
danw@116: 	for (p = pool->data; p < end; p++)
danw@116: 		*p = map[LIST_VALUE(p)] | LIST_FLAGS(p);
danw@116: }
danw@116: 
danw@116: void
danw@116: list_remap_if_immediate(uint32_t *list, uint32_t *map)
danw@116: {
danw@116: 	if ((*list & ~RAZOR_ENTRY_MASK) == RAZOR_IMMEDIATE)
danw@116: 		*list = map[LIST_VALUE(list)] | LIST_FLAGS(list);
danw@116: }
danw@116: 
danw@115: 
danw@115: void
danw@115: hashtable_init(struct hashtable *table, struct array *pool)
danw@115: {
danw@115: 	array_init(&table->buckets);
danw@115: 	table->pool = pool;
danw@115: }
danw@115: 
danw@115: void
danw@115: hashtable_release(struct hashtable *table)
danw@115: {
danw@115: 	array_release(&table->buckets);
danw@115: }
danw@115: 
danw@115: static unsigned int
danw@115: hash_string(const char *key)
danw@115: {
danw@115: 	const char *p;
danw@115: 	unsigned int hash = 0;
danw@115: 
danw@115: 	for (p = key; *p; p++)
danw@115: 		hash = (hash * 617) ^ *p;
danw@115: 
danw@115: 	return hash;
danw@115: }
danw@115: 
danw@115: uint32_t
danw@115: hashtable_lookup(struct hashtable *table, const char *key)
danw@115: {
danw@115: 	unsigned int mask, start, i;
danw@115: 	uint32_t *b;
danw@115: 	char *pool;
danw@115: 
danw@115: 	pool = table->pool->data;
danw@115: 	mask = table->buckets.alloc - 1;
danw@115: 	start = hash_string(key) * sizeof(uint32_t);
danw@115: 
danw@115: 	for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
danw@115: 		b = table->buckets.data + ((start + i) & mask);
danw@115: 
danw@115: 		if (*b == 0)
danw@115: 			return 0;
danw@115: 
danw@115: 		if (strcmp(key, &pool[*b]) == 0)
danw@115: 			return *b;
danw@115: 	}
danw@115: 
danw@115: 	return 0;
danw@115: }
danw@115: 
danw@115: static void
danw@115: do_insert(struct hashtable *table, uint32_t value)
danw@115: {
danw@115: 	unsigned int mask, start, i;
danw@115: 	uint32_t *b;
danw@115: 	const char *key;
danw@115: 
danw@115: 	key = (char *) table->pool->data + value;
danw@115: 	mask = table->buckets.alloc - 1;
danw@115: 	start = hash_string(key) * sizeof(uint32_t);
danw@115: 
danw@115: 	for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
danw@115: 		b = table->buckets.data + ((start + i) & mask);
danw@115: 		if (*b == 0) {
danw@115: 			*b = value;
danw@115: 			break;
danw@115: 		}
danw@115: 	}
danw@115: }
danw@115: 
danw@115: static uint32_t
danw@115: add_to_string_pool(struct hashtable *table, const char *key)
danw@115: {
danw@115: 	int len;
danw@115: 	char *p;
danw@115: 
danw@115: 	len = strlen(key) + 1;
danw@115: 	p = array_add(table->pool, len);
danw@115: 	memcpy(p, key, len);
danw@115: 
danw@115: 	return p - (char *) table->pool->data;
danw@115: }
danw@115: 
danw@115: uint32_t
danw@115: hashtable_insert(struct hashtable *table, const char *key)
danw@115: {
danw@115: 	uint32_t value, *buckets, *b, *end;
danw@115: 	int alloc;
danw@115: 
danw@115: 	alloc = table->buckets.alloc;
danw@115: 	array_add(&table->buckets, 4 * sizeof *buckets);
danw@115: 	if (alloc != table->buckets.alloc) {
danw@115: 		end = table->buckets.data + alloc;
danw@115: 		memset(end, 0, table->buckets.alloc - alloc);
danw@115: 		for (b = table->buckets.data; b < end; b++) {
danw@115: 			value = *b;
danw@115: 			if (value != 0) {
danw@115: 				*b = 0;
danw@115: 				do_insert(table, value);
danw@115: 			}
danw@115: 		}
danw@115: 	}
danw@115: 
danw@115: 	value = add_to_string_pool(table, key);
danw@115: 	do_insert (table, value);
danw@115: 
danw@115: 	return value;
danw@115: }
danw@115: 
danw@115: uint32_t
danw@115: hashtable_tokenize(struct hashtable *table, const char *string)
danw@115: {
danw@115: 	uint32_t token;
danw@115: 
danw@115: 	if (string == NULL)
danw@115: 		string = "";
danw@115: 
danw@115: 	token = hashtable_lookup(table, string);
danw@115: 	if (token != 0)
danw@115: 		return token;
danw@115: 
danw@115: 	return hashtable_insert(table, string);
danw@115: }