master

分支 (1)

管理

管理

master

spider
/
hash.c

#include "hash.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

int defaultslot = 10;
int defaultstep = 10;

static void _FreeHashItem(struct HashItem *pItem)
{
	if (pItem) {
		if (pItem->v) {
			if (pItem->FreeItemValue)
				pItem->FreeItemValue(pItem->v);
			else
				free(pItem->v);
		}
		if (pItem->k)
			free(pItem->k);
		/*  释放自己本身 */
		free(pItem);
	}
	pItem->k = NULL;
	pItem->v = NULL;
}

static void _FreeHashItemKV(struct HashItem *pItem)
{
	if (pItem) {
		if (pItem->v) {
			if (pItem->FreeItemValue) {
				pItem->FreeItemValue(pItem->v);
			}
			else
				free(pItem->v);
		}
		if (pItem->k)
			free(pItem->k);
	}
	pItem->k = NULL;
	pItem->v = NULL;
}

unsigned long SDBMHash(char *str)
{
	unsigned long hash = 0;
	while(*str) {
		//hash= 65599 * hash+ ?*str++);
		hash = (*str++) + (hash << 6) + (hash << 16) - hash;
	}
	return hash;
}

unsigned long RSHash(char *str)
{
	unsigned long a = 63689;
	unsigned long b = 378551;
	unsigned long hash = 0;
	while(*str) {
		hash = hash * a + (*str++);
		a *= b;
	}
	return hash;
}

unsigned long JShash(char *str)
{
	unsigned long hash = 1315423911;
	while(*str) {
		hash ^= (hash << 5) + (*str++) + (hash >> 2);
	}
	return hash;
}

unsigned long DBJHash( char *key )
{
	unsigned long   hashval = 5381 ;

	while( *key )
	{
		hashval += (hashval<<5) + (*key++) ;
	}

	return hashval;
}

static unsigned long (*DefaultGetHashValue)(char*) = JShash;

struct Hash* CreateHash(int initslot, int step, unsigned long (*pGetHashValue)(char *str))
{
	struct Hash *hash = NULL;
	hash = (struct Hash*)malloc(sizeof(struct Hash));
	if (!hash)
		return NULL;
	hash->totalslot = (initslot >0 ? initslot : defaultslot);
	hash->step 		= (step >0 ? step : defaultstep);
	/* 创建并将所有的HashItem初始化为0 */
	hash->slots = (struct HashItem*)(calloc(hash->totalslot, sizeof(struct HashItem)));
	if (pGetHashValue)
		hash->GetHashValue = pGetHashValue;
	else
		hash->GetHashValue = DefaultGetHashValue;
	if (!hash->slots)
		return NULL;
	hash->usedslot = 0;
	return hash;
}

static void _FreeHash(struct Hash *hash)
{
	if (hash) {
		free(hash);
		hash = NULL;
	}
}
/* 删除slots下的所有hashitem结构体，里面的k,v不删除 */
static void _FreeAllHashItem(struct Hash *hash)
{
	if (hash->slots)
		free(hash->slots);
}

void DestoryHash(struct Hash *hash)
{
	unsigned int i;
	if (!hash)	return;
	for (i = 0; i < hash->totalslot; i++) {
		_FreeHashItemKV(&hash->slots[i]);
	}
	free(hash->slots);
	_FreeHash(hash);
}

static int _LargerSlot(struct Hash *hash)
{
	int ret = 0;
	int newtotalslot;
	unsigned int i;
	struct Hash newhash;

	if (!hash)
		return HASH_PARAMETER;
	memset(&newhash, 0x00, sizeof(newhash));
	newtotalslot = hash->totalslot + hash->step;
	newhash.slots = (struct HashItem*)(calloc(newtotalslot, sizeof(struct HashItem)));
	newhash.totalslot = newtotalslot;
	newhash.step = hash->step;
	newhash.needlarger = 0;
	newhash.GetHashValue = hash->GetHashValue;
	newhash.ratiopoint = hash->ratiopoint;
	for (i = 0; i < hash->totalslot; i++) {
		ret = Put(&newhash, hash->slots[i].k, hash->slots[i].v, hash->slots[i].v_len, hash->slots[i].FreeItemValue);
		if (ret)
			return HASH_INTERNAL;
	}
	_FreeAllHashItem(hash);
	memcpy(hash, &newhash, sizeof(struct Hash));
	return 0;
}

