/*
   +----------------------------------------------------------------------+
   | Zend Engine                                                          |
   +----------------------------------------------------------------------+
   | Copyright (c) 1998-2003 Zend Technologies Ltd. (http://www.zend.com) |
   +----------------------------------------------------------------------+
   | This source file is subject to version 2.00 of the Zend license,     |
   | that is bundled with this package in the file LICENSE, and is        | 
   | available at through the world-wide-web at                           |
   | http://www.zend.com/license/2_00.txt.                                |
   | If you did not receive a copy of the Zend license and are unable to  |
   | obtain it through the world-wide-web, please send a note to          |
   | license@zend.com so we can mail you a copy immediately.              |
   +----------------------------------------------------------------------+
   | Authors: Sterling Hughes <sterling@php.net>                          |
   +----------------------------------------------------------------------+
*/

/* $Id: $ */

#include "zend.h"
#include "zend_fast_hash.h"

static inline unsigned long 
zend_fast_hash_hash(char *key, uint key_len)
{
	register ulong hash = 5381;

	for (; key_len >= 8; key_len -= 8) {
		hash = ((hash << 5) + hash) + *key++;
		hash = ((hash << 5) + hash) + *key++;
		hash = ((hash << 5) + hash) + *key++;
		hash = ((hash << 5) + hash) + *key++;
		hash = ((hash << 5) + hash) + *key++;
		hash = ((hash << 5) + hash) + *key++;
		hash = ((hash << 5) + hash) + *key++;
		hash = ((hash << 5) + hash) + *key++;
	}

	switch (key_len) {
		case 7: hash = ((hash << 5) + hash) + *key++;
		case 6: hash = ((hash << 5) + hash) + *key++;
		case 5: hash = ((hash << 5) + hash) + *key++;
		case 4: hash = ((hash << 5) + hash) + *key++;
		case 3: hash = ((hash << 5) + hash) + *key++;
		case 2: hash = ((hash << 5) + hash) + *key++;
		case 1: hash = ((hash << 5) + hash) + *key++; break;
		case 0: break;
	}

	return hash;
}


ZEND_API void zend_fast_hash_init(zend_fast_hash *h, int slots, zend_bool persistent, zend_fast_hash_dtor_func_t dtor TSRMLS_DC)
{
	h->dtor = dtor;
	h->size = 0;
	h->slots = slots;
	h->persistent = persistent;
	h->table = (zend_fast_hash_slist **) pemalloc(slots * sizeof(zend_fast_hash_slist), persistent);
	memset(h->table, 0, sizeof(zend_fast_hash_slist) * slots);
}

#define QUICK_COMPARE(k1, k1l, k2, k2l) ((k1l) == (k2l) && memcmp(k1, k2, k1l))

ZEND_API int zend_fast_hash_update(zend_fast_hash *h, char *key, int key_len, const void *p TSRMLS_DC)
{
	register zend_fast_hash_slist *current;
	zend_fast_hash_slist *prev;
	zend_fast_hash_slist **start;
	int loc;
	unsigned long hval;

	hval = zend_fast_hash_hash(key, key_len);

	loc = hval % h->slots;
	current = h->table[loc];

	while (current) {
		if (current->hval == hval && QUICK_COMPARE(key, key_len, current->key, current->key_len)) {
			if (h->dtor) {
				h->dtor(current->ptr TSRMLS_CC);
			}
			current->ptr = (void *) p;

			return SUCCESS;
		}

		current = current->next;
	}

	current = pemalloc(sizeof(zend_fast_hash_slist), h->persistent);
	current->hval = hval;
	current->ptr = (void *) p;
	current->key = estrndup(key, key_len);
	current->key_len = key_len;
	current->next = NULL;

	start = &h->table[loc];
	if (*start) {
		current->next = *start;
	}
	*start = current;
	h->size++;

	return SUCCESS;
}

