键树算法的实现

发布于:软件开发网 来源:互联网 作者:佚名 时间:2009-02-26 00:05

键树算法在计费系统中非常普遍，用来在共享内存中查找用户资料的时候，非常快，查找代价始终是常数级别。

下面是源码广泛应用在国内的计费系统之中，其中alloctor，dealloctor函数是用来在共享内存中分配和释放内存的，可以参考我的另一篇文章

为C 标准库容器写自己的内存分配程序

另外重复键值的算法采用的是线性链表的算法，比较简单，所以就没有列出源码。

h_trie.h

#ifndefH_TRIE_H_
#defineH_TRIE_H_

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

#include"error.h"
#include"list.h"

#defineTRIE_FANOUT 10

/*---键树节点结构---*/
typedefstructtrie_s
{
int subchanged[TRIE_FANOUT];/*记录子节点发生变化的情况*/
int listchanged; /*记录所属链表的变化情况*/
list_t *list;
structtrie_s *subtrie[TRIE_FANOUT];
}trie_t;

voidInitHTrie(trie_t**trie);

intInsertHTrie(trie_t**trie,constcharstr[],constintlevel,
void*data,size_tn,intchanged);

void*SearchHTrie(trie_t*trie,constcharstr[],constintlevel,void*data,
int(*cmp)(constvoid*data1,constvoid*data2));

intTouchHTrie(trie_t**trie,constcharstr[],constintlevel,list_t***list);

list_t*GetListofHTrie(trie_t*trie,constcharstr[],constintlevel);

voidPrintHTrie(trie_t*trie,constintlevel,constintkey,
void(*print)(constvoid*data));
/*
voidOperateTrie(trie_t*trie,void(*op_list)(void*data));
*/
voidRefreshHTrie(trie_t*trie,void(*op_data)(void*data));

voidFreeHTrie(trie_t*trie);

intNeedRefresh(trie_t*trie);

/*
* 最大可能匹配树查找
*/
list_t*MatchHTrie(trie_t*trie,constcharstr[],constintlevel);

/*
* 功能： TRIE树遍历操作函数
*
* 注意 节点操作可中断
*
* 返回 0 未执行完毕 1 执行完毕
*/
intDealHTrie(trie_t*trie,int(*op_data)(void*data));

#endif

h_trie.c

#include"stdafx.h"
#include<stdio.h>
#include<ctype.h>

#include"h_trie.h"
#include"alloc.h"
staticcharkeyarray[256];

/*-------------------------------
* usage: 初始化键值数组
* comment:将char映射成0-9的数值
*-------------------------------*/
voidInitHTrie(trie_t**trie)
{
int c;

for(c=0;c<256;c )
{
if(isdigit(c))
keyarray[c]=c-'0';
else
keyarray[c]=c;
}

*trie=NULL;
}

statictrie_t*NewNode()
{
int i;
trie_t *node=(trie_t*)allocate(sizeof(trie_t));

if(node)
{
node->list=NULL;
for(i=0;i<TRIE_FANOUT;i )
{
node->subchanged[i]=0;
node->listchanged=0;
node->subtrie[i]=NULL;
}
}

if(node==NULL)
pr_error("errorcode:%d,msg:NewNode:allocate()returnNULL\n");

returnnode;
}

/*--------------------------------
* usage: 向键树中插入一个新的数据
* arguments: *trie--键树头指针
* str --键值字符串
* level--键值长度
* data --要插入的数据

* n --要插入的数据的大小
* changed-记录当前节点的子节点的内容是否发生了变化
* 1--有变化 0--无变化
* return: -1--出错 0--正常
* comment：键树的叶节点是链表，出入数据时，先根据键值找到叶节点，再向
* 叶节点所指的链表中插入数据。
*---------------------------------*/
intInsertHTrie(trie_t**trie,constcharstr[],constintlevel,
void*data,size_tn,intchanged)
{
int i;
int key;
trie_t *curnode;

if(*trie==NULL)
{
*trie=NewNode();
if(*trie==NULL){
return-1;
}
}

curnode=*trie;
for(i=0;i<level;i )
{
key=(int)keyarray[(int)str[i]];
if(curnode->subtrie[key]==NULL)
{
if((curnode->subtrie[key]=NewNode())==NULL)
return-1;
}
curnode->subchanged[key]=changed;

curnode=curnode->subtrie[key];
}

curnode->listchanged=changed;

return(InsertList(&(curnode->list),data,n));
}

/*--------------------------------
* usage: 在键树中查找数据
* arguments: trie --键树头指针
* str --键值字符串
* level--键值长度
* data --要查找的数据
* cmp --比较函数指针
* return: 找到--返回指向该数据的指针 没找到--NULL
* comment:查找规则由cmp函数指定
*---------------------------------*/
void*SearchHTrie(trie_t*trie,constcharstr[],constintlevel,void*data,
int(*cmp)(constvoid*data1,constvoid*data2))
{
int i;
int key;
trie_t *curnode;

if(trie==NULL)
returnNULL;

curnode=trie;
for(i=0;i<level;i )
{
key=(int)keyarray[(int)str[i]];
if(curnode->subtrie[key]==NULL)
returnNULL;

curnode=curnode->subtrie[key];
}

return(SearchList(curnode->list,data,cmp));
}