static int _FindEmptySlot(struct Hash* hash, unsigned long hashval)
{
	unsigned int i;
	int ret;

	if (!hash)
		return HASH_PARAMETER;
	for (i = 0; i < hash->totalslot; i++) {
		int index = (i + hashval) % hash->totalslot;
		if (hash->slots[index].k == NULL)
			return index;
	}

	return HASH_NOTFOUND;
}

/****
  1. pFreeValue如果直接能使用free释放v可以传入NULL或者free
 ****/
int Put(struct Hash* hash, char *k, void *v, unsigned long v_len, void (*pFreeValue)(void *))
{
	int ret = 0;
	int slotindex;
	unsigned long hashval = 0;

	if (!hash || !k)
		return HASH_PARAMETER;

	/* 如果已经放不下了, 或者放入之后导致比率过高 */
	if (hash->usedslot >= hash->totalslot) {
		//|| (hash->usedslot + 1) * 1.0 / hash->totalslot >= hash->ratiopoint ) {
		ret = _LargerSlot(hash);
		if (ret)
			return ret;
	}

	hashval = hash->GetHashValue(k);
	slotindex = _FindEmptySlot(hash, hashval);
	if (slotindex < 0)
		return slotindex;
	else {
		struct HashItem *pItem = &hash->slots[slotindex];
		pItem->k = strdup(k);
		pItem->v = v;
		pItem->v_len = v_len;
		pItem->FreeItemValue = pFreeValue;
		hash->usedslot++;
	}
	return 0;
}

int Get(struct Hash* hash, char *k, void **v, unsigned long *v_len)
{
	unsigned int i, index;
	unsigned long hashval;

	if (!hash || !k)
		return HASH_PARAMETER;

	hashval = hash->GetHashValue(k);

	for (i = 0; i < hash->totalslot; i++) {
		index = (i + hashval) % hash->totalslot;
		if (hash->slots[index].k != NULL && strcmp(hash->slots[index].k, k) == 0)
			break;
	}
	if (i == hash->totalslot)
		return HASH_NOTFOUND;
	else {
		*v = hash->slots[index].v;
		*v_len = hash->slots[index].v_len;
		return 0;
	}
}

int Contain(struct Hash* hash, char *k)
{
	unsigned int i;
	unsigned long hashval;

	if (!hash || !k)
		return HASH_PARAMETER;

	hashval = hash->GetHashValue(k);
//printf("index %d ", hashval % hash->totalslot);
	for (i = 0; i < hash->totalslot; i++) {
		int index = (i + hashval) % hash->totalslot;
		if (hash->slots[index].k != NULL && strcmp(hash->slots[index].k, k) == 0) {
//printf("hashval %ul key = %s times = %d\n", hashval, k, i);
			break;
		}
	}
	if (i >= hash->totalslot)
		return HASH_NOTFOUND;
	return 0;
}

int Delete(struct Hash *hash, char *k)
{
	unsigned int i, index;
	int ret;
	unsigned long hashval;

	if (!hash || !k)
		return HASH_PARAMETER;

	hashval = hash->GetHashValue(k);
	for (i = 0; i < hash->totalslot; i++) {
		index = (i + hashval) % hash->totalslot;
		if (hash->slots[index].k != NULL && strcmp(hash->slots[index].k, k) == 0){
			_FreeHashItemKV(&hash->slots[index]);
			hash->usedslot--;
			return 0;
		}
	}
	if (i >= hash->totalslot)
		return HASH_NOTFOUND;
}

/*****
  @return	1.如果传入的key原来没有出现，直接返回HASH_NOTFOUND	2.更新成功返回0

  @input	1. pFreeValue == NULL, 使用free
 ****/
int Set(struct Hash* hash, char *k, void *v, unsigned long v_len, void (*pFreeValue)(void *))
{
	unsigned int i, index = 0;
	int slotindex;
	int ret = 0;
	unsigned long hashval = 0;

	if (!hash || !k)
		return HASH_PARAMETER;

	hashval = hash->GetHashValue(k);
	for (i = 0; i < hash->totalslot; i++) {
		index = (i + hashval) % hash->totalslot;
		if (hash->slots[index].k != NULL && strcmp(hash->slots[index].k, k) == 0)
			break;
	}
	if (i >= hash->totalslot)
		return HASH_NOTFOUND;
	else {
		struct HashItem *pItem = &hash->slots[index];
		/* 释放原来的v */
		if (pItem->FreeItemValue)
			pItem->FreeItemValue(pItem->v);
		else
			free(pItem->v);
		/* 更新 */
		pItem->v = v;
		pItem->v_len = v_len;
		pItem->FreeItemValue = pFreeValue;
	}
	return 0;
}

