782 lines
22 KiB
C
782 lines
22 KiB
C
/**************************************************
|
||
* 程序名称 : XipHashMap.c
|
||
* 程序作者 : icesky
|
||
* 程序版本 : 1.0.0
|
||
* 创建日期 : 2016.07.28
|
||
* 程序功能 :
|
||
* 参考java的hashmap实现机制,实现了C基本的
|
||
* hashmap实现，支持几种功能:
|
||
* 1.新建
|
||
* 2.销毁
|
||
* 3.加入/设置
|
||
* 4.获取
|
||
* 5.删除
|
||
* 6.判断是否存在
|
||
* 7.打印
|
||
* 注意事项:
|
||
*
|
||
* 修改记录 :
|
||
*************************************************/
|
||
#include <stdlib.h>
|
||
#include <stdio.h>
|
||
#include <string.h>
|
||
#include <stdarg.h>
|
||
#include "xiphashmap.h"
|
||
|
||
#define hmap_malloc(size) malloc(size)
|
||
#define HMAPFREE(x) free(x);x=NULL;
|
||
|
||
#define MAXIMUM_CAPACITY 1 << 30 /*1 073 741 824 */
|
||
#define DEFAULT_CAPACITY 1 << 4 /*16*/
|
||
#define DEFAULT_FACTOR 0.75f
|
||
#define INTER_MAX_VALUE 1<<31 /*int的最大值*/
|
||
#define MALLOC_FLAG_NO 1 /*不分配内存*/
|
||
|
||
|
||
/*hashmap node结构 */
|
||
typedef struct st_xip_hashmap_node
|
||
{
|
||
char * key;
|
||
struct
|
||
{
|
||
void *ptr; /*注意ptr本身,只是指针*/
|
||
int size; /*内存大小*/
|
||
}value;
|
||
struct st_xip_hashmap_node *next;
|
||
unsigned int hash;
|
||
} TxipHashmapNode;
|
||
|
||
/*hashmap 结构*/
|
||
typedef struct
|
||
{
|
||
TxipHashmapNode ** table; /*T表*/
|
||
unsigned int length; /*桶大小*/
|
||
unsigned int size; /*实际个数*/
|
||
unsigned int threshold; /*加载临界值*/
|
||
int malloc_flag; /*是否为value分配内存*/
|
||
float factor; /*加载因子,默认为0.75(0-1)*/
|
||
} TxipHashmap;
|
||
|
||
|
||
#define HMAPLOG(...) AppLog(__FILE__,__LINE__,__VA_ARGS__)
|
||
static void AppLog(char *file, long line, char *level, char *fmtstr, ...)
|
||
{
|
||
va_list ap;
|
||
char tmpstr[501];
|
||
|
||
memset(tmpstr, 0x0, sizeof(tmpstr));
|
||
|
||
va_start(ap, fmtstr);
|
||
|
||
vsprintf(tmpstr, fmtstr, ap);
|
||
va_end(ap);
|
||
|
||
printf("[%s][%s][%03ld]", level, file, line);
|
||
printf("[%s]\n", tmpstr);
|
||
|
||
return ;
|
||
}
|
||
|
||
/*** static 声明 ***/
|
||
/*新建T表*/
|
||
static TxipHashmapNode ** create_T_table( int opacity);
|
||
/*新建hashmap节点*/
|
||
static TxipHashmapNode * create_hashmap_node( char * key, void * value, TxipHashmapNode * next, int malloc_flag, int size);
|
||
/*重建hashmap*/
|
||
static int rebuild_hash( TxipHashmap * hashmap);
|
||
/*hash算法*/
|
||
static unsigned int XipHash(char * key);
|
||
|
||
/********************************************************************
|
||
* 函数名称: XipHashmapPrint
|
||
* 函数功能: 打印hashmap中所有的元素,主要用于调试和检查散列分布
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 外部调用函数，参见xiphashmap.h中描述
|
||
*********************************************************************/
|
||
int XipHashmapPrint( void * hashmap, void (*ref_func)(int,char *, void *))
|
||
{
|
||
TxipHashmap * map = ( TxipHashmap *)hashmap;
|
||
|
||
int idx = 0;
|
||
|
||
TxipHashmapNode * e = NULL;
|
||
TxipHashmapNode * next = NULL;
|
||
|
||
/** 打印日志 **/
|
||
if( map != NULL)
|
||
{
|
||
HMAPLOG("I", "HashMap:length(%d),size(%d),threshold(%d),malloc_flag(%d)",
|
||
map->length, map->size, map->threshold, map->malloc_flag);
|
||
for ( idx = 0; idx < map->length; idx++)
|
||
{
|
||
for( e = map->table[idx]; e != NULL; )
|
||
{
|
||
next = e->next;
|
||
if( ref_func == NULL)
|
||
{
|
||
HMAPLOG("I", "Node[%d]:hash[%d],key[%s],value[%d][%x][%s]",
|
||
idx, e->hash, e->key, e->value.size, e->value.ptr, (char *)e->value.ptr);
|
||
}
|
||
else
|
||
{
|
||
ref_func(idx, e->key, e->value.ptr);
|
||
}
|
||
e = next;
|
||
}
|
||
}
|
||
}
|
||
|
||
/** 打印分布情况图 **/
|
||
int i = 0;
|
||
if( map != NULL)
|
||
{
|
||
for( idx = 0; idx < map->length; idx++)
|
||
{
|
||
i = 0;
|
||
for( e= map->table[idx] ; e!= NULL; )
|
||
{
|
||
next = e->next;
|
||
i++;
|
||
e = next;
|
||
}
|
||
HMAPLOG("I","%08ld:%*d", idx, i, i);
|
||
}
|
||
}
|
||
|
||
return 0;
|
||
}
|
||
/********************************************************************
|
||
* 函数名称: XipHashmapGetNum
|
||
* 函数功能: 输出hashmap中的key:value对的个数
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.08.04
|
||
* 调用说明: 外部调用函数，参见xiphashmap.h中描述
|
||
*********************************************************************/
|
||
int XipHashmapNum( void * hashmap)
|
||
{
|
||
TxipHashmap * map = ( TxipHashmap *)hashmap;
|
||
if( map == NULL)
|
||
return 0;
|
||
|
||
return map->size;
|
||
}
|
||
|
||
|
||
/********************************************************************
|
||
* 函数名称: XipHashmapGetSize
|
||
* 函数功能: 打印hashmap中所有的元素,主要用于调试和检查散列分布
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 外部调用函数，参见xiphashmap.h中描述
|
||
*********************************************************************/
|
||
int XipHashmapSize( void * hashmap, int * mapsize, int * tablesize, int * nodesize, int * keysize, int * valuesize)
|
||
{
|
||
TxipHashmap * map = ( TxipHashmap *)hashmap;
|
||
if( map == NULL)
|
||
return 0;
|
||
|
||
int total_size = 0; /*总内存大小*/
|
||
int map_size = 0; /*map结构体大小*/
|
||
int table_size = 0; /*散列表大小*/
|
||
int node_size = 0; /*总节点大小*/
|
||
int key_size = 0; /*总key大小--当不分配内存为0*/
|
||
int value_size = 0; /*总值大小--当不分配内存为0*/
|
||
|
||
int idx = 0;
|
||
|
||
map_size = sizeof(TxipHashmap);
|
||
table_size = sizeof(TxipHashmapNode*) * map->length;
|
||
|
||
TxipHashmapNode * e = NULL;
|
||
TxipHashmapNode * next = NULL;
|
||
if( map != NULL)
|
||
{
|
||
for( idx = 0; idx < map->length; idx++)
|
||
{
|
||
for( e= map->table[idx] ; e!= NULL; )
|
||
{
|
||
next = e->next;
|
||
/*计算大小*/
|
||
node_size += sizeof(TxipHashmapNode);
|
||
if ( map->malloc_flag == MALLOC_FLAG_NO) /*不分配内存*/
|
||
{
|
||
;
|
||
}
|
||
else
|
||
{
|
||
key_size += strlen(e->key)+1;
|
||
value_size += e->value.size;
|
||
}
|
||
|
||
e = next;
|
||
}
|
||
}
|
||
}
|
||
|
||
total_size = map_size + table_size + node_size + key_size + value_size;
|
||
|
||
HMAPLOG("D","total_size[%d] = map_size[%d]+table_size[%d]+node_size[%d]+key_size[%d]+value_size[%d]",
|
||
total_size, map_size, table_size, node_size, key_size, value_size);
|
||
|
||
if( mapsize != NULL)
|
||
*mapsize = map_size;
|
||
if( tablesize != NULL)
|
||
*tablesize = table_size;
|
||
if( nodesize != NULL)
|
||
*nodesize = node_size;
|
||
if( keysize != NULL)
|
||
*keysize = key_size;
|
||
if( valuesize != NULL)
|
||
*valuesize = value_size;
|
||
|
||
|
||
return total_size;
|
||
}
|
||
/********************************************************************
|
||
* 函数名称: XipHashmapNew
|
||
* 函数功能: 以所有的默认参数，创建一个hashmap
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 外部调用函数，参见xiphashmap.h中描述
|
||
*********************************************************************/
|
||
void * XipHashmapNew()
|
||
{
|
||
return XipHashmapInit( 0, 0.00, 0); /*全默认选项*/
|
||
}
|
||
|
||
/********************************************************************
|
||
* 函数名称: XipHashmapInit
|
||
* 函数功能: 指定初始容量，加载因子和value存储方式，创建一个hashmap
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 外部调用函数，参见xiphashmap.h中描述
|
||
*********************************************************************/
|
||
void * XipHashmapInit( int opacity, float factor, int malloc_flag)
|
||
{
|
||
TxipHashmap * map = ( TxipHashmap *)hmap_malloc(sizeof( TxipHashmap));
|
||
if( map == NULL)
|
||
{
|
||
HMAPLOG("E","初始化hashmap内存失败!!!");
|
||
return NULL;
|
||
}
|
||
memset( map, 0x00, sizeof(TxipHashmap));
|
||
|
||
if ( opacity < DEFAULT_CAPACITY )
|
||
opacity = DEFAULT_CAPACITY;
|
||
if( opacity > MAXIMUM_CAPACITY)
|
||
opacity = MAXIMUM_CAPACITY;
|
||
if ( factor >= -0.005 && factor <=0.005 )
|
||
factor = DEFAULT_FACTOR;
|
||
|
||
if( opacity <= 1)
|
||
{
|
||
HMAPLOG("E","初始容量必须大于1!!!");
|
||
HMAPFREE(map);
|
||
map = NULL;
|
||
return NULL;
|
||
}
|
||
if( factor < 0.00 || factor > 1.00)
|
||
{
|
||
HMAPLOG("E","加载因子取值区间为[0.00-1.00],但本次加载因子为[%.2f]", factor);
|
||
HMAPFREE(map);
|
||
map = NULL;
|
||
return NULL;
|
||
}
|
||
|
||
map->table = create_T_table( opacity);
|
||
if( map->table == NULL)
|
||
{
|
||
HMAPLOG("E","创建hash值的T表失败!!!");
|
||
HMAPFREE(map->table);
|
||
map->table = NULL;
|
||
HMAPFREE(map);
|
||
map = NULL;
|
||
return NULL;
|
||
}
|
||
|
||
map->length = opacity;
|
||
map->size = 0;
|
||
map->factor = factor;
|
||
map->threshold = (unsigned int)( factor * opacity);
|
||
map->malloc_flag = malloc_flag;
|
||
|
||
return (void *)map;
|
||
}
|
||
|
||
/********************************************************************
|
||
* 函数名称: XipHashmapDestory
|
||
* 函数功能: 释放hashmap的内存资源
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 外部调用函数，参见xiphashmap.h中描述
|
||
*********************************************************************/
|
||
int XipHashmapDestory( void * hashmap)
|
||
{
|
||
TxipHashmap * map = (TxipHashmap *) hashmap;
|
||
|
||
TxipHashmapNode * e = NULL;
|
||
TxipHashmapNode * next = NULL;
|
||
register unsigned int idx;
|
||
|
||
/** 释放hashmap node 内存 **/
|
||
if( map != NULL)
|
||
{
|
||
/** 释放hashmap的node空间 **/
|
||
for ( idx = 0; idx < map->length; idx++)
|
||
{
|
||
for( e = map->table[idx]; e != NULL; )
|
||
{
|
||
next = e->next;
|
||
/* 释放node空间*/
|
||
if( map->malloc_flag == MALLOC_FLAG_NO)
|
||
{
|
||
;
|
||
}
|
||
else
|
||
{
|
||
/*释放node的key和value空间*/
|
||
HMAPFREE(e->key);
|
||
e->key = NULL;
|
||
HMAPFREE(e->value.ptr);
|
||
e->value.ptr = NULL;
|
||
}
|
||
/*释放node本身*/
|
||
HMAPFREE(e);
|
||
e=NULL;
|
||
e = next;
|
||
}
|
||
|
||
}
|
||
|
||
/** 释放hashmap的T表 **/
|
||
HMAPFREE( map->table);
|
||
map->table = NULL;
|
||
|
||
/** 释放hashmap本身的空间 **/
|
||
HMAPFREE( map);
|
||
map = NULL;
|
||
}
|
||
|
||
|
||
return 0;
|
||
}
|
||
|
||
/********************************************************************
|
||
* 函数名称: XipHashmapPut
|
||
* 函数功能: 将key和value放入hashmap中，如果key已存在，相当于Set命令
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 外部调用函数，参见xiphashmap.h中描述
|
||
*********************************************************************/
|
||
void * XipHashmapPut( void * hashmap, char * key, void * value, int size)
|
||
{
|
||
TxipHashmap * map = (TxipHashmap *)hashmap;
|
||
|
||
if( map == NULL)
|
||
{
|
||
HMAPLOG("E","hashmap指针为空,请检查是否已经调用XipHashmapNew/XipHashmapInit,或调用返回异常");
|
||
return NULL;
|
||
}
|
||
|
||
if ( key == NULL || strlen(key) == 0)
|
||
{
|
||
HMAPLOG("E","Key值必须为字符串,且Key值不能为空或者NULL!!!");
|
||
return NULL;
|
||
}
|
||
if ( value == NULL)
|
||
{
|
||
HMAPLOG("E","value不可以为空(NULL)");
|
||
return NULL;
|
||
}
|
||
if ( size <= 0)
|
||
{
|
||
HMAPLOG("E","值的大小size不可以为0");
|
||
return NULL;
|
||
}
|
||
|
||
TxipHashmapNode *e = NULL;
|
||
unsigned int hcode = XipHash(key);
|
||
unsigned int idx = hcode % map->length;
|
||
|
||
/*如果找到了key,则相当于set*/
|
||
for ( e = map->table[idx]; e != NULL ; e = e->next)
|
||
{
|
||
/*参考java的hashmap实现,先比较hash,再比较strcmp*/
|
||
if ( hcode == e->hash && (key == e->key || strcmp( key, e->key) == 0))
|
||
{
|
||
if( map->malloc_flag == MALLOC_FLAG_NO) /*不分配内存*/
|
||
{
|
||
e->value.ptr = value;
|
||
e->value.size = 0;
|
||
}
|
||
else
|
||
{
|
||
HMAPFREE(e->value.ptr);
|
||
e->value.size = size;
|
||
e->value.ptr = NULL;
|
||
e->value.ptr = hmap_malloc(size);
|
||
if( e->value.ptr == NULL)
|
||
{
|
||
HMAPLOG("E","为value分配内存时异常!!!");
|
||
return NULL;
|
||
}
|
||
memset( e->value.ptr, 0x00, size);
|
||
memcpy( e->value.ptr, value, size);
|
||
return e->value.ptr;
|
||
}
|
||
return e->value.ptr; /*将原value返回给调用者*/
|
||
}
|
||
}
|
||
|
||
/*新建node*/
|
||
map->table[idx] = create_hashmap_node( key, value, map->table[idx], map->malloc_flag, size);
|
||
if( map->table[idx] == NULL)
|
||
{
|
||
HMAPLOG("E","新建hashnode节点异常malloc_flag[%d],size[%d]!!!", map->malloc_flag, size);
|
||
return NULL; /*返回固定值*/
|
||
}
|
||
|
||
/*修改hashmap*/
|
||
e = map->table[idx];
|
||
e->hash = hcode;
|
||
map->size++;
|
||
|
||
/*如果触发临界值，则重建hash表*/
|
||
if( map->size > map->threshold)
|
||
{
|
||
/*
|
||
HMAPLOG("D","达到临界值[%d] > [%d]", map->size, map->threshold);
|
||
*/
|
||
if( rebuild_hash(map) != 0)
|
||
{
|
||
HMAPLOG("E","重建hash表错误!!!");
|
||
if( map->malloc_flag == MALLOC_FLAG_NO)
|
||
{
|
||
;
|
||
}
|
||
else
|
||
{
|
||
HMAPFREE(map->table[idx]->key);
|
||
map->table[idx]->key = NULL;
|
||
HMAPFREE(map->table[idx]->value.ptr);
|
||
map->table[idx]->value.ptr = NULL;
|
||
}
|
||
HMAPFREE(map->table[idx]);
|
||
map->table[idx] = NULL;
|
||
|
||
return NULL; /*返回固定值*/
|
||
}
|
||
}
|
||
|
||
return map->table[idx]->value.ptr; /*返回内存地址*/
|
||
}
|
||
|
||
/********************************************************************
|
||
* 函数名称: XipHashmapGet
|
||
* 函数功能: 根据Key值获取对应的value值
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 外部调用函数，参见xiphashmap.h中描述
|
||
*********************************************************************/
|
||
void * XipHashmapGet( void * hashmap, char *key)
|
||
{
|
||
TxipHashmap * map = (TxipHashmap *) hashmap;
|
||
if( map == NULL)
|
||
{
|
||
HMAPLOG("E","hashmap指针为空,请检查是否已经调用XipHashmapNew/XipHashmapInit,或调用返回异常");
|
||
return NULL;
|
||
}
|
||
|
||
if ( key == NULL || strlen(key) == 0)
|
||
{
|
||
HMAPLOG("E","Key值必须为字符串,且Key值不能为空或者NULL!!!");
|
||
return NULL;
|
||
}
|
||
|
||
unsigned int hcode = XipHash(key);
|
||
unsigned int idx = hcode % map->length;
|
||
|
||
TxipHashmapNode * e = NULL;
|
||
|
||
for ( e = map->table[idx]; e != NULL ; e = e->next)
|
||
{
|
||
/*参考java的hashmap实现,先比较hash,再比较strcmp, key == e->key是用来给ihashmap用的,待扩展*/
|
||
if ( hcode == e->hash && (key == e->key || strcmp( key, e->key) == 0))
|
||
{
|
||
return e->value.ptr;
|
||
}
|
||
}
|
||
return NULL;
|
||
}
|
||
|
||
/********************************************************************
|
||
* 函数名称: XipHashmapExists
|
||
* 函数功能: 判断Key是否在hashmap中存在
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 外部调用函数，参见xiphashmap.h中描述
|
||
*********************************************************************/
|
||
int XipHashmapExists( void * hashmap, char *key)
|
||
{
|
||
TxipHashmap * map = (TxipHashmap *) hashmap;
|
||
if( map == NULL)
|
||
{
|
||
HMAPLOG("E","hashmap指针为空,请检查是否已经调用XipHashmapNew/XipHashmapInit,或调用返回异常");
|
||
return -5;
|
||
}
|
||
if ( key == NULL || strlen(key) == 0)
|
||
{
|
||
HMAPLOG("E","Key值必须为字符串,且Key值不能为空或者NULL!!!");
|
||
return -10;
|
||
}
|
||
|
||
unsigned int hcode = XipHash(key);
|
||
unsigned int idx = hcode % map->length;
|
||
|
||
TxipHashmapNode * e = NULL;
|
||
|
||
for ( e = map->table[idx]; e != NULL ; e = e->next)
|
||
{
|
||
/*参考java的hashmap实现,先比较hash,再比较strcmp*/
|
||
if ( hcode == e->hash && (key == e->key || strcmp( key, e->key) == 0))
|
||
{
|
||
return 1;
|
||
}
|
||
}
|
||
|
||
return 0;
|
||
}
|
||
|
||
/********************************************************************
|
||
* 函数名称: XipHashmapRemove
|
||
* 函数功能: 删除map中对应的Key和VALUE的节点
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 外部调用函数，参见xiphashmap.h中描述
|
||
*********************************************************************/
|
||
int XipHashmapRemove( void * hashmap, char *key)
|
||
{
|
||
TxipHashmap * map = (TxipHashmap *) hashmap;
|
||
if( map == NULL)
|
||
{
|
||
HMAPLOG("E","hashmap指针为空,请检查是否已经调用XipHashmapNew/XipHashmapInit,或调用返回异常");
|
||
return -5;
|
||
}
|
||
if ( key == NULL || strlen(key) == 0)
|
||
{
|
||
HMAPLOG("E","Key值必须为字符串,且Key值不能为空或者NULL!!!");
|
||
return -10;
|
||
}
|
||
|
||
unsigned int hcode = XipHash(key);
|
||
unsigned int idx = hcode % map->length;
|
||
|
||
TxipHashmapNode * e = NULL;
|
||
TxipHashmapNode * prev = NULL;
|
||
|
||
for ( e = map->table[idx]; e != NULL ; prev = e, e = e->next)
|
||
{
|
||
/*参考java的hashmap实现,先比较hash,再比较strcmp*/
|
||
if ( hcode == e->hash && (key == e->key || strcmp( key, e->key) == 0))
|
||
{
|
||
if( prev == NULL)
|
||
map->table[idx] = e->next;
|
||
else
|
||
prev->next = e->next;
|
||
|
||
if( map->malloc_flag == MALLOC_FLAG_NO) /*不分配内存*/
|
||
{
|
||
;
|
||
}
|
||
else
|
||
{
|
||
HMAPFREE(e->key);
|
||
e->key = NULL;
|
||
HMAPFREE(e->value.ptr);
|
||
e->value.ptr = NULL;
|
||
}
|
||
|
||
HMAPFREE(e);
|
||
map->size--;
|
||
return 0;
|
||
}
|
||
}
|
||
|
||
return 0;
|
||
}
|
||
|
||
/********************************************************************
|
||
* 函数名称: create_T_table
|
||
* 函数功能: 申请指向node的连续内存指针，在《算法导论》关于散列表中，所处位置为T表
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 内部调用函数.注意返回值是指向TxipHashmapNode的指针的指针
|
||
*********************************************************************/
|
||
static TxipHashmapNode ** create_T_table( int opacity)
|
||
{
|
||
register unsigned int i=0;
|
||
|
||
TxipHashmapNode ** table = (TxipHashmapNode **)hmap_malloc( sizeof(TxipHashmapNode*) *opacity);
|
||
if( table == NULL)
|
||
{
|
||
return NULL;
|
||
}
|
||
memset( table, 0x00, sizeof(TxipHashmapNode*) * opacity);
|
||
|
||
/*初始化*/
|
||
for ( i = 0; i < opacity; i++)
|
||
table[i] = NULL;
|
||
|
||
return table;
|
||
}
|
||
|
||
/********************************************************************
|
||
* 函数名称: create_hashmap_node
|
||
* 函数功能: 创建具体的key,value的node节点
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 内部调用函数. 如果malloc_flag是1的话，则size无效，因为不需要
|
||
为value申请内存。
|
||
*********************************************************************/
|
||
static TxipHashmapNode * create_hashmap_node( char * key, void * value, TxipHashmapNode * next, int malloc_flag, int size)
|
||
{
|
||
TxipHashmapNode * node = ( TxipHashmapNode *) hmap_malloc( sizeof(TxipHashmapNode));
|
||
if ( node == NULL)
|
||
{
|
||
return NULL;
|
||
}
|
||
memset( node, 0x00, sizeof( TxipHashmapNode));
|
||
|
||
if( malloc_flag == MALLOC_FLAG_NO) /*不分配内存*/
|
||
{
|
||
node->key = key;
|
||
node->value.ptr = value;
|
||
}
|
||
else
|
||
{
|
||
/*限定KEY必须是字符串类型*/
|
||
node->key = hmap_malloc(strlen(key)+1);
|
||
if( node->key == NULL)
|
||
{
|
||
HMAPFREE(node);
|
||
node = NULL;
|
||
return NULL;
|
||
}
|
||
memset(node->key, 0x00, strlen(key)+1);
|
||
memcpy( node->key, key, strlen(key)+1);
|
||
|
||
node->value.size = size;
|
||
node->value.ptr = hmap_malloc(size);
|
||
if( node->value.ptr == NULL)
|
||
{
|
||
/*防止异常时内存泄漏*/
|
||
HMAPFREE(node);
|
||
node = NULL;
|
||
HMAPFREE(node->key);
|
||
node->key = NULL;
|
||
return NULL;
|
||
}
|
||
memset(node->value.ptr, 0x00, size);
|
||
memcpy( node->value.ptr, value, size);
|
||
}
|
||
node->next = next;
|
||
|
||
return node;
|
||
}
|
||
|
||
/********************************************************************
|
||
* 函数名称: rebuild_hash
|
||
* 函数功能: 当前hashmap中的size达到了临界值的时候，需要重新创建更大的hashmap
|
||
来进行存储。
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 内部调用函数. 注意重建失败了要判断返回值
|
||
*********************************************************************/
|
||
static int rebuild_hash( TxipHashmap * map)
|
||
{
|
||
register unsigned int i = 0;
|
||
unsigned int idx = 0;
|
||
|
||
/*如果达到最大了,则不在rebuild*/
|
||
if( map->length == MAXIMUM_CAPACITY)
|
||
{
|
||
map->threshold = INTER_MAX_VALUE;
|
||
return 0;
|
||
}
|
||
|
||
unsigned int length = map->length*2;
|
||
if( length > MAXIMUM_CAPACITY)
|
||
length = MAXIMUM_CAPACITY;
|
||
|
||
TxipHashmapNode *e=NULL;
|
||
TxipHashmapNode *next=NULL;
|
||
|
||
TxipHashmapNode ** newtable = create_T_table( length);
|
||
if ( newtable == NULL)
|
||
{
|
||
return -5;
|
||
}
|
||
|
||
for( i = 0; i < map->length; i++)
|
||
{
|
||
/*遍历*/
|
||
e = *(map->table + i);
|
||
if( e != NULL)
|
||
{
|
||
do
|
||
{
|
||
next = e->next;
|
||
|
||
idx = e->hash % length;
|
||
|
||
e->next = newtable[idx]; /*如果newtable[idx]的值已经存在了,该行则会将该值变为newtable[idx]->idx*/
|
||
|
||
newtable[idx] = e;
|
||
|
||
e = next;
|
||
}while( e != NULL);
|
||
}
|
||
}
|
||
|
||
/*释放oldtable*/
|
||
HMAPFREE(map->table);
|
||
map->table = newtable;
|
||
map->length = length;
|
||
map->threshold = (unsigned int)(map->factor * length);
|
||
|
||
return 0;
|
||
|
||
}
|
||
|
||
/********************************************************
|
||
* 函数名称: XipHash
|
||
* 函数功能: 通过key来计算hash值的算法，算法越好，散列的一致分布性越好
|
||
* 函数作者: icesky
|
||
* 创建日期: 2016.07.28
|
||
* 调用说明: 内部调用函数.
|
||
* hash算法,此处使用的是 simple BKDR hash algorithm
|
||
* 为JAVA的JDK中使用的算法
|
||
* 也可以使用PHP等使用的time33算法(DJP hash algorithm）
|
||
* 还可以使用暴雪公司的的One-Way-Hash(号称最快的hash算法)
|
||
*
|
||
* 之所以没有使用我推荐的算法,是因为我把机会留给了你.如果
|
||
* 你看到了这个地方,并且试图优化算法的话,可以使用我建议的
|
||
* 算法进行尝试.
|
||
* 不过我想等到系统瓶颈追溯到本代码的时候,或许早就有了更
|
||
* 完美的算法来保证趋近一致散列了.o(∩_∩)o
|
||
* icesky.2016.07.08
|
||
*********************************************************/
|
||
static unsigned int XipHash(char * key)
|
||
{
|
||
register unsigned int h = 0;
|
||
unsigned int seed = 131; //31 131 1313 13131
|
||
|
||
while ( *key != '\0' )
|
||
{
|
||
h = h * seed + ( *key++ );
|
||
}
|
||
|
||
return (h & 0x7FFFFFFF);
|
||
}
|