richard@300: /*
richard@300:  * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>
richard@300:  * Copyright (C) 2008  Red Hat, Inc
richard@300:  *
richard@300:  * This program is free software; you can redistribute it and/or modify
richard@300:  * it under the terms of the GNU General Public License as published by
richard@300:  * the Free Software Foundation; either version 2 of the License, or
richard@300:  * (at your option) any later version.
richard@300:  *
richard@300:  * This program is distributed in the hope that it will be useful,
richard@300:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
richard@300:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
richard@300:  * GNU General Public License for more details.
richard@300:  *
richard@300:  * You should have received a copy of the GNU General Public License along
richard@300:  * with this program; if not, write to the Free Software Foundation, Inc.,
richard@300:  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
richard@300:  */
richard@300: 
rhughes@241: #include <stdlib.h>
rhughes@241: #include <string.h>
rhughes@241: 
krh@248: #include "razor-internal.h"
rhughes@241: 
rhughes@241: void
rhughes@241: array_init(struct array *array)
rhughes@241: {
rhughes@241: 	memset(array, 0, sizeof *array);
rhughes@241: }
rhughes@241: 
rhughes@241: void
rhughes@241: array_release(struct array *array)
rhughes@241: {
rhughes@241: 	free(array->data);
rhughes@241: }
rhughes@241: 
rhughes@241: void *
rhughes@241: array_add(struct array *array, int size)
rhughes@241: {
rhughes@241: 	int alloc;
rhughes@241: 	void *data, *p;
rhughes@241: 
rhughes@241: 	if (array->alloc > 0)
rhughes@241: 		alloc = array->alloc;
rhughes@241: 	else
rhughes@241: 		alloc = 16;
rhughes@241: 
rhughes@241: 	while (alloc < array->size + size)
rhughes@241: 		alloc *= 2;
rhughes@241: 
rhughes@241: 	if (array->alloc < alloc) {
rhughes@241: 		data = realloc(array->data, alloc);
rhughes@241: 		if (data == NULL)
rhughes@241: 			return 0;
rhughes@241: 		array->data = data;
rhughes@241: 		array->alloc = alloc;
rhughes@241: 	}
rhughes@241: 
rhughes@241: 	p = array->data + array->size;
rhughes@241: 	array->size += size;
rhughes@241: 
rhughes@241: 	return p;
rhughes@241: }
rhughes@241: 
rhughes@241: /* RAZOR_IMMEDIATE and RAZOR_ENTRY_LAST must have the same value */
rhughes@241: #define RAZOR_ENTRY_LAST 0x80
rhughes@241: #define RAZOR_IMMEDIATE  0x80
rhughes@241: #define RAZOR_EMPTY_LIST 0xff
rhughes@241: 
rhughes@241: void
rhughes@241: list_set_empty(struct list_head *head)
rhughes@241: {
rhughes@241: 	head->list_ptr = ~0;
rhughes@241: 	head->flags = RAZOR_EMPTY_LIST;
rhughes@241: }
rhughes@241: 
rhughes@241: void
rhughes@241: list_set_ptr(struct list_head *head, uint32_t ptr)
rhughes@241: {
rhughes@241: 	head->list_ptr = ptr;
rhughes@241: 	head->flags = 0;
rhughes@241: }
rhughes@241: 
rhughes@241: void
rhughes@241: list_set_array(struct list_head *head, struct array *pool,
rhughes@241: 	       struct array *items, int force_indirect)
rhughes@241: {
rhughes@241: 	struct list *p;
rhughes@241: 
rhughes@241: 	if (!force_indirect) {
rhughes@241: 		if (items->size == 0) {
rhughes@241: 			list_set_empty(head);
rhughes@241: 			return;
rhughes@241: 		} else if (items->size == sizeof (uint32_t)) {
rhughes@241: 			head->list_ptr = *(uint32_t *) items->data;
rhughes@241: 			head->flags = RAZOR_IMMEDIATE;
rhughes@241: 			return;
rhughes@241: 		}
rhughes@241: 	}
rhughes@241: 
rhughes@241: 	p = array_add(pool, items->size);
rhughes@241: 	memcpy(p, items->data, items->size);
rhughes@241: 	p[items->size / sizeof *p - 1].flags = RAZOR_ENTRY_LAST;
rhughes@241: 	list_set_ptr(head, p - (struct list *) pool->data);
rhughes@241: }
rhughes@241: 
rhughes@241: struct list *
rhughes@241: list_first(struct list_head *head, struct array *pool)
rhughes@241: {
rhughes@241: 	if (head->flags == RAZOR_EMPTY_LIST)
rhughes@241: 		return NULL;
rhughes@241: 	else if (head->flags == RAZOR_IMMEDIATE)
rhughes@241: 		return (struct list *) head;
rhughes@241: 	else
rhughes@241: 		return (struct list *) pool->data + head->list_ptr;
rhughes@241: }
rhughes@241: 
rhughes@241: struct list *
rhughes@241: list_next(struct list *list)
rhughes@241: {
rhughes@241: 	if (list->flags)
rhughes@241: 		return NULL;
rhughes@241: 	return ++list;
rhughes@241: }
rhughes@241: 
rhughes@241: void
rhughes@241: list_remap_pool(struct array *pool, uint32_t *map)
rhughes@241: {
rhughes@241: 	struct list *p, *end;
rhughes@241: 
rhughes@241: 	end = pool->data + pool->size;
rhughes@241: 	for (p = pool->data; p < end; p++)
rhughes@241: 		p->data = map[p->data];
rhughes@241: }
rhughes@241: 
rhughes@241: void
rhughes@241: list_remap_head(struct list_head *head, uint32_t *map)
rhughes@241: {
rhughes@241: 	if (head->flags == RAZOR_IMMEDIATE)
rhughes@241: 		head->list_ptr = map[head->list_ptr];
rhughes@241: }
rhughes@241: 
rhughes@241: 
rhughes@241: void
rhughes@241: hashtable_init(struct hashtable *table, struct array *pool)
rhughes@241: {
rhughes@241: 	array_init(&table->buckets);
rhughes@241: 	table->pool = pool;
rhughes@241: }
rhughes@241: 
rhughes@241: void
rhughes@241: hashtable_release(struct hashtable *table)
rhughes@241: {
rhughes@241: 	array_release(&table->buckets);
rhughes@241: }
rhughes@241: 
rhughes@241: static unsigned int
rhughes@241: hash_string(const char *key)
rhughes@241: {
rhughes@241: 	const char *p;
rhughes@241: 	unsigned int hash = 0;
rhughes@241: 
rhughes@241: 	for (p = key; *p; p++)
rhughes@241: 		hash = (hash * 617) ^ *p;
rhughes@241: 
rhughes@241: 	return hash;
rhughes@241: }
rhughes@241: 
rhughes@241: uint32_t
rhughes@241: hashtable_lookup(struct hashtable *table, const char *key)
rhughes@241: {
rhughes@241: 	unsigned int mask, start, i;
rhughes@241: 	uint32_t *b;
rhughes@241: 	char *pool;
rhughes@241: 
rhughes@241: 	pool = table->pool->data;
rhughes@241: 	mask = table->buckets.alloc - 1;
rhughes@241: 	start = hash_string(key) * sizeof(uint32_t);
rhughes@241: 
rhughes@241: 	for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
rhughes@241: 		b = table->buckets.data + ((start + i) & mask);
rhughes@241: 
rhughes@241: 		if (*b == 0)
rhughes@241: 			return 0;
rhughes@241: 
rhughes@241: 		if (strcmp(key, &pool[*b]) == 0)
rhughes@241: 			return *b;
rhughes@241: 	}
rhughes@241: 
rhughes@241: 	return 0;
rhughes@241: }
rhughes@241: 
rhughes@241: static void
rhughes@241: do_insert(struct hashtable *table, uint32_t value)
rhughes@241: {
rhughes@241: 	unsigned int mask, start, i;
rhughes@241: 	uint32_t *b;
rhughes@241: 	const char *key;
rhughes@241: 
rhughes@241: 	key = (char *) table->pool->data + value;
rhughes@241: 	mask = table->buckets.alloc - 1;
rhughes@241: 	start = hash_string(key) * sizeof(uint32_t);
rhughes@241: 
rhughes@241: 	for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
rhughes@241: 		b = table->buckets.data + ((start + i) & mask);
rhughes@241: 		if (*b == 0) {
rhughes@241: 			*b = value;
rhughes@241: 			break;
rhughes@241: 		}
rhughes@241: 	}
rhughes@241: }
rhughes@241: 
rhughes@241: static uint32_t
rhughes@241: add_to_string_pool(struct hashtable *table, const char *key)
rhughes@241: {
rhughes@241: 	int len;
rhughes@241: 	char *p;
rhughes@241: 
rhughes@241: 	len = strlen(key) + 1;
rhughes@241: 	p = array_add(table->pool, len);
rhughes@241: 	memcpy(p, key, len);
rhughes@241: 
rhughes@241: 	return p - (char *) table->pool->data;
rhughes@241: }
rhughes@241: 
rhughes@241: uint32_t
rhughes@241: hashtable_insert(struct hashtable *table, const char *key)
rhughes@241: {
rhughes@241: 	uint32_t value, *buckets, *b, *end;
rhughes@241: 	int alloc;
rhughes@241: 
rhughes@241: 	alloc = table->buckets.alloc;
rhughes@241: 	array_add(&table->buckets, 4 * sizeof *buckets);
rhughes@241: 	if (alloc != table->buckets.alloc) {
rhughes@241: 		end = table->buckets.data + alloc;
rhughes@241: 		memset(end, 0, table->buckets.alloc - alloc);
rhughes@241: 		for (b = table->buckets.data; b < end; b++) {
rhughes@241: 			value = *b;
rhughes@241: 			if (value != 0) {
rhughes@241: 				*b = 0;
rhughes@241: 				do_insert(table, value);
rhughes@241: 			}
rhughes@241: 		}
rhughes@241: 	}
rhughes@241: 
rhughes@241: 	value = add_to_string_pool(table, key);
rhughes@241: 	do_insert (table, value);
rhughes@241: 
rhughes@241: 	return value;
rhughes@241: }
rhughes@241: 
rhughes@241: uint32_t
rhughes@241: hashtable_tokenize(struct hashtable *table, const char *string)
rhughes@241: {
rhughes@241: 	uint32_t token;
rhughes@241: 
rhughes@241: 	if (string == NULL)
rhughes@241: 		string = "";
rhughes@241: 
rhughes@241: 	token = hashtable_lookup(table, string);
rhughes@241: 	if (token != 0)
rhughes@241: 		return token;
rhughes@241: 
rhughes@241: 	return hashtable_insert(table, string);
rhughes@241: }