struct BHash* CreateBHash(int initbucket, unsigned long (*pGetHashValue)(char *))
{
	struct BHash *bhash = NULL;
	unsigned int i;

	if (initbucket <= 0) {
		initbucket = INITBUCKET;
	}

	bhash = (struct BHash*)malloc(sizeof(struct BHash));
	if (bhash == NULL)
		return NULL;

	bhash->slots = (struct HashItemList**)malloc(initbucket * sizeof(PTRLEN));
	memset(bhash->slots, 0x00, initbucket * sizeof(PTRLEN));

	bhash->bucketnum = initbucket;
	bhash->totalnum = 0;
	if (pGetHashValue == NULL)
		bhash->GetHashValue = DefaultGetHashValue;
	else
		bhash->GetHashValue = pGetHashValue;
	bhash->allowMuti = HASH_NOTALLOWMUTI;

	return bhash;

}
void SetAllowMuti(struct BHash *bhash, int flag)
{
	if (bhash == NULL)
		return;

	bhash->allowMuti = flag;
}
static int _BInsert(struct BHash *bhash, char *k, char *v, unsigned long v_len, void (*FreeValue)(void*))
{
	int ret = 0;
	int putslotindex;
	unsigned long hashval;
	struct HashItemList *pItem = NULL;
	struct HashItemList *pCur = NULL;
	struct HashItemList *pPrev = NULL;

	if (bhash == NULL || k == NULL )
		return HASH_PARAMETER;

	hashval = bhash->GetHashValue(k);
	putslotindex = hashval % bhash->bucketnum;

	pItem = (struct HashItemList*)malloc(sizeof(struct HashItemList));
	if (pItem == NULL)
		return HASH_MEMERR;

	memset(pItem, 0x00, sizeof(struct HashItemList));
	pItem->item.v_len = v_len;
	pItem->item.k = strdup(k);
	pItem->item.v = v;
	pItem->item.FreeItemValue = FreeValue;

	pPrev = bhash->slots[putslotindex];
	if (pPrev == NULL) {
		bhash->slots[putslotindex] = pItem;
		bhash->totalnum++;
		return 0;
	}

	pCur = bhash->slots[putslotindex];
	while(pCur) {
		if (bhash->allowMuti == HASH_NOTALLOWMUTI && pCur->item.k != NULL && strcmp(pCur->item.k, k) == 0) {
			free(pItem);
			return HASH_EXISITED;
		}
		if (pCur->item.k != NULL && strcmp(pCur->item.k, k) <= 0) {
			break;
		}
		pPrev = pCur;
		pCur = pCur->next;
	}
	pItem->next = pPrev->next;
	pPrev->next = pItem;
	bhash->totalnum++;

	return 0;
}

static void _FreeHashItemList(struct HashItemList *l)
{
	if (l) {
		/* 删除item中的kv */
		_FreeHashItemKV(&l->item);
		free(l);
		l = NULL;
	}
}

/**
FIXME:	当插入多个key值一样的键值对，会把所有的都删除
**/
int BDelete(struct BHash *bhash,  char *k)
{
	int ret = 0;
	int slotindex;
	unsigned long hashval;
	struct HashItemList *pCur = NULL;
	struct HashItemList *pPrev = NULL;

	if (bhash == NULL || k == NULL)
		return HASH_PARAMETER;

	hashval = bhash->GetHashValue(k);
	slotindex = hashval % bhash->bucketnum;

	pPrev = NULL;
	pCur = bhash->slots[slotindex];
	while (pCur) {
		/* 找到 */
		if (pCur->item.k != NULL && strcmp(pCur->item.k, k) == 0) {
			if (pPrev)
				pPrev->next = pCur->next;
			else
				bhash->slots[slotindex] = pCur->next;
			_FreeHashItemList(pCur);
			if (pPrev)
				pCur = pPrev->next;
			else
				pCur = bhash->slots[slotindex];

		}
		/* 未找到 */
		else  {
			pPrev = pCur;
			pCur = pCur->next;
		}
	}
	bhash->totalnum--;

	return 0;
}