/*--------------------------------
* usage: 在键树中查找键值指向的链头。并将经过的节点的changed字段置1
* 表示该节点的子节点要发生变化。如节点不存在，则生成该节点
* arguments: trie --键树头指针
* str --键值字符串
* level--键值长度
* list --保存指向链头list指针的指针，由于要保存指针的指针，
* 使用3层指针
* return: 找到--返回指向该链表头的指针 没找到--NULL
* comment:
*---------------------------------*/
intTouchHTrie(trie_t**trie,constcharstr[],constintlevel,list_t***list)
{
int i;
int key;
trie_t *curnode;

if(*trie==NULL)
{
*trie=NewNode();
if(*trie==NULL){
pr_error("errorcode:%d,msg:TouchHTrie:NewNode()returnNULL\n");

return-1;
}
}

curnode=*trie;
for(i=0;i<level;i )
{
key=(int)keyarray[(int)str[i]];
if(curnode->subtrie[key]==NULL)
{
if((curnode->subtrie[key]=NewNode())==NULL){
pr_error("errorcode:%d,msg:NewNode()error\n");
return-1;
}
}
curnode->subchanged[key]=1;

curnode=curnode->subtrie[key];
}

curnode->listchanged=1;

*list=&(curnode->list);

return0;
}

/*-------------------------------------------
*
*-------------------------------------------*/
list_t*GetListofHTrie(trie_t*trie,constcharstr[],constintlevel)
{
int i;
int key;
trie_t *curnode;

if(trie==NULL)
returnNULL;

curnode=trie;
for(i=0;i<level;i )
{
key=(int)keyarray[(int)str[i]];
if(curnode->subtrie[key]==NULL)
returnNULL;

curnode=curnode->subtrie[key];
}

returncurnode->list;
}

list_t*MatchHTrie(trie_t*trie,constcharstr[],constintlevel)
{
int i;
int key;
trie_t *curnode;

if(trie==NULL)
returnNULL;

curnode=trie;

for(i=0;i<level;i )
{
key=(int)keyarray[(int)str[i]];
if(curnode->subtrie[key]==NULL)
returncurnode->list;

curnode=curnode->subtrie[key];
}

returncurnode->list;
}

/*-------------------------------
* usage: 释放键树
* arguments: trie--theheadoftrie
*-------------------------------*/
voidFreeHTrie(trie_t*trie)
{
int i;

if(trie)
{
for(i=0;i<TRIE_FANOUT;i )
FreeHTrie(trie->subtrie[i]);
FreeList(trie->list);
free(trie);
}
}

/*----------------------------------
* usage: printthedataofthetrie
*----------------------------------*/
voidPrintHTrie(trie_t*trie,constintlevel,constintkey,void(*print)(constvoid*data))
{
int i;

if(trie)
{
fprintf(stderr,"entersubtrie--level:%d,key:%d\n",level,key);
for(i=0;i<TRIE_FANOUT;i )
{
PrintHTrie(trie->subtrie[i],level 1,i,print);
}
PrintList(trie->list,print);
}
}
/*
voidOperateHTrie(trie_t*trie,void(*op_list)(void*data))
{

}
*/

/*------------------------------------------
* usage: 刷新TRIE，对changed为1的节点的子节点的链表做op_list指定的操作
* parameters: trie --trieheadpointer
* op_list--对list的操作
*------------------------------------------*/
voidRefreshHTrie(trie_t*trie,void(*op_data)(void*data))
{
int i;

if(trie)
{
for(i=0;i<TRIE_FANOUT;i )
{
if(trie->subchanged[i])/*子节点发生过变化*/
{
RefreshHTrie(trie->subtrie[i],op_data);
trie->subchanged[i]=0;
}
}
if(trie->listchanged) 
{
OperateList(trie->list,op_data);
trie->listchanged=0;
}
}
}

intNeedRefresh(trie_t*trie)
{
int i;

if(trie)
{
for(i=0;i<TRIE_FANOUT;i )
{
if(trie->subchanged[i])/*子节点发生过变化*/
{
return1;
}
}
if(trie->listchanged)
{
return1;
}
}

return0;
}

/*
* 功能： TRIE树遍历操作函数
*
* 注意 节点操作可中断
*

* 返回 0 未执行完毕 1 执行完毕
*/ 
intDealHTrie(trie_t*trie,int(*op_data)(void*data))
{
int i;

if(trie)
{
for(i=0;i<TRIE_FANOUT;i )
{
if(trie->subchanged[i])/*子节点发生过变化*/
{
/*字节点操作中断，返回0*/
if(DealHTrie(trie->subtrie[i],op_data)==0)
return0;

trie->subchanged[i]=0;
}
}
if(trie->listchanged) 
{
if(DealList(trie->list,op_data)==0)
return0;
trie->listchanged=0;
}
}

return1;
}

测试主程序在vs2005中编译通过

#include"stdafx.h"
#include<stdio.h>
#include<stdlib.h>

#include"alloc.h"
#include"list.h"
#include"h_trie.h"

statictrie_t*pTrie;
structtestdata
{
intkey;
chardata[20];
};

int_tmain(intargc,_TCHAR*argv[])
{
structtestdata*pData;
inti;
charkey[10];

InitShm(sizeof(trie_t)*100 sizeof(list_t)*20);

PrintFreelistAndCookie();

InitHTrie(&pTrie);

for(i=0;i<10;i )
{
printf("main:i=%d\n",i);
pData=(structtestdata*)malloc(sizeof(structtestdata));
if(pData==NULL)
{
pr_error("allocatefail\n");
}

pData->key=i;
sprintf(pData->data,"%d",i*9999);
sprintf(key,"%d",pData->key);

if(-1==InsertHTrie(&pTrie,key,sizeof(int),pData,
sizeof(structtestdata),0))
{
pr_error("errorcode:%d,msg:inserttreeerror\n");
}

PrintFreelistAndCookie();
}

free(getShm());
return0;
};