鍵樹算法在計費系統(tǒng)中非常普遍，用來在共享內存中查找用戶資料的時候，非常快，查找代價始終是常數(shù)級別。

　　下面是源碼廣泛應用在國內的計費系統(tǒng)之中，其中alloctor，dealloctor函數(shù)是用來在共享內存中分配和釋放內存的．為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

/* - - - 鍵樹節(jié)點結構 - - - */
typedef struct trie_s
{
int subchanged[TRIE_FANOUT]; /* 記錄子節(jié)點發(fā)生變化的情況 */
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樹遍歷操作函數(shù)
*
* 注意 節(jié)點操作可中斷
*
* 返回 0 未執(zhí)行完畢 1 執(zhí)行完畢
*/
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: 初始化鍵值數(shù)組
* comment:將char映射成0-9的數(shù)值
*-------------------------------*/
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: 向鍵樹中插入一個新的數(shù)據(jù)
* arguments: *trie -- 鍵樹頭指針
* str -- 鍵值字符串
* level -- 鍵值長度
* data -- 要插入的數(shù)據(jù)
* n -- 要插入的數(shù)據(jù)的大小
* changed - 記錄當前節(jié)點的子節(jié)點的內容是否發(fā)生了變化
* 1 -- 有變化 0 -- 無變化
* return: -1 -- 出錯 0 -- 正常
* comment：鍵樹的葉節(jié)點是鏈表，出入數(shù)據(jù)時，先根據(jù)鍵值找到葉節(jié)點，再向
* 葉節(jié)點所指的鏈表中插入數(shù)據(jù)。
*---------------------------------*/
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: 在鍵樹中查找數(shù)據(jù)
* arguments: trie -- 鍵樹頭指針
* str -- 鍵值字符串
* level -- 鍵值長度
* data -- 要查找的數(shù)據(jù)
* cmp -- 比較函數(shù)指針
* return: 找到 -- 返回指向該數(shù)據(jù)的指針 沒找到 -- NULL
* comment:查找規(guī)則由cmp函數(shù)指定
*---------------------------------*/
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: 在鍵樹中查找鍵值指向的鏈頭。并將經(jīng)過的節(jié)點的changed字段置1
* 表示該節(jié)點的子節(jié)點要發(fā)生變化。如節(jié)點不存在，則生成該節(jié)點
* 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的節(jié)點的子節(jié)點的鏈表做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]) /* 子節(jié)點發(fā)生過變化 */
{
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]) /* 子節(jié)點發(fā)生過變化 */
{
return 1;
}
}
if (trie->listchanged)
{
return 1;
}
}

return 0;
}

/*
* 功能： TRIE樹遍歷操作函數(shù)
*
* 注意 節(jié)點操作可中斷
*
* 返回 0 未執(zhí)行完畢 1 執(zhí)行完畢
*/
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]) /* 子節(jié)點發(fā)生過變化 */
{
/* 字節(jié)點操作中斷， 返回 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;
};