void DestoryBHash(struct BHash *bhash)
{
	int ret = 0;
	unsigned int slotindex = 0;

	if (bhash == NULL)
		return;

	for (slotindex = 0; slotindex < bhash->bucketnum; slotindex++) {
		struct HashItemList *pList = bhash->slots[slotindex];
		while(pList) {
			struct HashItemList *pTemp = pList->next;
			_FreeHashItemList(pList);
			pList = pTemp;
		}
	}
	/* 释放桶 */
	free(bhash->slots);
	/* 释放自己 */
	free(bhash);
}

int BPut(struct BHash *bhash, char *k, void *v, unsigned long v_len, void (*pFreeItemValue)(void*))
{
	int ret = 0;
	unsigned long hashval;

	if (bhash == NULL || k == NULL)
		return HASH_PARAMETER;

	ret = _BInsert(bhash, k, v, v_len, pFreeItemValue);
	if (ret)
		return ret;
}

int BGet(struct BHash *bhash, char *k, void **v, unsigned long *v_len)
{
	unsigned long hashval;
	unsigned int slotindex;
	struct HashItemList *pList;

	if (bhash == NULL || k == NULL || v == NULL || v_len == NULL)
		return HASH_PARAMETER;

	hashval = bhash->GetHashValue(k);
	slotindex = hashval % bhash->bucketnum;

	pList = bhash->slots[slotindex];
	while(pList) {
		if (pList->item.k != NULL && strcmp(pList->item.k, k) == 0) {
			*v = pList->item.v;
			*v_len = pList->item.v_len;
			return 0;
		}
		pList = pList->next;
	}

	return HASH_NOTFOUND;
}

int BSet(struct BHash *bhash , char *k, void *v, unsigned long v_len, void (*FreeValue)(void *))
{
	struct HashItemList *pItem = NULL;
	struct HashItemList *pCur = NULL;
	unsigned long hashval;
	unsigned int slotindex;

	if (bhash ==  NULL || k == NULL)
		return HASH_PARAMETER;

	pItem = (struct HashItemList*)malloc(sizeof(struct HashItemList));
	if (pItem == NULL)
		return HASH_MEMERR;

	hashval = bhash->GetHashValue(k);
	slotindex = hashval % bhash->bucketnum;

	pCur = 	bhash->slots[slotindex];
	while (pCur) {
		if (pCur->item.k != NULL && strcmp(pCur->item.k, k) == 0) {
			if (pCur->item.FreeItemValue) {
				pCur->item.FreeItemValue(pCur->item.v);
			}
			pCur->item.v = v;
			pCur->item.v_len = v_len;
			pCur->item.FreeItemValue = FreeValue;
			return 0;
		}
		pCur = pCur->next;
	}

	return 0;
}
int BContain(struct BHash *hash, char *k)
{
	unsigned int slotindex;
	unsigned long hashval;
	struct HashItemList *pCur = NULL;

	if (hash == NULL || k == NULL)
		return HASH_PARAMETER;

	hashval = hash->GetHashValue(k);
	slotindex = hashval % hash->bucketnum;

	while (pCur) {
		if (pCur->item.k != NULL && strcmp(pCur->item.k, k) == 0) {
			return 0;
		}
		pCur = pCur->next;
	}

	return HASH_NOTFOUND;
}

int BHashDetail(struct BHash *hash)
{
	int ret = 0;
	//printf("bucketnum[%u] totalslot[%u]\n", hash->bucketnum, hash->totalnum);
	unsigned int i;
	for (i = 0; i < hash->bucketnum; i++) {
		printf("slot [%u]:", i);
		struct HashItemList *pList = hash->slots[i];
		while (pList) {
			//printf("[%s-%s],", pList->item.k, pList->item.v);
			pList = pList->next;
		}
		//printf("\n");
	}
	//printf("\n\n");
	return 0;
}

/*****
int HashStat(struct Hash *hash)
{
	printf("total=%d, used=%d, step=%d\n", hash->totalslot, hash->usedslot, hash->step);
	return 0;
}

int HashDetail(struct Hash* hash)
{
	int i = 0;
	for (i = 0; i < hash->totalslot; i++)
	{
		printf("%s %s\n", hash->slots[i].k, hash->slots[i].v);
	}
	return 0;
}
****/