repos_ecs/其他2015后/日志库/log4cproj_c/Log4C/sd/hash.c

/* 
* Copyright 2001-2003, Meiosys (www.meiosys.com). All rights reserved.
*
* See the COPYING file for the terms of usage and distribution.
*/

#include <tchar.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sd/hash.h"
#include "sd/malloc.h"

static const TCHAR version[] = _T("$Id$");

#define SD_HASH_FULLTAB	2	/* rehash when table gets this x full */
#define SD_HASH_GROWTAB 4	/* grow table by this factor */
#define SD_HASH_DEFAULT_SIZE 10 /* self explenatory */

struct __sd_hash {
	size_t			nelem;
	size_t			size;
	sd_hash_iter_t**		tab;
	const sd_hash_ops_t*	ops;
};

#define hindex(h, n)	((h)%(n))

/******************************************************************************/
static void rehash(sd_hash_t* a_this)
{
	size_t			i;
	int h, size;
	sd_hash_iter_t**	tab;
	sd_hash_iter_t*	p;
	sd_hash_iter_t*	q;

	size	= SD_HASH_GROWTAB * a_this->size;
	tab		= (sd_hash_iter_t**)sd_calloc(size, sizeof(*tab));

	if (tab == 0) return;

	for (i = 0; i < a_this->size; i++) {
		for (p = a_this->tab[i]; p; p = q) {
			q						= p->__next;
			h						= hindex(p->__hkey,
				size);
			p->__next					= tab[h];
			tab[h]					= p;
			if (p->__next != 0) p->__next->__prev	= p;
			p->__prev					= 0;
		}
	}
	free(a_this->tab);

	a_this->tab		= tab;
	a_this->size	= size;
}

/******************************************************************************/
extern sd_hash_t* sd_hash_new(size_t a_size, const sd_hash_ops_t* a_ops)
{
	const static sd_hash_ops_t default_ops = {
		/*(void*) &sd_hash_hash_string,
		(void*) &strcmp,*/
		(unsigned int ( *)(const void *))sd_hash_hash_string,
		(int ( *)(const void *,const void *))strcmp,
		0, 0, 0, 0
	};

	sd_hash_t*		hash;
	sd_hash_iter_t**	tab;

	if (a_size == 0) a_size = SD_HASH_DEFAULT_SIZE;

	hash	= (sd_hash_t*)sd_calloc(1, sizeof(*hash));
	tab		= (sd_hash_iter_t**)sd_calloc(a_size, sizeof(*tab));

	if (hash == 0 || tab == 0) {
		free(hash);
		free(tab);
		return 0;
	}

	hash->nelem	= 0;
	hash->size	= a_size;
	hash->tab	= tab;
	hash->ops	= a_ops != 0 ? a_ops : &default_ops;

	return hash;
}

/******************************************************************************/
extern sd_hash_iter_t* sd_hash_lookup(sd_hash_t* a_this, const void* a_key)
{
	int			h;
	sd_hash_iter_t*	p;

	if (a_this == 0 || a_key == 0) return 0;

	h = hindex(a_this->ops->hash(a_key), a_this->size);
	for (p = a_this->tab[h]; p != 0; p = p->__next)
		if (a_this->ops->compare(a_key, p->key) == 0) {
			return p;
		}

		return 0;
}

/******************************************************************************/
extern sd_hash_iter_t* sd_hash_lookadd(sd_hash_t* a_this, const void* a_key)
{
	int			h;
	sd_hash_iter_t*	p;

	if (a_this == 0 || a_key == 0)			return 0;
	if ((p = sd_hash_lookup(a_this, a_key)) != 0)	return p;
	if ((p = (sd_hash_iter_t*)sd_calloc(1, sizeof(*p))) == 0)		return 0;

	if (a_this->ops->key_dup != 0)
		p->key = a_this->ops->key_dup(a_key);
	else
		p->key = (void*) a_key;

	p->hash					= a_this;
	p->__hkey					= a_this->ops->hash(a_key);

	if (a_this->nelem > SD_HASH_FULLTAB * a_this->size) rehash(a_this);

	h						= hindex(p->__hkey,
		a_this->size);
	p->__next					= a_this->tab[h];
	a_this->tab[h]				= p;
	if (p->__next != 0) p->__next->__prev	= p;

	a_this->nelem++;

	return p;
}

/******************************************************************************/
extern sd_hash_iter_t* sd_hash_add(sd_hash_t* a_this, const void* a_key, void* a_data)
{
	sd_hash_iter_t* p;

	if ((p = sd_hash_lookadd(a_this, a_key)) == 0) return 0;

	if (a_this->ops->data_free != 0) a_this->ops->data_free(p->data);

	if (a_this->ops->data_dup != 0)
		p->data = a_this->ops->data_dup(a_data);
	else
		p->data = a_data;

	return p;
}

