键树算法在计费系统中非常普遍，用来在共享内存中查找用户资料的时候，非常快，查找代价始终是常数级别。
下面是源码广泛应用在国内的计费系统之中，其中alloctor，dealloctor函数是用来在共享内存中分配和释放内存的，可以参考我的另一篇文章
为C++标准库容器写自己的内存分配程序
另外重复键值的算法采用的是线性链表的算法，比较简单，所以就没有列出源码。
h_trie.h
#ifndef H_TRIE_H_
#define H_TRIE_H_
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "error.h"
#include "list.h"
#define TRIE_FANOUT 10
/* - - - 键树节点结构 - - - */
typedef struct trie_s
{
int subchanged[TRIE_FANOUT]; /* 记录子节点发生变化的情况 */
int listchanged; /* 记录所属链表的变化情况 */
list_t *list;
struct trie_s *subtrie[TRIE_FANOUT];
}trie_t;
void InitHTrie (trie_t **trie);
int InsertHTrie (trie_t **trie, const char str[], const int level,
void *data, size_t n, int changed);
void * SearchHTrie (trie_t *trie, const char str[], const int level, void *data,
int (*cmp) (const void *data1, const void *data2));
int TouchHTrie (trie_t **trie, const char str[], const int level, list_t ***list);
list_t *GetListofHTrie (trie_t *trie, const char str[], const int level);
void PrintHTrie (trie_t *trie, const int level, const int key,
void (*print) (const void *data));
/*
void OperateTrie (trie_t *trie, void (* op_list) (void *data));
*/
void RefreshHTrie (trie_t *trie, void (* op_data) (void *data));
void FreeHTrie (trie_t *trie);
int NeedRefresh (trie_t *trie);
/*
* 最大可能匹配树查找
*/
list_t *MatchHTrie (trie_t *trie, const char str[], const int level);
/*
* 功能： TRIE树遍历操作函数
*
* 注意 节点操作可中断
*
* 返回 0 未执行完毕 1 执行完毕
*/
int DealHTrie (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"
static char keyarray[256];
/*-------------------------------
* usage: 初始化键值数组
* comment:将char映射成0-9的数值
*-------------------------------*/
void InitHTrie (trie_t **trie)
{
int c;
for (c = 0; c < 256; c++)
{
if (isdigit (c))
keyarray[c] = c - '0';
else
keyarray[c] = c%10;
}
*trie = NULL;
}
static trie_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() return NULL\n");
return node;
}
/*--------------------------------
* usage: 向键树中插入一个新的数据
* arguments: *trie -- 键树头指针
* str -- 键值字符串
* level -- 键值长度
* data -- 要插入的数据
* n -- 要插入的数据的大小
* changed - 记录当前节点的子节点的内容是否发生了变化
* 1 -- 有变化 0 -- 无变化
* return: -1 -- 出错 0 -- 正常
* comment：键树的叶节点是链表，出入数据时，先根据键值找到叶节点，再向
* 叶节点所指的链表中插入数据。
*---------------------------------*/
int InsertHTrie (trie_t **trie, const char str[], const int level,
void *data, size_t n, int changed)
{
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, const char str[], const int level, void *data,
int (*cmp) (const void *data1, const void *data2))
{
int i;
int key;
trie_t *curnode;
if (trie == NULL)
return NULL;
curnode = trie;
for (i = 0; i < level ; i++)
{
key = (int) keyarray[ (int)str[i] ];
if (curnode->subtrie[key] == NULL)
return NULL;
curnode = curnode->subtrie[key];
}
return (SearchList (curnode->list, data, cmp));
}
/*--------------------------------
* usage: 在键树中查找键值指向的链头。并将经过的节点的changed字段置1
* 表示该节点的子节点要发生变化。如节点不存在，则生成该节点
* arguments: trie -- 键树头指针
* str -- 键值字符串
* level -- 键值长度
* list -- 保存指向链头list指针的指针，由于要保存指针的指针，
* 使用3层指针
* return: 找到 -- 返回指向该链表头的指针 没找到 -- NULL
* comment:
*---------------------------------*/
int TouchHTrie (trie_t **trie, const char str[], const int level, 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 () return NULL\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);
return 0;
}
/*-------------------------------------------
*
*-------------------------------------------*/
list_t *GetListofHTrie (trie_t *trie, const char str[], const int level)
{
int i;
int key;
trie_t *curnode;
if (trie == NULL)
return NULL;
curnode = trie;
for (i = 0; i < level ; i++)
{
key = (int) keyarray[(int)str[i]];
if (curnode->subtrie[key] == NULL)
return NULL;
curnode = curnode->subtrie[key];
}
return curnode->list;
}
list_t *MatchHTrie (trie_t *trie, const char str[], const int level)
{
int i;
int key;
trie_t *curnode;
if (trie == NULL)
return NULL;
curnode = trie;
for (i = 0; i < level ; i++)
{
key = (int) keyarray[(int)str[i]];
if (curnode->subtrie[key] == NULL)
return curnode->list;
curnode = curnode->subtrie[key];
}
return curnode->list;
}
/*-------------------------------
* usage: 释放键树
* arguments: trie -- the head of trie
*-------------------------------*/
void FreeHTrie (trie_t *trie)
{
int i;
if (trie)
{
for (i = 0; i < TRIE_FANOUT; i++)
FreeHTrie (trie->subtrie[i]);
FreeList (trie->list);
free (trie);
}
}
/*----------------------------------
* usage: print the data of the trie
*----------------------------------*/
void PrintHTrie (trie_t *trie, const int level, const int key, void (*print) (const void *data))
{
int i;
if (trie)
{
fprintf (stderr, "enter subtrie -- 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);
}
}
/*
void OperateHTrie (trie_t *trie, void (* op_list) (void *data))
{
}
*/
/*------------------------------------------
* usage: 刷新TRIE，对changed为1的节点的子节点的链表做op_list指定的操作
* parameters: trie -- trie head pointer
* op_list-- 对list的操作
*------------------------------------------*/
void RefreshHTrie (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;
}
}
}
int NeedRefresh (trie_t *trie)
{
int i;
if (trie)
{
for (i = 0; i < TRIE_FANOUT; i++)
{
if (trie->subchanged[i]) /* 子节点发生过变化 */
{
return 1;
}
}
if (trie->listchanged)
{
return 1;
}
}
return 0;
}
/*
* 功能： TRIE树遍历操作函数
*
* 注意 节点操作可中断
*
* 返回 0 未执行完毕 1 执行完毕
*/
int DealHTrie (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)
return 0;
trie->subchanged[i] = 0;
}
}
if (trie->listchanged)
{
if (DealList (trie->list, op_data) == 0)
return 0;
trie->listchanged = 0;
}
}
return 1;
}
测试主程序在vs2005中编译通过
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include "alloc.h"
#include "list.h"
#include "h_trie.h"
static trie_t *pTrie;
struct testdata
{
int key;
char data[20];
};
int _tmain(int argc, _TCHAR* argv[])
{
struct testdata *pData;
int i;
char key[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 = (struct testdata*)malloc(sizeof(struct testdata));
if (pData == NULL)
{
pr_error("allocate fail\n");
}
pData->key = i;
sprintf(pData->data ,"%d", i*9999);
sprintf(key, "%d", pData->key);
if ( - 1 == InsertHTrie(&pTrie, key, sizeof(int), pData,
sizeof(struct testdata), 0) )
{
pr_error("errorcode:%d,msg:insert tree error\n");
}
PrintFreelistAndCookie();
}
free(getShm());
return 0;
};
