/*ohtbl.c*/
#include <stdlib.h>
#include <string.h>
#include "ohtbl.h"
/*为空出的元素预留一个特殊的内存地址*/
static char vacated;
/*ohtbl_init 初始化htbl指定的开地址哈希表*/
int ohtbl_init(OHTbl *htbl,int positions, int (*h1)(const void *key), int (*h2)(const void *key),
int (*match)(const void *key1, const void *key2),void (*destroy)(void *data))
{
int i;
/*为空分配空间*/
if((htbl->table = (void **)malloc(positions * sizeof(void *))) == NULL)
return -1;
/*初始化每个槽位，把每个槽位的指针设置为NULL*/
htbl->positions = positions;
for(i=0; i<htbl->positions; i++)
htbl->table[i] = NULL;
/*将空出的成员设置为为此保留的特殊内存地址*/
htbl->vacated = &vacated;
/*封装4个函数*/
htbl->h1 = h1;
htbl->h2 = h2;
htbl->match = match;
htbl->destroy=destroy;
/*初始化元素数量*/
htbl->size = 0;
return 0;
}
/*ohtbl_destroy 销毁htbl指定的开地址式哈希表*/
void ohtbl_destroy(OHTbl *htbl)
{
int i;
if(htbl->destroy != NULL)
{
for(i=0; i < htbl->positions; i++)
{
if(htbl->table[i] != NULL && htbl->table[i] != htbl->vacated)
htbl->destroy(htbl->table[i]);
}
}
/*释放表空间*/
free(htbl->table);
/*清除数据结构*/
memset(htbl,0,sizeof(OHTbl);
return;
}
/*ohtbl_insert 向表中插入元素*/
int ohtbl_insert(OHTbl *htbl,const void *data)
{
void *temp;
int position,i;
/*因为开地址哈希表有固定的大小，所以在插入之前必须保证有足够的空间放置元素*/
if(htbl->size == htbl->positions)
return -1;
/*相同的键不允许重复插入表中，插入之前调用htbl_lookup检查是否有相同的元素*/
temp = (void *)data;
if(ohtbl_lookup(htbl,temp) == 0)
return 1;
/*满足以上条件，使用双散列法在表中寻找未被占用的槽*/
for(i=0; i< htbl->positions; i++)
{
position = (htbl->h1(data) + (i*htbl->h2(data))) % htbl->positions;
if(htbl->table[position]==NULL || htbl->table[position]==htbl->vacated)
{
/*将元素插入表中*/
htbl->table[position] = (void *)data;
htbl->size++;
return 0;
}
}
/*选用了错误的哈希函数*/
return -1;
}
/*ohtbl_remove 删除htbl指定表中与data相匹配的元素*/
int ohtbl_remove(OHTbl *htbl,void **data)
{
int position,i;
/*通过双散列定位到要删除元素的位置*/
for(i=0; i<htbl->positions; i++)
{
position = (htbl->h1(*data) + (i * h2(*data))) % htbl->positions ;
if(htbl->table[position] == NULL)
{
/*没有找到匹配的数据*/
return -1;
}
else if (htbl->table[position] == htbl->vacated)
{
/*查找到了突出的位置，继续搜索*/
continue;
}
else if (htbl->match(htbl->table[position],*data))
{
/*将data指向正在删除的数据*/
*data = htbl->table[position];
/*将此槽位的地址放到vacated成员中*/
htbl->[position] = htbl->vacated;
htbl->size--;
return 0;
}
}
/*如果没有找到元素，则返回-1*/
return -1;
}
/*ohtbl_lookup 查找htbl指定的表中，与data相匹配的元素*/
int ohtbl_lookup(const OHTbl *htbl,void **data)
{
int position,i;
for(i=0; i<htbl->positions; i++)
{
position = (htbl->h1(*data) + (i * htbl->h2(*data)))% htbl->positions;
if(htbl->table[position] == NULL)
{
/*没有找到数据*/
retun -1;
}
else if(htbl->match(htbl->table[position],*data))
{
/*将data指向找到的数据*/
*data = htbl->table[position];
return 0;
}
}
return -1;
}