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

　　下面是源码广泛应用在国内的计费系统之中，其中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));
}

[1] [2] 下一页