ZEND_API int zend_fast_hash_find(zend_fast_hash *h, char *key, int key_len, void **p TSRMLS_DC)
{
	register zend_fast_hash_slist *current;
	unsigned long hval;

	hval = zend_fast_hash_hash(key, key_len);
	
	current = h->table[hval % h->slots];
	while (current) {
		if (current->hval == hval && QUICK_COMPARE(key, key_len, current->key, current->key_len)) {
			*p = current->ptr;
			return SUCCESS;
		}

		current = current->next;
	}

	return FAILURE;
}

ZEND_API int zend_fast_hash_delete(zend_fast_hash *h, char *key, int key_len TSRMLS_DC)
{
	zend_fast_hash_slist *current;
	zend_fast_hash_slist **prev;
	unsigned long hval;
	
	hval = zend_fast_hash_hash(key, key_len);
	
	current = h->table[hval % h->slots];
	prev = &current;

	while (current) {
		if (current->hval == hval && QUICK_COMPARE(key, key_len, current->key, current->key_len)) {
			if (current->next) {
				(*prev)->next = current->next->next;
			} else {
				(*prev)->next = NULL;
			}

			*prev = current->next;
			
			if (h->dtor) {
				h->dtor(current->ptr TSRMLS_CC);
			}
			pefree(current, h->persistent);

			h->size--;

			return SUCCESS;
		}
		
		prev = &current;
		current = current->next;
	}

	return FAILURE;
}

ZEND_API int zend_fast_hash_count(zend_fast_hash *h TSRMLS_DC)
{
	return h->size;
}

ZEND_API void zend_fast_hash_copy(zend_fast_hash *target, zend_fast_hash *source TSRMLS_DC)
{
	register zend_fast_hash_slist *current;
	register int i;

	for (i = 0; i < source->slots; ++i) {
		current = source->table[i];

		while (current) {
			zend_fast_hash_update(target, current->key, current->key_len, current->ptr TSRMLS_CC);
			current = current->next;
		}
	}
}

ZEND_API void zend_fast_hash_apply(zend_fast_hash *h, apply_func_t apply_func TSRMLS_DC)
{
	register zend_fast_hash_slist *current;
	register int i;

	for (i = 0; i < h->slots; ++i) {
		current = h->table[i];

		while (current) {
			apply_func(current->ptr TSRMLS_CC);
			current = current->next;
		}
	}
}

ZEND_API void zend_fast_hash_apply_with_argument(zend_fast_hash *h, apply_func_arg_t apply_func, void *arg TSRMLS_DC)
{
	register zend_fast_hash_slist *current;
	register int i;

	for (i = 0; i < h->slots; ++i) {
		current = h->table[i];

		while (current) {
			apply_func(current->ptr, arg TSRMLS_CC);
			current = current->next;
		}
	}
}

ZEND_API void zend_fast_hash_display(zend_fast_hash *h TSRMLS_DC)
{
	register zend_fast_hash_slist *current;
	register int i;

	for (i = 0; i < h->slots; ++i) {
		current = h->table[i];

		while (current) {
			printf("Bucket = %d, Key = %s, Value = %x\n", i, current->key, current->ptr);
			current = current->next;
		}
	}
}

ZEND_API void zend_fast_hash_clean(zend_fast_hash *h TSRMLS_DC)
{
	register zend_fast_hash_slist *current;
	register zend_fast_hash_slist *next;
	register int i;

	for (i = 0; i < h->slots; ++i) {
		current = h->table[i];

		while (current) {
			next = current->next;

			if (h->dtor) {
				h->dtor(current->ptr TSRMLS_CC);
			}
			pefree(current, h->persistent);

			current = next;
		}
	}
	memset(h->table, 0, h->size * sizeof(zend_fast_hash_slist *));
}

ZEND_API void zend_fast_hash_destroy(zend_fast_hash *h TSRMLS_DC)
{
	zend_fast_hash_clean(h);
	efree(h->table);
}

/*
 * Local variables:
 * tab-width: 4
 * c-basic-offset: 4
 * indent-tabs-mode: t
 * End:
 * vim600: fdm=marker
 * vim: noet sw=4 ts=4
 */