/******************************************************************************/
extern void sd_hash_delete(sd_hash_t* a_this)
{
	sd_hash_clear(a_this);
	free(a_this->tab);
	free(a_this);
}

/******************************************************************************/
extern void sd_hash_clear(sd_hash_t* a_this)
{
	size_t		h;
	sd_hash_iter_t*	p;
	sd_hash_iter_t*	q;

	if (a_this == 0) return;

	for (h = 0; h < a_this->size; h++) {
		for (p = a_this->tab[h]; p; p = q) {
			q = p->__next;
			if (a_this->ops->key_free) a_this->ops->key_free(p->key);
			if (a_this->ops->data_free) a_this->ops->data_free(p->data);
			free(p);
		}
		a_this->tab[h] = 0;
	}
	a_this->nelem = 0;
}

/******************************************************************************/
extern void sd_hash_del(sd_hash_t* a_this, const void* a_key)
{
	int			h;
	sd_hash_iter_t*	p;

	h = hindex(a_this->ops->hash(a_key), a_this->size);
	for (p = a_this->tab[h]; p != 0; p = p->__next)
		if (a_this->ops->compare(a_key, p->key) == 0) break;
	if (p == 0) return;

	sd_hash_iter_del(p);
}

/******************************************************************************/
extern void sd_hash_foreach(sd_hash_t* a_this, sd_hash_func_t a_func, void* a_data)
{
	size_t			h, ret;
	sd_hash_iter_t*	p;
	sd_hash_iter_t*	q;

	if (a_this == 0 || a_func == 0) return;

	for (h = 0; h < a_this->size; h++)
		for (p = a_this->tab[h]; p != 0; p = q) {
			p->__foreach		= 1;
			ret			= (*a_func)(p->key, p->data, a_data);
			q			= p->__next;

			if (p->__foreach == 0)
				sd_hash_iter_del(p);
			else
				p->__foreach	= 0;

			if (ret != 0) return;
		}
}

/******************************************************************************/
extern unsigned int sd_hash_get_nelem(sd_hash_t* a_this)
{
	if (a_this == 0) return 0;
	return a_this->nelem;
}

/******************************************************************************/
extern unsigned int sd_hash_get_size(sd_hash_t* a_this)
{
	if (a_this == 0) return 0;
	return a_this->size;
}

/******************************************************************************/
extern sd_hash_iter_t* sd_hash_begin(sd_hash_t* a_this)
{
	size_t h;

	if (a_this == 0) return 0;
	for (h = 0; h < a_this->size; h++)
		if (a_this->tab[h])
			return a_this->tab[h];

	return 0;
}

/******************************************************************************/
extern sd_hash_iter_t* sd_hash_end(sd_hash_t* a_this)
{
	return 0;
}

/******************************************************************************/
extern sd_hash_iter_t* sd_hash_iter_next(sd_hash_iter_t* a_this)
{
	int h;
	size_t i;

	if (a_this == 0)		return 0;
	if (a_this->__next != 0)	return a_this->__next;

	h = hindex(a_this->__hkey, a_this->hash->size);

	for (i = h + 1; i < a_this->hash->size; i++)
		if (a_this->hash->tab[i])
			return a_this->hash->tab[i];

	return 0;
}

/******************************************************************************/
extern sd_hash_iter_t* sd_hash_iter_prev(sd_hash_iter_t* a_this)
{
	int			h, i;
	sd_hash_iter_t*	p;

	if (a_this == 0)		return 0;
	if (a_this->__prev != 0)	return a_this->__prev;

	h = hindex(a_this->__hkey, a_this->hash->size);

	for (i = h - 1; i > 0; i--)
		for (p = a_this->hash->tab[i]; p; p = p->__next)
			if (p->__next == 0)
				return p;

	return 0;
}

/******************************************************************************/
extern void sd_hash_iter_del(sd_hash_iter_t* a_this)
{
	if (a_this == 0) return;

	if (a_this->hash->ops->data_free != 0)
		a_this->hash->ops->data_free(a_this->data);
	a_this->data	= 0;

	if (a_this->hash->ops->key_free != 0)
		a_this->hash->ops->key_free(a_this->key);
	a_this->key		= 0;

	if (a_this->__foreach == 1) {
		a_this->__foreach = 0;
		return;
	}

	if (a_this->__next != 0) a_this->__next->__prev = a_this->__prev;
	if (a_this->__prev != 0)
		a_this->__prev->__next = a_this->__next;
	else
		a_this->hash->tab[hindex(a_this->__hkey, a_this->hash->size)] =
		a_this->__next;

	a_this->hash->nelem--;

	free(a_this);
}

/******************************************************************************/
extern unsigned int sd_hash_hash_string(const TCHAR* a_string)
{
	register unsigned int h;

	for (h = 0; *a_string != _T('\0'); a_string++)
		h = *a_string + 31 * h;

	return h;
}