120,140,138,28,84,186,198,131,54,2,56,78,173,151,83,27,
255,144,249,189,104,4,168,98,162,150,254,242,109,34,133,224,
228,79,103,201,160,90,18,61,10,233,91,80,124,96,244,36
};
int simulate_hashstr(char * s, int len)
{
int h = len % 256;
for (int i = 0; i < len; ++i)
{
h = (h + s[i]) % 256;
h = simulate_T[h];
}
return h;
}
显然,这个散 列函数生成的值在0~255之间。
处理字符串的散列函数还有很多,详见参 考资料3。 使用散列函数寻址
在MudOS源码(v22.2b14)中,定义了5个宏或函数分别处理应用中的各个散列表的寻址操作,这些宏包装了whashstr函数以方便使用:
1.
/* lex.h */
#define DEFHASH 64
#define defhash(s) (whashstr((s), 10) & (DEFHASH - 1))
2.
/* lex.c */
#define IDENT_HASH_SIZE 1024
#define IdentHash(s) (whashstr((s), 20) & (IDENT_HASH_SIZE - 1))
3.
/* object.c */
/* CFG_LIVING_HASH_SIZE定义于 options.h
#define CFG_LIVING_HASH_SIZE 256 */
INLINE_STATIC int hash_living_name P1(char *, str)
{
return whashstr(str, 20) & (CFG_LIVING_HASH_SIZE - 1);
}
4.
/* otable.c */
#define ObjHash(s) whashstr(s, 40) & otable_size_minus_one
5.
/* stralloc.c */
#define StrHash(s) (whashstr((s), 20) & (htable_size_minus_one))
对于1、2、3,参数和 函数功能已经很明显:萃取(extract)低位字节作为被评估(evaluated) 的字符串所在散列表的位置,对应的散列表的大小为DEFHASH,IDENT_HASH_SIZE,CFG_LIVING_HASH_SIZE,由于使用的“&” 操作(按位与)来萃取低位字节,因此,需要将这些散列表的大小置为2的指数。
对于第4个宏,参数otable_size_minus_one在 otable.c中 被赋值。
/* otable.c */
/*
* hash table - list of pointers to heads of object chains.
* Each object in chain has a pointer, next_hash, to the next object.
*/
static object_t **obj_table = 0;
void init_otable()
{
int x, y;
/* ensure that otable_size is a power of 2 */
y = OTABLE_SIZE;
for (otable_size = 1; otable_size < y; otable_size *= 2)
;
otable_size_minus_one = otable_size - 1;
obj_table = CALLOCATE(otable_size, object_t *,
TAG_OBJ_TBL, "init_otable");
for (x = 0; x < otable_size; x++)
obj_table[x] = 0;
}
宏OTABLE_SIZE的功能为存储配置文件中object table size的值,在MudOS启动时,在main函数里调用读取配置文件的函数,对OTABLE_SIZE进 行赋值,在init_otalbe函数中将这个值调整为2的 指数,并将这个值赋给otable_size_minus_one。
对于第5个宏,htable_size_minus_one的 赋值过程与otable_size_minus_one大同小异。但是在查看某个mudlib的配置文件时发现下面的问题:
/* 取自config.xxx */
# Define the size of the shared string hash table. This number should
# a prime, probably between 1000 and 30000; if you set it to about 1/5
# of the number of distinct strings you have, you will get a hit ratio
# (number of comparisons to find a string) very close to 1, as found strings
# are automatically moved to the head of a hash chain. You will n
下一页 上一页
返回列表
返回首页
©2024 MUD游戏网_文字mud 电脑版
Powered by iwms